哈夫曼树 c语言数组实现代码 （结果出现蜜汁等长编码？？——踏入冒泡排序的陷阱）

kyrieow

第一次发帖，先试试水，希望排版别太乱

今天给大家分享一串哈夫曼编码的代码。。。顺便一提 Sort（）函数里  冒泡排序的陷阱。。。

        一开始是用的冒泡排序，编译出来是等长的编码。。而且找了一天没发现错误，最后换了选择排序，总算把问题揪出来了

不多说，上代码——
——————————————————————————————————————————————————————

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #define N 8
   
5. 
   
6. struct hNode  //定义数组结点
   
7. {
   
8.         int suffix ;  //下标
   
9.         int weight ;  //权值
   
10.         int parent , lchild , rchild ;    //父子结点
    
11. };
    
12. 
    
13. struct cNode  // 定义编码结点
    
14. {
    
15.         int suffix ;
    
16.         int weight ;
    
17.         int length ;   //编码长度
    
18.         char *code ;   //编码字符串
    
19. };
    
20. 
    
21. void Initial( hNode h[],int w[] )//数组初始化( 将数组w[]里的数放到到h[]里面 )
    
22. {
    
23.         int i;
    
24.         for ( i = 1 ; i <= N ; i++ )     // 前半部分 , 叶子结点的标号从1 到 N
    
25.         {                                                                 
    
26.                 h[i].suffix = i ;
    
27.                 h[i].weight = w[i-1];
    
28.                 h[i].parent = 0 ;
    
29.                 h[i].lchild = 0 ;
    
30.                 h[i].rchild = 0 ;
    
31.         }
    
32. 
    
33.         for ( i = N + 1 ; i < 2*N ; i++ )   //  后半部分,非叶子结点的标号从N+1 到 2*N-1
    
34.         {                                                       
    
35.                 h[i].suffix =  i ;
    
36.                 h[i].weight =  0 ;
    
37.                 h[i].parent = 0 ;
    
38.                 h[i].lchild = 0 ;
    
39.                 h[i].rchild = 0 ;
    
40.         }
    
41. }
    
42. 
    
43. //将数组h[]的结点按权值大小或下标顺序排序
    
44. void Sort ( hNode h[] ,int m , int n ,int action )  
    
45. {
    
46.         int i , j , pos ,min , flag ;
    
47.         hNode temp ;
    
48.         if( action == 0 )           //action == 0 ,用选择排序依权值从小到大排序
    
49.         {
    
50.                 for( i = m ; i <= n-1 ; i++ )
    
51.                 {
    
52.                         min = h[i].weight ;pos = i ; flag = 0 ;
    
53.                         for ( j=i+1 ; j <= n ; j++ )
    
54.                         {
    
55.                                 if( h[j].weight < min )
    
56.                                 {
    
57.                                         min = h[j].weight ;pos = j ; flag = 1 ;
    
58.                                 }
    
59.                         }
    
60.                         if ( flag == 1 )
    
61.                         {
    
62.                                 temp = h[i];h[i]=h[pos];h[pos]=temp ;
    
63.                         }
    
64.                 }
    
65.         }
    
66. 
    
67.         else if ( action == 1 )     //action == 1  ,用选择排序依下标顺序排序
    
68.         {
    
69.                 for ( i = m ; i <= n-1 ; i++ )
    
70.                 {
    
71.                         min = h[i].suffix ;pos = i; flag = 0 ;
    
72.                         for ( j=i+1 ; j <= n ; j++ )
    
73.                         {
    
74.                                 if( h[j].suffix < min )
    
75.                                 {
    
76.                                         min = h[j].suffix ;pos = j ; flag = 1 ;
    
77.                                 }
    
78.                         }
    
79.                                 if ( flag == 1 )
    
80.                                 {
    
81.                                         temp = h[i];h[i]=h[pos];h[pos]=temp ;
    
82.                                 }
    
83.                 }
    
84.         }
    
85. 
    
86. /*注意，下面的冒泡排序是跟上面选择排序做对照的，正常情况下用一种排序就可以了*/
    
87. 
    
88.         else if ( action == 2 )   //action == 2  , 用冒泡法依权值大小从小到大排序
    
89.         {  
    
90.                 for ( i = m ; i <= n-1 ; i++ )
    
91.                         for( j = m ; j <= n-i ; j++ )
    
92.                         {
    
93.                                 if ( h[j].weight > h[j+1].weight )
    
94.                                 {
    
95.                                         temp = h[j] ;
    
96.                                         h[j] = h[j+1] ;
    
97.                                         h[j+1] = temp ;
    
98.                                 }
    
99.                         }
    
100.                
     
101.         }
     
102.         else     //else  , 用冒泡法依下标进行顺序排序
     
103.         {
     
104.                 for ( i = m ; i<= n-1 ; i++ )
     
105.                         for ( j = m ; j <= n-i ; j++ )
     
106.                         {
     
107.                                 if ( h[j].suffix > h[j+1].suffix )
     
108.                                 {
     
109.                                         temp = h[j] ;
     
110.                                         h[j] = h[j+1] ;
     
111.                                         h[j+1] = temp ;
     
112.                                 }
     
113.                         }
     
114.         }
     
115. }
     
