数据结构试验报告霍夫曼编码（DOC X页）
数据结构实验报告
(三)
学院 自动化学院
学号
姓名
日期 2014-12-09
实验目的
1、 掌握哈夫曼编码原理;
2、熟练掌握哈夫曼树的生成方法;
3、理解数据编码压缩和译码输出编码的实现;
4、掌握二叉树的基本3操作。
实验
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(解码)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。
实验要求
1) 初始化(Initialzation)。利用下表给出的字符集和频度的=;实际统计数据建
立哈夫曼树，并将它存于文件hfmTree中;
字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1
2) 编码(EnCoding)。利用已建好的哈夫曼树(若不在内存中，则从文件hfmTree
中读入)，对以下报文进行编码，结果存入文件CodeFile中;
报文内容:THIS PROGRAM IS MY FAVORITE
3) 译码(Decoding)。利用已建好的哈夫曼树，对文件CodeFile中编码后的报
文进行解码，结果存入文件Textfile中;
4) 输出(Output)。输出字符集中每个字符的哈夫曼编码;输出原始报文，及
其编码文件CodeFile和解码文件Textfile的内容。
扩展要求:将2)的编码结果以二进制形式存入CodeFile中，输出原始报文长度和编码后的报文长度。
1 需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
(1) 将实验要求中的
表格
关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载
写在文件“HfmTree.txt”中，程序初始化时从该文
件中读取字符及其频度，并据此建立Hfm树，生成编码表，打印出编码表; (2) 编码:用上一步生成的编码表，对报文进行编码，考虑到数据压缩性，这
一步将编码结果以二进制文件进行存储，文件名为CodeFile; (3) 解码:从文件CodeFile中读入编码后的报文，利用建立好的Hfm树对其
进行一一解码，输出解码结果，同时将结果存入Textfile.txt中; 2 概要设计
因本次实验涉及许多字符串的操作，文件读写，并且除了霍夫曼树外，还用到了许多其他数据结构，而本次实验重点在霍夫曼树上，为了省去编写其他数据结构的时间，本次实验选用了C#语言和 .NetFrameWork 4.0来实现。
自定义数据结构和类:
类
字段
方法
Node (+ 1 重载)
2.1 Node类:表示霍夫曼树的一个节点，在C#结构体是值类型，类是引用类型，故必须将结点定义成类;
成员变量:
public char data = '\0'; //该结点对应的欲编码的字符
public double probability; //频度，出现概率，即结点的权重
public Node left = null; //左子结点
public Node right = null;//右子结点
public bool isAccess = false;//用于标记是否已被访问过
public int id = 0; //独一无二的id，用于唯一标识一个结点
static int curId = 0;//每创建一个新Node时，都自动分配给其一个id，这个id逐个加1，防止出现完全相同的节点导致无法比较大小
方法:
此外为了排序方便，实现了IComparable接口的CompareTo函数，定义结点之间的比较大小规则，根据实际需求，首先比较频度(权值)，如果一样则通过唯一标识的id加以区分。
2.2 HfmTree类:表示一颗Hfm树
成员:public Node root = null;//树的根结点
方法:public HfmTree(Node[] nodes) //根据结点数据构造Hfm树
public HfmTree(string fileName) //根据文件里的数据构造Hfm树
public Dictionary
CreateCodeTable()//创建编码表，为每个字符创建一个编码
public string DeCode(string code) //根据输入的二进制编码进行解码，还原文本
2.3 用到的.Net里的数据结构
Dictionary:字典类，由键和值组成的集合，键、值可为任意类型，在 本作业中适合于存储编码表;
Stack :用于存储结点的栈，在遍历Hfm树的时候需要用于回到父结点; SortedSet:这是个结点的集合，而且里面的结点是自动排好序的，在建立霍夫曼树时寻找最小权值结点时要用到;
List :这是Byte型数据的链表，在创建二进制编码文件时用于组织文件的组成字节，该类型提供了函数可直接转成数组，非常方便;
2.4 全局函数
static void CreateBinaryFile(string code, string filename) 根据编码字符串code创建二进制文件
static string ReadCodeFromBinaryFile(string filename) 读取二进制文件还原成编码字符串
2.5 Main函数流程
a. 读取文件HfmTree，根据文件里的内容创建结点，进而构建霍夫曼树，文件HfmTree的形式如下:
每行表示一条
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
，先是字符，然后隔一个空格写上其频度; b. 根据生成的树，遍历树，生成编码表并输出;
c. 输出原始报文，并对其进行编码，编码结果输出到终端;
d. 将编码结果以二进制形式保存成文件Codefile，其中Codefile的前四个字节用于标识编码
的总长度，从第五个字节开始按位存储0和1的编码(从高位到低位填充)，最后一个字
节如果填不满默认为0;
e. 读入Codefile文件，将内容还原成string形式的编码结果，并将此结果送至HfmTree进行
解码得到原文，输出解码原文，并将结果存入Textfile.txt 中。
3 详细设计
public HfmTree(string fileName) //根据文件里的数据构造Hfm树
{
SortedSet sortedNodes = new SortedSet();//按序存储所有节点集
sortedNodes.Clear();
StreamReader reader = File.OpenText(fileName);//读入文件
string curLine = "";
char[] split=new char[1];
split[0]=' ';
while (true)
{
curLine=reader.ReadLine();
string[] data=curLine.Split(split);
if (data.Length < 2)
break;
char charData = data[0][0];
if (charData == '0')
charData = ' ';
double prob = Convert.ToDouble(data[1]);
sortedNodes.Add(new Node(charData, prob));//创建新结点加入有序结点集
if (reader.EndOfStream)
break;
}
reader.Close();
Node min = null; //当前结点集最小的元素
Node min2 = null;//当前结点集次小的元素
Node parent = null; //用于产生合并子结点的父结点
while (true)
{
min = sortedNodes.ElementAt(0);
min2 = sortedNodes.ElementAt(1);//首先取出权值最小的两个结点
sortedNodes.Remove(min);
sortedNodes.Remove(min2);//最小的两个从结点集中去除
parent = new Node('\0', min.probability + min2.probability);//创建一个父结点连接最小的两个结点
parent.left = min;
parent.right = min2;
sortedNodes.Add(parent);//将合并后的结点加入结点集
if (sortedNodes.Count < 2)//如果结点集中只剩一个元素，则构建完毕，跳出循环
break;
}
root = parent;//设置根结点
}
public Dictionary CreateCodeTable()//创建编码表，为每个字符创建一个编码
{
Dictionary codeTable = new Dictionary();//创建空字典
Stack nodeStack = new Stack();//创建结点栈
string curCode = "";//当前编码字符串
Node curNode = root;//当前访问的结点
while (true)
{
curNode.isAccess = true;//将当前结点标记为已访问过
if (curNode.left == null)//如果当前结点没有子节点，将curCode作为当前结点的data的编码，加入字典
{
codeTable.Add(curNode.data, curCode);
//Console.WriteLine(curNode.data.ToString());
curNode = nodeStack.Pop();//返回上一个结点
curCode = curCode.Remove(curCode.Length - 1);//curCode去掉最新的一位
continue;
}
else if (!curNode.left.isAccess)//如果左结点未访问过，跳至左子结点
{
nodeStack.Push(curNode);
curCode = curCode + "0";
curNode = curNode.left;
continue;
}
else if (!curNode.right.isAccess)//如果右结点未访问过，跳至左子结点
{
nodeStack.Push(curNode);
curCode = curCode + "1";
curNode = curNode.right;
continue;
}
else//如果左右都已访问过，则需要返回上一结点
{
if (nodeStack.Count > 0)//如果栈未空，则返回上一结点
{
curNode = nodeStack.Pop();
curCode = curCode.Remove(curCode.Length - 1);
continue;
}
else //如果栈已空，说明已经遍历完毕，退出循环
break;
}
}
return codeTable;
}
//根据输入的二进制编码进行解码，还原文本
public string DeCode(string code)
{
Node cur=root;
string output = "";
foreach (char x in code)
{
if (x == '0')//若是0，则进入左子树
{
cur = cur.left;
if (cur.left == null)//成功解出一个字符，加入输出字符串
{
output = output + cur.data.ToString();
cur = root;//返回根结点
}
}
else if (x == '1')//若是1，则进入右子树
{
cur = cur.right;
if (cur.left == null)
{
output = output + cur.data.ToString();
cur = root;
}
}
else
return "";
}
return output;
}
4 调试分析
调试过程中遇到了一点问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
。最初结点node类是没有唯一id去标识的，导致在比较大小时出现相等(权值和相等，又不是原始的子结点)的情况，sortedSet无法处理这种情况，所以编码表里重复的几项就被遗漏了。后来想到用流水方式分配给每个新建的Node一个独一无二的id，这样用id来做第二排序关键字，于是就不会出现无法排序的情况。最终运行时也不会遗漏了。
5 测试结果
从输出的编码表可看出，频度越小的字母编码越长，越大的编码越短，而且具有前缀性，不会产生歧义，这说明hfm树构建正确。
然后输出了原始报文，长度为27，编码后输出了编码字符串，后将此字符串打包成二进制文件长度变为19(文件头占了4字节)，可见数据已经被压缩了。
最后从文件读取二进制编码并进行了解码，可看出解码后结果完全正确。
之后我们通过winhex检查了Codefile里的内容，0~3字节表示了实际编码位数，第四字节D1变为二进制为11010001，第五字节为01100011„„可见二进制文件生成是成功的。
再来看看Textfile.txt的内容，也是正确的。
至此，实验成功～
6 实验总结
本次实验主要考察了霍夫曼树的建立与遍历，并结合了编码解码的实际应用，能让人对霍夫曼树有更深的体会。同时也考察了之前学的多种数据结构的应用，字符串操作以及文件读写。总体来说，这是个很好的实验题目。希望以后老师出题目也多结合实际应用。
7 附录
源代码文件:
HfmTree.cs
Program.cs
输入及输出文件(在bin\debug目录下):
HfmTree.txt 存储原始数据的文件
Codefile 编码的二进制文件
Textfile.txt 输出编码结果的文件
浙公网安备 33021202002483