计算机学院信管专业
数据结构课程设计
题 目：    哈夫曼树的应用               
班 级：                         
姓 名：    学 号：                 
同组人姓名：                 
起迄日期：                          二叉树的遍历及应用实验报告
课程设计地点:            　         
指导教师：                     
评阅意见：
成绩评定：
评阅人：          日期：
完成日期：2012年12月
一、需求分析…………………………………………3
二、概要设计…………………………………………4
三、详细设计…………………………………………6
四、调试分析和测试结果……………………………7
五、心得体会和总结……………………………… 10
六、参考文献……………………………………… 10
七、附录…………………………………………… 11
一、需求分析
（一）实验要求
要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。
要求实现的基本功能很简单，只有删除和插入，增加功能也不过是加上修改。这些在数据结构课上已经讲过，只要能够理解关于线性表的几个相关的基本算法就可以了。
问题是将输入的信息保存入文件和从文件输出。这里基本是自学的内容，而且要考虑到是否要自行选择保存的磁盘。
综上，做这个课题，要具备的知识就是线性表的基本算法，文件的保存和读取算法，必要的C或者C++知识（本次我将使用C++实现），以及丰富的程序调适经验。
（二）实验任务
一个完整的系统应具有以下功能：
功能1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；
功能2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
功能3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。
（三）实验步骤
分步实施：
1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2）完成最低要求：完成功能1；
3）进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。
要  求 ：
1）界面友好，函数功能要划分好
2）总体设计应画一流程图
3）程序要加必要的注释
4) 要提供程序测试方案
5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
二、概要设计
（一） 设计思想
哈夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。
（二 ） 函数间的关系如图所示：
（三）数据结构与算法设计
哈夫曼编\译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。
最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。
其主要流程图如下图所示。
哈夫曼树编\译码器流程图
三、详细设计
功能函数模块划分
void main()
void printhead()
void printree(HuffmanTree HT,int w) //打印赫夫曼树
void coprint(HuffmanTree start,HuffmanTree HT)//打印代码文件
void printcode()        //打印代码
void decode()      //完成译码功能
void encode()          //完成编码功能
void inputcode()   
void init()
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
void select(HuffmanTree t,int i,int &s1,int &s2)
int min(HuffmanTree t,int i)//两个最小的权值
（1）哈夫曼编码：首先定义函数，出全部权值中最小的两个，然后定义一个变量，使他始终成为最小的那个。再将两个函数最为叶子结点，并得到一个父亲节点，此父亲节点的权值为其叶子节点的权值之和。并将此父亲节点的权值与其余权值进行比较，重新选出两个最小的权值，再进行上述步骤，直到所有权值形成了一颗二叉树，而此二叉树就是我们所说的最优二叉树，即哈夫曼树。
以上为哈夫曼树的建立过程，下面为哈夫曼编码的过程，从叶子节点出发，若此叶子节点为其父亲节点的左孩子，则将其编码为0，若为右孩子，则将其编码为1，然后为其父亲节点编码，若为祖先的左孩子，则变为0，为右孩子则为1，依次向上一层进行遍历，直到遍历到根节点，停止编码。
（2）译码：对于已经建好的哈夫曼树，要对其进行译码，首先从根出发如果编码为0，则往左孩子遍历，如果编码为1，则往右孩子遍历，直到遍历到叶子节点，便求得该子串相应的字符。
（3）初始化哈夫曼链表:首先输入结点个数，再将字符及权值输入，调用编码函数，得到每个字符编码并将其输出。最后将哈夫曼编码写入文件。
（4）完成编码功能：打开目录下文件，读取里面的字符，对其进行编码后，将编码写入目录下的中。
（5）完成译码功能：打开根目录下文件，读取里面的编码，对其中的编码进行译码，并将得到的内容写入根目录下的文件中。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。