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

计算机学院信管专业

数据结构课程设计

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

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

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

评阅意见： 成绩评定： 评阅人： 日期： 完成日期：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

三、详细设计

功能函数模块划分 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）完成编码功能：打开目录下文件tobetran.txt，读取里面的字符，对其进行编码后，将编码写入目录下的codefile.txt中。

（5）完成译码功能：打开根目录下codefile.txt文件，读取里面的编码，对其中的编码进行译码，并将得到的内容写入根目录下的文件txtfile.txt中。 （6）打印编码 （7）打印哈夫曼树

6

四、调试分析和测试结果

（一）初始化哈夫曼链表

7

（二）编码字符

（三）编码

8

（四）译码

（五）打印编码

（六）打印哈夫曼函数

9

五、心得体会与总结

对于本次课程设计，主要是需要掌握哈夫曼树建立、哈夫曼编码以及哈夫曼译码的算法。并能将其熟练应用于编译码器的完成。经过这次的课程设计，使我们更加了解了数据结构，也更深入地了解了哈夫曼编码与译码算法，课程设计的题目比我们平常的实验内容要难，完成它不仅需要有厚实的语言基础，而且还要熟练掌握哈夫曼编码与译码的算法，另外对于文件的基本操作也需要熟悉。

通过数据结构课程设计，我的C++语言水平有了比较大的提高其中。C++语言关于类的操作理解的比以前深刻不少。另外是数据结构方面的提高对哈夫曼树的构造及哈夫曼码方面也有不少的提高。 在项目中也出现了很多的问题,最大的问题就是对程序设计框架结构的不了解,在实现代码与功能的连接时经常会出现各种不同的错误,

以致拖了整个设计的后腿。课程设计中，既回顾了很多以前的东西，也发现了很多的问题以前都没遇见过的，收获很大。 通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识。 此次哈夫曼树的应用系统的设计让自己对数据结构的了解更深入。

六、参考文献

《C++面向对象程序设计教程》（第三版） 陈维兴 林小茶编著 清华大学出版社 《数据结构》（C语言版）严蔚民 吴伟民编著 清华大学出版社

10

void decode() //完成译码功能 {

cout<<\下面对根目录下文件codefile.txt中的字符进行译码\ FILE *codef,*txtfile;

if((txtfile=fopen(\ { cout<<\不能打开文件\ }

if ((codef=fopen(\ { cout<<\不能打开文件\ }

char *tbdc,*outext,i2; int io=0,i,m;

unsigned long length=10000;

tbdc=(char*)malloc(length*sizeof(char)); //分配空间 fgets(tbdc,length,codef);

outext=(char*)malloc(length*sizeof(char)); //分配空间 m=2*n-1;

for(i=0;*(tbdc+i)!='\\0';i++) //进入循环 { i2=*(tbdc+i); if(HT[m].lchild==0) { *(outext+io)=*(z+m-1); io++; m=2*n-1; i--; } else if(i2=='0') m=HT[m].lchild; else if(i2=='1') m=HT[m].rchild; }

*(outext+io)='\\0'; fputs(outext,txtfile);

cout<<\译码完成\内容写入根目录下的文件txtfile.txt中\ free(tbdc); free(outext); fclose(txtfile); fclose(codef); }

//--------------------------------------------- void printcode() //打印代码 {

16

cout<<\下面打印根目录下文件CodePrin.txt中编码字符\ FILE * CodePrin,* codefile;

if((CodePrin=fopen(\ { cout<<\不能打开文件\ return; }

if((codefile=fopen(\ { cout<<\不能打开文件\ return; }

char *work3;

work3=(char*)malloc(51*sizeof(char)); do { if(fgets(work3,51,codefile)==NULL) { cout<<\不能读取文件\ break; } fputs(work3,CodePrin); puts(work3);

}while(strlen(work3)==50); free(work3);

cout<<\打印工作结束\ fclose(CodePrin); fclose(codefile); }

void coprint(HuffmanTree start,HuffmanTree HT)//打印代码文件 {char t=' '; if(start!=HT) {

FILE * TreePrint;

if((TreePrint=fopen(\ { cout<<\创建文件失败\ return; }

numb++;//该变量为已被声明为全局变量 coprint(HT+start->rchild,HT);

if(start->lchild!=NULL&&start->rchild!=NULL) t='<'; cout<weight<

17

fprintf(TreePrint,\ coprint(HT+start->lchild,HT); numb--;

fclose(TreePrint); } }

void printree(HuffmanTree HT,int w) //打印赫夫曼树 {

HuffmanTree p; p=HT+w;

cout<<\下面打印赫夫曼树\输出\打印赫夫曼树\语句 coprint(p,HT);

cout<<\打印工作结束\输出\打印工作结束\}

void printhead() {

cout<<\数据结构\\t课程设计\\t信管11101班 201117020126\\n\ cout<<\

cout<<\ i.初始化赫夫曼链表 w.编码字符 cout<<\ e.编 码 d.译 码 cout<<\ p.打印编码 t.打印赫夫曼树 cout<<\ q.退 出 \\n\\t\\t\ if(flag==0)cout<<\请先初始化赫夫曼链表,输入'i'\\n\ cout<<\请选择你要进行的操作:\}

/*2．主程序*/ void main() {

char choice;

while(choice!='q') { printhead(); cin>>choice; switch(choice) {

case 'i': //按下i则进行初始化赫夫曼链表,调用init函数 init(); break;

case 'w': //按下w编码字符，调用inputcode函数 inputcode(); break;

case 'e': //按下e编码，调用encode函数 encode(); break;

18

伍瑶\\n\\t\\t\\\n\\t\\t\ \\n\\t\\t\ case 'd': //按下d译码，调用decode函数 decode(); break;

case 'p': //按下p打印编码，调用printcode函数 printcode(); break;

case 't': //按下t打印赫夫曼树，调用printree函数 printree(HT,2*n-1); break;

case 'q': //按下q退出 break; default: cout<<\输入错误，请重新选择\ } }

free(z); //释放z结点 free(w); //释放w结点 free(HT); //释放HT结点 }

19

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