实验五-哈夫曼编码与译码的设计与实现.doc
23页
实验五 哈夫曼编码与译码的设计与实现一、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原)对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统试为这样的信息收发编写一个哈夫曼码的编/译码系统基本要求： (1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树,并将它存于文件nodedatadat中. (2）编码：利用已建好的哈夫曼树（如不在内存,则从文件nodedatadat中读入），对文件中的正文进行编码，然后将结果存入文件code.dat中 (3）译码：利用已建好的哈夫曼树将文件codedat中的代码进行译码,结果存入文件textfiletxt中 （4)打印编码规则：即字符与编码的一一对应关系 (5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上二、数据结构设计1、构造哈夫曼树时，使用静态链表作为哈夫曼树的存储在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n—1个结点,所以数组HuffNode的大小设置为2n—1，描述结点的数据类型为：typedef struct { int weight; int parent; int lchild； int rchild； char inf；}HNodeType；2.求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。
求哈夫曼编码实际上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位码.所以设计如下数据类型:＃define MaxBit 10struct HcodeType{ int bit［MaxBit］； int start；｝;3、文件nodedata.dat、code.dat、textfiletxt三、功能函数设计1、初始化功能模块此功能模块的功能为从键盘接受字符集大小n，以及n个字符和n个权值2、建立哈夫曼编码的功能模块此模块功能为使用1中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树，即将HuffNode数组中的各个位置的各个域都填上相关的值，并将这个结构体数组存于文件nodedata.dat中.函数原型为：void Creat_Haffmantree(int &n){ HNodeType ＊HaffNode=new HNodeType［2＊n—1］; int i，j; int m1，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 parent=n+i； HaffNode[n+i]weight=HaffNode［x1］weight+HaffNode[x2]weight; HaffNode［n+i]lchild=x2； HaffNode［n+i］rchild=x1； HaffNode［n+i].inf=NULL； ｝ cout<〈"显示存储的哈弗曼树信息:”〈〈endl； cout〈<”权值左孩子右孩子双亲”〈〈endl； for（i=0;i<2＊n-1；i++） ｛ cout< dat文件不能打开”〈〈endl； abort（）； } for（i=0;i〈2*n—1；i++） //将内存中从HaffNode[i］地址开始的sizeof(HaffNode[i]）的内容写入文件中 outfile1write（(char＊）＆HaffNode［i］，sizeof（HaffNode[i]）); outfile1.close （）；//关闭文件 delete ［］HaffNode; ｝3、建立哈弗曼编码功的功能模块此模块功能是从文件nodedata.dat中读入相关的字符信息进行哈弗曼编码，然后将结果存入codedat中，同时将字符与0和1代码串的一一对应关系显示到屏幕上函数原型为：void HaffCode（int &n）//哈夫曼编码｛ HNodeType *HaffNode=new HNodeType［Maxnode]； HcodeType ＊HaffCode=new HcodeType[Maxleaf］; 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)); inclose（）； fstream outfile; outfileopen（”E:\\codedata.dat”,ios:：out｜ios:：binary）；//建立进行写入的文件 for（i=0;i bit[j］； } cout〈〈”字符信息——编码信息”〈〈endl; for(i=0；i inf） ｛ for（j=HaffCode[i].start+1;j
