huffman(哈夫曼)树编码译码 课程设计报告

1、数据结构课程设计学 院： 信息科学与工程学院专 业： 计算机科学与技术 班 级： 计卓1601学 号： 学生姓名： 指导教师： 年 月 日题目名称一、实验内容哈夫曼编码译码系统【问题描述】用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。【基本要求】1）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树。2）编码。利用已建好的哈夫曼树

2、对输入英文进行编码，编码结果存储在数组中。3）译码。利用已建好的哈夫曼树将数组中的代码进行译码，结果存入一个字符数组。4）输出编码。将编码结果显示在终端上，每行50个代码。5）输出哈夫曼树。将哈夫曼树以直观的方式（树或凹入表形式）显示出来。【实现提示】用户界面可以设计为“菜单”方式，再加上一个“退出”功能。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“退出”为止。 参考教材P240-246 【选做内容】将哈夫曼树保存到文件中，编码和译码的结果也分别存放在两个文本文件中。二、数据结构设计储存结构struct HNodeType /字符结构体类型int weight;

3、/权int parent;/双亲位置int lchild;/左孩子int rchild;/右孩子char inf;/字符;struct HcodeType int bitMaxBit;/存储编码int start;/起始位置;三、算法设计1、在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1。求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码实际上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的父节点回退到根结点，每回

4、退一步，就走过了哈夫曼的一个分支，从而得到一位哈夫曼编码值。由于一个字符的哈夫曼编码就是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求的高位2、初始化为从键盘接受字符集大小n，以及n个字符和n个权值。3、建立哈夫曼编码为使用2中得到的数据按照教材中的构造哈弗曼的算法构造哈弗曼树，即将HuffNode数组中的各个位置的各个域都填上相关的值，并将这个结构体数组存于文件nodedata.dat中。void Creat_Haffmantree(int &n) /建树并输出树n+;HNodeType *HaffNode=new

5、 HNodeType2*n-1;int i,j;int m1,m2,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-1; i+) /输入字符及权值cout请输入字符:HaffNodei.inf;cout请输入该字符的权值:HaffNodei.weight;HaffNoden-1.inf= ;/最后一个为空格HaffNoden-1.weight=120;/空格权值for

6、(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&HaffNodej.weightm2) m2=HaffNodej.weight;x2=j;/合并Huffman树HaffNodex1.parent=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight

7、=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x1;HaffNoden+i.rchild=x2;HaffNoden+i.inf= ;/输出树cout显示存储的哈弗曼树信息:endl;cout 权值 左孩子 右孩子 父节点endl;for(i=0; i2*n-1; i+) coutHaffNodei.inf ;coutsetiosflags(ios:right)setw(4)HaffNodei.weight ;coutsetiosflags(ios:right)setw(4)HaffNodei.lchild ;coutsetios

8、flags(ios:right)setw(4)HaffNodei.rchild ;coutsetiosflags(ios:right)setw(4)HaffNodei.parentendl;/写入文件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地址开始的si

9、zeof(HaffNodei)的内容写入文件中outfile1.write(char*)&HaffNodei,sizeof(HaffNodei);outfile1.close ();/关闭文件delete HaffNode;4、 编码系统为从文件nodedata.dat中读入相关的字符信息进行哈弗曼编码，然后将结果存入code.dat中，同时将字符与0和1代码串的一一对应关系显示到屏幕上。void HaffCode(int &n) /哈夫曼编码HNodeType *HaffNode=new HNodeTypeMaxnode;/存储树HcodeType *HaffCode=new HcodeTy

10、peMaxleaf;/存储编码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; in; i+) /进行编码 并向数组中从右向左写入编码cd.start=n-1;c=i;p=HaffNode

11、c.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.bit

12、j;cout字符信息-编码信息endl;for(i=0; in; i+) coutHaffNodei.inf-;for(j=HaffCodei.start+1; jn; j+)/输出编码coutHaffCodei.bitj;/编码信息01串coutendl; outfile.close ();/关闭文件cout请输入要编码的字符串,基本元素为（;for(i=0; in; i+)coutHaffNodei.inf,;cout)endl;char inf100;/定义输入字符存放数组getchar();gets(inf);/读取屏幕字符int f=strlen(inf);fstream outfi

13、le1;outfile1.open(E:code.dat,ios:out|ios:binary);/建立进行写入的文件if(!outfile1) coutcode.dat文件不能打开!endl;abort(); else coutendl; cout字符串编码后为:n;int num=0;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.

14、bitj);coutHaffCodei.bitj;num+;if(num%50=0) coutendl; coutendl;coutendl;cout编译后的代码串已经存入code.dat文件中!endl;coutendl;outfile1.close();delete HaffNode;delete HaffCode;5、 译码系统为接收需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文件textfile.dat，同时将翻译的结果在屏幕上打印输出。接受0、1代码串有两种形式，一种是直接输入，一种是从文件中读取。void decode( int &n

15、) int i;HNodeType *HaffNode=new HNodeType2*n-1;fstream infile1;infile1.open(E:nodedata.dat,ios:in|ios:binary);/打开文件if(!infile1) coutnodedata.dat文件不能打开endl;abort();for(i=0; i2*n-1; i+)/从文件里读出Huffman树infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close();/关闭int tempcode100;/定义一个数组存放01串int num