116. 
     
117. void Merge( hNode h[] )  //将数组结点h[]合并成哈弗曼树
     
118. {
     
119.         int i,j,k ;
     
120.         for ( i = 1 ; i < N ;i++ )
     
121.         {
     
122.                 j = 2*i-1 ;               //j (j+1)分别是1(2)、3(4)、5(6)...
     
123.                 Sort( h ,j ,N+i-1 ,0) ;  //新结点生成之前都依权值拍好序，确保开头两个最小
     
124.                 /*  但是在这里把 "0 选择排序" 改为 "2 冒泡法" ,最后生成的编码是等长的 QAQ  */
     
125.                 h[N+i].weight = h[j].weight + h[j+1].weight ;  // N+i 是 9、10、11...
     
126.                 h[N+i].lchild = h[j].suffix ;
     
127.                 h[N+i].rchild = h[j+1].suffix;
     
128.                 h[j].parent = h[j+1].parent = h[N+i].suffix ;
     
129.         }
     
130. }
     
131. 
     
132. void Code( hNode h[] , cNode c[] )  //数组结点  ===>  编码结点
     
133. {
     
134.         int i ,j,k,len;
     
135.         char t[N];    //用一个字符数组存储编码
     
136.         for ( i = 1 ; i <= N ; i++ )
     
137.         {
     
138.                 len = 0 ;
     
139.                 for( j = i ,k = h[i].parent ; k != 0 ; j = k ,k = h[k].parent )
     
140.                 {
     
141.                         if( h[k].lchild == j )
     
142.                                 t[len++] = '0';
     
143.                         else
     
144.                                 t[len++] = '1' ;
     
145.                
     
146.                 }
     
147. 
     
148.                 c[i].suffix = i ;
     
149.                 c[i].length = len ;
     
150.                 c[i].weight = h[i].weight ;
     
151.                 c[i].code = ( char * )malloc ( sizeof(len+1) ); //给编码结点的编码字符串分配内存
     
152.                 c[i].code[len] = '\0';                         //前面len位放字符，第len+1位放结束符
     
153.                 len -- ;
     
154.                 j = 0 ;
     
155.                 while ( len >= 0 )
     
156.                 {
     
157.                         c[i].code [j++] = t[len--] ;
     
158.                 }
     
159.         }
     
160. }
     
161. 
     
162. void Output( hNode h[] )  //输出数组
     
163. {
     
164.         int i ;
     
165.         printf("哈弗曼数组输出为：\n");
     
166.         for( i = 1 ; i < 2*N ; i++ )
     
167.         {
     
168.                 printf("%3d%7d%7d%7d%7d \n",h[i].suffix ,h[i].weight ,h[i].parent ,h[i].lchild ,h[i].rchild );
     
169.         }
     
170. 
     
171.         printf("\n");
     
172. 
     
173. }
     
174. 
     
175. void Output( cNode c[] )  //输出编码
     
176. {
     
177.         int i ;
     
178.         printf("输出哈弗曼编码为：\n");
     
179.         for( i = 1 ; i <= N ; i++ )
     
180.         {
     
181.                 printf("%3d%7d%7d%7s\n",c[i].suffix ,c[i].weight ,c[i].length ,c[i].code );
     
182.         }
     
183.        
     
184.         printf("\n");
     
185. }
     
186. 
     
187. void main()  
     
188. {
     
189.         int w[N] = { 3,4,5,8,11,20,21,28 }; //这是要建树的数组 w
     
190.         hNode h[2*N-1];                                                //声明哈夫曼数组 h[]
     
191.         cNode c[N];                                                        //声明哈夫曼编码数组 c[]
     
192.         Initial( h , w );                                        //初始化 h[]
     
193.         Merge( h );                                                        //合并成哈夫曼树
     
194.         Output(h);                                                        //输出观赏一下
     
195. 
     
196.         Sort(h,0,2*N-2,1);                                        //h[] 依下标进行排序
     
197.         Code(h,c);                                                        //编码
     
198.         Output(c);                                                        //成品输出
     
199. }
     

复制代码

——————————————————————————————————————————————————————


代码就这样 ，有兴趣的小伙伴复制去玩耍吧......(估计没有2333   )

好了，下面是学习哈夫曼最难忘的经历——

        经过1天的查错，我仍然还是相信我的代码没错，嗯，很自信那种，还骂了编译器几百遍 编译器：怪我咯！！

在冒泡法走不通后我用了选择排序....我去，竟然真的行！！！！

        我就纳闷了，选择还是那个选择；冒泡还是那个冒泡。。。

对，还是那个。。那个。。那个。。。那个从0开始冒的。。。。
...

...

...

但这里的冒泡#&……%#*&@是m开头的，f...!!!
       
                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++ )

最后是两张运行后的界面——

di01

c语言，不会

di01

可以学习下，看着也不难，英文只要好

代号3

挺好 早日实现红黑树 发个代码学习下 刚好项目用