哈夫曼编码和译码系统

1、实 训 报 告题目：哈夫曼编码和译码系统院系：专业：姓名：学号：指导老师： 日期：31 / 28目录一.需求分析2二.概要设计（1） ） 建立哈夫曼树 、编码3（2） ） 字符匹配3（3） ） 哈夫曼树遍历3三.具体设计及编码实现3四.流程图（1） ） 总流程图15（2） ） 编码实现流程图16（3） ） 译码实现流程图17五.调试分析（ 1）运算权值18（ 1）生成哈夫曼树，建立编码表18（ 3）将输入字符编码19（ 4）输入新的字符串，进行译码19（ 5）输入新的二进制数将其译为字符20六.系统保护20七试验总结20八.源代码21一需求分析1问题描述：在传送电文时，人们总是期望传送时间尽可

2、能短，这就是 要求使电文代码长度尽可能短； 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本；但是，这要求在发送端通过一个编码系 统能够对待传输数据预先编码， 在接收端将传来的数据进行译码； 对于双工信道（即可以双向传输信息的信道） ，每段都需要一个完整的编 /译系统；所以为这样的信息收发站写一个哈夫曼的编译码系统；2打开一篇英文文章，统计该文章中每个字符显现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码；问题补充：1. 从硬盘的一个文件里读出一段英语文章；2. 统计这篇文章中的每个字符显现的次数；3. 以字符显现字数作为权值，构建哈

3、夫曼树，并将哈夫曼树的储备结构的初态和终态进行输出；4. 对每个字符进行编码并将所编码写入文件然后对所编码进行编译；3这个哈夫曼编码译码主要是以英文字母输入进行编码与编译，编码译码过程由系统自动完成， 人工操作部分就是电文的录入， 和编译出来时的读操作；二概要设计本程序主要用到了三个算法；(1) 哈夫曼树建立、编码在初始化 i 的过程中间，要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码；先将输入的字符和权值存放到一个结构体数组中，建立哈夫 曼树，将运算所得的哈夫曼编码储备到另一个结构体数组中；(2) 串的匹配在编码d 的过程中间， 要对已经编码过的代码译码， 可利用循环， 将代码中的与哈夫曼

4、编码的长度相同的串与这个哈夫曼编码比较(3) 哈夫曼遍历在印哈夫曼树 t 的中，由于哈夫曼树也是二叉树，所以就要利用二叉树的先序遍历将哈夫曼树输出；三具体设计及编码实现构造哈夫曼树的方法如下：初始化：每个字符就是一个结点，字符的频度就是结点的权；1、将结点按频度从小到大排序；2、选取频度最小的两个结点，以它们为儿子，构造出一个新的结点；新结点 的权值就是它两个儿子的权值之和； 构造之后， 从原先的结点序列里删除刚才选出的那两个结点，但同时将新生成的结点加进去；3、假如结点序列里只剩下一个结点，表示构造完毕，退出；否就回到第一步；编码：上面已经生成了树，接着就该对该树进行编码了；来到这里，基本上

5、艰苦的已经完成了，对某个具体的字符串编码和解码就只是简洁的“查表 替换”的工作了；译码：译码也是个简洁的查表 - 替换过程；假如利用该种编码发送字符串，就它的“字符编码”对应表也必需发送过去，不然对方是不知道怎么解码的；对给出的一串编码，从左向右，将编码组合起来并查表，“一旦”找到有匹配的字符，就立刻将当前的编码替换为对应的字符；由于该编码是不会显现 ”某一个字符的编码是另一个字符编码的缀”这种情况的，也就是不会显现类似于 “a 00b0010” 这样的情形，所以译码出来的字符串是唯独的，而且就是原先进行编码的那一个；代码如下：（ 1）求频率遍历过程：int frequentchar *pch

6、ar *pt2=p;int i=0;ch0=*pt2;freq0=0;可以假定，对某个结点而言，其左孩子在当前阶段的编码为0，右孩子的编码为 1；这样就可以通过 “树的遍历 ”的方式来生成字符 编码对比表；while*pt2.=0forint j=0;ji/ 遍历终止，该字符目前频度为1 ，跳至下一个字符i+;chi=*pt2;freqi=1;pt2+;coutendl统计权值： endl;forint j=0;j=i;j+cout 字符chj的权值为 freqjendl;return i+1;（2） ）预程序处理及结构体定义：#include #include using namespace

7、 std;struct hnodeint weight;int parent;int lchild;int rchild;struct hcode/哈夫曼编码表char data;char code100;class huffmanprivate:hnode* htree;hcode* hcodetable;int sentencelen;/编码前长度int codelen;/编码后长度protected:void selectminint&x,int&y,int start,int end; /从 1-i中选取权值最小的两个结点（ x,y 为游标）void reversechar *,int

