实验三哈夫曼树实验报告

数据结构实验报告

实验名称：实验三 树 学生姓名： 班级： 班内序号： 学号：

日期：2012年12月7号 1、 实验要求

利用二叉树结构实现赫夫曼编/解码器。 基本要求：

1、 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频

度，并建立赫夫曼树

2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符

的编码输出。

3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串

输出。

4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输

出译码结果。

5、 打印(Print)：以直观的方式打印赫夫曼树（选作）

6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压

缩效果。

测试数据：

I love data Structure, I love Computer。I will try my best to study data Structure.

提示：

1、用户界面可以设计为“菜单”方式：能够进行交互。

2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的

,.

字符一律不用编码。

2、 程序分析

2.1存储结构

（1）二叉树 template class BiTree { public: BiTree();

//构造函数，其前序序列由键盘输入 //析构函数

~BiTree(void);

BiNode* Getroot(); //获得指向根结点的指针 protected:

BiNode *root;

};

//指向根结点的头指针

//声明类BiTree及定义结构BiNode Data：

二叉树是由一个根结点和两棵互不相交的左右子树构成。 二叉树中的结点具有相同数据类型及层次关系。

示意图： root

lchild parent rchild ,.

（2）静态三叉链表

struct HNode //哈夫曼树的静态三叉链表 {

unsigned int weight; //结点权值 unsigned int parent; //双亲指针 unsigned int Lchild; //左孩子指针 unsigned int Rchild; //右孩子指针 };

示意图： data

(3) 编码表的节点结构

Lchild Rchild parent struct HCode //字符及其编码结构 {

char data;

,.

char code[100]; };

示意图： char data

char code[100] 2.2关键算法分析

一：关键算法

(一)初始化函数 void Huffman::Init(int a[],int n) （1）算法自然语言

1. 创建一个长度为2*n -1的三叉链表

2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将

对应结点的孩子域和双亲域赋为空 3. 从三叉链表的第n个结点开始，i=n

3.1 从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。 3.2 将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点

3.3 将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩

子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空

4. 根据哈夫曼树创建编码表

（2）源代码

void Huffman::Init(int a[],int n) //创建哈夫曼树

,.

{ //二叉树只有度为和度为的结点时，总结点数为（n-1）个

HTree=new HNode[2*n-1]; //根据权重数组a[1—>n]初始化哈夫曼树 int i,x,y;

for(i=0;iHTree[i].weight=a[i]; HTree[i].Lchild=-1; HTree[i].Rchild=-1; HTree[i].parent=-1; }

for(int i=n;i<2*n-1;i++) //开始建哈夫曼树，从底层向顶层搭建 {

SelectMin(HTree,i,x,y); //从--(i-1)中选出两个权值最小的结点

HTree[x].parent=i;

HTree[y].parent=i; //左右孩子权值相加为父结点的权值

HTree[i].weight=HTree[x].weight+HTree[y].weight; HTree[i].Lchild=x;

,.

HTree[i].Rchild=y; HTree[i].parent=-1; } }

(3)时间复杂度

在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数的时间复杂度为O（n^2）

（二）统计字符出现频度的代码

（1）算法自然语言

①用cin.getline（）函数获取一段字符串。同时设置一个权值数组weight，以及暂时统计和存放权值的数组s。

②用 strlen（）函数获取未编码时的字符串长度。

③从字符串的起始位置进行权值统计，即获得str[i]每个字符的ASⅡ编码，并在s[(int)str[i]]

数组中进行+1统计，为字符出现一次。

④ i进行自加，统计下面字符出现的频度，在相应的数组元素中进行+1统计。 ⑤继续循环，直到字符串结束。

（2）源代码（在main（）函数中实现）

int i,j=0,v; int s[200]={0};

int weight[M]; //权值数组

,.

cout<<\"请输入一段字符串，按回车键结束：\"<Len1=strlen(str); //得到未编码时的字符串长度 for(i=0;str[i]!='\\0';i++) //统计每个字符的权值

s[(int)str[i]]++; //(int)str[i]为每个字符的ASⅡ编码 for(i=0;i<200;i++)

if(s[i]!=0) //如果权值不为 {

