哈夫曼编码和译码系统_第1页
哈夫曼编码和译码系统_第2页
哈夫曼编码和译码系统_第3页
哈夫曼编码和译码系统_第4页
哈夫曼编码和译码系统_第5页
已阅读5页,还剩14页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、-作者xxxx-日期xxxx哈夫曼编码和译码系统【精品文档】实训报告题 目: 哈夫曼编码和译码系统院 系: 专 业: 姓 名: 学 号: 指导教师: 日 期: 【精品文档】目录一、前言.1二、需求分析.1.1.13.根据需求,该系统应具备以下功能.2.三、概要设计.2.2.3四、详细设计.4.42. 构造哈夫曼树.53. 根据哈夫曼树进行哈夫曼编码.64. 输出对应的哈夫曼编码表.7.8.9.10五、调试分析.13六、实验总结.16一、前言在这个信息高速发展的时代,每时每刻都进行着大量的信息传递,到处都离不开信息,它贯穿在人们日常的生活之中,对人们产生的影响日趋扩大,而利用哈夫曼码进行通信则可

2、以大大提高信道利用率,缩短通信传输时间,降低传输成本。在生产中则可以更大可能的降低成本从而获得更大里润,这也是信息时代发展的趋势所在。本次实训设计的是哈夫曼编码和译码系统,建立一个简易的系统,对于给定的一篇英文文章,统计字符出现的概率,并根据概率建立Huffman树,利用Huffman编码对文章进行编码和译码。掌握Huffman树的建立与应用,并进一步熟练掌握程序的设计流程。这是个拥有完整功能的系统程序,对将所学到的知识运用到实践中,在设计的同时,培养了学生各方面的能力。二、需求分析在传送电文时,人们总是希望传送时间尽可能短,这就是要求使电文代码长度尽可能短。利用哈夫曼编码进行通信可以大大提高

3、信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统能够对待传输数据预先编码,在接收端将传来的数据进行译码,所以为这样的信息收发站写一个哈夫曼的编译码系统。输入一段英文原文,构造哈夫曼树,生成对应的编码表,输出原文对应的编码,或者是根据已生成的编码表,输入一段二进制数编码,得到对应的字符原文。3.根据需求,该系统应具备以下功能对给出的字符以及字符的权值构造哈夫曼树,生成对应的编码表输入一段原文,对原文进行编码输入二进制编码,输出对应的原文3、 概要设计初始化,每个字符就是一个结点,对应节点的权值大小,选取权值最小的两个结点,以它们为儿子,构造出一个新的结点;新结点的

4、权值就是它两个儿子的权值之和;构造之后,从原来的结点序列里删除刚才选出的那两个结点,但同时将新生成的结点加进去;如果结点序列里只剩下一个结点,表示构造完毕,退出。否则回到第一步。对某个结点而言,其左孩子在当前阶段的编码为0,右孩子的编码为1,这样就可以通过遍历树来生成字符一一对应的编码表 来到这里,基本上艰苦的已经完成了,对某个具体的字符串编码和解码就只是简单的“查表替换”的工作了。 译码: 译码也是个简单的查表-替换过程。如果利用该种编码发送字符串,则它的“字符编码”对应表也必须发送过去,然后对给出的一串编码,从左向右,将编码组合起来并查表,一旦找到有匹配的字符,则将当前的编码替换为对应的字

5、符。 因为该编码是不会出现”某一个字符的编码是另一个字符编码的缀”这种情况的,也就是不会出现类似于“A 为00而 B 为0010” 这样的情况,所以译码出来的字符串是唯一的,而且就是原来进行编码的那一个。CreateHCodeDispHCodeeditHCodeCreatHTHuffmanMenu()deHCode取权值最小的两个节点节点权值小的至于左边,大的置于右边权值相加新的节点For循环直到添加完所有的节点值构成哈夫曼树四、详细设计class Node /节点类public:friend Hafuman;char data; /结点值int weight; /权值int parent;

