赫夫曼树实验报告

1、.数据结构实验报告赫夫曼树 电文翻译1. 设计目的本程序可将电文转换成由二进制的字符组成的字符串，便于信息的传输。用户可按照程序运行过程中的提示，输入所要转换的电文，即可得到结果。2. 设计原理程序中利用赫夫曼编码的原理设计赫夫曼树并存储在一维数组中，从而得到能使电文总长最短的二进制前缀编码。利用得到的各字符的赫夫曼编码既可对整段电文进行转换，也可对二进制电文进行译码从而还原电文。3. 程序结构主函数： voidmain()注：主函数包含对所输入电文的字符统计功能，并将每个字符出现的次数作为其在整段电文中的权值。.求赫夫曼编码的函数： voidHuffmanCoding()求无双亲结点中权值最

2、小的两个结点的函数：voidSelect(int)将电文转换的函数： voidtranslating(char)译码函数：voidyima()4. 算法概述由于在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既需知双亲的信息，又需知孩子结点的信息（本程序只可将当次程序运行过程中所输入的电文译码）。由此，设定下述存储结构：typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode ,*HuffmanTree ；/动态分配数组存储

3、赫夫曼typedef char *HuffmanCode; / 动态分配数组存储赫夫曼编码表求赫夫曼编码的算法如下所示：void HuffmanCoding(HuffmanTree&HT,HuffmanCode &HC,int *w,int n)/w 存放 n 个字符的权值（均 0）构造赫夫曼树HT ，并求出 n 个字符的赫夫曼编码 HC。if(n=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0 号单元未用for(p=&HT1,i=1,k=0;i=n&kn;+i,+p,+k)/*p=*w,0,0,0;for(;i=

4、m;+i,+p)/*p=0,0,0,0;for(i=n+1;i=m;+i)/建赫夫曼树/在 HT1 i-1 选择 parent 为 0 且 weight 最小的两个结点，其序号分别为 s1 和 s2。Select(HT,i-1,s1,s2);.HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;- 从叶子到根逆向求每个字符的赫夫曼编码-HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/ 分配 n 个字符编码的头指针向量。cd=(c

5、har*)malloc(n*sizeof(char);/分配求编码的工作区间cdn-1=0;/编码结束符for(i=1;i=n;+i)/ 逐个字符求赫夫曼编码start=n-1; /编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) / 从叶子到根逆向求编码if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char*)malloc(n)*sizeof(char);/为第 i 个字符编码分配空间strcpy(HCi,&cdstart);/从 cd 复制编码（串）到HCfree(cd);/释放工作空间

6、/HuffamCoding程序源码如下所示：#include#include#includestruct lettercharlet;int weight;charcode100=0;letter cishu100;int j=0;int s1,s2;struct selectint position;int weight;typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode ,*HuffmanTree;typedef char *HuffmanCode;HuffmanTree HT;Huffman

7、Code HC;.void Select(int a)int i=1,j,k=1;select sel100=0,0,temp;for(i=1;i=a;i+)if(HTi.parent!=0)continue;elseselk.position=i;selk.weight=HTi.weight;k+;for(i=1;i=k-2;i+)for(j=i+1;jselj.weight)temp=seli;seli=selj;selj=temp;s1=sel1.position;s2=sel2.position;void HuffmanCoding()int m,i,k,f,start,n;unsig

8、ned int c;char *cd;HuffmanTree p;n=j;if(n=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=&HT1,i=1,k=0;i=n&kweight=cishuk.weight;p-parent=0;p-lchild=0;p-rchild=0;for(;iweight=0;.p-parent=0;p-lchild=0;p-rchild=0;for(i=n+1;i=m;+i)Select(i-1);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1

9、;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char*)malloc(n)*sizeof(char);strcpy(HCi,&cdstart);fr

10、ee(cd);void translating(char test)int i,k;char *p=code;printf( 出现的字符权值编码 n);for(i=0,k=1;ij&kj)if(*p=0)a=HTa.lchild;p+;else if(*p=1) a=HTa.rchild;p+;printf(%c,cishua-1.let);void main()char test100;int i,k;int chuxian=0;printf( 电文翻译 n);printf( 请输入所要翻译的电文 :n);scanf(%s,test);for(i=0;i100&testi!=0;i+)if(

11、j=0)cishuj.let=testi;cishuj.weight=0;cishuj.weight+;j+;continue;for(k=0;kj;k+)if(cishuk.let=testi)chuxian=1;break;if(chuxian=1)cishuk.weight+;chuxian=0;continue;else if(chuxian=0)cishuj.let=testi;cishuj.weight=0;.cishuj.weight+;j+;HuffmanCoding();translating(test);yima();4. 调试分析以输入“ liaohandong”为例。经

12、理论分析所得的赫夫曼树如图所示：.运行程序进行验证：在运行程序后按提示输入“liaohandong”并按“enter”后黑屏上显示的内容为：电文翻译请输入所要翻译的电文：liaohandong出现的字符权值编码l1000i1001a2110o2101h1010n2111d1011g1100翻译结果：译码结果：LiaohandongPress any key to continue.程序运行所得结果与理论分析所得的赫夫曼编码一致，译码结果也正确，程序调试成功。5. 实验总结(1).通过编写此程序，我对赫夫曼编码的原理及算法有了更深入的认识。(2).在编程过程中， 出现了各种各样的问题， 包括基本的 c 语言语法问题，指针的应用问题等，花了好多时间去改正。在提高了找错并改错的能力的同时，也要在以后的编程实验中尽量减少低级错误的出现。(3).