数据结构哈夫曼编码实验报告 一、实验目的： 通过哈夫曼编、译码算法的实现，巩固二叉树及哈夫曼树相关知识的理解掌握，训练学生运用所学知识，解决实际问题的能力。 二、实验内容： 已知每一个字符出现的频率，构造哈夫曼树，并设计哈夫曼编码。 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.wddqw.com/doc/1ae3cf25deccda38376baf1ffc4ffe473268fd57.html