6、/双亲结点int lchild; /左孩子结点int rchild; /右孩子结点void CreateHT(Node ht, int n); void CreateHCode(Node ht, Hafuman hcd, int n); ;class Hafumanpublic:friend Node;char cdN; /存放哈夫曼码int start; /从start开始读cd中的哈夫曼码void DispHCode(Node ht, Hafuman hcd, int n);void editHCode(Node ht, Hafuman hcd, int n);void deHCode(N

7、ode ht, Hafuman hcd, int n);void Node:CreateHT( Node ht, int n) int i, k, lnode, rnode;int min1, min2;for (i = 0; i2 * n - 1; i+)hti.parent = hti.lchild = hti.rchild = -1; /所有结点的相关域置初值-1for (i = n; i2 * n - 1; i+) /构造哈夫曼树min1 = min2 = 32767; /int的范围是-3276832767lnode = rnode = -1; /记录最小权值的两个结点位置for (

8、k = 0; k = i - 1; k+)if (htk.parent = -1) /只在尚未构造二叉树的结点中查找if (htk.weightmin1) /若权值小于最小的左节点的权值min2 = min1; rnode = lnode;min1 = htk.weight; lnode = k;else if (htk.weightmin2)min2 = htk.weight; rnode = k; htlnode.parent = i; htrnode.parent = i; /两个最小节点的父节点是ihti.weight = htlnode.weight + htrnode.weight

9、; /两个最小节点的父节点权值为两个最小节点权值之和hti.lchild = lnode; hti.rchild = rnode; /父节点的左节点和右节点void Node:CreateHCode(Node ht, Hafuman hcd, int n)int i, f, c;Hafuman hc;for (i = 0; in; i+) /根据哈夫曼树求哈夫曼编码hc.start = n; c = i;f = hti.parent;while (f != -1) /循序直到树根结点结束循环if (htf.lchild = c) /处理左孩子结点hc.cdhc.start- = 0;else

10、/处理右孩子结点hc.cdhc.start- = 1;c = f; f = htf.parent;hc.start+; /start指向哈夫曼编码hc.cd中最开始字符hcdi = hc;void Hafuman:DispHCode(Node ht, Hafuman hcd, int n) int i, k;cout 输出哈夫曼编码:n;for (i = 0; in; i+) /输出data中的所有数据,即A-Z coutthti.data:;for (k = hcdi.start;k=n; k+)/输出所有data中数据的编码 cout hcdi.cdk;cout string; /把要进行

11、编码的字符串存入string数组中coutn输出编码结果:n;for (i = 0; stringi != #; i+) /#为终止标志for (j = 0; jn; j+)if (stringi = htj.data | stringi = htj.data+32)/循环查找与输入字符相同的编号,相同的就输出这个字符的编码for (k = hcdj.start; k = n; k+)cout code; /把要进行译码的字符串存入code数组中while (code0 != #)for (i = 0; in; i+)m = 0; /m为想同编码个数的计数器for (k = hcdi.star

12、t,j=0;k=n;k+,j+) /j为记录所存储这个字符的编码个数if (codej = hcdi.cdk) /当有相同编码时m值加1m+;if (m = j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据cout hti.data;for (x = 0; codex - 1 != #; x+) /把已经使用过的code数组里的字符串删除 codex = codex + j;Knum-;if (Knum 1) code0 = #;void main()int n = 26, i; int x, flag = 1;Node a; Hafuman b; Char str

13、= A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z ;/初始化Int fnum= 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26 ; /初始化Node htM; Hafuman hcdN; for (i = 0; in; i+) /把初始化的数据存入ht结构体中hti.data = stri;hti.weight = fnumi;while (flag) /菜单函数,当flag为0时跳出循环coutn;coutn *;coutn * 1-显示编码-1

14、 *;coutn * 2-进行编码-2 *;coutn * 3-进行译码-3 *;coutn * 4-退出-4 *;coutn *;coutn;coutx;switch (x)case 1:system(cls); /清屏函数a.CreateHT(ht, n);a.CreateHCode(ht, hcd, n);b.DispHCode(ht, hcd, n);coutn按任意键返回.;_getch();system(cls);break;case 2:system(cls);cout请输入要进行编码的字符串(以#结束):n;b.editHCode(ht, hcd, n);coutn按任意键返回

15、.;_getch();system(cls);break;case 3:system(cls);b.DispHCode(ht, hcd, n);cout请输入编码(以#结束):n;b.deHCode(ht, hcd, n);coutn按任意键返回.;_getch();system(cls);break;case 4:flag = 0;break;default:system(cls);五、调试分析一般情况下,为解决一个问题所编写的程序代码较长,可能包括几百条甚至成千上万条语句。在检查并排除所有语法错误后,还会有不易发现的逻辑错误,因此要对程序进行认真仔细的测试与调试。1、运行代码,显示主菜单2、将字符编码,显示编码3.输入新的字符串,进行编码4.输入新的二进制数,将其译为字

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论