16、=0;for(i=0; i100; i+)/数组初始化tempcodei=-1;HcodeType *Code=new HcodeTypen;cout请选择要做的操作：endl;cout4.输入01串解码endl;cout5.从文件中解码q;while(q!=4&q!=5) coutq;switch(q) case 4: cout请输入要解码的0,1串(按2结束输入）：a;if(a!=0&a!=1&a!=2)couta;if(a!=0&a!=1&a!=2)cout输入错误，请重新输入n; else break;if(a=0) tempcodei=0;else if(a=1)tempcodei=

17、1;else if(a=2) tempcodei=2;cout输入的编码为:n;for(i=0;inum;i+)couttempcodei;coutendl;int m=2*n-2;i=0;cout译码后为：endl;fstream outfile;outfile.open(E:textfile.txt,ios:out);/打开存放翻译结果的文件if(!outfile) couttextfile.txt文件不能打开!endl;abort();while(inum) while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1) /判断是不是叶子节点if(tem

18、pcodei=0) / 0为向左走m=HaffNodem.lchild;i+; else if(tempcodei=1) /1为向右走m=HaffNodem.rchild;i+;coutHaffNodem.inf;/输出叶子节点即翻译出的字符outfileHaffNodem.inf;/写入文件m=2*n-2;coutendl;outfile.close();cout译码后的结果已经存入textfile.txt中!endlendl;delete HaffNode;/释放break;case 5: fstream infile2;/读编码infile2.open(E:code.dat,ios:in

19、|ios:binary);while(!infile2.eof() infile2.read(char*)&tempcodenum,sizeof(tempcodenum);num+;infile2.close();num-;cout从文件中读出的编码为endl;for(i=0; inum; i+) couttempcodei;if(i+1)%50=0) coutendl;/每输出50个编码换行coutendl;int m=2*n-2;i=0;coutendl;cout译码后为:endl;fstream outfile;outfile.open(E:textfile.txt,ios:out);i

20、f(!outfile) couttextfile.txt文件不能打开!endl;abort();while(inum)/ 从根节点0向左1向右while(HaffNodem.lchild!=-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译码后的结果已经存入textfil

21、e.txt中!endl;delete HaffNode;/释放break;四、测试数据及程序运行情况用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。字符ABCDEFGHIJKLM频度6413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161图1程序运行界面：图1：程序开始界面 图2：程序初始化输出Huffman树图2图4图3图3：编码信息输出 图4：对字符串编码并输出图5：解码系统 图6：解码系统图5图6对01串译码输出并保存到文件读

22、出01串（文件或键入）输出字符与编码对应关系对已输入的字符编码赋初值for(i=0; i2*n-1; i+)输入字符和权值建树读入一串字符（文件或键入）输出Huffman树对字符串编码输出并保存到文件五、实验过程中出现的问题及解决方法1、用最小堆建立Huffman树出现太多错误且过于繁琐不易更改，故改用结构体数组建树。2、Huffman树输出时，权值大小不同导致显示错乱，故改用输出流控制。3、编码时出现非01字码，原因是定义的存储空间太小。后多次实验确定合适大小。4、编码时读到空格会导致系统停止，后给空格定义了权值。5、文件使用txt格式存放数据读取时出现乱码，故改为dat文件。6、当输出非法

23、字符是会导致系统错乱，后通过修改字符读入方式和循环判定解决问题六、自我评析与总结 通过本次课程设计，我对哈夫曼树及哈夫曼编码有了更深刻的理解。同时对C+的编程以及算法的实现和文件的读写产生了比以往更大的兴趣，还学到了许多在处理程序bug以及程序美化时的技巧和方法。如在处理数据时要分配合理的空间，也要及时释放空间。从刚开始一点头绪都没有，到后来一步步编写成功，查阅了好多资料，也询问了好多同学。根据老师要求，在译码处不单实现了从键盘读入，同时也实现了从文件读入。通过这次实验我积累了更多编程的经验。程序有很多不足的地方，例如程序健壮性不好，二进制读写容易出错等等。从文件中修改二进制编码功能尝试了很久

24、还是没能完成，没有能实现哈夫曼树的图形化输出，这些都是我们的遗憾。但是在程序的编写中，我们也完善了很多问题，添加了一些功能，在一定程度上提高了程序的健壮性。每解决一个问题，我们都会发自内心的感到高兴，这大概就是写程序的乐趣。通过这次课程设计，让我更好的理解了本学期数据结构的课程知识，也大大提高了我们用c+编程的能力，我们更加注重添加注释，增强代码的可读性，这都是我们在本次课程设计中取得的进步。七、参考文献 数据结构（面向对象方法与C+语言描述）殷人昆 清华大学出版社数据结构 严蔚敏，吴伟民 清华大学出版社双语版C+语言程序设计 电子工业出版社百度百科 CSDN社区/源代码#include#in

25、clude#include#include#includeusing namespace std;#define MaxBit 50#define Maxvalue 1000#define Maxleaf 50#define Maxnode Maxleaf*2-1struct HNodeType /字符结构体类型int weight;/权int parent;/双亲位置int lchild;/左孩子int rchild;/右孩子char inf;/字符;struct HcodeType int bitMaxBit;/存储编码int start;/起始位置;void Creat_Haffmant

26、ree(int &n) /建树并输出树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;HaffNodei.lchild=-1;HaffNodei.rchild=-1;HaffNodei.inf=0; for(i=0; in-1; i+) /输入字符及权值cout请输入字符:HaffNodei.inf;cout请输入该字符的权值:HaffNodei.weight;HaffNoden-1.

27、inf= ;/最后一个为空格HaffNoden-1.weight=120;/空格权值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&HaffNodej.weightm2) m2=HaffNodej.weight;x2=j;/合并Huffman树HaffNodex1.parent

