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

kyrieow

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

今天给大家分享一串哈夫曼编码的代码。。。顺便一提 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[i].suffix = i ;
                h[i].weight = w[i-1];
                h[i].parent = 0 ;
                h[i].lchild = 0 ;
                h[i].rchild = 0 ;
        }

        for ( i = N + 1 ; i < 2*N ; i++ )   //  后半部分,非叶子结点的标号从N+1 到 2*N-1
        {                                                        
                h[i].suffix =  i ;
                h[i].weight =  0 ;
                h[i].parent = 0 ;
                h[i].lchild = 0 ;
                h[i].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[i].weight ;pos = i ; flag = 0 ;
                        for ( j=i+1 ; j <= n ; j++ )
                        {
                                if( h[j].weight < min )
                                {
                                        min = h[j].weight ;pos = j ; flag = 1 ;
                                }
                        }
                        if ( flag == 1 )
                        {
                                temp = h[i];h[i]=h[pos];h[pos]=temp ;
                        }
                }
        }

        else if ( action == 1 )     //action == 1  ,用选择排序依下标顺序排序
        {
                for ( i = m ; i <= n-1 ; i++ )
                {
                        min = h[i].suffix ;pos = i; flag = 0 ;
                        for ( j=i+1 ; j <= n ; j++ )
                        {
                                if( h[j].suffix < min )
                                {
                                        min = h[j].suffix ;pos = j ; flag = 1 ;
                                }
                        }
                                if ( flag == 1 )
                                {
                                        temp = h[i];h[i]=h[pos];h[pos]=temp ;
                                }
                }
        }

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

        else if ( action == 2 )   //action == 2  , 用冒泡法依权值大小从小到大排序
        {  
                for ( i = m ; i <= n-1 ; i++ )
                        for( j = m ; j <= n-i ; j++ )
                        {
                                if ( h[j].weight > h[j+1].weight )
                                {
                                        temp = h[j] ;
                                        h[j] = h[j+1] ;
                                        h[j+1] = temp ;
                                }
                        }
                
        }
        else     //else  , 用冒泡法依下标进行顺序排序
        {
                for ( i = m ; i<= n-1 ; i++ )
                        for ( j = m ; j <= n-i ; j++ )
                        {
                                if ( h[j].suffix > h[j+1].suffix )
                                {
                                        temp = h[j] ;
                                        h[j] = h[j+1] ;
                                        h[j+1] = 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[N+i].weight = h[j].weight + h[j+1].weight ;  // N+i 是 9、10、11...
                h[N+i].lchild = h[j].suffix ;
                h[N+i].rchild = h[j+1].suffix;
                h[j].parent = h[j+1].parent = h[N+i].suffix ;
        }
}

void Code( hNode h[] , cNode c[] )  //数组结点  ===>  编码结点
{
        int i ,j,k,len;
        char t[N];    //用一个字符数组存储编码
        for ( i = 1 ; i <= N ; i++ )
        {
                len = 0 ;
                for( j = i ,k = h[i].parent ; k != 0 ; j = k ,k = h[k].parent )
                {
                        if( h[k].lchild == j )
                                t[len++] = '0';
                        else
                                t[len++] = '1' ;
                
                }

                c[i].suffix = i ;
                c[i].length = len ;
                c[i].weight = h[i].weight ;
                c[i].code = ( char * )malloc ( sizeof(len+1) ); //给编码结点的编码字符串分配内存
                c[i].code[len] = '\0';                         //前面len位放字符，第len+1位放结束符
                len -- ;
                j = 0 ;
                while ( len >= 0 )
                {
                        c[i].code [j++] = t[len--] ;
                }
        }
}

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

        printf("\n");

}

void Output( cNode c[] )  //输出编码
{
        int i ;
        printf("输出哈弗曼编码为：\n");
        for( i = 1 ; i <= N ; i++ )
        {
                printf("%3d%7d%7d%7s\n",c[i].suffix ,c[i].weight ,c[i].length ,c[i].code );
        }
        
        printf("\n");
}

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

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

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


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

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