数据结构试验报告霍夫曼编码

《数据结构试验报告霍夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验报告（三）学院自动化学院学号姓名日期2014-12-09实验目的1、掌握哈夫曼编码原理；2、熟练掌握哈夫曼树的生成方法；3、理解数据编码压缩和译码输出编码的实现；4、掌握二叉树的基本3操作。实验内容利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。实验要求1）初始化（Initialzation）。利用下表给出的字符集和频度的=;实际统计

2、数据建立哈夫曼树，并将它存于文件hfmTree中；字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811612）编码（EnCoding）。利用已建好的哈夫曼树（若不在内存中，则从文件hfmTree中读入），对以下报文进行编码，结果存入文件CodeFile中；报文内容：THISPROGRAMISMYFAVORITE3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile中编码后的报文进行解码，结果存入文件Textfile中；4）输出（Output）。输出字

3、符集中每个字符的哈夫曼编码；输出原始报文，及其编码文件CodeFile和解码文件Textfile的内容。扩展要求：将2）的编码结果以二进制形式存入CodeFile中，输出原始报文长度和编码后的报文长度。1需求分析（1）将实验要求中的表格写在文件“HfmTree.txt”中，程序初始化时从该文件中读取字符及其频度，并据此建立Hfm树，生成编码表，打印出编码表；（2）编码：用上一步生成的编码表，对报文进行编码，考虑到数据压缩性，这一步将编码结果以二进制文件进行存储，文件名为CodeFile；（3）解码：从文件CodeFile中读入编码后的报文，利用建立好的Hfm树对其进行一一解码，输出解

4、码结果，同时将结果存入Textfile.txt中；2概要设计因本次实验涉及许多字符串的操作，文件读写，并且除了霍夫曼树外，还用到了许多其他数据结构，而本次实验重点在霍夫曼树上，为了省去编写其他数据结构的时间，本次实验选用了C#语言和.NetFrameWork4.0来实现。自定义数据结构和类：2.1Node类：表示霍夫曼树的一个节点，在C#结构体是值类型，类是引用类型，故必须将结点定义成类;成员变量：publicchardata='';//该结点对应的欲编码的字符publicdoubleprobability;//频度，出现概率，即结点的权重publicNodeleft=null;

5、//左子结点publicNoderight=null;//右子结点publicboolisAccess=false;//用于标记是否已被访问过publicintid=0;//独一无二的id，用于唯一标识一个结点staticintcurId=0;//每创建一个新Node时，都自动分配给其一个id，这个id逐个加1，防止出现完全相同的节点导致无法比较大小方法：此外为了排序方便，实现了IComparable接口的CompareTo函数，定义结点之间的比较大小规则，根据实际需求，首先比较频度（权值），如果一样则通过唯一标识的id加以区分。2.2HfmTree类：表示一颗Hfm树成员：publ

6、icNoderoot=null;//树的根结点方法：publicHfmTree(Node[]nodes)//根据结点数据构造Hfm树publicHfmTree(stringfileName)//根据文件里的数据构造Hfm树publicDictionaryCreateCodeTable()//创建编码表，为每个字符创建一个编码publicstringDeCode(stringcode)//根据输入的二进制编码进行解码，还原文本2.3用到的.Net里的数据结构Dictionary：字典类，由键和值组成的集合，键、值可为任意类型，在本作业

7、中适合于存储编码表；Stack：用于存储结点的栈，在遍历Hfm树的时候需要用于回到父结点；SortedSet：这是个结点的集合，而且里面的结点是自动排好序的，在建立霍夫曼树时寻找最小权值结点时要用到；List：这是Byte型数据的链表，在创建二进制编码文件时用于组织文件的组成字节，该类型提供了函数可直接转成数组，非常方便；2.4全局函数staticvoidCreateBinaryFile(stringcode,strin