利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码.docx

《利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码（C语言）(2011-10-2812:57:30)转载▼标签：赫夫曼树赫夫曼编码c语言it分类：学术科技利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编对输入的一串电文字符实现赫夫曼编码，在对赫夫曼编码生成的代码进行译码，输出电文字符串。利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树德分之表示“0”码，指向右子树分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编

2、码，这就是赫夫曼编码。设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率做权，构造一颗赫夫曼树，次构造过程称为赫夫曼编码。根据分析，必须实现以下几个功能：（1）、赫夫曼树的建立。（2）、赫夫曼编码的生成。（3）、编码文件的译码。------------------------------------------------------------------------------------------------#include#include#definen100

3、//叶子结点数#definem2*n-1//赫夫曼树种的结点总数typedefstruct{charch;charbits[9];//存放编码位串intlen;//编码长度}CodeNode;typedefCodeNodeHuffmanCode[n+1];typedefstruct{intweight;//权值*菡枫*intlchild,rchild,parent;//左右孩子及双亲指针}HTNode;//树中的结点类型typedefHTNodeHuffmanTree[m+1];//0号单元不可用intnum;//

4、字母类型的个数voidselect(HuffmanTreeT,intk,int*s1,int*s2){//在HT[1……k]中选择parent为0且权值最小的两个根结点，其序号分别为S1和S2inti,j;intmin1=100;for(i=1;i<=k;i++)//查找s1if(T[i].weight

5、='A'&&*p<='Z'){k=*p-64;temp[k]++;}}j=0;for(i=

6、1,j=0;i<=26;i++)//统计有多少种字符if(temp[i]!=0){j++;str[j]=i+64;//将对应的数组送到数组中cnt[j]=temp[i];//存入对应数组的权值}returnj;}voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){//构造赫夫曼树HTinti,s1,s2;for(i=1;i<=2*num-1;i++)//初始化HT，左右孩子，双亲，权值都为0{HT[i].lchild=0;HT[i].rc

7、hild=0;HT[i].parent=0;HT[i].weight=0;}for(i=1;i<=num;i++)//输入num个叶节点的权值HT[i].weight=cnt[i];for(i=num+1;i<=2*num-1;i++)//从numd后面开始新建结点存放新生成的父节点{select(HT,i-1,&s1,&s2);//在HT[1……i-1]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2HT[s1].parent=i;HT[s2].parent=i;//将s1和s2的parent

8、赋值HT[i].lchild=s1;HT[i].rchild=s2;//新结点的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight;//新结点的权值}for(i=0;i<=num;i++)//输入字符集中的字符HC[i].ch=str[i];i=1;while(i<=num)printf("字符%c,次数为:%d",