课程设计报告哈夫曼编码.doc

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