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

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;六、调试分析编码译码退出七、实验心得与体会 在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是若没有定义所引用的相关头文件，必定调试不通过；在执行译码操作时，不知什么