8、;/将编码字符逆置public:void initint a,int n;void createtablechar b,int n;void encodechar *c, char *s,int n;void decodechar *s, char *d,int n;huffman;（3） ）主函数 main ：void mainhuffman obj;char *sentence1=new char500;char *code01=new char1000;*code01=0;coutn请输入所需文章: endl; getssentence1;int n=frequentsentence1;

9、char *sentence2=new char500;char *sentence3=new char500;forint i=0;i=499;i+*sentence3+i=0;char *code02=new char1000;*code02=0;cout*endl菜单:endl1. 建立编码表 nn2.编码nn3.编码新字符串 nn4.译码新编码串nn5.退出 n*endl;coutnnint w;请挑选菜单：n*w;switchwcase 1:obj.initfreq,n;obj.createtablech,n;coutnn请挑选菜单： n*endl; break;case 2:obj

10、.encodesentence1,code01,n;coutnn请挑选菜单： n*endl; break;case 3:getssentence2;coutendl请依据已编码字符再输入一句话：endl;getssentence2;obj.encodesentence2,code02,n;coutnn请挑选菜单： n*endl; break;case 4:getscode01;coutendl请依据编码表输入一个编码后的编码串：endl; getscode01;obj.decodecode01,sentence3,n;coutnn请挑选菜单： n*endl; break;case 5:tag=

11、0;break;default:cout挑选错误，请重新挑选！endl; coutendl;break;（4） ）初始化并创建哈夫曼树：void huffman:initint a,int nint x=0,y=0;htree= new hnode2*n-1;forint i=0;in;i+htreei.weight=ai;/依据权重数组a 初始化哈夫曼树htreei.lchild=-1;/初始化htreei.rchild=-1;/初始化htreei.parent=-1;/初始化fori=n; i2*n-1;i+/开头建哈夫曼树selectminx,y,0,i;/从 1-i中选出 2 个权值最

12、小的结点htreex.parent=htreey.parent=i;htreei.weight=htreex.weight+htreey.weight;htreei.lchild=x;htreei.rchild=y;htreei.parent=-1;/节点许多据void huffman:createtablechar b,int ncoutendl打印编码表： endl; hcodetable=new hcoden;/生成编码表forint i=0; in; i+hcodetablei.data=bi;int child=i;int parent=htreei.parent;int k=0;w

13、hileparent.=-1ifchild=htreeparent.lchildhcodetablei.codek=0;/左孩子标 0elsehcodetablei.codek=1;/右孩子标 1k+;child=parent;parent=htreechild.parent;hcodetablei.codek=0;reversehcodetablei.code,k-1+1;couthcodetablei.data的编码是： hcodetablei.codeendl;（5） ）编码：void huffman:encodechar *c, char *s,int n/编码sentencelen=

14、strlenc;while*c.=0/字符串是否为空forint i=0;i=n-1;i+if*c=hcodetablei.data/假如有值strcats,hcodetablei.code;break;c+;codelen=strlens;coutendl编码后结果： sendl;（6） ）译码：void huffman:decodechar *s, char *d,int n/译码 s为编码串， d 为译码后的字符串char *pd=d;/储备当前指针位置，便利最终输出；while*s.=0int parent=2*n-2;/根结点在 htree 中的下标whilehtreeparent.

15、lchild.=-1/判定有无节点if*s=0parent=htreeparent.lchild;elseparent=htreeparent.rchild;s+;*d=hcodetableparent.data;d+;coutendl译码后结果： pdrchildp.=rootcodei= 0p=p-lchildp-lchild=null&p-rchild=nul lsk+=strjp=root终止五、调试分析：1. 统计权值：2. 生成哈夫曼树，建立编码表3. 将输入字符编码4. 输入新的字符串，进行编码5. 输入任意译文可以得到原文六、系统保护经测试与调试确认软件无错时，开发就告一段落，

16、 这时可以交付软件供用户使用，但是在软件的使用过程中仍会面临更加漫长的工作，即软件保护； 一般保护的工作有：更换使用中发觉的错误； 为适应实际环境而对程序进行修改；为满意新的需求而对程序作必要的改进 等等；七、试验总结通过简洁哈夫曼编码和译码的设计与实现来把握树型结构，学会用次序表作为哈夫曼树的储备结构； 所编程序的各个模块比较清楚， 分块编写程序， 然后在整个程序中对各子模块函数进行调用， 是编写程序的重点； 执行过程、 比较顺当；实现哈夫曼树的建立及哈弗曼编码的构造上学到不少细节问题解决的方法，积存了独立摸索问题和解决问题的些许才能；程序编写要特殊留意细节问题， 善用指针，做到合理真却；但

