数据结构——实验四哈夫曼树与哈夫曼编码.doc

《数据结构——实验四哈夫曼树与哈夫曼编码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件学院哈夫曼树与哈夫曼编码实验报告课程名称：数据结构姓名：郑斌学号：7班级：卓越131实验四哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容本次实验提供3个题目，难度相当，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！题目一、哈夫曼树和哈夫曼编码[问题描述]　一电文，有若干个不同字符，要求从终端输入这些不同字符及其出现的频率，然后对这些字符进行哈夫曼编码，并输出。［测试数据］利用教材P.148例6－2中的数据调试程序(可自己设定测试数据)。[选作内容]1、打印出该哈夫曼树2、若从终端输入

2、任意一段电文（假设仅为26个大小写英文字母）,试编程高效地求出该段电文的哈夫曼编码。提示：如何快速统计不同字符的出现频率3、译码：将上述1的编码结果还原成电文。三、算法设计1)本程序包含三个模块1．voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)//选择函数2．voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)w存放n个权值,构造哈夫曼树p,3．VoidHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intn)求出哈夫曼编

3、码hc并输出哈弗曼编码四、实验结果图1-1输入哈弗曼树的权值图1-2显示哈弗曼树表与其编码五、总结通过做哈弗曼树实验让对最优二叉树这种结构有了更深的了解和应用，对我以后的编程产生了比较深远的影响。六、源程序（带注释）#include#include#include#include#includeusingnamespacestd;typedefstruct{intweight;intparent,lchild,rchild;charcharr;}HTNode,*Huff

4、manTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreeHT,inti,int&s1,int&s2){intj,k=1;while(HT[k].parent!=0)k++;s1=k;for(j=1;j<=i;++j)if(HT[j].parent==0&&HT[j].weight

5、

6、k==s1))k++;s2=k;for(j=1;j<=i;++j)if(HT[j].parent==0&&HT[j].weight

7、2].weight&&j!=s1)s2=j;}voidHuffmanCoding(HuffmanTree&HT,int*w,intn){intm,i,s1,s2;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i<=n;++i){HT[i].weight=w[i];HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;}for(i=n+1;i<=m;++i){HT[i].weight=0;HT[i].lchild=0;HT[i

8、].rchild=0;HT[i].parent=0;}//构建哈弗曼树for(i=n+1;i<=m;++i){Select(HT,i-1,s1,s2);//选择parent为0且weight最小的两个结点，期序号分别为s1，s2HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}cout<<"哈弗曼树表如下："<

9、d"<weight<parent<lchild<rchild<

10、r[n];