哈夫曼树课程设计报告
- 格式：doc
- 大小：418.00 KB
- 文档页数：19
数据结构
课程设计报告
设计题目：哈夫曼树应用
专 业
：
软件工程
班 级 ： 软件
学
生 ：
学 号 ：
指导教师 ： 罗作民 / 张翔
起止时间 ：2011-07-04—2011-07-08
2011 年 春季 学期
下载可编辑
.专业.整理. 目 录
一．具体任务 .....................................................…..2
1功能……………………………………………………………………………...2
2分步实施………………………………………………………………………...2.
3要求……………………………………………………………………………...2
二．哈夫曼编码 ...................................................... 2
1问题描述 ...................................................... 2
2.基本要求 ..................................................... 3
3实现提示 ...................................................... 3
三．设计流程图 ...................................................... 4
1建立哈夫曼树…………………………………………………………………...4
2编码……………………………………………………………………………...5
3译码……………………………………………………………………………...6
4主程序…………………………………………………………………………...7
四．设计概要 ........................................................ 8
1问题哈夫曼的定义..............................................................................................8..
2所实现的功能函数如下………………………………………………………..8
3功能模块………………………………………………………………………..8
五．源程序 .......................................................... 9
六．调试分析 ....................................................... 15
七．心得与体会 ..................................................... 18
八．参考文献 ....................................................... 18
下载可编辑
.专业.整理.
一、任务
题目：哈夫曼树应用
1.功能：
1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；
2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行
编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。
2.分步实施：
1） 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2） 完成最低要求：完成功能1；
3） 进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。
3.要求：
1）界面友好，函数功能要划分好
2）总体设计应画一流程图
3）程序要加必要的注释
4） 要提供程序测试方案
5） 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
二、哈夫曼编码
1. 问题描述
利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。
2. 基本要求
一个完整的系统应具有以下功能：
(1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。
(2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 下载可编辑
.专业.整理. (3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。
3. 实现提示
(1) 编码结果以文本方式存储在文件Codefile中。
(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。
(3) 在程序的一次执行过程中，第一次执行I， D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
三、设计流程图
建立哈夫曼树：
开始
n,<=1
Renturn 0 m=2*n-1
i=1;i<=n;++i
While(getchar()=”/n” 输入字符与权值
HT[i].ch=z HT[i].weight=w HT[i].parent=0 HT[i].lchild=0 HT[i].rchild=0 下载可编辑
.专业.整理.
编码：
译码： 开始
cd[start]=”1”
i=1;i<=n;++i
start=n-1
cd[start]=”0” c=I;f=HT[i].parent;
f!=0;f=HT[f].parent
HT[f].child==l
结束 下载可编辑
.专业.整理. 开始
L=k
!output_file
!cout”cant open file”
Return 1 Cout”can’t open file”
Strcmp(H[i].hlchild==0
结束 i=1;i
while(h[k]!=”0”)
j=0;j
h[j]=”\0”
输出译码 下载可编辑
.专业.整理.
主程序：
开始
main
建立哈夫曼树 choice==”I”||choice==”I”
结束 编码
return 0 choice==”E”||choice==”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（）函数。
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
译码功能： 利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.dat 中。
Print() 打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。
6.主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。
使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。
3）功能模块：