28、=n+i;HaffNodex2.parent=n+i;HaffNoden+i.weight=HaffNodex1.weight+HaffNodex2.weight;HaffNoden+i.lchild=x1;HaffNoden+i.rchild=x2;HaffNoden+i.inf= ;/输出树cout显示存储的哈弗曼树信息:endl;cout 权值 左孩子 右孩子 父节点endl;for(i=0; i2*n-1; i+) coutHaffNodei.inf ;coutsetiosflags(ios:right)setw(4)HaffNodei.weight ;coutsetiosflags(

29、ios:right)setw(4)HaffNodei.lchild ;coutsetiosflags(ios:right)setw(4)HaffNodei.rchild ;coutsetiosflags(ios:right)setw(4)HaffNodei.parentendl;/写入文件fstream outfile1;outfile1.open(E:nodedata.dat,ios:out|ios:trunc|ios:binary);/建立进行写入的文件并清空之前数据 if(!outfile1) /没有创建成功则显示相应信息coutnodedata.dat文件不能打开endl;abort(

30、);for(i=0; i2*n-1; i+) /将内存中从HaffNodei地址开始的sizeof(HaffNodei)的内容写入文件中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

31、;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; in; i+) /进行编码 并向数组中从右向左写入编码cd.start=n-1;c=i;p=HaffNodec.parent;while(p!=-1) if(HaffNodep.lchi

32、ld=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.bitj;cout字符信息-编码信息endl;for(i=0; in; i+) co

33、utHaffNodei.inf-;for(j=HaffCodei.start+1; jn; j+)/输出编码coutHaffCodei.bitj;/编码信息01串coutendl; outfile.close ();/关闭文件cout请输入要编码的字符串,基本元素为（;for(i=0; in; i+)coutHaffNodei.inf,;cout)endl;char inf100;/定义输入字符存放数组getchar();gets(inf);/读取屏幕字符int f=strlen(inf);fstream outfile1;outfile1.open(E:code.dat,ios:out|io

34、s:binary);/建立进行写入的文件if(!outfile1) coutcode.dat文件不能打开!endl;abort(); else coutendl; cout字符串编码后为:n;int num=0;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;num+;if(num%50

35、=0) coutendl; coutendl;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) coutnodedata.dat文件不能打开e

36、ndl;abort();for(i=0; i2*n-1; i+)/从文件里读出Huffman树infile1.read(char*)&HaffNodei,sizeof(HNodeType);infile1.close();/关闭int tempcode100;/定义一个数组存放01串int num=0;for(i=0; i100; i+)/数组初始化tempcodei=-1;HcodeType *Code=new HcodeTypen;cout请选择要做的操作：endl;cout4.输入01串解码endl;cout5.从文件中解码q;while(q!=4&q!=5) coutq;switch(

37、q) case 4: cout请输入要解码的0,1串(按2结束输入）：a;if(a!=0&a!=1&a!=2)couta;if(a!=0&a!=1&a!=2)cout输入错误，请重新输入n; else break;if(a=0) tempcodei=0;else if(a=1)tempcodei=1;else if(a=2) tempcodei=2;cout输入的编码为:n;for(i=0;inum;i+)couttempcodei;coutendl;int m=2*n-2;i=0;cout译码后为：endl;fstream outfile;outfile.open(E:textfile.txt,ios:out);/打开存放翻译结果的文件if(!outfile) couttextfile.txt文件不能打开!endl;abort();while(inum) while(HaffNodem.lchild!=-1&HaffNodem.rchild!=-1) /判断是不是叶子节点if(tempcodei=0) / 0为向左走m=Haff