赫夫曼树实验报告(含源程序)

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

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

3、ffmanTree ；/动态分配数组存储赫夫曼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); for(p=&HT1,i=1,k=0;i=n&kn;+i,+p,+k) for(;i=m;+i,+

4、p)for(i=n+1;i=m;+i)/0 号单元未用/*p=*w,0,0,0; /*p=0,0,0,0;/建赫夫曼树在HT1i-1选择pare nt为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 个字符编码的头指针 向

5、量。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) / 从叶子到根逆向求编码/为第 i 个字符编码分配空间 /从 cd 复制编码（串）到 HC/释放工作空间if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n)*sizeof(char); strcpy(HCi,&cdstart

6、);free(cd);/HuffamCoding程序源码如下所示：#include#include #include struct letterchar let;int weight;char code100=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; Huff

7、manTree HT; HuffmanCode 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;else selk.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()i

8、nt m,i,k,f,start,n;unsigned 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; H

9、Ts2.parent=i;HTi.lchild=s1; 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(

10、char); strcpy(HCi,&cdstart);free(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

11、); for(i=0;i100&testi!=0;i+)if(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+；Huffma nCodi ng(); tran slat in

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