《2022年2022年哈夫曼_编码_报告 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年哈夫曼_编码_报告 .pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、- 1 - 计算机设计报告课题:哈夫曼树在通信编码中的应用专业班级：学号：姓名：指导教师 : 完成日期 : 2010 年 5 月 10 日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 16 页 - - - - - - - - - - 2 - 目录目录 ,2 一、问题描述 ,3 二、基本要求 ,3 三、数据结构的设计 ,3 四、程序设计思想 ,3 五、软件模块结构图 ,4 六、程序流程图 ,4 (1)主程序,5 (2)构造哈弗曼树,6 (3)哈弗曼编码,7 (4)哈弗曼译
2、码,8 七、调试数据分析 ,8 八、用户使用手册 ,11 九、心得体会 ,11 十、源程序 ,13 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 16 页 - - - - - - - - - - 3 - 一、问题描述设一段电文中有不同出现频率的字符，为了提高电文的输入和翻译效率，必须有一套简短而又不会产生歧义的字符代码。试根据哈夫曼算法，对电文中的不同字符，构造出一棵哈夫曼树，对每个字符进行编码。二、基本要求给定一篇电文根据哈弗曼算法编程构造哈弗曼树, 对电文中不同的字
3、符进行哈弗曼编码: 扩展功能 : 根据哈弗曼编码进行译码三、数据结构的设计由于哈弗曼树是由节点构成, 每个节点都有如下5 个属性letter, weight, parent, lchild, rchild;节点之间的关系又由parent,和lchild, rchild连带, 因此定义结构体类型数组HTi 来表示哈弗曼树各个节点 , 整棵哈弗曼树用各节点间的关系表示建好哈弗曼树 , 各字符对应的哈弗曼编码本质上为字符串, 定义字符串数组 HCi 来存储哈弗曼编码四、程序设计思想本程序是用最优二叉树即哈夫曼树来实现哈夫曼编码译码的功能。假设每种字符在电文中出现的次数为Wi，编码长度为Li ，电文中
4、有n 种字符，则电文编码总长度为(W1*L1)+(W2*L2)+, +(Wi*Li) +(Wn*Ln)。若将此对应到二叉树上，Wi为叶结点， Li 为根结点到叶结点的路径长度。那么，(W1*L1)+(W2*L2)+, +(Wi*Li) 恰好为二叉树上带权路径长度 WPL 。但是由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL 值最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。哈夫曼（Haffman）依据这一特点提出了一种方法，这种方法的基本思想是
5、：（1）由给定的 n 个权值 W1 ，W2 ，, ， Wn 构造 n 棵只有一个叶子结点的二叉树，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 16 页 - - - - - - - - - - 4 - 从而得到一个二叉树的集合FT1，T2，, ， Tn；（2）在 F 中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；（3）在集合 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到
6、集合 F 中；（4）重复（ 2） （3）两步，当 F 中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。这样, 对于同一组给定叶子结点所构造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。五、软件模块结构图六、程序流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 16 页 - - - - - - - - - - 5 - 1).主程序流程图 : 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -
7、- - - - 名师精心整理 - - - - - - - 第 5 页，共 16 页 - - - - - - - - - - 6 - 2). 构造哈弗曼树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 16 页 - - - - - - - - - - 7 - 3). 哈弗曼编码名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 16 页 - - - - -
8、 - - - - - 8 - 4). 哈弗曼译码七、调试和数据分析以电文 tongxingongcheng为例测试程序字符数 n = 9 字符及其对应的权值如下: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 16 页 - - - - - - - - - - 9 - 字符权值t 1 o 2 n 4 g 4 x 1 i 1 c 1 h 1 e 1 手工构建哈弗曼树如下图: 再来看看程序对这个电文的字符编码是否一致, 1. 双击运行程序2.字符数 n = 9,输入 9 名师
9、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 16 页 - - - - - - - - - - 10 - 3. 依次输入个字符及其权值4. 输出个字符的哈弗曼编码如下: 结果与手工构建哈弗曼树得到的编码一致, 此功能实现5. 输入 Y,测试译码功能名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 16 页 - - - - - - - - - - 11
10、- 6. 输入编码序列号 , 回车7. 得到译码文本 :tongxingongcheng,译码功能实现八、用户使用手册使用本程序前 ,先对电文进行字符统计,记录总字符种类和各个字符及其权值,然后按程序的提示依次输入数据即可得到个字符的哈弗曼编码. 需要使用译码功能时,依次输入各个字符代表的编码号,输完后回车即可显示译码后的电文 . 九、心得体会在课程设计过程中，我们每个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试程序的经验并逐渐培养我们的编程能
11、力、用计算机解决实际问题的能力。我选择的是哈夫曼树在通信编码中的应用, 在当今信息时代， 如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码的应用很广泛， 利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“ 0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -
12、- - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 16 页 - - - - - - - - - - 12 - 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。作为通信工程专业的学生，我们应该很好的掌握这门技术。在课堂上，我们能过学到许多的理论知识，但我们很少有过自己动手实践的机会, 课程设计就是为解决这个问题提供了一个平台。 通过两周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。在课程
13、设计过程中， 我们不但有自己的独立思考， 还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。软件技术基础课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。名师资料总结
14、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 16 页 - - - - - - - - - - 13 - 十、源程序#include #include #include typedef struct char letter; int weight; int parent; int lchild; int rchild; HTNode,*HuffmanTree; /定义结构体类型typedef char * *HuffmanCode;/字符串数组void Select(Huffma
15、nTree &HT,int s,int &s1,int &s2) int j, k, i; j=k=10000; / 最大权值s1=s2=0; / 权值最小和次小的两个树根节点下标初始值for(i=1;i=s;i+) if(HTi.parent=0) / 判断森林中的节点哪些未合并过if(HTi.weightj) / 循环语句用找出根结点的权值最小和次小的两个树，k=j;s2=s1; / 并将其根结点的下标号记入s1 和 s2 中j=HTi.weight; s1=i; else if(HTi.weightk) k=HTi.weight; s2=i; void setHuffmanTree(Hu
16、ffmanTree &HT,char *zi,unsigned int *w,int n) HuffmanTree p; int m,i,s1,s2; m=2*n-1; / 哈弗曼树总结点数HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;iletter = zii; p-weight = wi; /转移到结构体类型数组变量HTi 对应的成员变量里(*p).parent = 0; p-lchild = 0; p-rchild = 0; / 并对余下的成员变量赋初值 for(;iweight=0; p-parent=0; p-l
17、child=0; p-rchild=0; / 对于新合并出的节点的成员变量赋初值for(i=n+1;i=m;+i) / 构造哈夫曼树Select(HT,i-1,s1,s2); / 调用 void Select() 函数找出根节点权值最小和次小的两个树HTs1.parent=i; HTs2.parent=i; / 将这两棵树的父节点设为HTi HTi.lchild=s1; HTi.rchild=s2; / 将 i 的左右子节点分别设为HTs1 和 HTs2 HTi.weight=HTs1.weight+HTs2.weight; / 父节点的权值为子节点权值之和 void setHuffmanCo
18、de(HuffmanTree &HT,HuffmanCode &HC,int n) int start = 1; char *cd; int f,c,i; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd=(char*)malloc(n*sizeof(char); / 临时的编码存储cdn-1=0; / 编码最多为n-1 位for(i=1;i=n;+i) / 按已生成的哈夫曼树，得到各个字符的哈夫曼编码start=n-1; for(c=i, f=HTi.parent; f !=0; c=f, f=HTf.parent) / 循环条件 :该节点的父节点
19、不为0 if(HTf.lchild=c) cd-start = 0; / 左 0 右 1 else cd-start = 1; HCi = (char *)malloc(n - start) * sizeof(char); strcpy(HCi, &cdstart); / 把编码转移到字符串数组 free(cd); / 释放 cd 里临时存储的编码 void deCode(HuffmanTree H,int n) char y100; int m=2*n-1; int i,length; couty; cout译码的文本是：; length=strlen(y); / 取输入序列的长度i=0;
20、while(ilength) while(Hm.lchild != 0|Hm.rchild != 0) / 循环条件 :该节点不是叶子节点时 if(yi = 0) m = Hm.lchild; / 代码为 0，则把左子节点号传给m 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 16 页 - - - - - - - - - - 15 - else m=Hm.rchild; / 代码为 1，则把右子节点号传给m i+; / 到叶子节点循环结束coutHm.letter;
21、/ 输出该叶子节点代表的字符m = 2*n-1; / 重新给 m 赋值if(i=(length) coutendl; / 全部代码译码后输出换行符 void main() HuffmanTree HT; HuffmanCode HC; int n,i; char zifu100; unsigned int w100; cout请输入要编码的字符种类个数:n; / 字符种类数if(n=1) /n值的合法性判断cout您输入的n 值不合法重新输入:n; if(n=1) cout您输入的n 值无效请重新输入:n; return; / 两次不合法退出程序 for(i=1;in+1;i+) / 输入各个
22、字符及其权值,分别存入zifui 和 wi cout请输入第 i个字符及其权值并以空格分隔开:zifuiwi; for( int r=1;r=i-1;r+) / 判断输入的字符是否重复if(zifui=zifur) cout该字符已经存在，请重新输入！endl; i-; setHuffmanTree(HT,zifu,w,n); / 构造哈夫曼树setHuffmanCode(HT,HC,n); / 利用哈夫曼树为字符编码coutendl; / 输出换行符for(i=1;i=n;i+) / 输出各个字符及其对应的权值和编码coutchar： HTi.letter weight: HTi.weigh
23、t huffmancode: HCiendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 16 页 - - - - - - - - - - 16 - char o; / 定义字符变量for(i=1;i=n;i+) / 译码程序部分coutendl若要译码请输入Y,若不译码输入N.o; if(o=y|o=Y) / 根据输入判断是否需要译码deCode(HT,n); / 译码并显示模块模块,根据哈夫曼树及输入的编码序列,译码并显示模块 else if(o=N|o=n) return; / 不译码 ,直接退出程序 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 16 页 - - - - - - - - -