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

X=#X会有大孽能传孽院故据储构实分抠告（本实验项目B□序号学号姓名成绩123指导教师..（签名）,C□实验难度A□方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）学期_____________任课教师________________实验题目实验五树的原理及其应用小组长____________________联系电话___________电子邮件完成提交时间年月日

四、【测试结果Testing]10%本部分应包括对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结测试过程

1.打开程序主界面:回X«Translater ofHuffman Code栩扬在德胜CopyRi ght@2•选择功能，比如把人类语言转换为赫夫曼编码:

4.输入要转换的语句，如THIS PROGRAM IS MYFAVORITE,然后握start按钮,结果如下:这个结果表明，我们所编写的程序可以把特定的一段人类语言报文转化为相应的赫夫曼编码，并且经过我们的计算，转换成的赫夫曼编码是正确的但是为了验证是否能把对应赫夫曼编码转换成对应的人类语言，我们又进行一下测试:打开程序并选择功能Huffman code-Human Language,然后在对应的框内填入:实验结果如下:Translater ofHuffman CodeHuffman CodeHuman LanguageTHISPROGRAMISMY FAVORIEModeHuffman Code-Human LanguageHuman Language-Huffman CodeStartHelp AboutExit畅扬许德胜CopyRi ght@实验结果表明此程序也可以把相应的赫夫曼编码转换为对应的人类语言,并且转换的是正确的人类语言测试成功！此程序实现了一个简单的赫夫曼编码/译码器，并且能根据一段电文设计赫夫曼编码，并能用该编码对一段给定的电文进行译码

五、【实验总结】10%本部分应包括自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得杨扬20091120048部分工作算法构思、设计、实现；编写代码总结

①这次实验使我对栈、树的遍历搜索算法有了熟练的掌握

②在设计程序时，摆在我面前有以下几个难题首先，如何用C#生成符合一^定规则的Huf缶anTree这个问题花了我不少时间，最后通过定义一个树的Class来避免指针的缺失，解决了此问题其次，在生成Huf缶anTree之后，如何实现HuffmanTree遍历算法呢？这个问题到没话我太多时间，因为它的原理很简单，就是直接对变量进行赋值操作即可最后，通过什么方式控制Huffman编码以正确的顺序输出呢，于是我想到了栈利用栈在每一次寻址之后得到一个结果进行进栈操作，然后在所有操作完成后进行退栈操作，很完美地使Huffman编码逆向榆出

③本次试验，小组配合得很好，一起讨论并解决了不少问题，使得程序更佳完善一个人不可能面面俱到，这时团队的帮助与合作尤为重要，一定要虚心求教，认真倾听别人的意见，不要认为自己做的东西才是最好的，只有这样才能进步许德胜20091120210部分:在本次实验中我参与了前期的算法设计，少部分代码的编写，负责后期程序的调试和测试以及测试结果总结，实验报告的撰写通过本次实验，我深刻的理解和领悟了赫夫曼树的构造，有以下几点首先根据给定的n个权值{n1,n2,…，ni}构成n课二叉树的集合F={T1,T2,-,Ti},其中每课二叉树Ti中只有一个带权为ni的根节点，其左右子树均为空然后在F中选取；两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上的权值之和再然后在F中删除这两棵树，同时将新到的二叉树加入F中最后重复以上步骤，直到F中只含一棵树为止，这棵树便是赫夫曼树在惊叹于这种树的构造的巧妙之时，我们又从书上得知了它的一个重要的应用一赫夫曼编码这正是本次实验核心的算法目前进行快速远距离通信主要手段是电报，利用赫夫曼编码我们可以在保证编译正确的情况下使得传输的电文总长为最短由于在构成赫夫曼树后，为求编码需从叶子节点出发走一条从叶子到根的路径，而为译码需从根出发走一条从根到叶子的路径则对每个节点而言，既需知双亲的信息，又须知孩子节点信息由此设定了上述存储结构在进行程序测试，刚开始我发现所有的菜单全是在一起的，所以我们就设计了一下，把功能菜单和输入框分开，最后做成一个比较好操作的界面还有原来输入框是可以一打开程序就可以输入内容的，那样的话容易引起程序的崩溃，所以最后我们增加了HuffmanLanguage—Huffman code,Huffman code-Human Language两个按钮，只有选择了两个其中一个功能时，对应的输入框才能进行的数据的输入最后在杨扬和我的团结合作之下，终于做出了现在这个程序的版本，虽然也许还有许多的不足,但我觉得我们尽力去做了，所以我们还是很开心的面对这次实验结果的

六、【项目运作描述（Operate）】（10%）（本部分应包括项目的成本效益分析，应用效果等的分析）

1.用户使用手册操作过程

