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

题目：哈夫曼编码和译码系统院系：专业：姓名：学号：指导教师：日期：实训报告目录一.需求分析····································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。这样就可以通过“树的遍历”的方式来生成字符——编码对照表。来到这里，基本上艰苦的已经完成了，对某个具体的字符串编码和解码就只是简单的“查表——替换”的工作了。译码：译码也是个简单的查表--替换过程。如果利用该种编码发送字符串，则它的“字符——编码”对应表也必须发送过去，不然对方是不知道怎么解码的。对给出的一串编码，从左向右，将编码组合起来并查表，“一旦”找到有匹配的字符，则马上将当前的编码替换为对应的字符。因为该编码是不会出现”某一个字符的编码是另一个字符编码的缀”这种情况的，也就是不会出现类似于“A00B0010”这样的情况，所以译码出来的字符串是唯一的，而且就是原来进行编码的那一个。代码如下：（1）求频率遍历过程：intFrequent(char*p){char*pt2=p;inti=0;ch[0]=*pt2;freq[0]=0;while(*pt2!='\0'){for(intj=0;j=i;j++)//在ch[0]~ch[i]中遍历是否有*pt2{if(ch[j]==*pt2){freq[j]++;break;}}if(ji)//遍历结束，该字符目前频度为1，跳至下一个字符{i++;ch[i]=*pt2;freq[i]=1;}pt2++;}coutendl统计权值：endl;for(intj=0;j=i;j++)cout字符ch[j]的权值为freq[j]endl;returni+1;}（2）预程序处理及结构体定义：#includeiostream#includestringusingnamespacestd;structHNode{intweight;intparent;intLChild;intRChild;};structHCode//哈夫曼编码表{chardata;charcode[100];};classHuffman{private:HNode*HTree;HCode*HCodeTable;intSentenceLen;//编码前长度intCodeLen;//编码后长度protected:voidSelectMin(int&x,int&y,intstart,intend);//从1-i中选取权值最小的两个结点（x,y为游标）voidReverse(char*,int);//将编码字符逆置public:voidInit(inta[],intn);voidCreateTable(charb[],intn);voidEncode(char*c,char*s,intn);voidDecode(char*s,char*d,intn);~Huffman(){};};（3）主函数main：voidmain(){Huffmanobj;char*sentence1=newchar[500];char*code01=newchar[1000];*code01='\0';cout\n《《《《《《《请输入所需文章:》》》》》》》endl;gets(sentence1);intn=Frequent(sentence1);char*sentence2=newchar[500];char*sentence3=newchar[500];for(inti=0;i=499;i++)*(sentence3+i)='\0';char*code02=newchar[1000];*code02='\0';cout********************************endl菜单:endl1.建立编码表\n\n2.编码\n\n3.编码新字符串\n\n4.译码新编码串\n\n5.退出\n********************************endl;cout\n\n请选择菜单：\n********************************endl;intw;booltag=1;while(tag)//菜单设计6tag=0,结束菜单{cinw;switch(w){case1:obj.Init(freq,n);obj.CreateTable(ch,n);cout\n\n请选择菜单：\n********************************endl;break;case2:obj.Encode(sentence1,code01,n);cout\n\n请选择菜单：\n********************************endl;break;case3:gets(sentence2);coutendl请根据已编码字符再输入一句话：endl;gets(sentence2);obj.Encode(sentence2,code02,n);cout\n\n请选择菜单：\n********************************endl;break;case4:gets(code01);coutendl请根据编码表输入一个编码后的编码串：endl;gets(code01);obj.Decode(code01,sentence3,n);cout\n\n请选择菜单：\n********************************endl;break;case5:tag=0;break;default:cout选择错误，请重新选择！endl;coutendl;break;}}}（4）初始化并创建哈夫曼树：voidHuffman::Init(inta[],intn){intx=0,y=0;HTree=newHNode[2*n-1];for(inti=0;in;i++){HTree[i].weight=a[i];//根据权重数组a[]初始化哈夫曼树HTree[i].LChild=-1;//初始化HTree[i].RChild=-1;//初始化HTree[i].parent=-1;//初始化}for(i=n;i2*n-1;i++)//开始建哈夫曼树{SelectMin(x,y,0,i);//从1-i中选出2个权值最小的结点HTree[x].parent=HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight;HTree[i].LChild=x;HTree[i].RChild=y;HTree[i].parent=-1;//节点无数据}}voidHuffman::CreateTable(charb[],intn){coutendl打印编码表：endl;HCodeTable=newHCode[n];//生成编码表for(inti=0;in;i++){HCodeTable[i].data=b[i];intchild=i;intparent=HTree[i].parent;intk=0;while(parent!=-1){if(child==HTree[parent].LChild)HCodeTable[i].code[k]='0';//左孩子标0elseHCodeTable[i].code[k]='1';//右孩子标1k++;child=parent;parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';Reverse(HCodeTable[i].code,k-1+1);coutHCodeTable[i].data的编码是：HCodeTable[i].codeendl;}}（5）编码：voidHuffman::Encode(char*c,char*s,intn)//编码{SentenceLen=strlen(c);while(*c!='\0')//字符串是否为空{for(inti=0;i=n-1;i++){if(*c==HCodeTable[i].data)//如果