哈夫曼树编码课程设计实验报告.doc

1、目 录摘 要IIAbstractIII第一章 设计概述11.1 实验背景11.2 设计目的1第二章 设计简介及设计方案论述32.1 方案论述3第三章 详细设计43.1 结构体的定义43.2 主函数定义43.2 副函数定义5第四章 设计结果及分析114.1 设计结果显示114.2 设计结果分析12总 结13致 谢14参考文献15代码附录16摘 要在这次课程设计中，所进行的实验是：哈夫曼编码和编译器。对哈夫曼树进行建立，由节点的权值建立最小二叉树，哈夫曼树haftree，并由所建立的哈夫曼树进行编码，求出各个节点的编码。在由所求的哈夫曼树，输入一段二进制电文，能够输出那所建立的哈夫曼树中的节点。建

2、立的haftree用图形化表示出来。在整个代码实现中，窗体的实现，功能的完善，哈夫曼树的建立，哈夫曼树的编码，遇到了许多难题，haftree对象数组的分配空间，节点的属性等都比较困难。在整个过程中，用的是C#语言，包的应用，字符串数组的空间分配，在计算每个字符的权值时，用的是sizeOf()检索整个字符串，计算字符的权值，建立字符出现频度的表格，根据表格中每个字符频度建立起哈夫曼树。从根节点出发检索每个节点的左右孩子，如果是左孩子遍历左边，路径为0，然后左孩子为根节点；如果是右孩子，遍历右孩子，路径为1，然后右孩子为根节点。在重新上述方法，直到所有的节点都遍历完，每个节点的编码就确定后输出来。

3、在译码过程中，由所输入的二进制电文，根据所建立的哈夫曼树，如果是0走左边，如果是1，走右边，直到节点的左右孩子为空时，输出给节点的信息，在回到根节点重新遍历后面的二进制电文，直到所有电文都遍历完为止，输出所有从电文中译码出来的信息。关键词：编译器；频度；译码AbstractIn 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, Huffm

4、an 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

5、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

6、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 tra

7、verse 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,

8、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 .

9、 Keywords: compiler;frequency;decoding第一章 课题背景1.1 设计背景目的及意义1.1.1设计背景在当今信息时代，信息技术已经成为当代知识经济的核心技术。我们时刻都在和数据打交道。但是这些海量的数据是怎么保存在计算机里面的呢？在客户需要数据时它又是怎么发送给用户的呢？这就涉及到哈弗曼编码的技术了。哈弗曼编码在这种背景下，适应时代的要求诞生了。作为无损压缩算法，哈弗曼编码用途非常广泛，在各个领域都有应用。1.1.2设计目的这次可课程设计主要是回顾我们上学期所学习的数据结构这门课程，重新温习一下这些经典算法，加深对它们的影响，以至于今后更好的应用这些经典算法，

10、还有就是培养我们的程序设计算法，平时都是在教室里上课，很少有像这样集体性的编程，通过这次课程设计，不仅能加强我们的编程能力，更能加强我们的程序设计能力。1.1.3设计意义这次课程设计很有意义。哈夫曼编码是个很有用、很有效的编码方式，是一个伟大的发明。通过这次课程设计，让我们亲身体会到了课本上知识的作用和重要性，从而达到了学以致用的目的，让我们对今后的学习有了更清楚的方向和更加强烈的兴趣。1.2理论依据和工作原理1.2.1 理论依据哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现

11、概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 1.2.2工作原理 哈夫曼编码依据字符出现的频率来构造一棵二叉树，然后根据这棵树对字符进行编码，这种编码机制使用最短编码来表示字符串，大大节省了字符传递时的长度，在网络通信中，特别是网络流量方面作用特别明显，它大大节省了网络资源，提高了网络运行速度，方便了人们的生活。 第二章 设计简介及设计方案论述2.1设计简介这次课程设计是哈夫曼编码，要求实现可视化编程。哈夫曼树是一种很有用的数据结构，在数据传输方面更显方便，它能用较少的编码代替复杂的字符。我们这次课程设计就是要实现对一段报文进行哈弗曼编码，然后随便输

