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

下载后可任意编辑 软件学院设计性实验报告 专业.NET 年级/班级 20242024学年第一学期 课程名称 数据结构 指导老师 本组成员 学号姓名 实验地点 实验时间 第十二、十三、十四周 项目名称 哈夫曼编/译码系统的设计与实现 实验类型 设计性 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 Node，将他们的data相加，构造出新的HTNode作为他们的父节点，指针parent，leftchild，rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。 通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。 五、实验流程 ① 初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树； ② 根据符号概率的大小按由大到小顺序对符号进行排序； ③ 把概率最小的两个符号组成一个节点； ④ 重复步骤（2）（3），直到概率和为1； ⑤ 从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”； ⑥ 从根节点开始，对符号进行编码； ⑦ 译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。 六、 实验程序 数据结构 下面是编译码系统中所用的数据结构。 在这个系统中，哈夫曼树的存储结构采纳顺序存储；其结点结构为 程序中用到的头文件、类型定义及主要的函数原型如下 includestdio.h includemalloc.h includestdlib.h includestring.h typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; unsigned char ch; }HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树 typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表 char str[9]{ ,a,b,c,d,e,f,g,h}; int m; void SelectHuffmanTree HT,int i,int s1,int s2 { int j,min1,min2; forj1;ji;j ifHT[j].parent0 ifHT[j].weights1||HT[j].weights2 { ifs1s2 { s1HT[j].weight; min1j; } else { s2HT[j].weight; min2j;} } s1min1; s2min2; } void Print1HuffmanTree HT { int i; printf建立好的赫夫曼树的存储情况\n; printf存储单元字符权值双亲左孩子右孩子\n; fori1;im;i printf -4d c -4d -4d d d\n,i,HT[i].ch,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild; } void Print2HuffmanCode HC { int i; printf各个字符的编码如下\n; fori1;i8;i printfc的编码s\n,str[i],HC[i]; } void Initialzationint *w { FILE *fp; char a; int i; int n0; iffpDataFile.data,wbNULL { printfcannot open flie\n; return; } printf请输入数据字符（a-h）以结束\n; agetchar; fori0;a;i { fprintffp,