没有合适的资源?快使用搜索试试~ 我知道了~
c++数据结构实验哈夫曼树.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 38 浏览量
2021-10-10
19:23:59
上传
评论
收藏 263KB DOCX 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/30575369/0001-96a3d47d18b620495e32e9b48a03b9a6_thumbnail-wide.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
16页
c++数据结构实验哈夫曼树.docx
资源推荐
资源详情
资源评论
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/release/download_crawler_static/30575369/bg1.jpg)
北京邮电大学信息与通信工程学院
数据结构实验报告
1.实验要求
i. 实验目的:
() 掌握二叉树基本操作的实现方法
(2) 掌握二叉树基本操作的实现方法
(3) 了解哈夫曼树的思想和相关概念
() 学习使用二叉树解决实际问题的能力
() 熟悉 语言的基本编程方法,掌握集成编译环境的调试方法,熟练改错方
法。
() 熟悉设计算法的过程
(7) 进一步掌握指针、异常处理的使用
ii. 实验内容:
利用二叉树结构实现赫夫曼编解码器。
基本要求:
、初始化:能够对输入的任意长度的字符串 进行统计,统计每个字符的频
度,并建立赫夫曼树
、建立编码表:利用已经建好的赫夫曼树进行编码,并将每个字
符的编码输出。
、编码:根据编码表对输入的字符串进行编码,并将编码后的字符串
输出。
、译码:利用已经建好的赫夫曼树对编码后的字符串进行译码,并
输出译码结果。
、打印:以直观的方式打印赫夫曼树〔选作〕
、计算输入的字符串编码前和编码后的长度,并进行分析,讨论赫夫曼编码的压
缩效果。
测试数据:
!!"#$!%&'#'!'
!!%
提示:
、用户界面可以设计为“菜单”方式:能够进行交互。
、根据输入的字符串中每个字符出现的次数统计频度,对没有出现的
第 1 页
![](https://csdnimg.cn/release/download_crawler_static/30575369/bg2.jpg)
北京邮电大学信息与通信工程学院
字符一律不用编码。
iii. 代码要求:
1、必须要有异常处理,比方删除空链表时需要抛出异常;
2、保持良好的编程的风格:
代码段与段之间要有空行和缩近
标识符名称应该与其代表的意义一致
函数名之前应该添加注释说明该函数的功能
关键代码应说明其功能
3、递归程序注意调用的过程,防止栈溢出
2. 程序分析
树形结构是一种非线性结构可以用结点之间的分支来表示层次关系,二叉树是每个结点
最多两个子树的有序树,十分适合电脑处理问题,而哈夫曼树是一种特殊的二叉树,它将
权值大的数据放在了离根较近的结点处,这样使得带权路径长度最短,是非常好的存储方
式。
2.1 存储结构
1.结点结构的存储方式:
根〔下面结点的父结点〕结点:
左孩子
右孩子
……
struct hnode //哈夫曼树结点的结构体
{
int weight;
int parent;
int lchild;
int rchild;
char data;
};
第 2 页
![](https://csdnimg.cn/release/download_crawler_static/30575369/bg3.jpg)
北京邮电大学信息与通信工程学院
结点存储示意图:
int weight int parent int lchild int rchild char data
2.编码表的实现中使用了以下结构体:
Struct hcode //编码表结构体
{
char data; //字符
char code[100]; //编码内容
};
示意图为:
char data char code[100]
3.在 select 函数中使用的结构体:
struct node
{
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;
第 3 页
![](https://csdnimg.cn/release/download_crawler_static/30575369/bg4.jpg)
北京邮电大学信息与通信工程学院
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;
}
}
}
将初始化的数据用于建立哈夫曼树:
)!*#++(
,
-./
(-&(0123/含有 种字符的哈夫曼树需要 12 个结点
4-./5/
,
&(!03%!#--.该字符没有出现,跳过,继续找出现过的字
符
,
/
6
(03%&(-!03%!#/将 ! 里统计的次数传入哈夫曼树
的节点中,作为字符权重
(03%(-2/
(03%(-2/
(03%$-2/将左右孩子结点和父节点都置空
(03%-!03%/将字符传入哈夫曼树的结点
/
6
7-2"'-2/
4-/512/
,
87"'"/挑选三者中的权重较小的两个
(073%$-(0'3%$-/令较小的 7、' 为孩子节点,该
两个结点的父节点是
(03%&(-(073%&((0'3%&(/ 结点字符的权重赋
为是左右孩子字符权重之和
(03%(-7/左孩子为 7
(03%(-'/右孩子为 '
(03%$-2/父节点置空
7-2/
第 4 页
剩余15页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/cb6aa90a299b4c48b5485fc622c9643a_weixin_43990727.jpg!1)
学习使人快乐张
- 粉丝: 27
- 资源: 6万+
![benefits](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-1.c8e153b4.png)
下载权益
![privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-2.ec46750a.png)
C知道特权
![article](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-3.fc5e5fb6.png)
VIP文章
![course-privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-4.320a6894.png)
课程特权
![rights](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-icon.fe0226a8.png)
开通VIP
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)