鱼C论坛

 找回密码
 立即注册
查看: 571|回复: 3

[技术交流] 哈夫曼树 c语言数组实现代码 (结果出现蜜汁等长编码??——踏入冒泡排序的陷阱)

[复制链接]
最佳答案
0 
发表于 2018-5-11 13:21:57 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 kyrieow 于 2018-5-11 13:18 编辑

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

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

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

不多说,上代码——

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

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define N 8

  4. struct hNode  //定义数组结点
  5. {
  6.         int suffix ;  //下标
  7.         int weight ;  //权值
  8.         int parent , lchild , rchild ;    //父子结点
  9. };

  10. struct cNode  // 定义编码结点
  11. {
  12.         int suffix ;
  13.         int weight ;
  14.         int length ;   //编码长度
  15.         char *code ;   //编码字符串
  16. };

  17. void Initial( hNode h[],int w[] )//数组初始化( 将数组w[]里的数放到到h[]里面 )
  18. {
  19.         int i;
  20.         for ( i = 1 ; i <= N ; i++ )     // 前半部分 , 叶子结点的标号从1 到 N
  21.         {                                                                 
  22.                 h[i].suffix = i ;
  23.                 h[i].weight = w[i-1];
  24.                 h[i].parent = 0 ;
  25.                 h[i].lchild = 0 ;
  26.                 h[i].rchild = 0 ;
  27.         }

  28.         for ( i = N + 1 ; i < 2*N ; i++ )   //  后半部分,非叶子结点的标号从N+1 到 2*N-1
  29.         {                                                       
  30.                 h[i].suffix =  i ;
  31.                 h[i].weight =  0 ;
  32.                 h[i].parent = 0 ;
  33.                 h[i].lchild = 0 ;
  34.                 h[i].rchild = 0 ;
  35.         }
  36. }

  37. //将数组h[]的结点按权值大小或下标顺序排序
  38. void Sort ( hNode h[] ,int m , int n ,int action )  
  39. {
  40.         int i , j , pos ,min , flag ;
  41.         hNode temp ;
  42.         if( action == 0 )           //action == 0 ,用选择排序依权值从小到大排序
  43.         {
  44.                 for( i = m ; i <= n-1 ; i++ )
  45.                 {
  46.                         min = h[i].weight ;pos = i ; flag = 0 ;
  47.                         for ( j=i+1 ; j <= n ; j++ )
  48.                         {
  49.                                 if( h[j].weight < min )
  50.                                 {
  51.                                         min = h[j].weight ;pos = j ; flag = 1 ;
  52.                                 }
  53.                         }
  54.                         if ( flag == 1 )
  55.                         {
  56.                                 temp = h[i];h[i]=h[pos];h[pos]=temp ;
  57.                         }
  58.                 }
  59.         }

  60.         else if ( action == 1 )     //action == 1  ,用选择排序依下标顺序排序
  61.         {
  62.                 for ( i = m ; i <= n-1 ; i++ )
  63.                 {
  64.                         min = h[i].suffix ;pos = i; flag = 0 ;
  65.                         for ( j=i+1 ; j <= n ; j++ )
  66.                         {
  67.                                 if( h[j].suffix < min )
  68.                                 {
  69.                                         min = h[j].suffix ;pos = j ; flag = 1 ;
  70.                                 }
  71.                         }
  72.                                 if ( flag == 1 )
  73.                                 {
  74.                                         temp = h[i];h[i]=h[pos];h[pos]=temp ;
  75.                                 }
  76.                 }
  77.         }

  78. /*注意,下面的冒泡排序是跟上面选择排序做对照的,正常情况下用一种排序就可以了*/

  79.         else if ( action == 2 )   //action == 2  , 用冒泡法依权值大小从小到大排序
  80.         {  
  81.                 for ( i = m ; i <= n-1 ; i++ )
  82.                         for( j = m ; j <= n-i ; j++ )
  83.                         {
  84.                                 if ( h[j].weight > h[j+1].weight )
  85.                                 {
  86.                                         temp = h[j] ;
  87.                                         h[j] = h[j+1] ;
  88.                                         h[j+1] = temp ;
  89.                                 }
  90.                         }
  91.                
  92.         }
  93.         else     //else  , 用冒泡法依下标进行顺序排序
  94.         {
  95.                 for ( i = m ; i<= n-1 ; i++ )
  96.                         for ( j = m ; j <= n-i ; j++ )
  97.                         {
  98.                                 if ( h[j].suffix > h[j+1].suffix )
  99.                                 {
  100.                                         temp = h[j] ;
  101.                                         h[j] = h[j+1] ;
  102.                                         h[j+1] = temp ;
  103.                                 }
  104.                         }
  105.         }
  106. }

  107. void Merge( hNode h[] )  //将数组结点h[]合并成哈弗曼树
  108. {
  109.         int i,j,k ;
  110.         for ( i = 1 ; i < N ;i++ )
  111.         {
  112.                 j = 2*i-1 ;               //j (j+1)分别是1(2)、3(4)、5(6)...
  113.                 Sort( h ,j ,N+i-1 ,0) ;  //新结点生成之前都依权值拍好序,确保开头两个最小
  114.                 /*  但是在这里把 "0 选择排序" 改为 "2 冒泡法" ,最后生成的编码是等长的 QAQ  */
  115.                 h[N+i].weight = h[j].weight + h[j+1].weight ;  // N+i 是 9、10、11...
  116.                 h[N+i].lchild = h[j].suffix ;
  117.                 h[N+i].rchild = h[j+1].suffix;
  118.                 h[j].parent = h[j+1].parent = h[N+i].suffix ;
  119.         }
  120. }

  121. void Code( hNode h[] , cNode c[] )  //数组结点  ===>  编码结点
  122. {
  123.         int i ,j,k,len;
  124.         char t[N];    //用一个字符数组存储编码
  125.         for ( i = 1 ; i <= N ; i++ )
  126.         {
  127.                 len = 0 ;
  128.                 for( j = i ,k = h[i].parent ; k != 0 ; j = k ,k = h[k].parent )
  129.                 {
  130.                         if( h[k].lchild == j )
  131.                                 t[len++] = '0';
  132.                         else
  133.                                 t[len++] = '1' ;
  134.                
  135.                 }

  136.                 c[i].suffix = i ;
  137.                 c[i].length = len ;
  138.                 c[i].weight = h[i].weight ;
  139.                 c[i].code = ( char * )malloc ( sizeof(len+1) ); //给编码结点的编码字符串分配内存
  140.                 c[i].code[len] = '\0';                         //前面len位放字符,第len+1位放结束符
  141.                 len -- ;
  142.                 j = 0 ;
  143.                 while ( len >= 0 )
  144.                 {
  145.                         c[i].code [j++] = t[len--] ;
  146.                 }
  147.         }
  148. }

  149. void Output( hNode h[] )  //输出数组
  150. {
  151.         int i ;
  152.         printf("哈弗曼数组输出为:\n");
  153.         for( i = 1 ; i < 2*N ; i++ )
  154.         {
  155.                 printf("%3d%7d%7d%7d%7d \n",h[i].suffix ,h[i].weight ,h[i].parent ,h[i].lchild ,h[i].rchild );
  156.         }

  157.         printf("\n");

  158. }

  159. void Output( cNode c[] )  //输出编码
  160. {
  161.         int i ;
  162.         printf("输出哈弗曼编码为:\n");
  163.         for( i = 1 ; i <= N ; i++ )
  164.         {
  165.                 printf("%3d%7d%7d%7s\n",c[i].suffix ,c[i].weight ,c[i].length ,c[i].code );
  166.         }
  167.        
  168.         printf("\n");
  169. }

  170. void main()  
  171. {
  172.         int w[N] = { 3,4,5,8,11,20,21,28 }; //这是要建树的数组 w
  173.         hNode h[2*N-1];                                                //声明哈夫曼数组 h[]
  174.         cNode c[N];                                                        //声明哈夫曼编码数组 c[]
  175.         Initial( h , w );                                        //初始化 h[]
  176.         Merge( h );                                                        //合并成哈夫曼树
  177.         Output(h);                                                        //输出观赏一下

  178.         Sort(h,0,2*N-2,1);                                        //h[] 依下标进行排序
  179.         Code(h,c);                                                        //编码
  180.         Output(c);                                                        //成品输出
  181. }
复制代码

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


代码就这样 ,有兴趣的小伙伴复制去玩耍吧......(估计没有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++ )

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


正常输出界面

正常输出界面

用了冒泡的有毒界面

用了冒泡的有毒界面
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-5-11 13:52:54 | 显示全部楼层
c语言,不会
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-5-11 13:53:28 | 显示全部楼层
可以学习下,看着也不难,英文只要好
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-5-11 16:15:41 | 显示全部楼层
挺好 早日实现红黑树 发个代码学习下 刚好项目用
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2018-12-11 16:15

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表