哈夫曼树.doc

北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验三哈夫曼树学生姓名： 吴淳班 级： 2011211106班班内序号： 27学 号： 2011210180日 期： 2012年11月29日1 实验要求一、实验目的：掌握二叉树基本操作的实现方法；了解哈夫曼树的思想和相关概念；培养使用二叉树解决实际问题的能力。二、实验内容：利用二叉树结构实现哈夫曼编/解码器1.初始化（Init）：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。2.建立编码表(CreatTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。3.编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4.译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。5.打印(Print)：以直观的方式打印哈夫曼树(选作)。6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。测试数据如下：I love data structure.I love computer.I will try my best to study data structure.7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2.程序分析2.1存储结构哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。且哈夫曼树是一棵只有度为0和2的结点的正则二叉树。一棵有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的一位数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以可以使用一个静态三叉链表来存储哈夫曼树。class Huffmanprivate:HNode*HTree;/哈夫曼树HCode*HcodeTable;/编码表public:void Init(int a,int n);/初始化,void CreatTable(char character,int n);/创立编码表void Encoding(char*s,int n);/编码int Decoding(char*s,int n);/解码void Selectmin(HNode*hTree,int n,int &i1,int &i2);/挑出最小的;二叉树是由一个根结点和两棵互不相交的左右子树构成： 【图一】正则二叉树的结构图静态三叉链表C+描述如下：struct HNode int weight; /结点权值int parent; /双亲指针int lchild; /左孩子指针int rchild; /右孩子指针;示意图1：int rchildint lchildint parentint weightT parentT rchildT lchild data 【图二】示意图1编码表的结点结构：struct HCodechar data; /编码表中的字符char code100; /该字符对应的编码;示意图2：char code100char data 【图三】示意图22.2关键算法分析一关键算法：(1).初始化函数（void Huffman:Init(int weight,int n)）算法伪代码：1. 创建一个长度为2n-1的三叉链表；2.获得输入字符串的第一个字符，并赋予其相应权值，同时将其双亲、左孩子、右孩子值赋为-1;3.重复上一步；4.合成哈夫曼树：i=n；Selectmin(HTree,i,x,y)；合成HTreex和 HTreex。5. 若满足i2*n-1，重复上一步，每次i+。(2)创建编码表void Huffman:CreatTable(char character,int n) 算法伪代码： 1.初始化编码表 2.i=0；HcodeTablei.data=characteri；child=i；parent=HTreei.parent；k=0; . 3 .如果parent!=-1; 3.1如果当前结点是其双亲的左孩子，则其对应的编码为0，否则为1;3.2.k+;3.3 将当前结点的parent值赋给child值，child的parent值赋给parent值; 3.4重复上面三步； 4.若in,重复2和3； 5. 最后一位编码=0; 6. 将已完成的编码倒序 7输出编码表(3). 选择两个最小权值（void Huffman:Selectmin(HNode*HTree,int n,int &i1,int &i2)）算法语言描述：1. 从下标为0的结点开始，寻找第一个没用过的结点2. 从第一个没用过的结点的后一个结点开始，找下一个没用过的结点；3. 比较两个结点的权值，将权值较小的结点赋给i1，另一个赋给i2;4. 对这两个结点之后的结点进行遍历，并最终将最小的赋给i1，第二小的赋给i2;（4）编码函数（void Huffman:Encoding(char*s,int n)） 算法语言描述： 1. 当*s不为空时； 2. 在编码表中查找与当前字符对应的字符； 3如果找到了与当前字符对应的编码表中的字符，将其编码增加到到解码串的最后，同时输出该编码值； 4. 重复以上步骤，直到所有待编码串中的字符都编码完毕。（5）解码函数（int Huffman:Decoding(char*s,int n)） 算法伪代码：1. 若*s!=0，进行以下步骤；2. parent=2*n-2;3. 若HTreeparent.lchild!=-1，进行以下步骤；4. 若*s为0，则parent指向当前parent结点的左孩子;若为1，则指向当前parent结点的右孩子;否则，输出对不起，此处编码值输入错误！按任意键退出程序；s+;5. 重复步骤3,4；6. 输出当前结点对应的编码值；7. 重复以上所有步骤。二代码详细分析：(1).初始化函数（void Huffman:Init(int weight,int n)）关键代码：HTree=new HNode2*n-1;先初始化n个叶子结点：for(int i=0;in;i+) HTreei.weight=weighti; HTreei.parent=-1; HTreei.lchild=-1; HTreei.rchild=-1;int x,y;开始建哈夫曼树：for(int i=n;i2*n-1;i+) 比较挑选权值最小的两个结点：Selectmin(HTree,i,x,y);合成哈夫曼树：HTreex.parent=HTreey.parent=i;HTreei.weight=HTreex.weight+HTreey.weight;HTreei.parent=-1;HTreei.lchild=x;HTreei.rchild=y;(2)创建编码表void Huffman:CreatTable(char character,int n)关键代码：生成有n个结构体的数组：HcodeTable=new HCoden;/对n个叶子结点循环：for(int i=0;in;i+) HcodeTablei.data=characteri; int child=i;给parent赋值： int parent=HTreei.parent;int k=0；自下而上找双亲结点：while(parent!=-1) 若为左孩子：if(child=HTreeparent.lchild) HcodeTablei.codek=0;若为右孩子：if(child=HTreeparent.rchild) HcodeTablei.codek=1; k+;自动寻找结点：child=parent;parent=HTreechild.parent; 最后一位编码置空：HcodeTablei.codek=0; l3i=k;对编码值将进行翻转：char code100;for(int u=0;uk;u+) codeu=HcodeTablei.codek-u-1; for(int u=0;uk;u+) HcodeTablei.codeu=codeu;cout字符编码表为:endl;for(int i=0;in;i+)coutHcodeTablei.data的哈夫曼编码为HcodeTablei.codeendl;(3). 编码函数（void Huffman:Encoding(char*s,int n)） 关键代码：coutendl输入的字符串转化为哈夫曼编码为:endl;输入字符串从前向后读取，编码:while(*s) 依次在编码表里找寻字符:for(int i=0;in;i+) if(*s=HcodeTablei.data) 输出编码:for(int m=0;HcodeTablei.codem!=0;m+)coutHcodeTablei.codem;l2=l2+l3i;s+; （4）解码函数（int Huffman:Decoding(char*s,int n)）关键代码：while(*s!=0)根节点在HTree中的下标：int parent=2*n-2;找寻对应结点：while(HTreeparent.lchild!=-1)if(*s=0) parent=HTreeparent.lchild; else if(*s=1) parent=HTreeparent.rchild;else coutendl对不起，此处编码值输入错误！按任意键退出程序endl;return 0; s+;coutHcodeTableparent.data; 三、计算关键算法的时间、空间复杂度1）初始化函数:时间复杂度为O(n);2）创建编码表: 时间复杂度为O（n2）;3) 选择两个最小权值:时间复杂度为O（n）;4）编码函数: 时间复杂度为O（n2）;5) 解码函数: 待解码串长度为n，则复杂度为O(n)。3.程序运行结果1.测试主函数流程，流程图如图4所示图【4】主函数流程图程序运行结果如下：【图5】程序运行结果1 【图6】程序运行结果22. 测试条件：根据系统提示输入字符串，然后解码系统自行进行解码及相关运算。3.测试结论：程序基本运行良好，且若输入编码值不存在，会自动提醒，不会出现运行问题。4总结1.调试时出现的问题及解决的方法调试时，出现的一个较为重要的问题是在Selectmin函数的编写过程中，久久没有思路。后来虽然写出来了初步版的，却发现无法运行。后来几经完善，却仍有漏洞。最后，我想起老师讲的PPT上有相关代码，此次改动后才成功运行。当时看见老师给的代码以后，才发觉自己的想法存在很多漏洞。虽然也考虑到一开始i1、i2经遍历选出来后，要比较其大小并可能要交换。但却没有在i2选出时的结点范围中将i1除去，这样会造成i1和i2相等，从而导致结果的错误甚至于无法运行。其次，一开始也没有考虑解码时输入的字符串中可能有编码表里不存在的码值，致使输入不合适时，程序就无法正常运行。后来我将Decoding函数返回值改为int类型，若在某一步解码时，发现*s为空，则报告错误，同时返回0并结束该函数。2.心得体会经过这次实验，我了解了哈夫曼树的创建过程，了解了自行编写一种不等长编码的方法，对于曾多次在多科课本中出现的通过编解码来压缩解压缩的问题有了实质性的深刻认识，相信对于以后此类问题的学习会有很大的促进作用。对于本次试验中多次出现的字符串的多种使用方法，我通过翻阅去年学习的c+书也有了更为详尽的认识，第一次如此频繁的自行将字符数组的指针作为函数形