哈夫曼树 课程设计报告

数据结构课程设计报告

题目：哈夫曼树及其应用

学生姓名： 刘昶志 学 号： 1021111609 班 级： 10211116 指导教师： 张军

2012年 6 月 3 日

东华理工大学 软件学院 软件工程系

1

目录

1、 需求分析说明~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 3 2、 总体设计~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~4 3、 详细设计~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~5 4、 实现部分~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~7 5、 程序测试~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~9 6、 总结~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~10

东华理工大学 软件学院 软件工程系

2

一．需求分析说明

设计目的：

熟悉树的各种存储结构及其特点。

掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。 设计内容

数据的读入﹑存储，生成文件，将键盘输入的信息存入指定的文件中；设计一程序求解此问题．哈夫曼（Huffman）编码原理是一种利用二叉树实现的编码原理

哈夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。

哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。

锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。

在信息传递时，希望长度能尽可能短，即采用最短码。哈夫曼编码的应用，就是采用这种有效的数据压缩技术可以节省数据文件的存储空间和计算机网络的传送时间。

东华理工大学 软件学院 软件工程系

3

二．总体设计 哈夫曼树编/译码系统 初始化 重新建立哈夫曼树 退出 编码 打印编码 译码 （1）.初始化：提示初始化界面→提示各字符及其权值将存放在hfmTree中→以字母出现次数为权值建立哈弗曼树→弹出选择菜单进行进一步操作；

（2）.编码：弹出编码界面→读取文件→提示输入要编码的字符串→对文本进行哈弗曼编码并输出编码→保存编码文件；

（3）.译码：弹出译码界面→利用建立好的哈弗曼树进行译码→将译码输出→保存译码文件；

东华理工大学 软件学院 软件工程系

4

三．详细设计

1.数据结构设计

#include //包含的库函数 #include #include

const int n=6; //叶子数目

const int m=2*n-1; //森林中树的棵树 const int c=4; class tree {

public: char data;

int weight; //权值 int parent; //双亲

int lch,rch; //左右孩子

void creathafumantree(); //建立哈夫曼树 void editcode();//编码函数

void trancode(char b[],int max);//译码函数 };

2．算法设计

哈夫曼树编码算法：

输入字符，权值算法：输入一些字符,然后再输入相对应数量的权值,建哈夫曼树,然后进行编码,并得到相对应的哈夫曼编码。

void tree::editcode(){ //编码 int i,j,k,f,count=0; int code[n+1][c+1]; for(i=1;i<=n;i++) for(j=1;j<=c;j++) code[i][j]=2;

for(i=1;i<=n;i++) { k=1;

j=hftree[i].parent; f=i;

while(j!=0) {

if(hftree[j].lch==f) {code[i][k++]=0;} else

{code[i][k++]=1;} j=hftree[j].parent;

东华理工大学 软件学院 软件工程系

5

本文来源：https://www.bwwdw.com/article/f72f.html