哈夫曼编码和译码系统方案

1、.实训报告题目：哈夫曼编码和译码系统院系：专业：姓名：学号：指导教师：日期：.目录一、前言1二、需求分析11. 问题描述12. 基本要求13. 根据需求，该系统应具备以下功能2.三、概要设计21. 哈夫曼编码和译码的方法概述22. 流程图3四、详细设计41. 用类来定义变量和函数42. 构造哈夫曼树53. 根据哈夫曼树进行哈夫曼编码64. 输出对应的哈夫曼编码表75. 对输入的字符进行编码86. 对输入的编码进行译码97. 主函数10五、调试分析13六、实验总结16.一、前言在这个信息高速发展的时代，每时每刻都进行着大量的信息传递，到处都离不开信息，它贯穿在人们日常的生活之中，对人们产生的影响

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

3、电文代码长度尽可能短。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统能够对待传输数据预先编码，在接收端将传来的数据进行译码，所以为这样的信息收发站写一个哈夫曼的编译码系统。2. 基本要求输入一段英文原文，构造哈夫曼树，生成对应的编码表，输出原文对应的编码，或者是根据已生成的编码表，输入一段二进制数编码，得.到对应的字符原文。3. 根据需求，该系统应具备以下功能对给出的字符以及字符的权值构造哈夫曼树，生成对应的编码表输入一段原文，对原文进行编码输入二进制编码，输出对应的原文三、概要设计1. 哈夫曼编码和译码的方法概述初始化，每个

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

5、，然后对给出的一串编码，从左向右，将编码组合起来并查表，一旦找到有匹配的字符，则将当前的编码替换为对应的字符。因为该编码是不会出现”某一个字符的编码是另一个字符编.码的缀”这种情况的，也就是不会出现类似于“A为00而B为0010”这样的情况，所以译码出来的字符串是唯一的，而且就是原来进行编码的那一个。2. 流程图HuffmanMenu()CreatHTCreateHCodeDispHCodeeditHCodedeHCode取权值最小的两个节点节点权值相加权值小的至于左边，大的置于右边新的节点For 循环直到添加完所有的节点值构成哈夫曼树.四、详细设计1. 用类来定义变量和函数class Nod

6、e /节点类public:friend Hafuman;char data;/结点值int weight;/权值int parent;/双亲结点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, i

7、nt n); void editHCode(Node ht, Hafuman hcd, int n); void deHCode(Node ht, Hafuman hcd, int n);2. 构造哈夫曼树void Node:CreateHT( Node ht, int n) int i, k, lnode, rnode;int min1, min2;for (i = 0; i<2 * n - 1; i+)hti.parent = hti.lchild = hti.rchild = -1;/所有结点的相关域置初值-1for (i = n; i<2 * n - 1; i+)/构造哈夫

8、曼树min1 = min2 = 32767;/int的范围是 -32768 32767lnode = rnode = -1；/记录最小权值的两个结点位置for (k = 0; k <= i - 1; k+)if (htk.parent = -1)/只在尚未构造二叉树的结点中查找if (htk.weight<min1)/若权值小于最小的左节点的权值min2 = min1; rnode = lnode;.min1 = htk.weight; lnode = k;else if (htk.weight<min2)min2 = htk.weight; rnode = k;htlnod

9、e.parent=i;htrnode.parent=i;/ 两个最小节点的父节点是 ihti.weight=htlnode.weight+htrnode.weight;/ 两个最小节点的父节点权值为两个最小节点权值之和hti.lchild=lnode;hti.rchild=rnode;/ 父节点的左节点和右节点3. 根据哈夫曼树进行哈夫曼编码void Node:CreateHCode(Node ht, Hafuman hcd, int n)int i, f, c;Hafuman hc;for (i = 0; i<n; i+)/根据哈夫曼树求哈夫曼编码.hc.start = n; c =

10、i;f = hti.parent;while (f != -1)/循序直到树根结点结束循环if (htf.lchild = c)/处理左孩子结点hc.cdhc.start- = '0'else/处理右孩子结点hc.cdhc.start- = '1'c = f; f = htf.parent;hc.start+; /start指向哈夫曼编码hc.cd中最开始字符hcdi = hc;4. 输出对应的哈夫曼编码表void Hafuman:DispHCode(Node ht, Hafuman hcd, int n)int i, k;cout << "

11、;输出哈夫曼编码 :n"for (i = 0; i<n; i+)/输出 data 中的所有数据，即A-Z. cout<<"t"<<hti.data<<":"for(k = hcdi.start;k<=n;k+)/ 输出所有 data 中数据的编码 cout<< hcdi.cdk;cout<<"n"5. 对输入的字符进行编码void Hafuman:editHCode(Node ht, Hafumanhcd, int n) char stringMAXSI

12、ZE;int i, j, k;cin>> string;/把要进行编码的字符串存入string数组中cout<<"n输出编码结果 :n"for (i = 0; stringi != '#' i+)/#为终止标志for (j = 0; j<n; j+)if(stringi=htj.data|stringi=htj.data+32)/循环查找与输入字符相同的编号，相同的就输出这个字符的编码.for (k = hcdj.start; k <= n; k+)cout<< hcdj.cdk;break;/输出完成后跳出当

13、前for 循环6. 对输入的编码进行译码voidHafuman:deHCode(Node ht,Hafuman hcd,intn)/ 译码函数char codeMAXSIZE;int i, j, k, m, x,Knum = 50;cin>> code;/把要进行译码的字符串存入code 数组中while (code0 != '#')for (i = 0; i<n; i+)m = 0;/m为想同编码个数的计数器for (k = hcdi.start,j=0;k<=n;k+,j+)/j为记录所.存储这个字符的编码个数if (codej = hcdi.cdk

14、)/当有相同编码时m值加 1m+;if(m = j)/当输入的字符串与所存储的编码字符串个数相等时则输出这个的data 数据cout<< hti.data;for (x = 0; codex - 1 != '#' x+)/把已经使用过的 code 数组里的字符串删除codex = codex + j;Knum-;if (Knum < 1) code0 = '#'7. 主函数void main().int n = 26, i;int x, flag = 1;Node a; Hafuman b;Charstr= 'A','B

15、','C','D','E','F','G','H','I','J','K','L','M','N ','O','P','Q','R','S','T','U','V','W','X','Y','Z' ;/初始化

16、Intfnum= 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; i<n; i+)/把初始化的数据存入ht 结构体中hti.data = stri;hti.weight = fnumi;while (flag)/菜单函数，当 flag为 0 时跳出循环cout<<"n"cout<<"n*".cout<<"n * 1-显示编码 -1 *&q

17、uot;cout<<"n * 2-进行编码 -2 *"cout<<"n * 3-进行译码 -3 *"cout<<"n * 4-退出 -4 *"cout<<"n*"cout<<"n"cout<<" 请输入选择的编号 :"cin >>x;switch (x)case 1:system("cls");/清屏函数a.CreateHT(ht, n);a.CreateHCode(ht,

18、 hcd, n);b.DispHCode(ht, hcd, n);cout<<"n按任意键返回 ."_getch();system("cls");break;case 2:system("cls");.cout<<" 请输入要进行编码的字符串( 以#结束 ):n"b.editHCode(ht, hcd, n);cout<<"n按任意键返回 ."_getch();system("cls");break;case 3:system("cls");b.DispH