赫夫曼树的实现数据结构实验报告

下载后可任意编辑软件学院设计性实验报告专业：.NET 年级/班级： 2024—2024 学年第一学期课程名称数据结构指导老师本组成员学号姓名实验地点实验时间第十二、十三、十四周项目名称哈夫曼编/译码系统的设计与实现实验类型设计性1．问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。2．一个完整的系统应具有以下功能：1）初始化（Initialzation）。从数据文件 DataFile.data 中读入字符及每个字符的权值，建立哈夫曼树 HuffTree；2）编码（EnCoding）。用已建好的哈夫曼树，对文件 ToBeTran.data 中的文本进行编码形成报文，将报文写在文件 Code.txt 中；3）译码（Decoding）。利用已建好的哈夫曼树，对文件 CodeFile.data 中的代码进行解码形成原文，结果存入文件 Textfile.txt 中；4）输出（Output）: 输出 DataFile.data 中出现的字符以及各字符出现的频度（或概率）；输出 ToBeTran.data 及其报文 Code.txt；输出 CodeFile.data 及其原文 Textfile.txt；要求：所设计的系统应能在程序执行的过程中，根据实际情况（不同的输入）建立DataFile.data、ToBeTran.data 和 CodeFile.data 三个文件，以保证系统的通用性。一、实验目的1、掌握哈夫曼编码原理；2、熟练掌握哈夫曼树的生成方法； 3、理解数据编码压缩和译码输出编码的实现。二、实验要求实现哈夫曼编码和译码的生成算法。三、实验内容先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后下载后可任意编辑的文件，并对其进行译码输出，最后存入另一个文件中。四、实验原理1、哈夫曼树的定义：假设有 n 个权值，试构造一颗有 n 个叶子节点的二叉树，每个叶子带权值为 wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；2、哈夫曼树的构造：weight 为输入的频率数组，把其中的值赋给依次建立的 HT Node 对象中的 data 属性，即每一个 HT Node 对应一个输入的频率。然后根据 data 属性按从小到大顺序排序，每次从data 取出两个最小和此次小的 HT N...