哈夫曼编码和译码系统(附源代码)

实训报告题 目： 哈夫曼编码和译码系统院 系： 专 业： 姓 名： 学 号： 指导教师： 日 期： 目录一. 需求分析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打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。 问题补充：1. 从硬盘的一个文件里读出一段英语文章。2. 统计这篇文章中的每个字符出现的次数。3. 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储 结构的初态和终态进行输出。 4. 对每个字符进行编码并将所编码写入文件然后对所编码进行编译。 3这个哈夫曼编码译码主要是以英文字母输入进行编码与编译，编码译码过程由系统自动完成，人工操作部分就是电文的录入，和编译出来时的读操作。二概要设计本程序主要用到了三个算法。(1)哈夫曼树建立、编码在初始化(I)的过程中间，要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码。先将输入的字符和权值存放到一个结构体数组中，建立哈夫曼树，将计算所得的哈夫曼编码存储到另一个结构体数组中。(2)串的匹配在编码(D)的过程中间，要对已经编码过的代码译码，可利用循环，将代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较(3)哈夫曼遍历 在印哈夫曼树(T)的中，因为哈夫曼树也是二叉树，所以就要利用二叉树的先序遍历将哈夫曼树输出。三详细设计及编码实现构造哈夫曼树的方法如下： 初始化：每个字符就是一个结点，字符的频度就是结点的权； 1、将结点按频度从小到大排序； 2、选取频度最小的两个结点，以它们为儿子，构造出一个新的结点；新结点的权值就是它两个儿子的权值之和；构造之后，从原来的结点序列里删除刚才选出的那两个结点，但同时将新生成的结点加进去； 3、如果结点序列里只剩下一个结点，表示构造完毕，退出。否则回到第一步。编码： 上面已经生成了树，接着就该对该树进行编码了。 可以假定，对某个结点而言，其左孩子在当前阶段的编码为0，右孩子的编码为1。这样就可以通过“树的遍历”的方式来生成字符编码对照表。 来到这里，基本上艰苦的已经完成了，对某个具体的字符串编码和解码就只是简单的“查表替换”的工作了。 译码： 译码也是个简单的查表-替换过程。如果利用该种编码发送字符串，则它的“字符编码”对应表也必须发送过去，不然对方是不知道怎么解码的。 对给出的一串编码，从左向右，将编码组合起来并查表，“一旦”找到有匹配的字符，则马上将当前的编码替换为对应的字符。 因为该编码是不会出现”某一个字符的编码是另一个字符编码的缀”这种情况的，也就是不会出现类似于“A 00 B 0010” 这样的情况，所以译码出来的字符串是唯一的，而且就是原来进行编码的那一个。代码如下：（1）求频率遍历过程：int Frequent(char *p)char *pt2=p;int i=0;ch0=*pt2;freq0=0;while(*pt2!=0)for(int j=0;ji) /遍历结束，该字符目前频度为1，跳至下一个字符i+;chi=*pt2;freqi=1;pt2+;coutendl统计权值：endl;for(int j=0;j=i;j+)cout字符chj的权值为freqjendl;return i+1;（2） 预程序处理及结构体定义：#include #include using namespace std;struct HNode int 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 SelectMin(int&x,int&y,int start,int end); / 从1-i中选取权值最小的两个结点（x,y为游标）void Reverse(char *,int); / 将编码字符逆置public:void Init(int a,int n);void CreateTable(char b,int n);void Encode(char *c, char *s,int n); void Decode(char *s, char *d,int n);Huffman();（3） 主函数main：void main()Huffman obj;char *sentence1=new char500;char *code01=new char1000;*code01=0;coutn 请输入所需文章:endl;gets(sentence1);int n=Frequent(sentence1);char *sentence2=new char500;char *sentence3=new char500;for(int i=0;i=499;i+)*(sentence3+i)=0;char *code02=new char1000;*code02=0;cout*endl 菜单:endl 1.建立编码表nn 2.编码nn 3.编码新字符串nn 4.译码新编码串nn 5.退出n*endl;coutnn请选择菜单：n*w;switch(w)case 1:obj.Init(freq,n);obj.CreateTable(ch,n);coutnn请选择菜单：n*endl;break;case 2:obj.Encode(sentence1,code01,n);coutnn请选择菜单：n*endl;break;case 3:gets(sentence2);coutendl请根据已编码字符再输入一句话：endl;gets(sentence2);obj.Encode(sentence2,code02,n);coutnn请选择菜单：n*endl;break;case 4:gets(code01);coutendl请根据编码表输入一个编码后的编码串：endl;gets(code01);obj.Decode(code01,sentence3,n);coutnn请选择菜单：n*endl;break;case 5:tag=0;break;default: cout选择错误，请重新选择！endl;coutendl;break;（4） 初始化并创建哈夫曼树：void Huffman:Init(int a,int n)int x=0,y=0;HTree= new HNode2*n-1;for(int i=0;in;i+) HTreei.weight=ai; /根据权重数组a初始化哈夫曼树HTreei.LChild=-1; /初始化HTreei.RChild=-1; /初始化HTreei.parent=-1; /初始化for(i=n; i2*n-1;i+) /开始建哈夫曼树SelectMin(x,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:CreateTable(char b,int n)coutendl打印编码表：endl;HCodeTable=new HCoden; / 生成编码表for(int i=0; in; i+)HCodeTablei.data=bi;int child=i;int parent=HTreei.parent;int k=0;while(parent!=-1)if(child=HTreeparent.LChild)HCodeTablei.codek=0; /左孩子标0elseHCodeTablei.codek=1; /右孩子标1k+;child=parent;parent=HTreechild.parent;HCodeTablei.codek=0;Reverse(HCodeTablei.code,k-1+1);coutHCodeTablei.data的编码是：HCodeTablei.codeendl;（5） 编码：void Huffman:Encode(char *c, char *s,int n) /编码SentenceLen=strlen(c);while(*c!=0) /字符串是否为空for(int i=0;i=n-1;i+)if(*c=HCodeTablei.data) /如果有值strcat(s,HCodeTablei.code);break;c+;CodeLen=strlen(s);coutendl编码后结果：sendl;（6） 译码：void Huffman:Decode(char *s, char *d,int n) /译码 s为编码串，d为译码后的字符串char *pd=d; /存储当前指针位置，方便最后输出。while(*s!=0)int parent=2*n-2; /根结点在HTree中的下标while(HTreeparent.LChild!=-1) /判断有无节点if(*s=0) parent=HTreeparent.LChild;elseparent=HTreeparent.RChild;s+;*d=HCodeTableparent.data;d+;coutendl译码后结果：pdLChild=NULL&p-RChild=NULLP=p-LChildSk+=strjP=root结束P=p-RChild五、调试分析：1.统计权值：2. 生成哈夫曼树，建立编码表3.将输入字符编码4. 输入新的字符串，进行编码5.输入任意译文可以得到原文六、系统维护经测试与调试确认软件无错时，开发就告一段落，这时可以交付软件供用户使用，但是在软件的使用过程中还会面临更加漫长的工作，即软件维护。一般维护的工作有：更改使用中发现的错误；为适应实际环境而对程序进行修改；为满足新的需求而对程序作必要的改进等等。七、实验总结通过简单哈夫曼编码和译码的设计与实现来掌握树型结构，学会用顺序表作为哈夫曼树的存储结构。所编程序的各个模块比较清晰，分块编写程序，然后在整个程序中对各子模块函数进行调用，是编写程序的重点。执行过程、比较顺利。 实现哈夫曼树的建立及哈弗曼编码的构造上学到不少细节问题解决的方法，积累了独立思考问题和解决问题的些许能力。程序编写要特别注意细节问题，善用指针，做到合理真却。 但是在实验过程中，遇到了很多问题，在编写程序之前没有仔细的分析实验的目的和要求就动手做实验，导致走了很多弯路，而且总是卡住。另外在哈夫曼编码时，考虑的不够周到，这也是由于认识不够全面。 程序虽然最终实现了特定的功能，但就编写效率，算法优化，程序执行效率方面还的有很大的提高！学习数据结构就是提高时间效率，降低空间复杂度。 实训是迅速提高教学要求的主要手段，所以，在今后要多动手，动脑，为自己的成功做好坚实的根基。我相信未来一定会做的越来越好。验收的时候设备出了点小故障，没能很好的顺利验收，下次会好好注意。8. 源代码#include #include using namespace std;struct HNode int 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 SelectMin(int&x,int&y,int start,int end); / 从1-i中选取权值最小的两个结点（x,y为游标）void Reverse(char *,int); / 将编码字符逆置public:void Init(int a,int n);void CreateTable(char b,int n);void Encode(char *c, char *s,int n); void Decode(char *s, char *d,int n);Huffman();void Huffman:Init(int a,int n)int x=0,y=0;HTree= new HNode2*n-1;for(int i=0;in;i+) HTreei.weight=ai; /根据权重数组a初始化哈夫曼树HTreei.LChild=-1; /初始化HTreei.RChild=-1; /初始化HTreei.parent=-1; /初始化for(i=n; i2*n-1;i+) /开始建哈夫曼树SelectMin(x,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:CreateTable(char b,int n)coutendl打印编码表：endl;HCodeTable=new HCoden; / 生成编码表for(int i=0; in; i+)HCodeTablei.data=bi;int child=i;int parent=HTreei.parent;int k=0;while(parent!=-1)if(child=HTreeparent.LChild)HCodeTablei.codek=0; /左孩子标0elseHCodeTablei.codek=1; /右孩子标1k+;child=parent;parent=HTreechild.parent;HCodeTablei.codek=0;Reverse(HCodeTablei.code,k);coutHCodeTablei.data的编码是：HCodeTablei.codeendl;void Huffman:Encode(char *c, char *s,int n) /编码SentenceLen=strlen(c);while(*c!=0) /字符串是否为空for(int i=0;i=n-1;i+)if(*c=HCodeTablei.data) /如果有值strcat(s,HCodeTablei.code);break;c+;CodeLen=strlen(s);coutendl编码后结果：sendl;void Huffman:Decode(char *s, char *d,int n) /译码 s为编码串，d为译码后的字符串char *pd=d; /存储当前指针位置，方便最后输出。while(*s!=0)int parent=2*n-2; /根结点在HTree中的下标while(HTreeparent.LChild!=-1) /判断有无节点if(*s=0) parent=HTreeparent.LChild;elseparent=HTreeparent.RChild;s+;*d=HCodeTableparent.data;d+;coutendl译码后结果：pdendl;void Huffman:SelectMin(int &x,int &y,int n1,int n2)/从下标n1开始到n2-1的结点中找出没分配父结点的最小的两个，x，y分别为其下标，x更小if(n2-n11)throw error;x=-1;y=-1; /x,y为游标，初始值为-1for(int i=n1; in2; i+)if(HTreei.parent=-1) /未分配父结点if(x=-1)x=i;else if(y=-1)if(HTreex.weightHTreei.weight) /x,y中x的权值更小y=i;elsey=x;x=i;else if(HTreei.weightHTreex.weight) /x,y中x的权值更小y=x;x=i;else if(HTreei.weightHTreey.weight)y=i;void Huffman:Reverse(char *c,int len) / 字符逆置for(int 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 Frequent(char *p); /统计字符串p各字符出现的频率（权值）void main()Huffman obj;char *sentence1=new char500;char *code01=new char1000;*code01=0;coutn 请输入所需文章:endl;gets(sentence1);int n=Frequent(sentence1);char *sentence2=new char