《实验五哈夫曼编码与译码的设计与实现》由会员分享，可在线阅读，更多相关《实验五哈夫曼编码与译码的设计与实现（22页珍藏版）》请在金锄头文库上搜索。
1、.实验五 哈夫曼编码与译码的设计与实现一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。基本要求：（1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat中。（2）编码：利用已建好的哈夫曼树（如不在内存，则从文件nodedata.dat中读入），对文件中的正文进行编码，然后将
2、结果存入文件code.dat中。（3）译码：利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件textfile.txt中。（4）打印编码规则：即字符与编码的一一对应关系。（5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。二、数据结构设计1、构造哈夫曼树时，使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为：typedef struct int weight;in
3、t parent;int lchild;int rchild;char inf;HNodeType;2.求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码实际上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位码。所以设计如下数据类型：#define MaxBit 10struct HcodeTypeint bitMax
4、Bit;int start;3、文件nodedata.dat、code.dat、textfile.txt三、功能函数设计1、初始化功能模块此功能模块的功能为从键盘接受字符集大小n，以及n个字符和n个权值。2、建立哈夫曼编码的功能模块此模块功能为使用1中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树，即将HuffNode数组中的各个位置的各个域都填上相关的值，并将这个结构体数组存于文件nodedata.dat中。函数原型为：void Creat_Haffmantree(int &n)HNodeType *HaffNode=new HNodeType2*n-1;int i,j;int m1,m
5、2,x1,x2;for(i=0;i2*n-1;i+)HaffNodei.weight=0;HaffNodei.parent=-1;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf=0;for(i=0;in;i+)cout请输入字符HaffNodei.inf;cout请输入该字符的权值HaffNodei.weight;for(i=0;in-1;i+)/构造哈夫曼树m1=m2=Maxvalue;x1=x2=0;for(j=0;jn+i;j+)/选取最小和次小if(HaffNodej.parent=-1&HaffNodej.weightm1)
6、m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;elseif(HaffNodej.parent=-1&HaffNodej.weightm2)m2=HaffNodej.weight;x2=j;/将找出的最小和次小合并，创造其父母结点HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x2;HaffNoden+i.rchild=x1;HaffNoden+i.inf=NULL;cout显示存储
7、的哈弗曼树信息:endl; cout权值左孩子右孩子双亲endl; for(i=0;i2*n-1;i+) coutHaffNodei.inf ; coutHaffNodei.weight ; coutHaffNodei.lchild ; coutHaffNodei.rchild ; coutHaffNodei.parentendl; /写入文件fstream outfile1;outfile1.open(E:nodedata.dat,ios:out|ios:trunc|ios:binary);/建立进行写入的文件if(!outfile1) /没有创建成功则显示相应信息coutnodedata.
8、dat文件不能打开endl;abort();for(i=0;i2*n-1;i+) /将内存中从HaffNodei地址开始的sizeof(HaffNodei)的内容写入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/关闭文件delete HaffNode;3、建立哈弗曼编码功的功能模块此模块功能是从文件nodedata.dat中读入相关的字符信息进行哈弗曼编码，然后将结果存入code.dat中，同时将字符与0和1代码串的一一对应关系显示到屏幕上。函数原型为：void HaffCode(int &n)/
9、哈夫曼编码HNodeType *HaffNode=new HNodeTypeMaxnode;HcodeType *HaffCode=new HcodeTypeMaxleaf;HcodeType cd;int i,j,c,p;fstream in(E:nodedata.dat,ios:in|ios:binary);in.read(char*)HaffNode,(2*n-1)*sizeof(HNodeType);in.close();fstream outfile;outfile.open(E:codedata.dat,ios:out|ios:binary);/建立进行写入的文件for(i=0;i
10、n;i+)cd.start=n-1;c=i;p=HaffNodec.parent;while(p!=-1)if(HaffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.parent;for(j=cd.start+1;jn;j+)HaffCodei.bitj=cd.bitj;HaffCodei.start=cd.start;for(i=0;in;i+) outfileHaffNodei.inf;for(j=HaffCodei.start+1;jn;j+)outfileHaffCodei.
11、bitj; cout字符信息-编码信息endl; for(i=0;in;i+) coutHaffNodei.inf-; for(j=HaffCodei.start+1;jn;j+) coutHaffCodei.bitj; coutendl; outfile.close ();cout请输入要编码的字符串,基本元素为（;for(i=0;in;i+)coutHaffNodei.inf,;cout)inf;int f=strlen(inf);fstream outfile1;outfile1.open(E:code.dat,ios:out|ios:binary);/建立进行写入的文件if(!outf
12、ile1) coutcode.dat文件不能打开!endl; abort(); else coutendl; cout字符串编码后为:; for(int x=0;xf;x+) for(i=0;in;i+) if(infx=HaffNodei.inf) for(j=HaffCodei.start+1;jn;j+) outfile1.write(char*)&HaffCodei.bitj,sizeof(HaffCodei.bitj); coutHaffCodei.bitj; coutendl; cout编译后的代码串已经存入code.dat文件中!endl; coutendl; outfile1.close(); delete HaffNode;delete HaffCode;4. 此模块功能为接收需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文件textfile.dat，同时将翻译的结果在屏幕上打印输出。接受0、1代码串有两种形式，一种是直接输入，一种是从文件中读取。函数原型为：void decode( in