1.打开程序主面板；Human Language-Huffman Codes^|Translater ofHuffman CaXHuffman CodeHuman LanguageStart杨扬许德胜CopyRight@Help若不懂操作，可以点击■■■按钮，会出现帮助文档;冈Help.I__JYou canenter humanlanguage inthe secondtextbox whenyou wangtto thanslateit intoHuffmanCode.You canenter Huffman Code inthe firsttextbox whenyou wantto translateit intohemanlanguage.Copy Right@杨扬许德胜About点击.按钮，可以查看产品相关信息:点击按钮，将退出程序Exi t

2.点击HuffmanCode一-〉Human Language按钮选择相应的功能然后在对应的输入框内输入要编码或者译码HumanLanguage—HuffmanCode的数据吧Translater ofHuffmanCode■01Huffman CodeHumanLanguageModeHuffman Code-Human LanguageStartHelp AboutExitHuman Language-HuffmanCode杨扬许德胜CopyRight@Start然后掘,即可在相应的框内显示对应的编码或译码的数据本程序所占空间16KB,运行所占内存极少，运行环境要求也比较低，windows98以上版本的系统就行实现此程序用了六个实验课时，以及课下大概四个课时的时间，所用时间也不算太多运行此程序可以实现了一个简单的赫夫曼编码/译码器，并且能根据一段电文设计赫夫曼编码，并能用该编码对一段给定的电文进行译码运行界面也比较友好的

2.运作分析

①在成本方面有培训相关设计营销人员成本人力资源的消耗（成员基本工资）软件售后服务支持通信，交通费用

②在效益方面有应用后大大地减少了编码空间的浪费，提高了编码空间的利用率给我们提供难得的实践机会软件使用相关费用

③应用效果可改写成服务器版本，使之在传递数据时能够节约带宽为后续的编程实现奠定了算法基础

3.用户反馈

①王同杰（软件学院09级学生）程序总体上看来没有大的问题，能比较流畅的完成我们需要的工作，性能较为稳定

②钟威（软件学院09级学生）程序所占用的内存比我想象的少很多，运行环境要求不高，运行时几乎没有延迟，界面友好

③王涛（软件学院09级学生）总体不错，不过也有一些需要注意的问题打开程序后若输入内容为空也撼开始按钮，会导致程序崩溃（此BUG我们小组会在后续版本中改进）云南大学软件学院2010学年秋季学期《数据结构实验》成绩考核表学号—姓名:本人承担角色课题分析，算法设计，程序编写，后期调试，完成实验报告评分项目评分指标分值得分实验构思10%

1.实验目的明确

52.实验内容理解透彻、对实验所涉及到5的知识点分析到位实验设计15%

1.有对基本数据结构的抽象数据类型定5义

2.实验方案设计完整，数据结构、算法5选择合理

53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图实验实现25%

51.代码编写规范、风格统

一、注释清楚易读

2.程序运行正常，测试结果正确

153.界面友好、易于操作、有较强的容错5性实验报告撰写

1.内容详实无缺漏，文字流畅、图表清510%楚

2.实验结果分析客观、详细，实验体会5真实可信，对原实验方案的改进和对实验内容的发散性思考个人工作量

1.个人完成工作量1530%

2.个人技术水平

103.团队合作精神5实验运作10%

1.有一定用户群

52.应用前景分析5综合得分满分100分指导教师年月日注此表在难度为c时使用，每个成员一份云南大学软件学院2010学年秋季学期《数据结构实验》成绩考核表学号_姓名—本人承担角色课题分析，算法设计，后期调试，完成实验报告评分项目评分指标分值得分实验构思10%

1.实验目的明确

52.实验内容理解透彻、对实验所涉及到5的知识点分析到位实验设计15%

1.有对基本数据结构的抽象数据类型定5义

2.实验方案设计完整，数据结构、算法5选择合理

53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图实验实现25%

51.代码编写规范、风格统

一、注释清楚易读

2.程序运行正常，测试结果正确

153.界面友好、易于操作、有较强的容错5性实验报告撰写

1.内容详实无缺漏，文字流畅、图表清510%楚

2.实验结果分析客观、详细，实验体会5真实可信，对原实验方案的改进和对实验内容的发散性思考个人工作量

1.个人完成工作量1530%

2.个人技术水平

103.团队合作精神5实验运作10%

1.有一定用户群

52.应用前景分析5综合得分满分100分指导教师年月日注此表在难度为C时使用，每个成员一份下面的内容由学生填写，格式统一为，字体楷体，行距固定行距18,字号小四，个人报告按下面每一项的百分比打分难度A满分70分，难度B满分90分

一、【实验构思Conceive]10%本部分应包括描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识

1.数据结构算法的知识•树的定义•树的节点和边的表示•树的存储结构•树的分类二叉树一》Heffman树•树的遍历前序遍历，中序遍历，后序遍历

2.面向对象的程序设计相关知识•C#基本语法知识•类的定义，实例化•对象的生成调用•变量的传递

