没有合适的资源?快使用搜索试试~ 我知道了~
《数据结构课程设计》赫夫曼编码实验报告.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 37 浏览量
2022-11-07
15:15:04
上传
评论
收藏 435KB PDF 举报
温馨提示
试读
20页
。。。
资源推荐
资源详情
资源评论
目 录
一、概述 ................................................. 1
二、系统分析 ............................................. 1
三、概要设计 ............................................. 2
四、详细设计 ............................................. 4
4.1 赫夫曼树的建立 .................................... 4
4.1.1 选择选择 parent 为 0 且权值最小的两个根结点的算
法 ................................................. 5
4.1.2 统计字符串中字符的种类以及各类字符的个数 ..... 7
4.1.3 构造赫夫曼树.................................. 8
4.2 赫夫曼编码 ....................................... 10
4.2.1 赫夫曼编码算法............................... 10
4.2.2 建立正文的编码文件........................... 11
4.3 代码文件的译码.................................... 12
五、运行与测试 .......................................... 14
六、总结与心得 .......................................... 14
参考文献 ................................................ 15
附录 .................................................... 15
一、概述
本设计是对输入的一串电文字符实现赫夫曼编码,再对赫夫曼编
码生产的代码串进行译码,输出 电文字符串。
在当今信息爆炸时代,如何采用有效的数据压缩技术节省数据文
件的存储空间和计算机网络的传送时 间越来越引起人们的重视,赫
夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
二、系统分析
赫夫曼编码的应用很广泛,利用赫夫曼树求得的用于通信的二进
制编码成为赫夫曼编码。树中从根到 每个叶子都有一条路径,对路
径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的
分支表示 “1”码,取每条路径上的“0”或“1”的序列作为和每个
叶子对应的字符的编码,这就是赫夫曼编码。
通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。
电报通信是传递文字的二进制码形式 的字符串,但在信息传递时,
总希望总长度能尽可能短,即采用最短码。
假设每种字符在电文中出现的次数为 W i ,编码长度为 L i ,电
文中有 n 种字符,则电文编码总长为∑W i L i 。 若将此对应到二
叉树上,W i 为叶节点的权 ,L i 为根节点到叶节点的路径长度。
1
那么,∑W i L i 恰好为二叉 树上带权路径长度。
因此,设计电文总长最短的二进制前缀编码,就是以 n 种子符
出现的频率作权,构造一刻赫夫曼树, 此构造过程成为赫夫曼编码。
根据设计要求和分析,要实现设计,必须实现以下方面的功能:
(1) 赫夫曼树的建立;
(2) 赫夫曼编码的生成;
(3) 编码文件的译码;
三、概要设计
程序由哪些模块组成以及模块之间的层次结构、各模块的调用关
系;每个模块的功能。
void main()
void HufffmanEncoding(HuffmanTree HT,HuffmanCode HC)//编码部
分
char *decode(HuffmanCode Hc)//译码
void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int
cnt[],char str[]) //生成 Huffman 树
void select(HufmanTree HT,int k,int &s1,int &s2) //找寻 parent
为 0,权最小的两个节点
2
其流程图如下:
开始
进行相应的操作
构 对 对 程
造 字 编 序
赫 符 码 结
夫 串 串 束
曼 编 译 退
树 码 码 出
进行相应的操作
输出结果
结束
3
剩余19页未读,继续阅读
资源评论
xxpr_ybgg
- 粉丝: 6559
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功