教学规划报告哈夫曼编码

1、学 号:或用?三尢專程设计哈夫曼编码计算机科学与技术 计算机科学与技术指导教师2010年 07月 02 日课程设计任务专业班级:计算机0806学生姓名:拉巴珠久码;指导教师:初始条件:姚寒冰哈夫曼编码工作单位:计算机科学系输入一段英文字符，试为该文中的每个字符编制相应的哈夫曼码。(1)(2)(3)I :初始化(Initialization)。对输入的一段英文中的每个字符统计其权值，建立哈夫曼树;E：编码(Encoding )。利用已建好的哈夫曼树，对每个字符进行编码。D :译码(Decoding )。利用已建好的每个编码，对输入的一个由0、1组成的序列进行译(4)P:印代码文件(Print )

2、。将每个字符编的哈夫曼码和译码结果显示在终端上。测试用例见题集 P149。求)要求完成的主要任务:(包括课程设计工作量及其技术要求，以及说明书撰写等具体要问题描述 简述题目要解决的问题是什么。设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计;调试报告 调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。经验和体会（包括对算法改进的设想） 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出,0分。CD 盘）。6、设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为时间安排:1、第18周（6月28日至7月

3、2日）完成。2、7月2日08 : 30到计算中心检查程序、交课程设计报告、源程序（指导教师签名:系主任（或责任教师）签名:1目录2问题描述3.1数据结构设计3.2主要算法设计3.3测试用例设计4调试报告5结束语弋、课程设计参考资料附录9.16F1源代码F2运行结果哈夫曼编码1设计题目哈夫曼编码2问题描述输入一段英文字符，试为该文中的每个字符编制相应的哈夫曼码。(1)I :初始化(Initialization )。对输入的一段英文中的每个字符统计其权值，建 立哈夫曼树;(2) E：编码(Encoding )。利用已建好的哈夫曼树，对每个字符进行编码。(3) D：译码(Decoding )。利用已

4、建好的每个编码，对输入的一个由0、1组成的序列进行译码;(4) P:印代码文件(Print )。将每个字符编的哈夫曼码和译码结果显示在终端上。3 .设计3.1数据结构设计抽象数据类型二叉树的定义如下:ADT Bin aryTree数据对象D : D是具有相同特性的数据元素的集合。数据关系R: 基本操作P:InitBiTree (&T )； 操作结果：构造空二叉树T0DestroyBiTree (&T )； 初始条件：二叉树T存在。操作结果：销毁二叉树ToCreateBiTree (&T，definition )；初始条件：definition 给出二叉树T的定义。操作结果：按definitio

5、n 构造二叉树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，

6、e）；初始条件：二叉树T存在，e是T中某个结点。操作结果：若e是T的非根结点，贝U返回它的双亲,否则返回“空”。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

7、Huffma n/定义指向结点的结构体int weight;/ 权值int paren t,lchild,rchild;/父亲结点和左右结点的位置；void select(Huffman * ht,i nt i,i nt & s1,i nt & s2)/选择权值较小的两个作为新的叶子结点，用于huffman的构造。int j,k;k=s1;for(j=0;ji+1;j+)if(s1!=j&j!=s2&htj. pare nt=O)s1=j;break;for(j=0;ji+1;j+)if(s2!=j&s1!=j&j!=k&htj. paren t=0)s2=j;break;for(j=1;j=

8、i;j+)if(htj.weightvhts1.weight&htj. pare nt=0)s仁j;if(s1=s2)for(j=0;jvi+1;j+) if(s2!=j&s1!=j&j!=k&htj. paren t=0) s2=j;break;for(j=0;j=i;j+)if(htj.weightvhts2.weight&htj. paren t=0&j!=s1) s2=j;void Huffma ncodi ng(Huffma n * ht,char * *&hc,i nt k) /对haffman 进行编码int m,s1=0,s2=0,start,c,i,f,j;char * cd

9、;m=2*k-1;for(i=k;im;i+)/ 构建 huffman 树select(ht,i-1,s1,s2);/ 调用 select 函数hts1. paren t=i;hts2. paren t=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;jvk;j+) cdj=;start=k-1;for(c=i,f=hti. paren t;f!=0;c=f,f=htf .parent)if(htf.lc

10、hild=c) cdstart-=0; else cdstart-=1;hci=&cdstart+1;void freque ncy(i nt * & w,char str100,i nt * & c,i nt n,i nt & k)/涵数用于统计输入的字符的权 w （出现的次数）。int i,j,m;for(i=0;i vn ;i+)if(i=0)c0=0;co ntin ue;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;m n; m+)if(cm= =j)wj+;3.3测试用例设计

11、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，构造哈夫曼树。如下图:哈夫曼编码：4调试报告程序调试:（1.）当01序列解码成字符串时，要注意是否与已得出的字符串的编码匹配，如果不匹配，就把它后面的01序列截掉，不进行解码。（2.） &表示函数的参数是按地址传递的，当函数有多个返回值而无法用return实现时,通常使用这种。比如：void frequency(int

12、* & w,char str1OO,int * & c,int n,int & k)5结束语经验和体会:通过一个星期的努力，总算把课程设计给完成了，这是一个坚苦而又漫长的过程。是 啊，读了那么多年的书，课程设计可是第一次。看着劳动成果，很欣慰！通过这次课程设 计之后我觉得自己对书上知识的掌握有很大的欠缺， 看了题目都不知道怎么下手，一点头 绪都没有，之后自己认真看了一遍书上的知识，查阅了一些网上资料，我能熟练掌握了二 叉树，然后在此基础上掌握理解 haffman树和编码，熟知了二叉树的性质。可是这点小进展远远不够，这只是一个小小的开始，只能程序的大概轮廓可以写出来了。 但是有很多 的细节和特殊