二、【实验设计Design】20%本部分应包括抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系本实验创建了四个类Form类〃用于窗口的初始化，控制各控件的属性和动作Data类〃用于本程序所需的频度表数组的生成以及调用Huf缶anTree类〃用于构造Huffman树以及控制树的各项操作HuffmanTreeNode类//用于构造Huffman树的节点抽象数据类型的功能规格说明窗口初始化pr i vate voi dForm1_Load objectsender,EventArgs e转换模式pr ivate void button1_CI ickobject sender,EventArgs epr ivate voidbutton1_CI ickobject sender,EventArgs e开始按钮:privatevoidbutton3_CI ickobject sender,EventArgs e声明全局数组pub Ii cmember[]a II Members=new member

[27];定义结构体数组pub Iic structmember{pub Iic char ch;//保存频度字符pub Ii ci ntfrequentness;//保存频度}Data的构造函数创建Huffman树pub Iic DataData类中的寻找当前最大项函数pub Iic int FindMax0Data类中的寻找当前第二大项函数:pub Iic i ntFindSecondMax0Data类中的计算当前有效项的数目的函数publ ic i ntCount HuffmanTreeNode类中创建节点的构造函数:pub Iic HuffmanTreeNode char ch2,i ntfrequentness2HuffmanTree类中定义的节点类型pub Iic Huffman!reeNode root,p,r；HuffmanTree类中实例化一个Data类来构造频度表pub Ii c DatafrequentnessTabIe;HuffmanTree类中的构造函数，创建一棵Huffman树pub Ii cHuffmanTree HuffmanTree类中的成员函数，对于指定的字符实行中序遍历，遍历完之后逆向回溯得到该字符的Huffman编码pub Ii ci ntSearchTree HuffmanTree类中的两个节点变量，用于判断左右子树pub Ii ci ntSearchTree主程序模块伪代码说明创建新的字母频度表f requentnessTabI e=new Data0;创建栈来倒装输出赫夫曼编码Stackchar HuffmanCode=Stackchar；退出程序this.Close子程序伪代码说明HuffmanTree:构建Huffman》对pub Ii cHuffman!reeNode root,p,r;核心程序段（生成Huffman编码）while（r二二root）r=p.parent;if p==r.leftHuffmanCode.Push f11;//栈中存1e IseHuffmanCode.Push CO1;//栈中存0p=p.parent;返回栈中元素个数pub Iicint count{get{return Ii st.Count;}}主程序模块与各子程序模块间的调用关系Class Forml调用Class Data初始化程序所要的各项数据Class Forml调用Class HuffmanTree生成Huffman树并且生成Huffman编码CI ass HuffmanTree调用Class HuffmanTreeNode来初始化各个节点CI assHuffmanTree调用Class Stack保存产生的编码并逆向输出

三、【实现描述（Implement）］（30%）（本部分应包括抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析）

①抽象数据类型具体实现的函数原型说明

1、节点类型；pub Ii c cI assHuffman!reeNode（pub Ii ccharch;〃存放当前的字母pub Iic int frequentness;//存放当前的字母的频度pub Iic Huffman!reeNode left;//定义一，个指向左子树的类型pub Ii cHuffman!reeNode r ight;//定义一个指向右子树的类型pub Iic Huffman!reeNode parent;//定义一个指向双亲的类型pub Iic Huffman!reeNodecharch2,intfrequentness2//初始化节点ch=ch2;〃字母赋值frequentness=frequentness2;〃频度赋值left=nul I;//初始化左子树right二nu II;//初始化右子树}}、2Huffman算法cIassHuffmanTree{pub Ii cHuffman!reeNode root,p,r;//定义一，个指向节点的变量pubI i cDatafrequentnessTable;//创建频度表pub Ii cHuffmanTree//构建一个空树root=nul I;〃初始化操作f requentnessTabIe=new Data;//初4台彳匕频度表}pub IicintSearchTree//HuffmanTree搜索Stackchar Huf缶anCode=Stackchar;//定义并初始化栈while r二二root//退出条件r=p.parent;//r变量移动至双亲节点if p=r.left//判断是否左子树HuffmanCode.Push「；//进栈1e IseHuffmanCode.Push0;进栈0p二p.parent;//p变量移动至双亲节点pub Iic Huffman!reeNode nodel=nu II;//函数会使用到的变量pub IicHuffman!reeNode node2=nu II;//函数会使用到的变量

②关键操作实现的伪码算法中序遍历查找伪代码现访问根节点，如果不是目标值，然后访问左子树，若左子树全部被访问过或者不存在则访问右子树，同时栈进栈，保存走过的路径，若右子树全部被遍历过或者不存在，栈退栈，指针退回上一次的访问点位继续第一步操作，直至左右子树无法访问且栈为空的时候，算法结束没找到的话返回7

③关键的程序流程图:N1晤对读取根节点NII N指针改为栈顶N。