实验五 哈夫曼编码与译码的设计与实现

《实验五 哈夫曼编码与译码的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验五哈夫曼编码与译码的设计与实现一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。基本要求：（1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat中。（2）编码：利用已建好的哈夫曼树（如不在内存，则从文件noded

2、ata.dat中读入），对文件中的正文进行编码，然后将结果存入文件code.dat中。（3）译码：利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件textfile.txt中。（4）打印编码规则：即字符与编码的一一对应关系。（5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。二、数据结构设计1、构造哈夫曼树时，使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组Hu

3、ffNode的大小设置为2n-1，描述结点的数据类型为：typedefstruct{intweight;intparent;intlchild;intrchild;charinf;}HNodeType;2.求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码实际上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码

4、为所求编码的低位码，后得到的分支代码为所求的高位码。所以设计如下数据类型：#defineMaxBit10structHcodeType{intbit[MaxBit];intstart;};3、文件nodedata.dat、code.dat、textfile.txt三、功能函数设计1、初始化功能模块此功能模块的功能为从键盘接受字符集大小n，以及n个字符和n个权值。2、建立哈夫曼编码的功能模块此模块功能为使用1中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树，即将HuffNode数组中的各个位置的各个域都填上相关的值，并将这个结构体数组

5、存于文件nodedata.dat中。函数原型为：voidCreat_Haffmantree(int&n){HNodeType*HaffNode=newHNodeType[2*n-1];inti,j;intm1,m2,x1,x2;for(i=0;i<2*n-1;i++){HaffNode[i].weight=0;HaffNode[i].parent=-1;HaffNode[i].lchild=-1;HaffNode[i].rchild=-1;HaffNode[i].inf='0';}for(i=0;i

6、符"<>HaffNode[i].inf;cout<<"请输入该字符的权值"<>HaffNode[i].weight;}for(i=0;i

7、nt==-1&&HaffNode[j].weight

8、示存储的哈弗曼树信息:"<