用赫夫曼树进行字符串的编码

《用赫夫曼树进行字符串的编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告实验三树的应用一、实验题目：树的应用——哈夫曼编码二、实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。要求：1．输出存放哈夫曼树的数组HT的初态和终态；2．输出每个字符的哈夫曼编码；3．输入由上述若干字符组成的字符串，对电文进行编码并输出；三、程序源代码：#include#include#

2、include#defineN8#defineM4typedefstruct{chardata;char*code;unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,char*data,int*w,intn,char*str){//存放n个字符的权值(均>

3、0)，构造赫夫曼树HT，并求出n各字符的赫夫曼编码HCif(n<=1)return;intm=2*n-1;//总节点数HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用HuffmanTreep;第7页共7页inti,j;printf("");printf("------------------------------");printf("存放哈夫曼树的数组HT的初态:");printf("叶子节点以及它的双亲节点，权值，左孩子，右孩子分别为:");for(p=HT+1,i=1;i<=n;++i,+

4、+p,++data,++w){p->data=*data;p->parent=p->lchild=p->rchild=0;p->weight=*w;p->code=(char*)malloc(n*sizeof(char));printf("%c%2d%2d%2d%2d",p->data,p->parent,p->weight,p->lchild,p->rchild);}for(;i<=m;++p,++i){p->parent=p->lchild=p->rchild=p->weight=0;p->data=NULL;p->code=(char*)malloc(n*s

5、izeof(char));printf("%2d%2d%2d%2d",p->parent,p->weight,p->lchild,p->rchild);}for(i=n+1;i<=m;++i){//建赫夫曼树//在HT[1--i-1]选择parent为0且weight最小的两个节点，其序号分别为s1和s2unsignedintm1=32767;unsignedintm2=32767;//m1,m2为最小和次小权值ints1=0;ints2=0;//s1,s2为最小和次小节点的序号for(intk=1;k<=i-1;k++){if((HT[k].parent==0)

6、&&(HT[k].weight

7、n");printf("存放哈夫曼树的数组HT的终态:");printf("叶子节点以及它的双亲节点，权值，左孩子，右孩子分别为:");for(p=HT+1,i=1;i<=n;++p,++i)printf("%c%2d%2d%2d%2d",p->data,p->parent,p->weight,p->lchild,p->rchild);for(;i<=m;++p,++i)printf("%2d%2d%2d%2d",p->parent,p->weight,p->lchild,p->rchild);//----从叶子到根逆向求每个字符的赫