12、入一段编码，根据前面的编码进行解码。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(c

13、har c,double w)。还有就是HafumanT类，这个类中主要实现哈夫曼树的构造和编码以及解码。Form1类是主窗体类，在这里就不详细介绍了，在后面详细设计里面会有详细分析。第三章 详细设计3.1 总体分析这次课程设计，我设计了3个类，分别是哈夫曼节点类（HafumanNode）、哈夫曼树（HafumanT）、主窗体类（Form1）。这些类各有各的功能和作用，分别实现不同的功能，这样设计使代码更显调理性，而不至于把所有的功能都写在一个类里面，钠那样显得没有调理，很乱，可读性和可维护性不强。 3.2详细分析3.2.1 HafumanNode类这个类的主要代码如下：class Hafum

14、anNode 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; 这个类比较简单，代码非常少，这个类相当于课本上C语言中的结构体，只是在C#中我用类来实现。3.3.2 HafumanT类这个类有点复杂，因为

15、它要实现很多功能。这里就不详细列出它的所有代码了，而是把主要代码展示如下：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(listNodej.parent=-1) if (listNodej.weigh

16、t min1) min2 = min1; rchild = lchild; min1 = listNodej.weight; lchild = j; else if (listNodej.weight min2) min2 = listNodej.weight; rchild = j; double w = listNodelchild.weight + listNoderchild.weight; HafumanNode newNode = new HafumanNode(#, w); newNode.lchild = lchild; newNode.rchild = rchild; lis

17、tNode.Add(newNode); HafumanNode templchild =listNodelchild; templchild.parent = i; listNodelchild = templchild; HafumanNode temprchild = listNoderchild; temprchild.parent = i; listNoderchild = temprchild; 上面这个函数主要是构造哈夫曼树，这个算法跟课本上的一模一样。有技巧，但没有难度。下面这个函数是根据构造好的哈夫曼树对各个字符求出它的哈夫曼编码，然后存放在字符数组中对应的位置。public

18、string CreateHCode() string str=; for (int i = 0; i leaf; i+) str = ; int f = listNodei.parent; int c = i; while (f != -1) if (listNodef.lchild = c) str += 0; else str += 1; c = f; f = listNodef.parent; codei =ReverseString(str); return code; 3.2.3 Form1类这个Form1类看起来很不爽，因为它的名字是默认的，而没有按照匈牙利命名法来命名。这个类是

19、主窗体类。下面列出了它的主要功能代码：这个函数是编码，根据已经编码好的编码数组，查找各个字符的编码，然后把它连接起来，组成一个1和0的字符串，就是输入字符串的编码了。 private bool Code(string s,string str) char codestr = s.ToCharArray(); richTextBox1.Text = ; string temp = ; int m = 0; for (int i = 0; i codestr.Length; i+) m = GetIndex(hafumantree.listNode, codestri); if (m = -1)

20、MessageBox.Show(你?输?入?了?不?存?在的?编括?码?:n+codestri.ToString(); return false ; temp += strm; 这个主窗体还有个很重要的函数就是画树，以下是它的全部代码。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

21、,20,20); if (hafumantree.listNoden.lchild != -1) lchild = hafumantree.listNoden.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); else Font font = new Font(黑体

22、?,10); Brush brush = new SolidBrush(Color.Green); g.DrawString(hafumantree.listNoden.data.ToString(), font, brush, point); if (hafumantree.listNoden.rchild != -1) rchild = hafumantree.listNoden.rchild; Point newPoint = new Point(point.X + 35, point.Y + 30); DrawTree(rchild, newPoint); g.DrawLine(pen

23、, 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.listNoden.data.ToString(), font, brush, point); 第四章 设计结果及分析4.1 程序运行结果程序运行后的界面如图所示：图 4.1 程序运行结果输入字符串abcda，点击编码后

24、输出正常，但是在解码框中输入110001101时就有问题了，如图所示，解码输出框中的字符串最后一个字符是#图 4.2 编码和解码后的运行结果4.2错误分析经过仔细调试和分析，这个错误原因中于找出来了。原因是输入的1和0字符串最后几个不构成一个字符的编码，循环在某个父节点处就跳出来了，并输出了这个父节点的值，由于父节点默认值都是#，所以有时程序在译码时会出现个#，这个错误想了好久都没有解决，最后由于时间关系，就没有解决。总 结这次课程设计真的学到了很多东西。不仅是知识方面的学习，我觉得这次在生活或者说是工作方面更是学到了很重要的东西。其中最重要的东西是合作，或者说是交流。在这次课程设计中，我几乎

