没有合适的资源?快使用搜索试试~ 我知道了~
数据结构-实验7.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 130 浏览量
2022-07-11
12:25:30
上传
评论
收藏 62KB PDF 举报
温馨提示
试读
19页
119 ൌဒ ݗڏણщ/ၲఖൌဒᆷ֝ ၂aൌဒଢ֥ ๙ݖݗڏણඎ֥ܒᄯđധख़ࢳؽҭඎ֥ܒᄯb๙ݖݗڏણщ/ၲݖӱđധख़ਵ߶ؽҭ ඎ֥ࠎЧҠቔބؽҭඎ֥ႋႨđϺᇹ࿐ളඃᅧؽҭඔቆᆮඔऌ֥ࠎЧჰބؓؽҭඔҠ ቔ֥ൌགྷٚمb ؽaൌဒଽಸ Чൌဒ֥ᇶေଽಸ൞ğ 1aႮ໓Чሳژࠣሳژᄝ໓Ч໓ࡱᇏԛགྷ֥ੱđܒᄯջಃਫ਼ࣥቋ؋֥ቋႪؽҭඎčݗڏ ણඎĎ đѩ၇ՎູࠎԤܒᄯሳژ֥భሗщčݗڏણщĎ Ġ 2aщğՖ໓Ч໓ࡱᇏೆ໓Чሳژđοᅶၘᆩ֥ሳژݗڏણщࡼ໓Чሳژሇߐູؽ ࣉᇅԱ֥ݗڏણщྙൔb 3aၲğՖ໓ࡱᇏೆؽࣉᇅԱሳژđοᅶݗڏણඎࡼఃሇߐູ໓Чሳژb 4aൻԛݗڏણඎğၛχೆіčҪՑіĎ֥ྙൔཁൕݗڏણඎb ඹaൌဒჰ 1aݗڏણඎ֥קၬ ݗڏણඎčቋႪؽҭඎĎ ğഡႵœ۱ಃᆴŠw1,w2,...,wnŢ đ൫ܒᄯ၂ॐႵœ۱ွࢲ֥ׄؽ ҭඎđֻŎ۱ွࢲ֥ׄಃᆴູ wiđᄵఃᇏջಃਫ਼ࣥӉ؇ູቋཬ֥ؽҭඎФӫູቋႪؽҭඎࠇ ݗڏણඎb 2aݗڏણෘم ݗڏણෘمေׄ൞ğ (1)۴ऌ۳ק֥œ۱ಃᆴ{w1,w2,...,wn}ܒӮœॐؽҭඎ֥ࠢކīĢ{T1,T2
资源推荐
资源详情
资源评论
119
实验七 哈夫曼编/译码器实验指导书
一、实验目的
通过哈夫曼树的构造,深刻理解二叉树的构造。通过哈夫曼编/译码过程,深刻领会二叉
树的基本操作和二叉树的应用,帮助学生熟练掌握二叉数组织数据的基本原理和对二叉数操
作的实现方法。
二、实验内容
本实验的主要内容是:
1、由文本字符及字符在文本文件中出现的频率,构造带权路径最短的最优二叉树(哈夫
曼树),并依此为基础构造字符的前缀编码(哈夫曼编码);
2、编码:从文本文件中读入文本字符,按照已知的字符哈夫曼编码将文本字符转换为二
进制串的哈夫曼编码形式。
3、译码:从文件中读入二进制串字符,按照哈夫曼树将其转换为文本字符。
4、输出哈夫曼树:以凹入表(层次表)的形式显示哈夫曼树。
四、实验原理
1、哈夫曼树的定义
哈夫曼树(最优二叉树):设有n个权值{w1,w2,...,wn},试构造一棵有n个叶结点的二
叉树,第i个叶结点的权值为 wi,则其中带权路径长度为最小的二叉树被称为最优二叉树或
哈夫曼树。
2、哈夫曼算法
哈夫曼算法要点是:
(1)根据给定的n个权值{w1,w2,...,wn}构成n棵二叉树的集合F={T1,T2,...,Tn},其中每
棵二叉树 Ti 只有一个带权为 Wi 的根结点,左右子树为空。
(2)在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的
二叉树根结点的权值为左右子树根结点权值之和。
(3)在F中删除这两棵树,同时将新得到的树加入到F中。
(4)重复(2)和(3),直到只剩下一棵二叉树为止。这棵二叉树便是哈夫曼树。
3、哈夫曼编码
对于字符的二进制编码,若任一字符的二进制编码都不是另一个字符的二进制编码的前
缀。这种编码叫做前缀编码。
以 n 种字符出现的频率作权,设计一棵哈夫曼树,并用二叉树的叶结点分别表示待编码
120
的字符,并约定左分支表示字符‘0’,右分支表示字符‘1’。则对每个叶结点,都有唯一的
一条从根结点出发的路径,则该路径上分支字符组成的字符串作为该叶子结点的编码。由此
得到的编码必为二进制的前缀编码,而且是编码总长最短的二进制前缀编码,这种编码即为
哈夫曼编码。
例:设有 8 个字符{A,B,C,D,E,F,G,H},其概率为{0.05,0.29,0.07,0.08,
0.14,0.23,0.03,0.11},设其权值用整数表示为 {5,29,7,8,14,23,3,11},其哈夫曼树
如图 1 所示。
则字符的哈夫曼编码为:
A 0001 B 10
C 1110 D 1111
E 110 F 01
G 0000 H 001
四、实现
1、哈夫曼树的存储结构
根据哈夫曼树的构造算法,哈夫曼树除叶结点外,其余结点的度均为 2。对于具有 n 个
权值构造的哈夫曼树,根据二叉树的性质 3,哈夫曼树的结点总数为 m=2n-1,即哈夫曼树所需
存储空间是由文本中不同字符的个数唯一确定的。为了便于对多棵二叉树进行组织和便于查
找各二叉树的根结点,采用静态链表作为二叉树的存储结构。其存储结构描述如下:
typedef struc {
char ch;
unsigned int weight;
unsigned int parent,lchild,rchild;
100
42 58
1
9
2
3
2
9
2
9
8
11
15 14
3
5
7
8
图 7-1 哈夫曼树示意图
121
}HTNode,*HuffmanTree;
A 5 8 -1 -1
B 29 13 -1 -1
C 7 9 -1 -1
D 8 9 -1 -1
E 14 11 -1 -1
F 23 12 -1 -1
G 3 8 -1 -1
H 11 10 -1 -1
* 8 10 6 0
* 15 11 2 3
* 19 12 8 7
* 29 13 4 9
* 42 14 10 5
* 58 1 1 11
* 100 -1 12 13
2、哈夫曼编码的存储结构
若要编码的文本文件的字符集不变,则其哈夫曼编码不变。字符的哈夫曼编码一旦确定,
可以长期使用。因此,需要用文件同时保存字符的哈夫曼编码和字符。哈夫曼编码的表示形
式既要考虑存储空间的效率,也要考虑文件读取的方便。
文本字符的哈夫曼编码是不等长的二进制码,用不等长的二进制字符串表示,节省存储
空间,但用文件读取不方便。若用等长的结构体表示,可能要浪费一点存储空间,但文件存
取方便。为了便于文件存取,采用等长结构体表示哈夫曼具有可取之处,其存储结构描述如
下:
#define NODENUM 26 //字符集
struct HuffmanCoding
{ char ch; //字符
char coding[NODENUM]; //字符编码
};
3、字符及权值的输入形式
为了避免字符及其权值的手工键盘输入带来的错误,可以将字符及其权值组织成文本文件
的形式。文本文件的格式为:
字符 权值
例如:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
剩余18页未读,继续阅读
资源评论
是空空呀
- 粉丝: 183
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于MSP430和3G传输的便携式心电监护仪
- MYv11教程.mp4
- SmartPack智能包裹毕业设计说明书.docx
- Real tom毕业设计说明.doc
- Packet Tracer - Design and Implement a VLSM
- 10-1 Packet Tracer - HSRP Configuration Guide
- 8-2 Packet Tracer - Configure IPv6 Addresses on Network Devices
- 7-2 Packet Tracer - Implement DHCPv4
- 6-3 Packet Tracer - Troubleshoot EtherChannel
- 5-1 Packet Tracer - Configuring PVST
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功