《哈夫曼树应用课程设计报告》由会员分享，可在线阅读，更多相关《哈夫曼树应用课程设计报告（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);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) /初始化其余的结点
