1、对输入的一段英文中的每个字符统计其权值，建立哈夫曼树；（2）E：编码（Encoding）。利用已建好的哈夫曼树，对每个字符进行编码。（3）D：译码（Decoding）。利用已建好的每个编码，对输入的一个由0、1组成的序列进行译码；（4）P：印代码文件（Print）。将每个字符编的哈夫曼码和译码结果显示在终端上。 测试用例见题集p149。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例
2、设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第18周（6月28日至7月2日）完成。2、7月2 日08：30到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目录1 设计题目12 问题描述13.1数据结构设计13.2主要算法设计33.3测试用例设计64调试报
3、告75结束语7六、课程设计参考资料8附录9F1 源代码9F2 运行结果16 1 设计题目 哈夫曼编码2 问题描述输入一段英文字符，试为该文中的每个字符编制相应的哈夫曼码。3设计3.1数据结构设计抽象数据类型二叉树的定义如下：ADT BinaryTree数据对象D：D是具有相同特性的数据元素的集合。数据关系R：基本操作P：InitBiTree（&T）；操作结果：构造空二叉树T。DestroyBiTree（&二叉树T存在。销毁二叉树T。CreateBiTree（&T，definition）；definition给出二叉树T的定义。按definition构造二叉树T。ClearBiTree（&将二叉
4、树T清为空树。BiTreeEmpty（T）；若T为空二叉树。则返回TRUE，否则FALSE。BiTreeDepth（T）；返回T的深度。Root（T）；返回T的根。Value（T，e）；二叉树T的存在，e是T中某个结点。返回e的值。Assign（T，&e，value）；二叉树T存在，e是T中某个结点。结点e赋值为value。Parent（T，e）；二叉树T存在，e是T 中某个结点。若e是T的非根结点，则返回它的双亲，否则返回“空”。DeleteChild（T，p，LR）；二叉树T存在，p指向T中某个结点，LR为0或1。根据LR为0或1，删除T中p所指结点的左或右子树。InsertChild（T
5、，p，LR，c）；二叉树的T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。根据LR为0或1，插入c为T中p所指结点的左或右子树。P所指结点的原有左或右子树则成为c的右子树。3.2主要算法设计程序中一共定义了一个结构体和三个函数如下：struct Huffman/定义指向结点的结构体int weight;/权值int parent,lchild,rchild;/父亲结点和左右结点的位置;void select（Huffman * ht,int i,int & s1,int & s2）/选择权值较小的两个作为新的叶子结点，用于huffman的构造。int j,k;k=
6、s1;for（j=0;ji+1;j+）if（s1!=j&j!=s2&htj.parent=0）s1=j;break; for（j=0;if（s2!s1!=k&s2=j;for（j=1;=i;if（htj.weighthts1.weight&htj.parent=0）s1=j;if（s1=s2） for（j=0; if（s2!hts2.weight&htj.parent=0&=s1） s2=j;void Huffmancoding（Huffman * ht,char * *&hc,int k）/对haffman进行编码int m,s1=0,s2=0,start,c,i,f,j;char * cd
7、;m=2*k-1;for（i=k;im;i+）/构建huffman树select（ht,i-1,s1,s2）;/调用select函数hts1.parent=i;hts2.parent=i;hti.lchild=s1; hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;for（i=0;=k-1;i+）/对每个叶子结点进行编码 cd=new chark; hci= ;for（j=0;k;cdj= start=k-1;for（c=i,f=hti.parent;f!=0;c=f,f=htf.parent）if（htf.lchild=c） cdstart-
8、=0else cdstart-=1hci=&cdstart+1;void frequency（int * & w,char str100,int * & c,int n,int & k）/涵数用于统计输入的字符的权w（出现的次数）。 int i,j,m;n;i+） if（i=0）c0=0;continue;i; if（strj=stri）ci=cj;if（j= =i）ci=+k;=k;for（m=0;mm+）if（cm= =j）wj+;3.3测试用例设计已知某系统在通信联络中只可能出现八种字符，其概率分别为0.05；0.29；0.07；0.08；0.14；0.23；0.03；0.11,试设计哈
9、夫曼编码。设权w=（5，29；7；8；14；23；3；11），n=8，则m=15，构造哈夫曼树。如下图：2311145378291哈夫曼编码：246011010111011111100001110104调试报告程序调试：（1.）当01序列解码成字符串时，要注意是否与已得出的字符串的编码匹配，如果不匹配，就把它后面的01序列截掉，不进行解码。（2.） &表示函数的参数是按地址传递的，当函数有多个返回值而无法用return实现时，通常使用这种。比如: void frequency（int * &5结束语经验和体会：通过一个星期的努力，总算把课程设计给完成了，这是一个坚苦而又漫长的过程。是啊，读了那
10、么多年的书，课程设计可是第一次。看着劳动成果，很欣慰！通过这次课程设计之后我觉得自己对书上知识的掌握有很大的欠缺，看了题目都不知道怎么下手，一点头绪都没有，之后自己认真看了一遍书上的知识，查阅了一些网上资料，我能熟练掌握了二叉树，然后在此基础上掌握理解haffman树和编码，熟知了二叉树的性质。可是这点小进展远远不够，这只是一个小小的开始，只能程序的大概轮廓可以写出来了。但是有很多的细节和特殊情况没法写上去，例如：用于huffman的构造；用于对haffman进行编码；用于统计输入的字符的权w（出现的次数）；实现这些的程序不知道该怎么写。后来经过同学的帮助和指导慢慢地程序里用到的函数通过哪些语
11、句来实现它，那些关键的函数怎样把它们有机结合起来等等，总之，在同学的多次指导下一个完整的程序写出来了，我也努力地去读懂它，发现自己隐约读懂了它！真正的收获更多是思想上的，让我认识程序的复杂，自己的微不足道，“学无止境”头一次认识的这么深刻，察觉自己的不足。在这次编程中，同学帮了我很多，我一个人是不能完成的。查书，查资料，请教同学的过程就是我提高的过程，总之，通过这次的课程设计，我发现程序设计最重要的就是上机实践，以前只是看书，觉得看懂了，但是真正到机子上写程序时感觉无从下手，没有什么头绪，可能就是因为实际上机操作的太少了，以后需要在这方面好好地加强了。以后的学习生活真的要踏踏实实，自己的计算机生涯必定是坎坷的，信心受挫了。六、课程设计参考资料1数据结构（STL框架），王晓东编著，清华大学出版社，出版或修订时间：2009年9月2数据结构（C语言版），严蔚敏，吴伟民编著，出版社：清华大学出版社，出版或修订时间：1997年4月3数据结构习题集（C语言版），严蔚敏，吴伟民，米宁编著，清华大学出版社，出版或修订时间：1999年2月起草人：杨克俭2010-6-22附录F1 源代码#include using namespace std;
