文档介绍：数据结构实验报告

实验目的:
掌握二叉树基本操作的实现方法
掌握二叉树基本操作的实现方法
了解哈夫曼树的思想和相关概念
学习使用二叉树解决实际问题的能力
熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法,熟练改错方法。
熟悉设计算法的过程
进一步掌握指针、异常处理的使用
实验内容:
利用二叉树结构实现赫夫曼编/解码器。
基本要求:
初始化(Init):能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立赫夫曼树
建立编码表(CreateTable):利用已经建好的赫夫曼树进行编码,并将每个字符的编码输出。
编码(Encoding):根据编码表对输入的字符串进行编码,并将编码后的字符串输出。
译码(Decoding):利用已经建好的赫夫曼树对编码后的字符串进行译码,并输出译码结果。
打印(Print):以直观的方式打印赫夫曼树(选作)
计算输入的字符串编码前和编码后的长度,并进行分析,讨论赫夫曼编码的压缩效果。
测试数据:
I love data Structure, I will try my best to study data structure.
提示:
1、用户界面可以设计为“菜单”方式:能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度,对没有出现的
字符一律不用编码。
代码要求:
1、必须要有异常处理,比如删除空链表时需要抛出异常;
2、保持良好的编程的风格:
代码段与段之间要有空行和缩近
标识符名称应该与其代表的意义一致
函数名之前应该添加注释说明该函数的功能
关键代码应说明其功能
3、递归程序注意调用的过程,防止栈溢出
2. 程序分析
树形结构是一种非线性结构可以用结点之间的分支来表示层次关系,二叉树是每个结点最多两个子树的有序树,十分适合计算机处理问题,而哈夫曼树是一种特殊的二叉树,它将权值大的数据放在了离根较近的结点处,这样使得带权路径长度最短,是非常好的存储方式。
存储结构
:
根(下面结点的父结点)结点:
左孩子
右孩子
……

struct hnode //哈夫曼树结点的结构体
{
int weight;
int parent;
int lchild;
int rchild;
char data;
};
结点存储示意图:
int weight
int parent
int lchild
int rchild
char data
:
Struct hcode //编码表结构体
{
char data; //字符
char code[100]; //编码内容
};
示意图为:
char data
char code[100]
:
struct node
{
int num;
char data;
};
int num
char data
关键算法分析:
A)Init初始化:统计需要编码的字符串中每个字符的频度并建立哈夫曼树
实现:在函数中设置了一个数组type用来统计字符串中字符的类型,no数组则用于统计每种字符串的个数,count用于存储每类字符的相应的个数。
void Huffman::Init() //将输入的数据保存至类中
{
cout << "请输入需要编译压缩的内容" << endl;
(in, 500, '\n');
n = 0;
no = 0;
count = new node[127]; //type
for (int j = 0; j < 127; j++) //对每一种字符的个数进行初始化
{
count[j].num = 0;
}
while (in[no] != '\0') //结束之前,每输入一个字符,则对应的数目增1
{
++count[in[no]].num;
count[in[no]].data = in[no];
++no;
}
for (int k = 0; k<127; k++) {
if (count[k].num>0)
{
n++;
cout << count[k].data << count[k].num << endl;
}
}
}
将初始化的数据用于建立哈夫曼树:
void Huffman::createht()
{
no = 0;
htree = new hnode[2 * n