注册 登录
编程论坛 数据结构与算法

哈夫曼树编码的问题,求大神赐教

踏月光 发布于 2017-11-25 09:14, 3564 次点击
(1)输入一串包含abcdefgh  8种字符的字符串,统计并输出每种字符出现的次数,并据此创建相应的哈夫曼树
(2)输出每种字符的哈夫曼编码
(3)输入一个字符串,其可能出现的字符有abcdefgh  8种,输出该字符串的编码结果
4 回复
#2
九转星河2017-11-25 13:45
不用感谢我,要感谢的话就感谢我们的数据结构老师~
这排版,我也醉了,最好自己整理消化一下~
程序代码:

#include<stdio.h>
#include<stdlib.h>
#include <string.h>#define  N  6                /* 叶子结点数 */#define  MAX_NODE  2*N-1    /* 总结点数=2n-1  */ #define  M  MAX_NODE+1        /* 数组大小=总结点数+1,下标0废弃 */typedef struct{         int Weight;    /*  权值域  */    int Parent , Lchild , Rchild ;} HTNode ;void main(){    int i;    char *MyHC[M];  //存放每个叶子结点Huffman编码的指针    HTNode MyHT[M];    void Create_Huffman(int n, HTNode HT[ ], int m);  //n叶子结点数,m总结点数(2*n-1)    void Huff_coding(   int n, HTNode HT[ ], int m,char *HC[]);    /*  m应为n+1,编码的最大长度n加1 */    Create_Huffman(N, MyHT, M);    printf("Huffman树结点数组HT[]:\n");    printf("HT[i]\t权\t父\t左\t右\t\n");    for (i=1; i<M; i++)  //输出Huffman结点数组MyHT[]        printf("%d\t%d\t%d\t%d\t%d\n",i,MyHT[i].Weight,MyHT[i].Parent,MyHT[i].Lchild,MyHT[i].Rchild);    Huff_coding(N, MyHT, M, MyHC);    printf("\n Huffman编码如下:\n");    printf("权值:\t");    for (i=1; i<N+1; i++)        printf("(%d)%d\t",i,MyHT[i]);    printf("\n");    printf("编码:\t");    for (i=1; i<N+1; i++)        printf("%s\t",MyHC[i]);    printf("\n");}        void Create_Huffman(int n, HTNode HT[ ], int m)  //n叶子结点数,m总结点数(2*n-1)   /*  创建一棵叶子结点数为n的Huffman树  */{      int  w , k , j ;    for (k=1 ; k<m ; k++) //初始化HT[ ]向量    {           if  (k<=n)  //创建n个叶子结点的权值        {              printf("请输入权值W%d即HT[%d]=:",k,k);            scanf("%d", &w) ;            HT[k].Weight=w ;          }        /*  输入时,所有叶子结点都有权值  */        else  HT[k].Weight=0;  /*  非叶子结点没有权值 */               HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0 ;    }        /* 初始化向量HT */        for (k=n+1; k<m ; k++)    {           int w1=32767 , w2=w1 ;        /*  w1 , w2分别保存权值最小的两个权值  */        int  p1=0 , p2=0 ;            /* p1 , p2保存两个最小权值的下标*/        for (j=1 ; j<=k-1 ; j++)        {               if (HT[j].Parent==0)    /* 尚未合并 */            {                   if (HT[j].Weight<w1)/*  找到权值最小的两个值及其下标  */                    {                         w2=w1 ; p2=p1 ; w1=HT[j].Weight ; p1=j ;                    }                else if (HT[j].Weight<w2)                     {  w2=HT[j].Weight ;  p2=j ;   }                                 }            }        HT[k].Lchild=p1 ; HT[k].Rchild=p2 ;        HT[k].Weight=w1+w2 ;        HT[p1].Parent=k ; HT[p2].Parent=k ;     }//end for}void Huff_coding(int n , HTNode HT[] , int m,char * HC[])    /*  m应为n+1,编码的最大长度n加1 */{      int  k , sp ,fp, p ;    char *cd;// , *HC[M] ;    cd=(char *)malloc(m*sizeof(char)) ;         /*  动态分配求编码的工作空间  */    cd[n]='\0';                                    /*  编码的结束标志 */    for (k=1 ; k<n+1 ; k++)                        /*  逐个求字符的编码    */    {             sp=n ; p=k ; fp=HT[k].Parent ;         for (  ; fp!=0 ;p=fp , fp=HT[p].Parent)        /*   从叶子结点到根逆向求编码,逐次压站,正向输出即为正向编码  */             if  (HT[fp].Lchild==p)  cd[--sp]='0';            else                    cd[--sp]='1';        HC[k]=(char *)malloc((n-sp)*sizeof(char)) ;    /*  为第k个字符分配保存编码的空间 */        strcpy(HC[k] , &cd[sp]) ;    }    free(cd) ;}
#3
踏月光2017-11-25 14:22
太感谢你啦!但是请问一下,你这个和我的题目是一样的吗,你运行成功了没有?我之前写的编码没有成功。。。
#4
九转星河2017-11-25 14:59
回复 3楼 踏月光
这是老师的代码,正常来说应该可以运行,我是用手机打开的复制粘贴排版有问题~

抱歉说我没啥功夫自己进行排版,至于测试运行就要看自己造化了~当然方便直接的还是上网搜吧,毕竟这么经典的题目参考资料还是挺多的~

还有嘛,功能方面可以自己改改看,直接给个现成品你也太直接了吧,自己试试排版弄弄看或者可以加深理解~

[此贴子已经被作者于2017-11-25 15:01编辑过]

#5
踏月光2017-11-25 15:17
嗯嗯,我晚上再在电脑上看看吧,谢谢你了!
1