实验五简单哈夫曼编

实验五 简单哈夫曼编/译码的设计与实现本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几个功能来设计和实现。一、【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能：1、接收原始数据。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。2、编码。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。3、译码。利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。4、打印编码规则。即字符与编码的一一对应关系。5、打印哈夫曼树，将已在内存中的哈夫曼树以直观的方式显示在终端上。二、【数据结构设计】1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为：Typedef strcutInt weight；/*结点权值*/Int parent；Int lchild；Int rchild；HNodeType；2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型：#define MAXBIT 10Typedef structInt bitMAXBIT；Int start；HCodeType；3、文件hfmtree.dat、codefile.dat和textfile.dat。三、【功能（函数）设计】1、初始化功能模块。此功能模块的功能为从键盘接收字符集大小n，以及n个字符和n个权值。2、建立哈夫曼树的功能模块。此模块功能为使用1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树，即将HuffNode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件hfmtree.dat中。3、建立哈夫曼编码的功能模块。此模块功能为从文件hfmtree.dat中读入相关的字符信息进行哈夫曼编码，然后将结果存入codefile.dat中，同时将字符与0、1代码串的一一对应关系打印到屏幕上。4、译码的功能模块。此模块功能为接收需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文件textfile.dat，同时将翻译的结果在屏幕上打印输出。5、打印哈夫曼树的功能模块。此模块功能为从HuffNode数组中读入相关的结点信息，以图形的方式将各个结点以及叶子结点的权值和左分支上的0和右分支上的1画出来。四、【编码实现】#include iostream#include fstream#include stringusing namespace std;#define MAXBIT 10#define MAX 1000#define MAXVALUE 1000typedef structint dataMAX;int front,rear;SeQueue;typedef structint weight;int parent;int lchild;int rchild;HNodeType;typedef structchar c;int n;int x;Math;typedef structint bitMAXBIT;int start;HCodeType;SeQueue *Init_SeQueue()SeQueue *q;q=new SeQueue;q-front=q-rear=-1;return q;int In_SeQueue(SeQueue *q,int x)if(q-rear=MAX-1)return 0;elseq-rear+;q-dataq-rear=x;return 1;int Out_SeQueue(SeQueue *q,int *x)if(q-rear=q-front)return 0;elseq-front+;*x=q-dataq-front;return 1;int WriteFile()char xMAX;int n;ofstream outfile(hfmtree.txt,ios:out);if(!outfile)cerrOpen file or create file error.endl;elsecoutx;outfilexendl;n=strlen(x);outfile.close();return n-1;int ReadFile(int a)char *x,*y;Math M26;for(int i=0;i26;i+)Mi.n=0;Mi.x=-1;int *n,m=0,b=0;ifstream infile(hfmtree.txt,ios:in);if(!infile)cerrFile open error.x;for(int i=0;ia;i+)for(int j=0;j26;j+)if(xi=a+j)Mj.c=xi;Mj.n+;Mj.x=0;for(int i=0;i26;i+)if(Mi.x=0)m+;n=new intm;y=new charm+1;for(int i=0;im;i+)ni=0;for(int i=0;i26;i+)if(Mi.x=0)yb=Mi.c;nb=Mi.n;b+;for(int i=0;im-1;i+)for(int j=i+1;jyj)char h;h=yi;yi=yj;yj=h;ofstream outfile2(char.txt,ios:out);if(!outfile2)cerrOpen or creat char error.endl;elsefor(int i=0;im;i+)outfile2yi;outfile2.close();ofstream outfile(hfmtree.txt,ios:app);if(!outfile)cerrOpen or creat hfmtree error.endl;elsefor(int i=0;im;i+)outfileniendl;outfile.close();ofstream outfile1(value.txt,ios:out);if(!outfile1)cerrOpen or creat value error.endl;elsefor(int i=0;im;i+)outfile1niendl;outfile1.close();return m;void HaffmanTree(int m)int *n;char *y;n=new intm;y=new charm+1;ifstream infile1(char.txt,ios:in);if(!infile1)cerrRead file char error.y;HNodeType *Huffnode;Huffnode=new HNodeType26*2-1;int m1,m2,x1,x2;for(int i=0;i2*m-1;i+)Huffnodei.weight=0;Huffnodei.parent=-1;Huffnodei.lchild=-1;Huffnodei.rchild=-1;ifstream infile(value.txt,ios:in);if(!infile)cerrRead file error.endl;elsefor(int i=0;ini;for(int i=0;im;i+)Huffnodei.weight=ni;for(int i=0;im-1;i+)m1=m2=MAXVALUE;x1=x2=0;for(int j=0;jm+i;j+)if(Huffnodej.parent=-1&Huffnodej.weightm1)m2=m1;x2=x1;m1=Huffnodej.weight;x1=j;elseif(Huffnodej.parent=-1&Huffnodej.weightm2)m2=Huffnodej.weight;x2=j;Huffnodex1.parent=m+i;Huffnodex2.parent=m+i;Huffnodem+i.weight=Huffnodex1.weight+Huffnodex2.weight;Huffnodem+i.lchild=x1;Huffnodem+i.rchild=x2;ofstream outfile(hfmtree.txt,ios:app);if(!outfile)cerrOpen or create file error.endl;elsefor(int i=0;i2*m-1;i+)outfileHuffnodei.weight ; outfileHuffnodei.parent ; outfileHuffnodei.lchild ; outfileHuffnodei.rchildendl;ofstream outfile1(hfmtree1.txt,ios:out);if(!outfile)cerrOpen or create file error.endl;elsefor(int i=0;i2*m-1;i+)outfile1Huffnodei.weight ; outfile1Huffnodei.parent ; outfile1Huffnodei.lchild ; outfile1Huffnodei.rchildendl;void HaffmanCode(int m)char *y;int n,a,b;y=new charm+1;HNodeType *HuffNode;HuffNode=new HNodeType2*m-1;HCodeType HuffCode100,cd;int i,j,c,p; HaffmanTree(m);ifstream infile(hfmtree1.txt,ios:in);if(!infile)cerrRead file error.endl;elsefor(i=0;iHuffNodei.weight;infileHuffNodei.parent;infileHuffNodei.lchild;infileHuffNodei.rchild;for(i=0;im;i+)cd.start=m-1;c=i;p=HuffNodec.parent;while(p!=-1)if(HuffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1; cd.start-; c=p; p=HuffNodec.parent; for(j=cd.start+1;jm;j+) HuffCodei.bitj=cd.bitj; HuffCodei.start=cd.start;ifstream infile1(char.txt,ios:in);if(!infile1)cerrRead char error.y;for(i=0;im;i+)coutyi ;for(j=HuffCodei.start+1;jm;j+)coutHuffCodei.bitj;coutendl;coutn;SeQueue *Q;Q=Init_SeQueue();for(int i=0;in;i+)couta;In_SeQueue(Q,a);HNodeType h; for(int i=0;irear!=Q-front)Out_S