文档介绍：数据结构课程设计---哈弗曼编码译码哈夫曼编码译码一、需求分析在当今信息爆炸时代,如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视,哈夫曼编码正是一种应用广泛即最优且非常有效的数据压缩技术。哈夫曼编码是一种编码方式,以哈夫曼树—二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码,这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码,输入二进制代码时可以编译成字符串二、其主要流程图:开始将data和权值赋给ht否结点数是否大于1是输出根结点和权值否I<2*N?是I++调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点否是否为根结点,是是左子是否为空,否是右子是否为空此时编码为0否编码为1结束三、设计要求:(1)哈夫曼树的建立;(2)哈夫曼编码的生成(3)编码文件的译码四、总结:通过这次的课程设计了解课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,,当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。回顾起此次课程设计,至今我仍感慨颇多,的确,自从拿到题目到完成整个编程,从理论到实践,在整整一个星期的日子里,可以学到很多很多的的东西,同时不仅可以巩固了以前所学过的知识,而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的,只有把所学的理论知识与实践相结合起来,从理论中得出结论,才能真正为社会服务,从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题,这毕竟独立做的,难免会遇到过各种各样的问题,同时在设计的过程中发现了自己的不足之处,对以前所学过的知识理解得不够深刻,掌握得不够牢固,比如说结构体„„通过这次课程设计之后,一定把以前所学过的知识重新温故。我表示感谢~同时,对给过我帮助的所有同学和各位指导老师再次表示忠心的感谢~五、源程序:#include<>#include<>//要用system函数要调用的头文件#include<>//用getch()要调用的头文件#include<>#defineN50//义用N表示50叶节点数#defineM2*N-1//用M表示节点总数当叶节点数位n时总节点数为2n-1#defineMAXSIZE100typedefstruct{chardata;//结点值intweight;//权值intparent;//双亲结点intlchild;//左孩子结点intrchild;//右孩子结点}HTNode;typedefstruct{charcd[N];//存放哈夫曼码intstart;//从start开始读cd中的哈夫曼码}HCode;voidCreateHT(HTNodeht[],intn)//调用输入的数组ht[],和节点数n{inti,k,lnode,rnode;intmin1,min2;for(i=0;i<2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;//所有结点的相关域置初值-1for(i=n;i<2*n-1;i++)//构造哈夫曼树{min1=min2=32767;//int的范围是-32768-32767lnode=rnode=-1;//lnode和rnode记录最小权值的两个结点位置for(k=0;k<=i-1;k++){if(ht[k].parent==-1)//只在尚未构造二叉树的结点中查找{if(ht[k].weight<min1)//若权值小于最小的左节点的权值{min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}elseif(ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}}ht[lnode].parent=i