哈夫曼树课程设计论文

课 程 论 文

题目： 哈夫曼树及其应用课程设计报告

学 号： [1**********]5 姓 名： 黄文宣 班 级： 1232101 专 业： 信息安全 课程名称： 数据结构 课程老师： 王晓燕

二零一肆年一月

目录

1、课程设计的题目及简介………………………………………………3

2、实验目的………………………………………………………………3

3、设计说明………………………………………………………………4

4、总体流图………………………………………………………………4

5、详细设计………………………………………………………………5

6、实现部分………………………………………………………………6

7、测试程序………………………………………………………………9

8、心得与体会……………………………………………………………10

一、课程设计题目

哈夫曼树及其应用

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

建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。

哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。 锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。

二、实验目的

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

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

三、设计说明

建立哈夫曼树，将哈夫曼树的结构定义为一个结构型的一维数

组，每个元素含有四项：权值，双亲，左孩子，右孩子。哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。给定的权值从键盘输入，输出所建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。

四、总体流图

五、详细设计

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);//译码函数

哈夫曼树译码算法：

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

void tree::trancode(char b[],int max){ //译码

int i=0; int j=m; cout

该段代码编译为 :"

while(b[i]!='\0'){ if(b[i]=='0') j=hftree[j].lch; else

j=hftree[j].rch;

if(hftree[j].lch==0 && hftree[j].rch==0) {

cout

六、实现部分

#include #include #include #define n 6

#define m 2*n-1 typedef struct { float weight;

int lchild,rchild,parent; }codenode;

typedef codenode huffmantree[m]; typedef struct { char ch;

char bits[n+1]; }code;

typedef code huffmancode[n];

void inithf(huffmantree T) //－哈夫曼树的初始化{ int i;

for(i=0;i

void inputhf(huffmantree T) //－输入哈夫曼树的树据 { int i;float k; for(i=0;i

void selectmin(huffmantree T,int k,int *p1,int *p2) { int i;float small1=10000,small2=10000; for(i=0;i

small1=T[i].weight; *p2=*p1; *p1=i; }

else

if(T[i].weight

void creathftree(huffmantree T) //－建哈夫曼树 { int i,p1,p2; inithf(T); inputhf(T);

for(i=n;i

{ selectmin(T,i-1,&p1,&p2); T[p1].parent=T[p2].parent=i; T[i].lchild=p1; T[i].rchild=p2;

T[i].weight=T[p1].weight+T[p2].weight; } }

void creathfcode(huffmantree T, huffmancode H) //－哈夫曼编码表{ int i,c,p,start;char cd[n+1]; cd[n]='\0';

for(i=0;i

{ H[i].ch=getchar(); start=n; c=i;

while((p=T[c].parent)>=0) {

cd[--start]=(T[p].lchild==c)?'0':'1'; c=p; }

strcpy(H[i].bits,&cd[start]); } }

void zip(huffmancode H,char *ch,char *s) //－编码 { int j=0;char *p[n]; unsigned int i; for(i=0;i

{ while(ch[i]!=H[j].ch) j++; p[i]=H[j].bits; }

strcpy(s,p[0]); for(i=1;i

}

void uzip(huffmancode H,char *s,huffmantree T) //－解码 { int j=0,p;

unsigned int i; char ch[n+1]; while(i

while(T[p].lchild!=-1) { if(s[ i]=='0') { p=T[p].lchild;i++;} else

{ p=T[p].rchild;i++;} }

ch[j]=H[p].ch; j++; }

ch[j]='\0'; puts(ch); }

main()

{ char ch[]="abcdef", s[36]; huffmantree T; huffmancode H; creathftree(T); creathfcode(T,H); zip(H,ch,s); uzip(H,s,T); }

七、测试程序

七、心得体会

这次实验，感觉到相对难度较大，用了比较长的时间来做，从这也反映了对 树的知识不够熟练。但在这次实验的练习中，不仅对树的知识进行了综合运用，还有了较深一步的了解，掌握了运用树的基本知识。总之，对树和二叉树这方面的知识了解和运用都还有待加强。

在实验中也出现了很多的问题，最大的问题就是对程序设计框架结构的不了解，在实现代码与功能的连接时经常会出现各种不同的错误，在实现一些功能时系统常常会报错。许多错误不知从哪修改，让程序运行不出来。

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

己对数据结构的了解更深入。

通过老师和同学的细心的帮助，终于做出了这个系统，感觉很棒！