c[j]=i; //ASⅡ编码为i的字符写入字符数组c weight[j]=s[i]; //权值s数组赋给权值weight数组 j++; }

n=j; //叶子结点个数 for(v=0;v(3) 时间复杂度：

若输入的字符串长度为n，则时间复杂度为O(n)

（三）选择两个最小权值的函数

,.

（1）算法自然语言

①先暂时将前两个叶子结点作为权值最小的两个结点i1，i2

②从第三个叶子结点开始，每一个结点的权值与i1，i2进行比较，如果此结点权值比i1权值要小，则将i1结点赋给i2，此结点赋给i1。 ③如果此结点权值比i2要小，此结点赋给i2。

④每进行一次循环，总结点个数－1.（两个结点进行权值合并） ⑤继续执行循环，直到循环到根结点，循环结束。

（2）源代码

void Huffman::SelectMin(HNode*hTree,int n,int &i1,int &i2) {

int i,j; //找一个比较的起始值 for(i=0;iif(hTree[i].parent==-1) {

i1=i; break;

} } i++;

,.

for(;i{ //先让前两个叶子结点分别为i1，i2

if(hTree[i].parent==-1) {

i2=i; break;

} }

if(hTree[i1].weight>hTree[i2].weight) //i1指向最小的 { } i++;

for(;iif(hTree[i].parent==-1&&hTree[i].weight{ //如果之后的叶子结点权值小于前两个，那么进行交换

j=i2; i2=i1; i1=j;

,.

i2=i1; //把i1赋给i2 i1=i;

}

else if(hTree[i].parent==-1&&hTree[i].weighti2=i; //始终保证i2权值大于i1

} } }

（3）时间复杂度

若输入的字符串长度为n，则时间复杂度为O(n)

（四）创建编码表 （1）算法自然语言

1.生成一个编码表

2.从终端结点开始，如果此结点是其父结点的左孩子，则标“0”；如果是其父结点的右孩子，则标“1”。

3.将父结点赋给孩子结点，并将新的孩子结点的父结点作为当前父结点，重复2操作。 4.继续循环，直到根结点，即不满足循环条件时，将编码表的最后一位置0.

5.将编码字符逆置。将编码串的最后一位置换成新编码串的第一位，倒数第二位置换成新编码串的第二位，直到置换完毕。 6.将新的编码串重新赋给编码表。 7.输出字符的哈夫曼编码。

8.循环将字符编码后的长度赋给Len3数组。

,.

（2）源代码

void Huffman::CreateTable(char data[],int n) {

HCodeTable=new HCode[n]; //生成编码表 for(int i=0;iHCodeTable[i].data=data[i]; int child=i;

int parent=HTree[i].parent;

int k=0; 编码串的长度

while(parent!=-1) {

if(child==HTree[parent].Lchild)

HCodeTable[i].code[k]='0'; else

HCodeTable[i].code[k]='1'; k++; child=parent; parent=HTree[child].parent;

//从终端结点开始编码，代表每个//左孩子标“0” //右孩子标“1”

//向上追溯 ,.

}

HCodeTable[i].code[k]='\\0'; //当编码到根结点时循环结束，编码串最后一位置表结束

{ //将编码字符逆置

char code[M]; int u;

for(u=0;ucode[u]=HCodeTable[i].code[k-u-1];//上述编码串的最后一位变成新

的编码表中编码串的第一位 for(u=0;uHCodeTable[i].code[u]=code[u]; //将新的编码串重新赋给编码表

cout<Len3[i]=k; //每个字符编码后的长度 } } }

（3）时间复杂度

若输入的字符串长度为n，则时间复杂度为O(n)。

,.

（五）编码算法 （1）算法自然语言

1.从字符串的起始位置开始，将每个字符与编码表中的字符进行比对。 2.当两字符相等时，输出编码表中字符对应的编码。

3.将此字符编码的长度加到Len2中，循环结束后，Len2的数值为字符串编码后的总长度。

（2）源代码

void Huffman::Encoding(int n) //编码 {

cout<for(int j=0;jif(str[i]==HCodeTable[j].data) //如果字符串中的字符与编码表中的字符相等 {

cout<cout<,.

}

（3）时间复杂度

设待编码字符串长度为n，编码表中字符个数为m，则复杂度为O（n*m）。

（六）解码算法 （1）算法自然语言

1.从根节点开始，如果编码串为0，则下溯到此结点的左孩子结点；如果编码串为1，则下溯到此结点的右孩子结点。

2.执行循环，直到不满足while循环条件，即追溯到叶子结点。输出叶子结点的字符。

（2）源代码

void Huffman::Decoding(char* p) //p为编码串 {

cout<<\"解码后的字符串为: \"<int parent=2*n-1-1; //根结点在哈夫曼树中的下标 while(HTree[parent].Lchild!=-1) //如果不是叶子结点就执行循环 {

if(*p=='0')

parent=HTree[parent].Lchild;

,.

else if(*p=='1')

parent=HTree[parent].Rchild;

p++; }

cout<cout<（3）时间复杂度

若输入的字符串长度为n，则时间复杂度为O(n)。

（七）计算压缩比函数 （1）算法自然语言

1. 获得编码前字符串的长度，即其占用的字节数（float类型）。

2. 获得编码后的字符串的长度，将其除以8，得到其占用的字节数（float类

型）。

3. 压缩比将两个相除。

（2）源代码

void Huffman::Calculate(int x, int y) //编码前后的压缩比 {

cout<<\"编码前字符串长度为：\"<,.

储

cout<<\"编码后字符串的大小为:\"<时间复杂度为O(1)。

2.3其他

1.由于题目要求能输入任意长的字符串，所以本程序采用了string变量来记录输入的字符串，并采用string类的类成员函数来完成各项任务

2.统计权值代码和将编码串逆置的代码都没有单独定义函数。其中统计权值代码放到了主程序中，将编码串逆置代码放到了CreateTable（）函数中。 3.未能将哈夫曼树直观打印出来。

3、程序运行结果

（1）程序流程图

开始 调用主函数 等待用户输入字符串 ,.

结束

（2）测试条件

由用户任意输入一段字符，进行编码解码等操作。 （3）运行结果：

利用用户输入的字符串创建哈夫曼树和编码表 打印权值表和编码表 计算编码前后的压缩比 重新输入二进制编码 调用解码函数进行解码 ,.

,.

（4）说明：各函数运行正常，没有出现bug。

四、总结

1、调试时出现的问题及解决方法

在给每个字符编码时，由于编码是从根结点开始，所以选用与前序遍历相似的递归遍历形式。其中需要一个字符型数组来记录路径和编码，由于递归一次才有一位编码，所以这个数组也要随着递归的进行而不断修改。开始时我没有用引用作为参数而是直接将数组作为参数，结果发现每次调用递归时数组都是空。原来我用的是值传递，数组就算修改了也无法返回。这提醒了我之后运用递归时如果需要某个变量随函数递归而修改时应该使用地址传递而非值传递。

2、心得体会

这是第三次实验编程，相比前两次实验的相对生疏来说，这次对于基本语句的运用差不多能熟练掌握。但是还是出现了不少的问题，比如在基本代码以及主程序敲定完成以后，编

,.

译并没有出现错误，但是一运行，编码就输出为无限循环，反复调试也找不出关键所在，一直坐在电脑前呆呆地看了代码两个小时，还是一无所获；后来隔一段时间之后自己又转回来重新看代码，才恍然大悟，原来是循环条件写错，编码逆置和逆置后的代码重新赋给数组没有做到两层分别循环，导致整个语句块未能正常调用。修改之后一切运行正常。我也明白了，如果一直盯着代码看，多数情况是什么也看不出来的，因为你脑袋里充斥的都是那短短几句代码，越想反而越糊涂；如果过一阵自己头脑清醒了再去想问题说不定会有新发现。

这次实验，总结说来，让我更好地掌握了哈夫曼树的创建过程，了解了一种不等长编码的方法，用设断点调试的方法更加熟练，同时熟悉了STL中string类型的用法，对C++更加熟悉。

3.下一步改进

可以直观输出哈夫曼树，但是打印树需要考虑到结点所在的层次和需要打印空格的个数，难度有点大。

主函数中用户交互界面做得还不是很好，之后的改进可以是用case条件语句，由用户决定输出权值、编码、解码等函数执行结果的次序。

,.