17、是在试验过程中，遇到了许多问题，在编写程序之前没有认真的分析实验的目的和要求就动手做试验， 导致走了许多弯路， 而且总是卡住； 另外在哈夫曼编码时，考虑的不够周到，这也是由于熟悉不够全面；程序虽然最终实现了特定的功能，但就编写效率，算法优化，程序执行效率方面仍的有很大的提高！学习数据结构就是提高时间效率，降低空间复杂度；实训是快速提高教学要求的主要手段，所以，在今后要多动手，动脑，为自己的胜利做好坚实的根基；我信任将来肯定会做的越来越好；验收的时候设备出了点小故障，没能很好的顺当验收，下次会好好留意；八. 源代码#include #include using namespace std;str

18、uct hnodeint weight; int parent; int lchild; int rchild;struct hcode/哈夫曼编码表char data;char code100;class huffmanprivate:hnode* htree;hcode* hcodetable;int sentencelen;/编码前长度int codelen;/编码后长度protected:void selectminint&x,int&y,int start,int end; /从 1-i中选取权值最小的两个结点（ x,y 为游标）void reversechar *,int;/将编码

19、字符逆置public:void initint a,int n;void createtablechar b,int n; void encodechar *c, char *s,int n;void decodechar *s, char *d,int n;huffman;void huffman:initint a,int nint x=0,y=0;htree= new hnode2*n-1; forint i=0;in;i+htreei.weight=ai;/依据权重数组a 初始化哈夫曼树htreei.lchild=-1;/初始化htreei.rchild=-1;/初始化htreei.p

20、arent=-1;/初始化fori=n; i2*n-1;i+/开头建哈夫曼树selectminx,y,0,i;/从 1-i中选出 2 个权值最小的结点htreex.parent=htreey.parent=i; htreei.weight=htreex.weight+htreey.weight;htreei.lchild=x;htreei.rchild=y;htreei.parent=-1;/节点许多据void huffman:createtablechar b,int ncoutendl打印编码表： endl; hcodetable=new hcoden;/生成编码表forint i=0;

21、in; i+hcodetablei.data=bi; int child=i;int parent=htreei.parent; int k=0;whileparent.=-1ifchild=htreeparent.lchildhcodetablei.codek=0;/左孩子标 0elsehcodetablei.codek=1;/右孩子标 1k+;child=parent; parent=htreechild.parent;hcodetablei.codek=0; reversehcodetablei.code,k;couthcodetablei.data的编码是： hcodetablei.c

22、odeendl;void huffman:encodechar *c, char *s,int n/编码sentencelen=strlenc;while*c.=0/字符串是否为空forint i=0;i=n-1;i+if*c=hcodetablei.data/假如有值 c+;strcats,hcodetablei.code; break;codelen=strlens;coutendl编码后结果： sendl;void huffman:decodechar *s, char *d,int n/译码 s为编码串， d 为译码后的字符串char *pd=d;/储备当前指针位置，便利最终输出；wh

23、ile*s.=0int parent=2*n-2;/根结点在 htree 中的下标whilehtreeparent.lchild.=-1/判定有无节点if*s=0parent=htreeparent.lchild;elses+;parent=htreeparent.rchild;*d=hcodetableparent.data; d+;coutendl译码后结果： pdendl;void huffman:selectminint &x,int &y,int n1,int n2/ 从下标 n1 开头到 n2-1 的结点中找出没安排父结点的最小的两个，x，y 分别为其下标， x更小ifn2-n11

24、throw error;x=-1;y=-1;/x,y为游标，初始值为-1 forint i=n1; in2; i+ifhtreei.parent=-1/未安排父结点ifx=-1x=i; else ify=-1ifhtreex.weighthtreei.weight/x,y中 x 的权值更小y=i;elseelsey=x; x=i;ifhtreei.weighthtreex.weight/x,y中 x 的权值更小y=x; x=i;else ifhtreei.weighthtreey.weight y=i;void huffman:reversechar *c,int len/字符逆置forint

25、 i=0;i=len/2-1;i+char temp=*c+i;*c+i=*c+len-1-i;*c+len-1-i=temp;char ch50;int freq50=0;int frequentchar *p;/统计字符串 p 各字符显现的频率（权值）void mainhuffman obj;char *sentence1=new char500; char *code01=new char1000;*code01=0;coutn请输入所需文章 : endl; getssentence1;int n=frequentsentence1;char *sentence2=new char500;