数据结构课程设计实验报告哈夫曼树的应用

计算机学院信管专业

数据结构课程设计

题 目： 哈夫曼树的应用 班 级：

姓 名： 学 号： 同组人姓名：

起迄日期： 课程设计地点: 指导教师：

评阅意见： 成绩评定： 评阅人： 日期： 完成日期：2012年12月

目 录

一、 需求分析…………………………………………3 二、 概要设计…………………………………………4 三、 详细设计…………………………………………6 四、 调试分析和测试结果……………………………7 五、 心得体会和总结……………………………… 10 六、 参考文献……………………………………… 10 七、 附录…………………………………………… 11

2

一、 需求分析

（一）实验要求

要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。

要求实现的基本功能很简单，只有删除和插入，增加功能也不过是加上修改。这些在数据结构课上已经讲过，只要能够理解关于线性表的几个相关的基本算法就可以了。

问题是将输入的信息保存入文件和从文件输出。这里基本是自学的内容，而且要考虑到是否要自行选择保存的磁盘。

综上，做这个课题，要具备的知识就是线性表的基本算法，文件的保存和读取算法，必要的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）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。

3

二、概要设计

（一） 设计思想

哈夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。 （二 ） 函数间的关系如图所示：

主函数 显示初始输入编码 译码 打印打印表头 化树 字符 编码 哈夫曼树

（三）数据结构与算法设计

哈夫曼编\\译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。 最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。 其主要流程图如下图所示。

选最小两个权值

4

开始 将data和权值赋给ht 否 结点数是否大于1 是 输出根结点和权值 否 I<2*N? 是 I++ 调用SELECT函数 计算根结点函数 父结点为两子结点之和 输出两子结点和已构造的结点 否 是否为根结点？ 是 左子是否为空？ 是 否 此时编码为0 否 编码为1 右子是否为空 是 结束

哈夫曼树编\\译码器流程图

5