武汉工程大学
计算机科学与工程学院
综合设计报告
设计题目：学生学号： 1005080228 专业班级： 学生姓名： 张建雄 学生成绩： 指导教师（职称）： 刘黎志（副教授） 课题工作时间： 至
说明：
1、报告中的第一、二、三项由指导教师在综合设计开始前填写并发给每个
学生；四、五两项（中英文摘要）由学生在完成综合设计后填写。
2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。
3、指导教师评语一栏由指导教师就学生在整个设计期间的平时表现、设计
完成情况、报告的质量及答辩情况，给出客观、全面的评价。
4、所有学生必须参加综合设计的答辩环节，凡不参加答辩者，其成绩一律
按不及格处理。答辩小组成员应由2人及以上教师组成。
5、报告正文字数一般应不少于5000字，也可由指导教师根据本门综合设
计的情况另行规定。
6、平时表现成绩低于6分的学生，其综合设计成绩按不及格处理。
7、此表格式为武汉工程大学计算机科学与工程学院提供的基本格式（适用
于学院各类综合设计），各教研室可根据本门综合设计的特点及内容做适当的调整，并上报学院批准。
成绩评定表
学生姓名： 张建雄 学号： 1005080228 班级： 计算机工程02班
答辩记录表
指导教师评语
五、综合设计（课程设计）Abstract：
In this design, the experiment was : Huffman coding and compiler. The Huffman tree to establish, by the node weights to establish a minimum of two fork tree, Huffman tree haftree, and by the Huffman tree coding, and every node coding. By the Huffman tree, enter a binary message, can output the set up by the Huffman tree nodes. Establishment of haftree graphical representation. In the implementation of the code, the realization form, function perfect, Huffman tree is established, Huffman coding tree, encountered a lot of problems, an array of haftree objects allocated space, node attributes are difficult. Throughout the process, using the C# language, the application package, an array of strings in the spatial distribution, calculated for each weight of characters, using sizeOf to retrieve the entire string, calculating the weight of characters, establish character appearance frequency of form, form the basis of each character frequency established Huffman tree. Starting from the root node to retrieve each node around children, if children left traverse left, path 0, then left the child as the root node; if it is right child, traversing the right path for children, 1 children for the root node, then the right. In the new method described above, until all of the node traversal finished, each node is determined after the output coding.
In the decoding process, by the input binary message, according to the established Huffman tree, if it is 0 the left, if it is 1, go right, until the left and right child node is empty, the output to the node information, in the back of the root node to traverse behind a binary message, until all message traversal finished so far, the output from all the message decoding of information.
Keywords: compiler;frequency;decoding
武汉工程大学计算机科学与工程学院 综合设计报告
目 录
摘 要 ................................................................................. 错误！未定义书签。 Abstract................................................................................ 错误！未定义书签。
第一章 设计概述 ............................................................. 错误！未定义书签。
1.1 实验背景 ..................................................................... 错误！未定义书签。
1.2 设计目的 ..................................................................... 错误！未定义书签。
第二章 设计简介及设计方案论述 ................................. 错误！未定义书签。
2.1 方案论述 ..................................................................... 错误！未定义书签。
第三章 详细设计 ............................................................. 错误！未定义书签。
3.1 结构体的定义 ............................................................. 错误！未定义书签。
3.2 主函数定义 ................................................................. 错误！未定义书签。
3.2 副函数定义 ................................................................. 错误！未定义书签。
第四章 设计结果及分析 ................................................. 错误！未定义书签。
4.1 设计结果显示 ............................................................. 错误！未定义书签。
4.2 设计结果分析 ............................................................. 错误！未定义书签。 总 结 ............................................................................... 错误！未定义书签。 致 谢 ............................................................................... 错误！未定义书签。 参考文献 ............................................................................. 错误！未定义书签。 代码附录 ............................................................................. 错误！未定义书签。
- 1 -
武汉工程大学计算机科学与工程学院 综合设计报告
摘 要
在这次课程设计中，所进行的实验是：哈夫曼编码和编译器。对哈夫曼树进行建立，由节点的权值建立最小二叉树，哈夫曼树haftree，并由所建立的哈夫曼树进行编码，求出各个节点的编码。在由所求的哈夫曼树，输入一段二进制电文，能够输出那所建立的哈夫曼树中的节点。建立的haftree用图形化表示出来。在整个代码实现中，窗体的实现，功能的完善，哈夫曼树的建立，哈夫曼树的编码，遇到了许多难题，haftree对象数组的分配空间，节点的属性等都比较困难。在整个过程中，用的是C#语言，包的应用，字符串数组的空间分配，在计算每个字符的权值时，用的是sizeOf()检索整个字符串，计算字符的权值，建立字符出现频度的表格，根据表格中每个字符频度建立起哈夫曼树。从根节点出发检索每个节点的左右孩子，如果是左孩子遍历左边，路径为0，然后左孩子为根节点；如果是右孩子，遍历右孩子，路径为1，然后右孩子为根节点。在重新上述方法，直到所有的节点都遍历完，每个节点的编码就确定后输出来。
在译码过程中，由所输入的二进制电文，根据所建立的哈夫曼树，如果是0走左边，如果是1，走右边，直到节点的左右孩子为空时，输出给节点的信息，在回到根节点重新遍历后面的二进制电文，直到所有电文都遍历完为止，输出所有从电文中译码出来的信息。
关键词：编译器；频度；译码
- - 2
武汉工程大学计算机科学与工程学院 综合设计报告
Abstract In this design, the experiment was : Huffman coding and compiler. The Huffman tree to establish, by the node weights to establish a minimum of two fork tree, Huffman tree haftree, and by the Huffman tree coding, and every node coding. By the Huffman tree, enter a binary message, can output the set up by the Huffman tree nodes. Establishment of haftree graphical representation. In the implementation of the code, the realization form, function perfect, Huffman tree is established, Huffman coding tree, encountered a lot of problems, an array of haftree objects allocated space, node attributes are difficult. Throughout the process, using the C# language, the application package, an array of strings in the spatial distribution, calculated for each weight of characters, using sizeOf to retrieve the entire string, calculating the weight of characters, establish character appearance frequency of form, form the basis of each character frequency established Huffman tree. Starting from the root node to retrieve each node around children, if children left traverse left, path 0, then left the child as the root node; if it is right child, traversing the right path for children, then the right. In new method described above, until all of the node traversal finished, each node is determined after coding。
In the decoding process, by the input binary message, according to the established Huffman tree, if it is 0 the left, if it is 1, go right, until the left and right child node is empty, the output to the node information, in the back of the root node to traverse behind a binary message, until all message traversal finished so far, the output from all .
Keywords: compiler;frequency;decoding
- - 3
武汉工程大学计算机科学与工程学院 综合设计报告
第一章 课题背景
1.1 设计背景目的及意义
1.1.1设计背景
在当今信息时代，信息技术已经成为当代知识经济的核心技术。我们时刻都在和数据打交道。但是这些海量的数据是怎么保存在计算机里面的呢？在客户需要数据时它又是怎么发送给用户的呢？这就涉及到哈弗曼编码的技术了。哈弗曼编码在这种背景下，适应时代的要求诞生了。作为无损压缩算法，哈弗曼编码用途非常广泛，在各个领域都有应用。
1.1.2设计目的
这次可课程设计主要是回顾我们上学期所学习的数据结构这门课程，重新温习一下这些经典算法，加深对它们的影响，以至于今后更好的应用这些经典算法，还有就是培养我们的程序设计算法，平时都是在教室里上课，很少有像这样集体性的编程，通过这次课程设计，不仅能加强我们的编程能力，更能加强我们的程序设计能力。
1.1.3设计意义
这次课程设计很有意义。哈夫曼编码是个很有用、很有效的编码方式，是一个伟大的发明。通过这次课程设计，让我们亲身体会到了课本上知识的作用和重要性，从而达到了学以致用的目的，让我们对今后的学习有了更清楚的方向和更加强烈的兴趣。
- - 4
武汉工程大学计算机科学与工程学院 综合设计报告
1.2理论依据和工作原理
1.2.1 理论依据
哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于19xx年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。
1.2.2工作原理
哈夫曼编码依据字符出现的频率来构造一棵二叉树，然后根据这棵树对字符进行编码，这种编码机制使用最短编码来表示字符串，大大节省了字符传递时的长度，在网络通信中，特别是网络流量方面作用特别明显，它大大节省了网络资源，提高了网络运行速度，方便了人们的生活。
- - 5
武汉工程大学计算机科学与工程学院 综合设计报告
第二章 设计简介及设计方案论述
2.1设计简介
这次课程设计是哈夫曼编码，要求实现可视化编程。哈夫曼树是一种很有用的数据结构，在数据传输方面更显方便，它能用较少的编码代替复杂的字符。我们这次课程设计就是要实现对一段报文进行哈弗曼编码，然后随便输入一段编码，根据前面的编码进行解码。
2.2设计方案的论述
看到这个课程设计，第一感觉就是不怎么难。因为哈弗满编码主要代码课本上都有，我们只需要将代码添加到窗体类中就可以。首先，我设计了3个类，分别是HafumanNode类，HafumanT类和Form1主窗体类。HafumanNode类是哈弗曼节点类，这个类中有public char data; public int pinDu; public double weight; public int parent;public int lchild; public int rchild;这六个字段和构造函数public HafumanNode(char c,double w)。还有就是HafumanT类，这个类中主要实现哈夫曼树的构造和编码以及解码。Form1类是主窗体类，在这里就不详细介绍了，在后面详细设计里面会有详细分析。
- - 6
武汉工程大学计算机科学与工程学院 综合设计报告
第三章 详细设计
3.1 总体分析
这次课程设计，我设计了3个类，分别是哈夫曼节点类（HafumanNode）、哈夫曼树（HafumanT）、主窗体类（Form1）。这些类各有各的功能和作用，分别实现不同的功能，这样设计使代码更显调理性，而不至于把所有的功能都写在一个类里面，钠那样显得没有调理，很乱，可读性和可维护性不强。
3.2详细分析
3.2.1 HafumanNode类
这个类的主要代码如下：
class HafumanNode
{
public char data;
public int pinDu;
public double weight;
public int parent;
public int lchild;
public int rchild;
public HafumanNode(char c,double w)
{
data = c;
weight = w;
pinDu = 0;
parent = -1;
lchild = -1;
rchild = -1;
}
- - 7
武汉工程大学计算机科学与工程学院 综合设计报告
}
这个类比较简单，代码非常少，这个类相当于课本上C语言中的结构体，只是在C#中我用类来实现。
3.3.2 HafumanT类
这个类有点复杂，因为它要实现很多功能。这里就不详细列出它的所有代码了，而是把主要代码展示如下：
public void CreateHafumanTree()
{
int lchild, rchild;
double min1, min2;
int number = listNode.Count;
for (int i = number; i < number * 2 - 1; i++)
{
lchild = -1;
rchild = -1;
min1 = 3000;
min2 = 3000;
for (int j = 0; j < i; j++)
if(listNode[j].parent==-1)
if (listNode[j].weight < min1)
{
min2 = min1;
rchild = lchild;
min1 = listNode[j].weight;
lchild = j;
}
else if (listNode[j].weight < min2)
{
- - 8
武汉工程大学计算机科学与工程学院 综合设计报告
min2 = listNode[j].weight;
rchild = j;
}
double w = listNode[lchild].weight + listNode[rchild].weight; HafumanNode newNode = new HafumanNode('#', w);
newNode.lchild = lchild;
newNode.rchild = rchild;
listNode.Add(newNode);
HafumanNode templchild =listNode[lchild];
templchild.parent = i;
listNode[lchild] = templchild;
HafumanNode temprchild = listNode[rchild];
temprchild.parent = i;
listNode[rchild] = temprchild;
}
}
上面这个函数主要是构造哈夫曼树，这个算法跟课本上的一模一样。有技巧，但没有难度。下面这个函数是根据构造好的哈夫曼树对各个字符求出它的哈夫曼编码，然后存放在字符数组中对应的位置。
public string[] CreateHCode()
{
string str="";
for (int i = 0; i < leaf; i++)
{
str = "";
- - 9
武汉工程大学计算机科学与工程学院 综合设计报告
int f = listNode[i].parent;
int c = i;
while (f != -1)
{
if (listNode[f].lchild == c)
str += "0";
else
str += "1";
c = f;
f = listNode[f].parent;
}
code[i] =ReverseString(str);
}
return code;
}
3.2.3 Form1类
这个Form1类看起来很不爽，因为它的名字是默认的，而没有按照匈牙利命名法来命名。这个类是主窗体类。下面列出了它的主要功能代码：
这个函数是编码，根据已经编码好的编码数组，查找各个字符的编码，然后把它连接起来，组成一个1和0的字符串，就是输入字符串的编码了。
private bool Code(string s,string [] str)
{
char[] codestr = s.ToCharArray();
- 10 -
武汉工程大学计算机科学与工程学院 综合设计报告
richTextBox1.Text = "";
string temp = "";
int m = 0;
for (int i = 0; i < codestr.Length; i++)
{
m = GetIndex(hafumantree.listNode, codestr[i]);
if (m == -1)
{
MessageBox.Show("你?输?入?了?不?存?在ú的?编括?码?:\n"+codestr[i].ToString());
return false ;
}
temp += str[m];
}
这个主窗体还有个很重要的函数就是画树，以下是它的全部代码。
private void DrawTree(int n, Point point)
{
int lchild=-1,rchild=-1;
Graphics g = Graphics.FromHwnd(pictureBox1.Handle);
Pen pen = new Pen(Color.Red);
g.DrawEllipse(pen,point.X,point.Y,20,20);
if (hafumantree.listNode[n].lchild != -1)
{
lchild = hafumantree.listNode[n].lchild;
Point newPoint = new Point(point.X - 35, point.Y + 30);
DrawTree(lchild, newPoint);
g.DrawLine(pen, new Point(point.X + 10, point.Y + 10), new Point(newPoint.X + 10, newPoint.Y + 10));
}
- - 11
武汉工程大学计算机科学与工程学院 综合设计报告
else
{
Font font = new Font("黑ú体?",10);
Brush brush = new SolidBrush(Color.Green);
g.DrawString(hafumantree.listNode[n].data.ToString(), font, brush, point);
}
if (hafumantree.listNode[n].rchild != -1)
{
rchild = hafumantree.listNode[n].rchild;
Point newPoint = new Point(point.X + 35, point.Y + 30);
DrawTree(rchild, newPoint);
g.DrawLine(pen, new Point(point.X + 10, point.Y + 10), new Point(newPoint.X + 10, newPoint.Y + 10));
}
else
{
Font font = new Font("黑ú体?", 10);
Brush brush = new SolidBrush(Color.Green);
g.DrawString(hafumantree.listNode[n].data.ToString(), font, brush, point);
}
}
- 12 -
武汉工程大学计算机科学与工程学院 综合设计报告
第四章 设计结果及分析
4.1 程序运行结果
程序运行后的界面如图所示：
图 4.1 程序运行结果
输入字符串abcda，点击编码后输出正常，但是在解码框中输入110001101时就有问题了，如图所示，解码输出框中的字符串最后一个字符是#
- 13 -
武汉工程大学计算机科学与工程学院 综合设计报告
图 4.2 编码和解码后的运行结果
4.2错误分析
经过仔细调试和分析，这个错误原因中于找出来了。原因是输入的1和0字符串最后几个不构成一个字符的编码，循环在某个父节点处就跳出来了，并输出了这个父节点的值，由于父节点默认值都是#，所以有时程序在译码时会出现个#，这个错误想了好久都没有解决，最后由于时间关系，就没有解决。
- 14
-
武汉工程大学计算机科学与工程学院 综合设计报告
总 结
这次课程设计真的学到了很多东西。不仅是知识方面的学习，我觉得这次在生活或者说是工作方面更是学到了很重要的东西。·其中最重要的东西是合作，或者说是交流。在这次课程设计中，我几乎没有跟别人讨论，而是自己做自己的，被人问我的算法，我只是跟他们将一遍而没有问他们的算法，觉得没必要，因为我觉得这个课程设计应该完全自己做，自己想。但是当刘老师检查我们的代码是，我才恍然大悟，别人写的程序比我的都好，不仅程序界面好看、功能强大，而且算法也比我的简单，原来他们是在综合了别人跟自己的思想后总结出来更好的算法，而我一个人自己想，所以我的程序肯定没有他们做的好，很多细节和功能也没有考虑，自然而然我的成绩不会太理想，所以说这次课程设计对我来说是个教训。这次真的体会到了交流的重要性了，一个人的力量真的是有限的，思想也是有界的，俗话说三个臭皮匠顶个诸葛亮，这话真的没错。尤其是在这个信息如此发达的社会，交流能力更是重要，所以今后要重点训练自己这方面的能力了。
这从课程设计有个非常大的遗憾就是程序一直有个文件读写错误没有解决，严重影响了我的程序设计。在课程设计进行到第六天的时候，我打开文件时它说有个文件不存在，程序不能调试和运行，这个错误一直没有解决，于是从那天起我就没有写程序，而是每天在机房帮别人改程序，当然改程序不仅能帮助别人，而且自己也能从中学到很多知识，所以这是我一直都非常愿意做的，但是每天都想着自己程序有可以修改的地方但就是不能改，很烦躁，所以这次课程设计对我来说是比较失败的，还好有点收获。
- 15 -
武汉工程大学计算机科学与工程学院 综合设计报告
致 谢
在这次课程设计中，哈弗曼编码及译码的实现中，用的是C#语言的窗体控制台实现所要完成的功能，虽然对这门C#语言不怎么熟练，但是在不断地在图书馆进行学习过程中，还是学到了不少知识。虽然还有图形化哈弗曼树没有实现，但是还是顺利完成了本次实验。在这期间，当然遇到了许多问题，感谢同学的帮助，也感谢刘老师的指导。
- 16 -
武汉工程大学计算机科学与工程学院 综合设计报告
参考文献
[1] 李纯莲，刘玉宝，刘金凤等．C#.NET实用教程[M]．北京：电子工业出版社，20xx年．100-150．
[2] 田鲁怀．数据结构[M]．北京：电子工业出版社，20xx年．178-210．
[3] 李春葆，尹为民，李蓉蓉等．数据结构教程[M]．北京：清华大学出版社.20xx年．210-250．
- 17 -
武汉工程大学计算机科学与工程学院 综合设计报告
代码附录
using System;
using System.Collections.Generic;
using System.Text;
namespace HafumanTree
{
class HafumanT
{
string codeStr;
double [] pinDu=new double[1000];
int [] pinShu=new int[1000];
public List<HafumanNode> listNode = new List<HafumanNode>(); public int leaf;
//public HafumanNode [] node=new HafumanNode[200];
string [] code=new string[1000];
//在容器中根据左孩子查找给定元素
public int Searchlchild(List<HafumanNode> listNode, double w) {
for (int i = 0; i < listNode.Count && listNode[i].parent == -1; i++)
if (listNode[i].weight == w)
return i;
return -1;
}
public int SearchNode(List<HafumanNode> listNode, char ch) {
- 18 -
武汉工程大学计算机科学与工程学院 综合设计报告
for (int i = 0; i < listNode.Count; i++)
if (listNode[i].data == ch)
return i;
return -1;
}
//在容器中根据右孩子查找给定元素
public int Searchrchild(List<HafumanNode> listNode, double w) {
for (int i = 0; i < listNode.Count; i++)
if (listNode[i].weight == w&&listNode[i].parent==-1) return i;
return -1;
}
public HafumanT(string codeStr)
{
this.codeStr=codeStr;
}
//求频数
public void PinShu()
{
int j = codeStr.Length;
char [] code=codeStr.ToCharArray();
for (int i = 0; i < code.Length; i++)
{
- 19 -
武汉工程大学计算机科学与工程学院 综合设计报告
switch (code[i])
{
case 'a':
{
int m = 0;
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * }
{
HafumanNode h =
h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
{
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * } if ((m = SearchNode(listNode, 'a')) != -1) else new HafumanNode('a', 0); break; case 'b': int m = 0; if ((m = SearchNode(listNode, 'b')) != -1)
- 20 - 1.0 /j; 1.0 / j;
武汉工程大学计算机科学与工程学院 综合设计报告
else
{
HafumanNode h = new HafumanNode('b', 0); h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
{
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * }
{
HafumanNode h =
h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
{
break; case 'c': int m = 0; if ((m = SearchNode(listNode, 'c')) != -1) else new HafumanNode('c', 0); break; case 'd': int m = 0;
- 21 - 1.0 / j;
武汉工程大学计算机科学与工程学院 综合设计报告
if ((m = SearchNode(listNode, 'd')) != -1) {
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * 1.0 / j;
}
{
HafumanNode h =
h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
{
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * 1.0 / j;
}
{
HafumanNode h =
h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h); else new HafumanNode('d', 0); break; case 'e': int m = 0; if ((m = SearchNode(listNode, 'e')) != -1) else new HafumanNode('e', 0);
- 22 -
武汉工程大学计算机科学与工程学院 综合设计报告
}
}; break;
case 'f':
{
int m = 0;
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * }
{
HafumanNode h =
h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
{
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * } if ((m = SearchNode(listNode, 'f')) != -1) else new HafumanNode('f', 0); break; case 'g': int m = 0; if ((m = SearchNode(listNode, 'g')) != -1)
- 23 - 1.0 / j; 1.0 / j;
武汉工程大学计算机科学与工程学院 综合设计报告
else
{
HafumanNode h = new HafumanNode('g', 0); h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
{
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * }
{
HafumanNode h =
h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
{
break; case 'h': int m = 0; if ((m = SearchNode(listNode, 'h')) != -1) else new HafumanNode('h', 0); break; case 'i': int m = 0;
- 24 - 1.0 / j;
武汉工程大学计算机科学与工程学院 综合设计报告
if ((m = SearchNode(listNode, 'i')) != -1) {
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * 1.0 / j;
}
{
HafumanNode h =
h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
{
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * 1.0 / j;
}
{
HafumanNode h =
h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h); else new HafumanNode('i', 0); break; case 'j': int m = 0; if ((m = SearchNode(listNode, 'j')) != -1) else new HafumanNode('j', 0);
- 25 -
武汉工程大学计算机科学与工程学院 综合设计报告
}
}; break;
case 'k':
{
int m = 0;
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * }
{
HafumanNode h =
h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
{
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * } if ((m = SearchNode(listNode, 'k')) != -1) else new HafumanNode('k', 0); break; case 'l': int m = 0; if ((m = SearchNode(listNode, 'l')) != -1)
- 26 - 1.0 / j; 1.0 / j;
武汉工程大学计算机科学与工程学院 综合设计报告
else
{
HafumanNode h = new HafumanNode('l', 0); h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
{
{
listNode[m].pinDu++;
listNode[m].weight = listNode[m].pinDu * }
{
HafumanNode h =
h.pinDu = 1;
h.weight = h.pinDu * 1.0 / j;
listNode.Add(h);
}
};
}
} break; case ' ': int m = 0; if ((m = SearchNode(listNode, ' ')) != -1) else new HafumanNode(' ', 0); break; default: break;
- 27 - 1.0 / j;
武汉工程大学计算机科学与工程学院 综合设计报告
leaf = listNode.Count;
}
public void CreateHafumanTree()
{
int lchild, rchild;
double min1, min2;
int number = listNode.Count;
for (int i = number; i < number * 2 - 1; i++) {
lchild = -1;
rchild = -1;
min1 = 3000;
min2 = 3000;
for (int j = 0; j < i; j++)
if(listNode[j].parent==-1)
if (listNode[j].weight < min1) {
min2 = min1;
rchild = lchild;
min1 = listNode[j].weight; lchild = j;
}
else if (listNode[j].weight < min2) {
min2 = listNode[j].weight; rchild = j;
}
double w = listNode[lchild].weight +
- 28 -
武汉工程大学计算机科学与工程学院 综合设计报告
listNode[rchild].weight;
HafumanNode newNode = new HafumanNode('#', w); newNode.lchild = lchild;
newNode.rchild = rchild;
listNode.Add(newNode);
HafumanNode templchild =listNode[lchild]; templchild.parent = i;
listNode[lchild] = templchild;
HafumanNode temprchild = listNode[rchild]; temprchild.parent = i;
listNode[rchild] = temprchild;
}
}
public string ReverseString(string str)
{
string returnstr = "";
for(int i=str.Length-1;i>=0;i--)
returnstr+=str[i];
return returnstr;
}
//哈弗曼编码
public string[] CreateHCode()
{
- 29 -
武汉工程大学计算机科学与工程学院 综合设计报告
string str="";
for (int i = 0; i < leaf; i++) {
str = "";
int f = listNode[i].parent; int c = i;
{
str +=
str +=
c = f;
f = listNode[f].parent; }
code[i] =ReverseString(str); }
}
}
} while (f != -1) if (listNode[f].lchild == c) "0"; else "1"; return code;
- 30 -