《哈夫曼编码算法实现完整编辑.doc》由会员分享,可在线阅读,更多相关《哈夫曼编码算法实现完整编辑.doc(8页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、实验三实验三 树的应用树的应用一一. .实验题目实验题目:树的应用树的应用哈夫曼编码哈夫曼编码二二. .实验内容:实验内容:利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时 间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点 权值的基础上求哈夫曼编码。 要求:从键盘输入若干字符及每个字符出现的频率,将字符出现的频率作 为结点的权值,建立哈夫曼树,然后对各个字符进行哈夫曼编码,最后打印输 出字符及对应的哈夫曼编码。 三、程序源代码三、程序源代码: : #include #include #include #include typedef structchar d
2、ata;int weight;int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char * * HuffmanCode; void Select(HuffmanTree int tmp;for(int j=n+1;js2) /将选出的两个节点中的序号较小的始终赋给将选出的两个节点中的序号较小的始终赋给 s1s1 tmp=s1; s1=s2; s2=tmp; ps1.parent=j;ps2.parent=j; pj.lchild=s1; pj.rchild=s2; pj.weight=ps1.weight+ps2.weight; v
3、oid HuffmanCoding(HuffmanTree if(nch; return ch; void main() int n;int Array100;char cArray100;HuffmanTree HT;coutArrayi;int tag;char x=menu();while(1) switch (x) case I:HuffmanCoding(HT,n,cArray,Array);break;case E:Encoding(HT,n);break;case D:Decoding(HT,n);break;case P:Print();break;case Q:tag=0;c
4、outch;if (ch=y) coutc;x=c;else exit(1); 测试数据:测试数据:用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实 现以下报文的译码和编码:“THISTHIS PROGRAMPROGRAM ISIS MYMY FAVORITEFAVORITE“. 字符字符 空格 A B C D E F G H I J K L M 频度频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符字符 N O P Q R S T U V W X Y Z 频度频度 57 63 15 1 48 51 80 23 8 18 1 16 1 四四.
5、 .测试结果测试结果:如图一所示:如图一所示 五五. .实验体会实验体会通过本次实验,尤其在自己对程序的调试过程中,感觉对树的存储结构, 终结状态,还有编码,译码的过程都有了比较清晰的认识。在做本次实验时, 其他的都没什么问题,以前很少进行文件操作,刚开始有点手生,但是在实验 作完后,文件操作已经用的比较熟练了。最近几次实验,感到自己对本题实验 的运行机理和过程掌握的最为透彻。收获不小。在实验过程中,遇到的一个主 要问题是在 C+里面输入单个空格字符的问题。最终通过用 cin.getline()来 解决,但是还不是很理想。为了察看方便,把有些文件的内容直接显示在终端 上了,没有列出生成的文件里的结果。图一图一