没有合适的资源?快使用搜索试试~ 我知道了~
c++数据结构实验哈夫曼树 (3).pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 181 浏览量
2022-10-30
01:21:25
上传
评论
收藏 548KB PDF 举报
温馨提示
试读
11页
c++数据结构实验哈夫曼树 (3).pdfc++数据结构实验哈夫曼树 (3).pdf
资源推荐
资源详情
资源评论
数据结构实验报告
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、必须要有异常处理,比如删除空链表时需要抛出异常;
2、保持良好的编程的风格:
1 / 11
代码段与段之间要有空行和缩近
标识符名称应该与其代表的意义一致
函数名之前应该添加注释说明该函数的功能
关键代码应说明其功能
3、递归程序注意调用的过程,防止栈溢出
2. 程序分析
树形结构是一种非线性结构可以用结点之间的分支来表示层次关系,二叉树是每个结点最
多两个子树的有序树,十分适合计算机处理问题,而哈夫曼树是一种特殊的二叉树,它将权值
大的数据放在了离根较近的结点处,这样使得带权路径长度最短,是非常好的存储方式.
2.1 存储结构
1.结点结构的存储方式:
根〔下面结点的父结点〕结点:
左孩子
右孩子
structhnode//哈夫曼树结点的结构体
{
int weight;
int parent;
int lchild;
int rchild;
char data;
};
结点存储示意图:
int weight int parent int lchild int rchild chardata
……
2.编码表的实现中使用了以下结构体:
Struct hcode//编码表结构体
{
char data;//字符
char code[100];//编码内容
};
示意图为:
char data char code[100]
3.在 select 函数中使用的结构体:
structnode
{
int num;
char data;
2 / 11
};
int num char data
2.2 关键算法分析:
A>Init 初始化:统计需要编码的字符串中每个字符的频度并建立哈夫曼树
实现:在函数中设置了一个数组 type 用来统计字符串中字符的类型,no 数组则用于
统计每种字符串的个数,count 用于存储每类字符的相应的个数.
voidHuffman::Init<> //将输入的数据保存至类中
{
cout << "请输入需要编译压缩的内容" << endl;
cin.getline<in, 500, '\n'>;
n = 0;
no = 0;
count = newnode[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;
}
}
}
将初始化的数据用于建立哈夫曼树:
voidHuffman::createht<>
{
no = 0;
htree = newhnode[2 * n - 1];//含有n种字符的哈夫曼树需要2*n-1个结点
for <int i = 0; i<n; i++>
{
while <count[no].num == 0> //该字符没有出现,跳过,继续找出现过的字符
{
no++;
}
htree[i].weight = count[no].num; //将count里统计的次数传入哈夫曼树的节
3 / 11
剩余10页未读,继续阅读
资源评论
G11176593
- 粉丝: 6671
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功