c++数据结构实验哈夫曼树 下载本文

内容发布更新时间 : 2024/6/17 2:30:19星期一 下面是文章的全部内容请认真阅读。

北京邮电大学信息与通信工程学院

数据结构实验报告

1.实验要求

i.

实验目的:

(1) 掌握二叉树基本操作的实现方法 (2) 掌握二叉树基本操作的实现方法 (3) 了解哈夫曼树的思想和相关概念 (4) 学习使用二叉树解决实际问题的能力

(5) 熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法,熟练改错方

法。 (6) 熟悉设计算法的过程

(7) 进一步掌握指针、异常处理的使用

ii. 实验内容:

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

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、根据输入的字符串中每个字符出现的次数统计频度,对没有出现的 字符一律不用编码。

iii. 代码要求:

第1页

北京邮电大学信息与通信工程学院

1、必须要有异常处理,比如删除空链表时需要抛出异常; 2、保持良好的编程的风格:

代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致

函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能

3、递归程序注意调用的过程,防止栈溢出

2. 程序分析

树形结构是一种非线性结构可以用结点之间的分支来表示层次关系,二叉树是每个结点最多两个子树的有序树,十分适合计算机处理问题,而哈夫曼树是一种特殊的二叉树,它将权值大的数据放在了离根较近的结点处,这样使得带权路径长度最短,是非常好的存储方式。

2.1 存储结构

1.结点结构的存储方式: 根(下面结点的父结点)结点: 左孩子

右孩子

……

struct hnode //哈夫曼树结点的结构体 { int weight; int parent; int lchild; int rchild; char data; };

结点存储示意图: int weight int parent int lchild int rchild char data 2.编码表的实现中使用了以下结构体:

Struct hcode //编码表结构体 {

第2页

北京邮电大学信息与通信工程学院

char data; //字符 char code[100]; //编码内容 };

示意图为: char data char code[100] 3.在select函数中使用的结构体: struct node { int num; char data; }; int num

char data 2.2 关键算法分析:

A)Init初始化:统计需要编码的字符串中每个字符的频度并建立哈夫曼树

实现:在函数中设置了一个数组type用来统计字符串中字符的类型,no数组则用于统计每种字符串的个数,count用于存储每类字符的相应的个数。

void Huffman::Init() //将输入的数据保存至类中 { cout << \请输入需要编译压缩的内容\ << endl; cin.getline(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;

第3页