哈夫曼树 c语言数组实现代码 （结果出现蜜汁等长编码？？——踏入冒泡排序的陷阱）
本帖最后由 kyrieow 于 2018-5-11 13:18 编辑第一次发帖，先试试水，希望排版别太乱{:10_297:}
今天给大家分享一串哈夫曼编码的代码。。。顺便一提 Sort（）函数里冒泡排序的陷阱。。。
一开始是用的冒泡排序，编译出来是等长的编码。。而且找了一天没发现错误，最后换了选择排序，总算把问题揪出来了
不多说，上代码——
——————————————————————————————————————————————————————
#include <stdio.h>
#include <stdlib.h>
#define N 8
struct hNode//定义数组结点
{
int suffix ;//下标
int weight ;//权值
int parent , lchild , rchild ; //父子结点
};
struct cNode// 定义编码结点
{
int suffix ;
int weight ;
int length ; //编码长度
char *code ; //编码字符串
};
void Initial( hNode h[],int w[] )//数组初始化( 将数组w[]里的数放到到h[]里面 )
{
int i;
for ( i = 1 ; i <= N ; i++ ) // 前半部分 , 叶子结点的标号从1 到 N
{
h.suffix = i ;
h.weight = w;
h.parent = 0 ;
h.lchild = 0 ;
h.rchild = 0 ;
}
for ( i = N + 1 ; i < 2*N ; i++ ) //后半部分,非叶子结点的标号从N+1 到 2*N-1
{
h.suffix =i ;
h.weight =0 ;
h.parent = 0 ;
h.lchild = 0 ;
h.rchild = 0 ;
}
}
//将数组h[]的结点按权值大小或下标顺序排序
void Sort ( hNode h[] ,int m , int n ,int action )
{
int i , j , pos ,min , flag ;
hNode temp ;
if( action == 0 ) //action == 0 ,用选择排序依权值从小到大排序
{
for( i = m ; i <= n-1 ; i++ )
{
min = h.weight ;pos = i ; flag = 0 ;
for ( j=i+1 ; j <= n ; j++ )
{
if( h.weight < min )
{
min = h.weight ;pos = j ; flag = 1 ;
}
}
if ( flag == 1 )
{
temp = h;h=h;h=temp ;
}
}
}
else if ( action == 1 ) //action == 1,用选择排序依下标顺序排序
{
for ( i = m ; i <= n-1 ; i++ )
{
min = h.suffix ;pos = i; flag = 0 ;
for ( j=i+1 ; j <= n ; j++ )
{
if( h.suffix < min )
{
min = h.suffix ;pos = j ; flag = 1 ;
}
}
if ( flag == 1 )
{
temp = h;h=h;h=temp ;
}
}
}
/*注意，下面的冒泡排序是跟上面选择排序做对照的，正常情况下用一种排序就可以了*/
else if ( action == 2 ) //action == 2, 用冒泡法依权值大小从小到大排序
{
for ( i = m ; i <= n-1 ; i++ )
for( j = m ; j <= n-i ; j++ )
{
if ( h.weight > h.weight )
{
temp = h ;
h = h ;
h = temp ;
}
}
}
else //else, 用冒泡法依下标进行顺序排序
{
for ( i = m ; i<= n-1 ; i++ )
for ( j = m ; j <= n-i ; j++ )
{
if ( h.suffix > h.suffix )
{
temp = h ;
h = h ;
h = temp ;
}
}
}
}
void Merge( hNode h[] )//将数组结点h[]合并成哈弗曼树
{
int i,j,k ;
for ( i = 1 ; i < N ;i++ )
{
j = 2*i-1 ; //j (j+1)分别是1(2)、3(4)、5(6)...
Sort( h ,j ,N+i-1 ,0) ;//新结点生成之前都依权值拍好序，确保开头两个最小
/*但是在这里把 "0 选择排序" 改为 "2 冒泡法" ,最后生成的编码是等长的 QAQ*/
h.weight = h.weight + h.weight ;// N+i 是 9、10、11...
h.lchild = h.suffix ;
h.rchild = h.suffix;
h.parent = h.parent = h.suffix ;
}
}
void Code( hNode h[] , cNode c[] )//数组结点===>编码结点
{
int i ,j,k,len;
char t; //用一个字符数组存储编码
for ( i = 1 ; i <= N ; i++ )
{
len = 0 ;
for( j = i ,k = h.parent ; k != 0 ; j = k ,k = h.parent )
{
if( h.lchild == j )
t = '0';
else
t = '1' ;
}
c.suffix = i ;
c.length = len ;
c.weight = h.weight ;
c.code = ( char * )malloc ( sizeof(len+1) ); //给编码结点的编码字符串分配内存
c.code = '\0'; //前面len位放字符，第len+1位放结束符
len -- ;
j = 0 ;
while ( len >= 0 )
{
c.code = t ;
}
}
}
void Output( hNode h[] )//输出数组
{
int i ;
printf("哈弗曼数组输出为：\n");
for( i = 1 ; i < 2*N ; i++ )
{
printf("%3d%7d%7d%7d%7d \n",h.suffix ,h.weight ,h.parent ,h.lchild ,h.rchild );
}
printf("\n");
}
void Output( cNode c[] )//输出编码
{
int i ;
printf("输出哈弗曼编码为：\n");
for( i = 1 ; i <= N ; i++ )
{
printf("%3d%7d%7d%7s\n",c.suffix ,c.weight ,c.length ,c.code );
}
printf("\n");
}
void main()
{
int w = { 3,4,5,8,11,20,21,28 }; //这是要建树的数组 w
hNode h; //声明哈夫曼数组 h[]
cNode c; //声明哈夫曼编码数组 c[]
Initial( h , w ); //初始化 h[]
Merge( h ); //合并成哈夫曼树
Output(h); //输出观赏一下
Sort(h,0,2*N-2,1); //h[] 依下标进行排序
Code(h,c); //编码
Output(c); //成品输出
}
——————————————————————————————————————————————————————
代码就这样 ，有兴趣的小伙伴复制去玩耍吧......(估计没有2333{:10_277:} {:10_277:})
好了，下面是学习哈夫曼最难忘的经历——
经过1天的查错，我仍然还是相信我的代码没错，嗯，很自信那种，还骂了编译器几百遍{:10_277:} {:10_277:} 编译器：怪我咯！！
在冒泡法走不通后我用了选择排序....我去，竟然真的行！！！！
我就纳闷了，选择还是那个选择；冒泡还是那个冒泡。。。
对，还是那个。。那个。。那个。。。那个从0开始冒的。。。。{:10_247:}
...
...
...
但这里的冒泡#&……%#*&@是m开头的，f...!!!{:10_306:}
for ( i = m; i <= n-1 ; i++ )
for(j = m ; j <= n-i ; j++,k++ )
n 你再减个 i试试 ？?
好了，修改过来，以后都不敢再犯了@#￥#%0.0
for ( i = m; i <= n-1 ; i++ )
for(j = m，k=0 ; j <=n-k; j++,k++ )
最后是两张运行后的界面——
c语言，不会 可以学习下，看着也不难，英文只要好 挺好 早日实现红黑树 发个代码学习下 刚好项目用
页:
[1]