课程论文
题目：哈夫曼树及其应用课程设计报告学号： 201230210115
姓名：黄文宣
班级： 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<j=m;
}
i++;
}
}
六、实现部分
#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{ T[i].weight=0;
T[i].parent=-1;
T[i].lchild=-1;
T[i].rchild=-1;
}
}
void inputhf(huffmantree T) //－输入哈夫曼树的树据{ int i;float k;
for(i=0;i{ scanf("%f",&k);
T[i].weight=k;
}
}
void selectmin(huffmantree T,int k,int *p1,int *p2)
{ int i;float small1=10000,small2=10000;
for(i=0;i<=k;i++)
{ if(T[i].parent==-1)
if(T[i].weight{ small2=small1;
small1=T[i].weight;
*p2=*p1;
*p1=i;
}
