哈夫曼树应用课程设计报告

《哈夫曼树应用课程设计报告》由会员分享，可在线阅读，更多相关《哈夫曼树应用课程设计报告（19页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计报告设计题目：哈夫曼树应用 专 业 ： 软件工程 班 级 ： 软件 学 生 ： 学 号 ： 指导教师 ： 罗作民 / 张翔 起止时间 ：2011-07-042011-07-08 2011 年 春季 学期目 录一具体任务.2 1功能.2 2分步实施.2. 3要求.2二哈夫曼编码21问题描述22.基本要求33实现提示3三设计流程图4 1建立哈夫曼树.4 2编码.5 3译码.6 4主程序.7四设计概要81问题哈夫曼的定义.8.2所实现的功能函数如下.83功能模块.8五源程序9六调试分析15七心得与体会18八参考文献18一、任务题目：哈夫曼树应用1.功能： 1从终端读入字符集大小n，以

2、及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；2利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。3利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。2.分步实施：1） 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2） 完成

3、最低要求：完成功能1；3） 进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。3.要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4） 要提供程序测试方案5） 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。二、哈夫曼编码1. 问题描述利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编

4、/译码系统。2. 基本要求一个完整的系统应具有以下功能：(1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。(2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。3. 实现提示(1) 编码结果以文本方式存储在文件Codefile中。(2) 用户界面

5、可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。(3) 在程序的一次执行过程中，第一次执行I， D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。三、设计流程图建立哈夫曼树：开始n,=1Renturn 0m=2*n-1i=1;i=n;+iWhile(getchar()=”/n”输入字符与权值HTi.ch=zHTi.weight=wHTi.parent=0HTi.lchild=0HTi.rchild=0编码：开始cds

6、tart=”1”i=1;i=n;+istart=n-1cdstart=”0”c=I;f=HTi.parent; f!=0;f=HTf.parentHTf.child=l结束译码：开始L=k!output_file!cout”cant open file”Return 1Cout”cant open file”Strcmp(Hi.hlchild=0结束i=1;in;i+while(hk!=”0”)j=0;jstrlen(hi);j+;l+K=0hj=”0”输出译码主程序：开始main建立哈夫曼树choice=”I”|choice=”I”结束编码return 0choice=”E”|choice=

7、”e”choice=”D”|choice=”d”choice=”Q”|choice=”q”编码四、概要设计1）问题哈夫曼的定义：1.哈夫曼树节点的数据类型定义为：typedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;2）所实现的功能函数如下1、void hfmcoding(hfmtree &HT,hfmcode &HC,int n)初始化哈夫曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树。此函数块调用了Select（）函

8、数。2、void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函数，选出HT树到a为止，权值最小且parent为0的2个节点3、 int main()主函数： 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.txt中读入）对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。4、Encoding 编码功能：对输入字符进行编码5、Decoding译码功能： 利用已建

9、好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat 中。Print() 打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。6.主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。3）功能模块：哈夫曼编码/译码器初始化哈夫曼树编码译码打印哈夫曼树打印编码五、源程序#include#include#include#include#includetypedef struct /哈夫曼树的结构体char ch;int weight;

10、 /权值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函数，选出HT树到a为止，权值最小且parent为0的2个节点int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /选出最小的节点for(j=1;j=a;+j)if(HTj.parent

11、=0&x!=j)y=j;break;for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /构建哈夫曼树HT，并求出n个字符的哈夫曼编码HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i) /初始化n个叶子结点printf(请输入第%d字符信息和权值：,i

12、);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的结点HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;+i) /建立哈夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.

13、weight=HTp1.weight+HTp2.weight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /给n个字符编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);

14、int main()char code100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件输入输出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;coutn;cout 软件092班 姓名:张耀飞 学号：3090921040n ;while(choice!=Q&choice!=q) /当choice的值不为q且不为Q时循环cout *哈夫曼编码/译码器*n; cout I.Init E.Encoding D.Decoding Q.Exitn; coutchoice;

15、 if(choice=I|choice=i) /初始化赫夫曼树coutn;hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant open file!endl;return 1;for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();cout哈夫曼树已经创建完毕，并且已经放入hfmTree.txt文件中!endl; else if(choice=E|choice=e) /进行编

16、码，并将字符放入ToBeTran.txt，码值放入CodeFile.txt中printf(请输入字符：);gets(str);output_file.open(ToBeTree.txt);if(!output_file)coutcant open file!endl;return 1;output_filestrendl;output_file.close();output_file.open(CodeFile.txt);if(!output_file)coutcant open file!endl;return 1;for(i=0;istrlen(str);i+)for(j=0;j=n;+j

17、)if(HTj.ch=stri)output_fileHCj;break;output_file.close();coutn;cout编码完毕，并且已经存入CodeFile.txt文件！n;input_file.open(CodeFile.txt); /从CodeFile.txt中读入编码，输出在终端if(!input_file)coutcant open file!code;cout编码码值为：codeendl;input_file.close(); else if(choice=D|choice=d) /读入CodeFile.txt中的编码进行译码，将译出来的字符放入Textfile.tx

18、t中input_file.open(CodeFile.txt);if(!input_file)coutcant open file!h;input_file.close();output_file.open(Textfile.txt);if(!output_file)coutcant open file!endl;return 1;k=0;while(hk!=0) /先用编码中的前几个和字符的编码相比较，然后往后移for(i=1;i=n;i+)l=k;for(j=0;jstrlen(HCi);j+,l+)hlj=hl;hlj=0;if(strcmp(HCi,hl)=0)output_fileH

19、Ti.ch;k=k+strlen(HCi);break;output_file.close();input_file.open(Textfile.txt);if(!input_file)coutcant open file!h; couthendl;input_file.close();cout译码结束，字符已经存入Textfile.txt文件中！endl; else if(choice=Q|choice=q) /退出程序 exit(0); else /如果选了选项之外的就让用户重新选择cout您没有输入正确的步骤，请重新输入！endl;coutendl;return 0;六、调试分析编码译码

20、退出七、实验心得与体会 在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是若没有定义所引用的相关头文件，必定调试不通过；在执行译码操作时，不知什么原因，总是不能把要编译的二进制数与编译成的字符用连接号连接起来，而是按顺序直接放在一起，视觉效果不是很好。还有就是，很遗憾的是，我们的哈夫曼编码/译码器没有像老师要求的那样完成编一个文件的功能，这是我们设计的失败之处。 通过本次数据结构的课程设计，我学习了很多在上

21、课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。这次课程设计，我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存数据，对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏，我的程序有了更高的质量。八参考文献： 1 谭浩强. C 程序设计(第二版) M . 北京:清华大学出版社,1999. 161 - 163.2 谭浩强,张基温,唐永炎. C 语言程序设计教程(第二版) M . 北京:高等教育出版社,1998. 113 - 115.3 严蔚敏,吴伟民. 数据结构(C 语言版) M . 北京:清华大学出版社,2002. 55 - 58.4 李士峰,张谢华,孙清滇. ActiveX文档技术在VB 程序设计网络课件制作中的应用 5 王颖,王正洲. 汉诺塔问题迭代算法实现和分析J . 合肥联合大学学报,1999 , 考核成绩评定：签字：年 月 日 19