云南大学软件学院数据结构实验五实验报告-赫夫曼编码译码器

云南大学软件学院云南大学软件学院数据结构实验报告（本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度：A□B□C□序号学号姓名成绩123指导教师（签名）学期：任课教师: 实验题目: 实验五树的原理及其应用小组长: 联系电话: 电子邮件: 完成提交时间：年月日云南大学软件学院2010学年秋季学期《数据结构实验》成绩考核表学号：姓名：本人承担角色：课题分析，算法设计，程序编写，后期调试，完成实验报告评分项目评分指标分值得分实验构思（10%）1.实验目的明确52.实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1.有对基本数据结构的抽象数据类型定义52.实验方案设计完整，数据结构、算法选择合理53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1.代码编写规范、风格统一、注释清楚易读52.程序运行正常，测试结果正确153.界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1.内容详实无缺漏，文字流畅、图表清楚52.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1.个人完成工作量152.个人技术水平103.团队合作精神5实验运作（10%）1.有一定用户群52.应用前景分析5综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。）云南大学软件学院2010学年秋季学期《数据结构实验》成绩考核表学号：姓名：本人承担角色：课题分析，算法设计，后期调试，完成实验报告评分项目评分指标分值得分实验构思（10%）1.实验目的明确52.实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1.有对基本数据结构的抽象数据类型定义52.实验方案设计完整，数据结构、算法选择合理53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1.代码编写规范、风格统一、注释清楚易读52.程序运行正常，测试结果正确153.界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1.内容详实无缺漏，文字流畅、图表清楚52.实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1.个人完成工作量152.个人技术水平103.团队合作精神5实验运作（10%）1.有一定用户群52.应用前景分析5综合得分：（满分100分）指导教师：年月日（注：此表在难度为C时使用，每个成员一份。）（下面的内容由学生填写，格式统一为，字体:楷体,行距:固定行距18，字号:小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）1.数据结构算法的知识：树的定义。树的节点和边的表示。树的存储结构。树的分类：二叉树—》Heffman树。树的遍历：前序遍历，中序遍历，后序遍历。2.面向对象的程序设计相关知识：C#基本语法知识。类的定义，实例化。对象的生成调用。变量的传递。二、【实验设计(Design)】(20%)（本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）本实验创建了四个类Form类//用于窗口的初始化，控制各控件的属性和动作Data类//用于本程序所需的频度表数组的生成以及调用HuffmanTree类//用于构造Huffman树以及控制树的各项操作HuffmanTreeNode类//用于构造Huffman树的节点抽象数据类型的功能规格说明：窗口初始化：privatevoidForm1_Load(objectsender,EventArgse)转换模式：privatevoidbutton1_Click(objectsender,EventArgse)privatevoidbutton1_Click(objectsender,EventArgse)开始按钮：privatevoidbutton3_Click(objectsender,EventArgse)声明全局数组：publicmember[]allMembers=newmember[27];定义结构体数组：publicstructmember{publiccharch;//保存频度字符publicintfrequentness;//保存频度}Data的构造函数（创建Huffman树）publicData()Data类中的寻找当前最大项函数：publicintFindMax()Data类中的寻找当前第二大项函数：publicintFindSecondMax()Data类中的计算当前有效项的数目的函数：publicintCount()HuffmanTreeNode类中创建节点的构造函数：publicHuffmanTreeNode(charch2,intfrequentness2)HuffmanTree类中定义的节点类型：publicHuffmanTreeNoderoot,p,r;HuffmanTree类中实例化一个Data类来构造频度表：publicDatafrequentnessTable;HuffmanTree类中的构造函数，创建一棵Huffman树：publicHuffmanTree()HuffmanTree类中的成员函数，对于指定的字符实行中序遍历，遍历完之后逆向回溯得到该字符的Huffman编码：publicintSearchTree()HuffmanTree类中的两个节点变量，用于判断左右子树：publicintSearchTree()主程序模块伪代码说明：创建新的字母频度表：frequentnessTable=newData();创建栈来倒装输出赫夫曼编码：Stack<char>HuffmanCode=Stack<char>;退出程序：this.Close（）子程序伪代码说明（HuffmanTree）：构建Huffman树：publicHuffmanTreeNoderoot,p,r;核心程序段（生成Huffman编码）：while(r==root){r=p.parent;if(p==r.left)HuffmanCode.Push('1');//栈中存1elseHuffmanCode.Push('0');//栈中存0p=p.parent;}返回栈中元素个数：publicintcount{get{returnlist.Count;}}主程序模块与各子程序模块间的调用关系：ClassForm1调用ClassData初始化程序所要的各项数据。ClassForm1调用ClassHuffmanTree生成Huffman树并且生成Huffman编码。ClassHuffmanTree调用ClassHuffmanTreeNode来初始化各个节点。ClassHuffmanTree调用ClassStack保存产生的编码并逆向输出。三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）=1\*GB3①抽象数据类型具体实现的函数原型说明：节点类型；publicclassHuffmanTreeNode{publiccharch;//存放当前的字母publicintfrequentness;//存放当前的字母的频度publicHuffmanTreeNodeleft;//定义一个指向左子树的类型publicHuffmanTreeNoderight;//定义一个指向右子树的类型publicHuffmanTreeNodeparent;//定义一个指向双亲的类型publicHuffmanTreeNode(charch2,intfrequentness2)//初始化节点{ch=ch2;//字母赋值frequentness=frequentness2;//频度赋值left=null;//初始化左子树right=null;//初始化右子树}}2、Huffman算法classHuffmanTree{publicHuffmanTreeNoderoot,p,r;//定义一个指向节点的变量publicDatafrequentnessTable;//创建频度表publicHuffmanTree()//构建一个空树{root=null;//初始化操作frequentnessTable=newData();//初始化频度表}publicintSearchTree()//HuffmanTree搜索{Stack<char>HuffmanCode=Stack<char>;//定义并初始化栈while(r==root)//退出条件{r=p.parent;//r变量移动至双亲节点if(p==r.left)//判断是否左子树HuffmanCode.Push('1');//进栈1elseHuffmanCode.Push('0');进栈0p=p.parent;//p变量移动至双亲节点}}publicHuffmanTreeNodenode1=null;//函数会使用到的变量publicHuffmanTreeNodenode2=null;//函数会使用到的变量}=2\*GB3②关键操作实现的伪码算法:中序遍历查找伪代码：现访问根节点，如果不是目标值，然后访问左子树，若左子树全部被访问过或者不存在则访问右子树，同时栈进栈，保存走过的路径，若右子树全部被遍历过或者不存在，栈退栈，指针退回上一次的访问点位继续第一步操作，直至左右子树无法访问且栈为空的时候，算法结束。没找到的话返回-1。③关键的程序流程图：四、【测试结果（Testing）】(10%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）测试过程：打开程序主界面：2.选择功能，比如把人类语言转换为赫夫曼编码：4.输入要转换的语句，如THISPROGRAMISMYFAVORITE,然后摁start按钮，结果如下：这个结果表明，我们所编写的程序可以把特定的一段人类语言报文转化为相应的赫夫曼编码，并且经过我们的计算，转换成的赫夫曼编码是正确的。但是为了验证是否能把对应赫夫曼编码转换成对应的人类语言，我们又进行一下测试：打开程序并选择功能：HuffmancodeHumanLanguage,然后在对应的框内填入：0011111010001001000110001110101100010000110101000010110001000100100000101100100100000101001001100001011011011000101实验结果如下：实验结果表明此程序也可以把相应的赫夫曼编码转换为对应的人类语言，并且转换的是正确的人类语言。测试成功！此程序实现了一个简单的赫夫曼编码/译码器，并且能根据一段电文设计赫夫曼编码，并能用该编码对一段给定的电文进行译码。五、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）杨扬（20091120048）部分：工作：算法构思、设计、实现；编写代码。总结：=1\*GB3①这次实验使我对栈、树的遍历搜索算法有了熟练的掌握。=2\*GB3②在设计程序时，摆在我面前有以下几个难题：首先，如何用C#生成符合一定规则的HuffmanTree？这个问题花了我不少时间，最后通过定义一个树的Class来避免指针的缺失，解决了此问题。其次，在生成HuffmanTree之后，如何实现HuffmanTree遍历算法呢？这个问题到没话我太多时间，因为它的原理很简单，就是直接对变量进行赋值操作即可。最后，通过什么方式控制Huffman编码以正确的顺序输出呢，于是我想到了栈。利用栈在每一次寻址之后得到一个结果进行进栈操作，然后在所有操作完成后进行退栈操作，很完美地使Huffman编码逆向输出。=3\*GB3③本次试验，小组配合得很好，一起讨论并解决了不少问题，使得程序更佳完善。一个人不可能面面俱到，这时团队的帮助与合作尤为重要，一定要虚心求教，认真倾听别人的意见，不要认为自己做的东西才是最好的，只有这样才能进步。许德胜（20091120210）部分：在本次实验中我参与了前期的算法设计，少部分代码的编写，负责后期程序的调试和测试以及测试结果总结，实验报告的撰写。通过本次实验,我深刻的理解和领悟了赫夫曼树的构造，有以下几点：首先根据给定的n个权值{n1,n2,…,ni}构成n课二叉树的集合F={T1，T2，…,Ti}，其中每课二叉树Ti中只有一个带权为ni的根节点，其左右子树均为空。然后在F中选取；两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上的权值之和。再然后在F中删除这两棵树，同时将新到的二叉树加入F中。最后重复以上步骤，直到F中只含一棵树为止，这棵树便是赫夫曼树。在惊叹于这种树的构造的巧妙之时，我们又从书上得知了它的一个重要的应用—赫夫曼编码。这正是本次实验核心的算法。目前进行快速远距离通信主要手段是电报，利用赫夫曼编码我们可以在保证编译正确的情况下使得传输的电文总长为最短。由于在构成赫夫曼树后，为求编码需从叶子节点出发走一条从叶子到根的路径，而为译码需从根出发走一条从根到叶子的路径。则对每个节点而言，既需知双亲的信息，又须知孩子节点信息。由此设定了上述存储结构。在进行程序测试，刚开始我发现所有的菜单全是在一起的，所以我们就设计了一下，把功能菜单和输入框分开，最后做成一个比较好操作的界面。还有原来输入框是可以一打开程序就可以输入内容的，那样的话容易引起程序的崩溃，所以最后我们增加了HuffmanLanguage—>Huffmancode,HuffmancodeHumanLanguage两个按钮，只有选择了两个其中一个功能时，对应的输入框才能进行的数据的输入。最后在杨扬和我的团结合作之下，终于做出了现在这个程序的版本，虽然也许还有许多的不足，但我觉得我们尽力去做了，所以我们还是很开心的面对这次实验结果的。六、【项目运作描述（