【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《数据结构哈夫曼编码实验报告》,欢迎阅读!
数据结构哈夫曼编码实验报告
一、实验目的:
通过哈夫曼编、译码算法的实现,巩固二叉树及哈夫曼树相关知识的理解掌握,训练学生运用所学知识,解决实际问题的能力。
二、实验内容:
已知每一个字符出现的频率,构造哈夫曼树,并设计哈夫曼编码。 1、从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树。
2、打印每一个字符对应的哈夫曼编码。
3、对从终端读入的字符串进行编码,并显示编码结果。 4、对从终端读入的编码串进行译码,并显示译码结果。 三、实验方案设计:
(对基本数据类型定义要有注释说明,解决问题的算法思想描述要完整,算法结构和程序功能模块之间的逻辑调用关系要清晰,关键算法要有相应的流程图,对算法的时间复杂度要进行分析)
1、算法思想:
(1)构造两个结构体分别存储结点的字符及权值、哈夫曼编码值:
(2)读取前n个结点的字符及权值,建立哈夫曼树: (3)根据哈夫曼树求出哈夫曼编码: 2、算法时间复杂度:
(1)建立哈夫曼树时进行n到1次合并,产生n到1个新结点,并选出两个权值最小的根结点:O(n²);
(2)根据哈夫曼树求出哈夫曼编码:O(n²)。 (3)读入电文,根据哈夫曼树译码:O(n)。 四、该程序的功能和运行结果:
(至少有三种不同的测试数据和相应的运行结果,充分体现该程序的鲁棒性)
1、输入字符A,B,C,D,E,F及其相应权值16、12、9、30、6、3。
2、输入字符F,E,N,G,H,U,I及其相应权值30、12、23、22、12、7、9。
3、输入字符A,B,C,D,E,F,G,H,I,G及其相应权值19、23、25、18、12、67、23、9、32、33。
本文来源:https://www.wddqxz.cn/1ae3cf25deccda38376baf1ffc4ffe473268fd57.html