25、没有跟别人讨论，而是自己做自己的，被人问我的算法，我只是跟他们将一遍而没有问他们的算法，觉得没必要，因为我觉得这个课程设计应该完全自己做，自己想。但是当刘老师检查我们的代码是，我才恍然大悟，别人写的程序比我的都好，不仅程序界面好看、功能强大，而且算法也比我的简单，原来他们是在综合了别人跟自己的思想后总结出来更好的算法，而我一个人自己想，所以我的程序肯定没有他们做的好，很多细节和功能也没有考虑，自然而然我的成绩不会太理想，所以说这次课程设计对我来说是个教训。这次真的体会到了交流的重要性了，一个人的力量真的是有限的，思想也是有界的，俗话说三个臭皮匠顶个诸葛亮，这话真的没错。尤其是在这个信息如此发达

26、的社会，交流能力更是重要，所以今后要重点训练自己这方面的能力了。这从课程设计有个非常大的遗憾就是程序一直有个文件读写错误没有解决，严重影响了我的程序设计。在课程设计进行到第六天的时候，我打开文件时它说有个文件不存在，程序不能调试和运行，这个错误一直没有解决，于是从那天起我就没有写程序，而是每天在机房帮别人改程序，当然改程序不仅能帮助别人，而且自己也能从中学到很多知识，所以这是我一直都非常愿意做的，但是每天都想着自己程序有可以修改的地方但就是不能改，很烦躁，所以这次课程设计对我来说是比较失败的，还好有点收获。致 谢在这次课程设计中，哈弗曼编码及译码的实现中，用的是C#语言的窗体控制台实现所要完成

27、的功能，虽然对这门C#语言不怎么熟练，但是在不断地在图书馆进行学习过程中，还是学到了不少知识。虽然还有图形化哈弗曼树没有实现，但是还是顺利完成了本次实验。在这期间，当然遇到了许多问题，感谢同学的帮助，也感谢刘老师的指导。参考文献1 李纯莲，刘玉宝，刘金凤等C#.NET实用教程M北京：电子工业出版社，2011年100-1502 田鲁怀数据结构M北京：电子工业出版社，2010年178-2103 李春葆，尹为民，李蓉蓉等数据结构教程M北京：清华大学出版社.2010年210-250代码附录using System;using System.Collections.Generic;using Syste

28、m.Text;namespace HafumanTree class HafumanT string codeStr; double pinDu=new double1000; int pinShu=new int1000; public List listNode = new List(); public int leaf; /public HafumanNode node=new HafumanNode200; string code=new string1000; /在容器中根据左孩子查找给定元素 public int Searchlchild(List listNode, double

29、 w) for (int i = 0; i listNode.Count & listNodei.parent = -1; i+) if (listNodei.weight = w) return i; return -1; public int SearchNode(List listNode, char ch) for (int i = 0; i listNode.Count; i+) if (listNodei.data = ch) return i; return -1; /在容器中根据右孩子查找给定元素 public int Searchrchild(List listNode, d

30、ouble w) for (int i = 0; i listNode.Count; i+) if (listNodei.weight = w&listNodei.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+) switch (codei)

31、 case a: int m = 0; if (m = SearchNode(listNode, a) != -1) listNodem.pinDu+; listNodem.weight = listNodem.pinDu * 1.0 /j; else HafumanNode h = new HafumanNode(a, 0); h.pinDu = 1; h.weight = h.pinDu * 1.0 / j; listNode.Add(h); ; break; case b: int m = 0; if (m = SearchNode(listNode, b) != -1) listNod

32、em.pinDu+; listNodem.weight = listNodem.pinDu * 1.0 / j; else HafumanNode h = new HafumanNode(b, 0); 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) listNodem.pinDu+; listNodem.weight = listNodem.pinDu * 1.0 / j; else HafumanNode h = new HafumanNode(c, 0); h.pinDu = 1; h.weight = h.pinDu * 1.0 / j; listNode.Add(h); ; break; case d: int m = 0; if (m = SearchNode(listNode, d) != -1) listNodem.pinDu+; listNodem.weight = listNodem.pinDu * 1.0 / j; else