13、情况没法写上去，例如：用于huffman的构造；用于对haffman进行编码;用于统计输入的字符的权 w （出现的次数）；实现这些的程序不知道该怎么写。后来经过同学的帮助和指导慢慢地程序里用到的函数通过哪些语句来实现它，那些关键的函数怎样 把它们有机结合起来等等，总之，在同学的多次指导下一个完整的程序写出来了， 我也努 力地去读懂它，发现自己隐约读懂了它!真正的收获更多是思想上的，让我认识程序的复杂，自己的微不足道，“学无止境” 头一次认识的这么深刻，察觉自己的不足。在这次编程中，同学帮了我很多，我一个人是 不能完成的。查书，查资料，请教同学的过程就是我提高的过程，总之，通过这次的课程 设计，

14、我发现程序设计最重要的就是上机实践， 以前只是看书，觉得看懂了，但是真正到 机子上写程序时感觉无从下手，没有什么头绪，可能就是因为实际上机操作的太少了， 以后需要在这方面好好地加强了。以后的学习生活真的要踏踏实实，自己的计算机生涯必定 是坎坷的，信心受挫了。六、课程设计参考资料1 数据结构（STL框架），王晓东编著，清华大学出版社，出版或修订时间：20092 数据结构（C语言版）严蔚敏，吴伟民编著，出版社：清华大学出版社，出版或修订时间：1997年4月3 数据结构习题集（C语言版）严蔚敏，吴伟民，米宁编著，清华大学出版社,出版或修订时间：1999年2月起草人：杨克俭2010-6-22附录F1源

15、代码#in elude using n ames pace std;struct Huffma n/定义指向结点的结构体int weight ；/ 权值int parent,lchild,rchild;/父亲结点和左右结点的位置 ；void select(Huffman * ht,i nt i,i nt & s1,i nt & s2)/选择权值较小的两个作为新的叶子结点，用于huffman的构造。int j,k;k=s1;for(j=0;jvi+1;j+)if(s1!=j&j!=s2&htj. pare nt=0)s1=j;break;for(j=0;ji+1;j+)if(s2!=j&s1!=

16、j&j!=k&htj. paren t=0)s2=j;break;for(j=1;j=i;j+)if(htj.weightvhts1.weight&htj. pare nt=0)s1=j;if(s1=s2)for(j=0;jvi+1;j+) if(s2!=j&s1!=j&j!=k&htj. paren t=0) s2=j;break;for(j=0;j=i;j+)if(htj.weightvhts2.weight&htj. paren t=0&j!=s1) s2=j;void Huffma ncodi ng(Huffma n * ht,char * *&hc,i nt k) /对haffman

17、 进行编码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. paren t=i;hts2. paren t=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;jvk;j+) cdj=;start=k-1;for(c=i,f=hti

18、. paren t;f!=0;c=f,f=htf .parent)if(htf.lchild=c) cdstart-=0; else cdstart-=1;hci=&cdstart+1;void freque ncy(i nt * & w,char str100,i nt * & c,i nt n,i nt & k)涵数用于统计输入的字符的权 w （出现的次数）。int i,j,m;for(i=0;i vn ;i+)if(i=0)c0=0;co ntin ue;for(j=0;ji;j+)if(strj=stri)ci=cj;break;if(j= =i)ci=+k;for(j=0;j=k;j

19、+)for(m=0;m str;i=0;while(stri!=)n+;i+;n-;/while循环统计输入的字符串中的字符数；c=new int n;for(i=0;i vn ;i+)ci=0;w=new int n;for(i=0;ivn;i+)wi=0;/ 对 c 和 w 分配初值；freque ncy(w,str,c, n,k);m=2*n-1 ;/计算总的结点数ht=new Huffma n m;hc=new char* n*sizeof(char*);hti.weight=wi;hti. paren t=hti.lchild=hti.rchild=O;for(;ivm;i+)hti

20、.weight=hti. pare nt=hti.lchild=hti.rchild=0;k+;Huffma ncodi ng(ht,hc,k);coutvv 各字符及其相应的编码为：vvendl;for(i=0;i vn ;i+)for(l=O;lvi;l+)if(ci=cl)break;if(l=i)coutvvstri;for(j=O;jv n;j+)if(hccij!=O&hccij!=1)break;else coutvv vvhccij;coutvve ndl;coutvv您输入的字符串的编码为: endl;for(i=0;i n ;i+)for(j=0;j n;j+)if(hcc

21、ij!=0&hccij!=1)break;else couthccij;coute ndl;/ /前面的就是调用上面定义的函数来实现i=0;cout 请输入需要译码的字符串: str1;m=0;while(str1i!= )m+;i+;m-;j=0;cout译码后为：endl;while(jk)for(l=0,i=r;lk,i=m;i+,l+)if(hcjl!=0&hcjl!=1)r=i;for(t=0;t vn ;t+)if(ct=j)coutvvstrt;break;j=0； break;”但最后的 i-r 个字符if(str1i!=hcjl)j+;break;if(i=m)&(hcjl=0|hcjl=1)coutvv无法