《数据结构哈夫曼编码实验报告.pdf》由会员分享，可在线阅读，更多相关《数据结构哈夫曼编码实验报告.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构实验报告 实验五 简单哈夫曼编/译码的设计与实现 本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几个功能来设计和实现。一、【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输本钱。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能：1、接收原始数据。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件nodedata.dat 中
2、。2、编码。利用已建好的哈夫曼树如不在内存，那么从文件 nodedata.dat 中读入，对文件中的正文进行编码，然后将结果存入文件 code.dat 中。3、译码。利用已建好的哈夫曼树将文件 code.dat 中的代码进行译码，结果存入文件textfile.dat 中。4、打印编码规那么。即字符与编码的一一对应关系。二、【数据结构设计】1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组 HuffNode 保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点，所以数组 HuffNode的大小设置为 2n-1，
3、描述结点的数据类型为：typedef struct int weight;/结点权值 int parent;int lchild;int rchild;char inf;HNodeType;2、求哈夫曼编码时使用一维结构数组 HuffCode 作为哈夫曼编码信息的存储。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的 0、1 序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设
4、计如下数据类型：#define MAXBIT 10 typedef struct int bitMAXBIT；int start；HcodeType；3、文件 nodedata.dat、code.dat 和 textfile.dat。三、【功能函数设计】1、初始化功能模块。此功能模块的功能为从键盘接收字符集大小 n，以及 n 个字符和 n 个权值。2、建立哈夫曼树的功能模块。此模块功能为使用 1 中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树，即将 HuffNode 数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件hfmtree.dat 中。3、建立哈夫曼编码的功能模
5、块。此模块功能为从文件 nodedata.dat 中读入相关的字符信息进行哈夫曼编码，然后将结果存入 code.dat 中，同时将字符与 0、1 代码串的一一对应关系打印到屏幕上。4、译码的功能模块。此模块功能为接收需要译码的 0、1 代码串，按照 3 中建立的编码规那么将其翻译成字符集中字符所组成的字符串形式，存入文件 textfile.dat，同时将翻译的结果在屏幕上打印输出。四、【编码实现】#include#include#include#include#define MaxBit 10#define Maxvalue 100/应该大于权重之和#define Maxleaf 100#de
6、fine Maxnode Maxleaf*2-1 typedef struct int weight;int parent;int lchild;int rchild;char inf;HNodeType;struct HcodeType int bitMaxBit;int start;void Creat_Haffmantree(int&n)HNodeType*HaffNode=new HNodeType2*n-1;int i,j;int m1,m2,x1,x2;for(i=0;i2*n-1;i+)HaffNodei.weight=0;HaffNodei.parent=-1;HaffNode
7、i.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)m2=m1;x2=x1;m1=HaffNodej.weight;x1=j;else if(HaffNodej.parent=-1&HaffNo
8、dej.weightm2)m2=HaffNodej.weight;x2=j;/将找出的最小和次小合并，创造其父母结点 HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x1;HaffNoden+i.rchild=x2;HaffNoden+i.inf=NULL;cout显示存储的哈弗曼树信息:endl;cout权值 左孩子 右孩子 双亲endl;for(i=0;i2*n-1;i+)coutHaffNodei.we
9、ight ;coutHaffNodei.lchild ;coutHaffNodei.rchild ;coutHaffNodei.parent ;coutHaffNodei.infendl;/写入文件 fstream outfile1;outfile1.open(E:nodedata.dat,ios:out|ios:trunc|ios:binary);/建立进行写入的文件 if(!outfile1)/没有创立成功那么显示相应信息 coutnodedata.dat 文件不能翻开endl;abort();for(i=0;i2*n-1;i+)/将内存中从 HaffNodei地址开始的 sizeof(H
10、affNodei)的内容写入文件中 outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close();/关闭文件 delete HaffNode;void HaffCode(int&n)/哈夫曼编码 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*)Ha
11、ffNode,(2*n-1)*sizeof(HNodeType);in.close();fstream outfile;outfile.open(E:codedata.dat,ios:out|ios:binary);/建立进行写入的文件 for(i=0;in;i+)cd.start=n-1;c=i;p=HaffNodec.parent;while(p!=-1)if(HaffNodep.lchild=c)cd.bitcd.start=0;else cd.bitcd.start=1;cd.start-;c=p;p=HaffNodec.parent;for(j=cd.start+1;jn;j+)Ha
12、ffCodei.bitj=cd.bitj;HaffCodei.start=cd.start;for(i=0;in;i+)outfileHaffNodei.inf;for(j=HaffCodei.start+1;jn;j+)outfileHaffCodei.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+)coutHaf
13、fNodei.inf,;cout)inf;int f=strlen(inf);fstream outfile1;outfile1.open(E:code.dat,ios:out|ios:binary);/建立进行写入的文件 if(!outfile1)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
14、.bitj,sizeof(HaffCodei.bitj);coutHaffCodei.bitj;coutendl;cout编译后的代码串已经存入 code.dat 文件中!endl;coutendl;outfile1.close();delete HaffNode;delete HaffCode;void decode(int&n)/解码 int i;HNodeType*HaffNode=new HNodeType2*n-1;fstream infile1;infile1.open(E:nodedata.dat,ios:in|ios:binary);/读出哈夫曼树 if(!infile1)co
15、utnodedata.dat 文件不能翻开endl;abort();for(i=0;i2*n-1;i+)infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close();int tempcode100;int num=0;for(i=0;i100;i+)tempcodei=-1;HcodeType*Code=new HcodeTypen;fstream infile2;/读编码 infile2.open(E:code.dat,ios:in|ios:binary);while(!infile2.eof()infile2.read(ch
16、ar*)&tempcodenum,sizeof(tempcodenum);num+;infile2.close();num-;cout从文件中读出的编码为endl;for(i=0;inum;i+)couttempcodei;coutendl;int m=2*n-2;i=0;coutendl;cout译码后为:endl;fstream outfile;outfile.open(E:textfile.txt,ios:out);if(!outfile)couttextfile.txt 文件不能翻开!endl;abort();while(inum)/小于字符串的长度 while(HaffNodem.l
17、child!=-1&HaffNodem.rchild!=-1)if(tempcodei=0)m=HaffNodem.lchild;i+;else if(tempcodei=1)m=HaffNodem.rchild;i+;coutHaffNodem.inf;outfileHaffNodem.inf;m=2*n-2;coutendl;outfile.close();cout译码后的结果已经存入 textfile.txt 中!endl;delete HaffNode;int main()int n;cout*欢送进入编/译码系统！*endl;int ch1;do cout 1.建树endl;cout
18、 2:编码，并显示字符和对应的编码endl;cout 3:译码endl;cout 0:退出endl;cout*endl;coutch1;while(!(ch1=0)/输入不在 0 到 4 之间无效 coutch1;switch(ch1)case 1:coutttt 请输入编码个数n;Creat_Haffmantree(n);break;case 2:HaffCode(n);break;case 3:decode(n);break;while(ch1!=0);return 0;五、【运行与测试】1、令叶子结点个数 n 为 4，权值集合为1，3，5，7，字符集合为A，B，C，D，并有如下对应关系，A1、B3，C5，D7，调用初始化功能模块可以正确接收这些数据。2、调用建立哈夫曼树的功能模块，构造静态链表 HuffNode 的存储。3、调用建立哈夫曼编码的功能模块，在屏幕上显示如下对应关系：A111、B110、C10、D0 4、调用译码的功能模块，输入代码串“111110100”后，屏幕上显示译码结果：111110100 ABCD