北邮数据结构实验三

北京邮电大学信息与通信工程学院第1页北京邮电大学电信工程学院第1页2009级数据结构实验报告实验名称：实验三哈夫曼树学生姓名：班级：班内序号：学号： 日期：2010年12月2日1．实验要求实验目的：通过选择下面两个题目之一进行实现，掌握如下内容：·掌握二叉树基本操作的实现方法·了解赫夫曼树的思想和相关概念·学习使用二叉树解决实际问题的能力实验内容：利用二叉树结构实现赫夫曼编/解码器。基本要求：初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。打印(Print)：以直观的方式打印赫夫曼树（选作）计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：IlovedataStructure,IloveComputer.IwilltrymybesttostudydataStructure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2.程序分析2.1存储结构 主存储结构：单链表，三叉链表。另外在某些函数中也用到了其他的存储结构，如创建编码表时栈的应用和打印树时队列的应用等等。 下面对主存储结构进行简析： 在对树进行初始化的过程中，首先统计字符出现频率，然后依次生成叶子结点，按权值从小到大排列。存储使用的单链表带双头结点（其作用后文将提到），插入叶子结点后，第一个头结点处于链首，第二个头结点处于链尾，如下图所示（忽略某些数据）：↓firstpr↓/\/\////////////ch1w1////////////chnwn…下一步由单链表转化为三叉链表。忽略只有一个叶子结点的特殊情况（这种情况的处理在后文会有提到），在第二头结点后面连接新的结点，将合适的结点从单链上“摘下”连接到新结点的左右孩子上。之后依此类推，在链尾插入新结点，与前面的区别是需要在叶子结点和已连接的根结点（pr之后的结点）中寻找合适的结点。该过程中的一种情况如下图所示：↓firstpr↓w2w2ch2w1ch1////////////ch6w6////////////chnwn…w’2/\w’3w4ch4w’1w5ch5w3ch3示意图中忽略了叶子结点中空的左右孩子指针。事实上此时非根结点的next指针依然有效，只是在存储结构中已不起作用。当结点的组合进行结束时，单链表只含第一头结点、第二头结点和最终得到的根结点。该根结点即为所求哈夫曼树的根结点。此时释放掉两个头结点，头指针前移两位，即为哈夫曼树的根结点。至此，哈夫曼树构造完成。示意图如下：↓firstwwi1wi2wi3wi4wi5……2.2关键算法分析建树又可分为3个子过程：频率统计、创建叶子结点单链表、叶子结点连接成树。其中频率统计比较简单，使用一个256个元素的数组，对应unsignedchar0~255个值，并全部置初值为0。输入的字符串由首至尾读取，对读取的每个字符对应数组元素自增1即可。该算法问题规模只与字符串长度有关，时间复杂度为O(n)，空间复杂度O(1)（循环条件）。单链表的创建过程也不很复杂。对存在的每个字符建立叶子结点，并按权值递增有序插入单链表，再将字符的叶子指针（其作用将在后文提到）指向该结点。插入位置选择的代码如下： p=first;while(p->next->next) { if(p->next->weight>=CodeList[i].freq) break; else p=p->next; }需要强调的是，有序插入时应寻找权值大于当前叶子结点权值的前一位置（或表尾）插入，此时工作指针p应指向插入位置的前一结点，即需对p->next指针指向的结点的权值进行判断。另外，此时第二头结点尚未利用，置于表尾，所以判断工作指针指向真正的表尾的条件是p->next->next==NULL。这里的问题规模为频率非0的字符个数，处理所有字符的时间复杂度为O(n2)（相当于插入排序法），空间复杂度为O(1)（工作指针，临时指针）。单链表建立完成，下面详细说明单链表转换成树的过程。伪代码如下：1.循环直至“头指针->第一头结点->第二头结点->根结点->NULL” 1.1定义p1等于第一头结点的next指针,p2等于第二头结点的next指针； 1.2如果p2为空，或权值最小的两个叶子结点的权值均小于已生成根结点的最小权值 1.2.1建立新结点作为根结点 1.2.2根结点权值等于权值最小的两个叶子结点权值之和 1.2.3与权值最小的两个叶子结点建立父子关系 1.2.4左子树编码为0，右子树编码为 1.2.5 1.2.6新结点插入表尾 1.2.7第一头结点next指针后移两步 后两种情况类似。这里我们还需要考虑一种特殊情况。如果读入的字符串中只存在一种字符，即单链表中只含有单一叶子结点时，无法找到“两个”权值最小的叶子结点，故需作特殊处理。在执行上述一般情况的代码前加入判断以处理特殊情况。相关的伪代码如下：1.若第一头结点的next指针指向的结点的next指针等于第二头结点的头指针（即两头结点间只含一个结点） 1.1建立新结点作为根结点； 1.2叶子结点权值赋值给根结点权值； 1.3左、右孩子指针指向同一叶子结点； 1.4叶子结点父指针指向新结点； 1.5叶子结点编码为0； 1.6新结点next域置空； 1.7新结点插入表尾； 1.8第一头结点next指针后移一步；通过上述处理，可以将特殊情况与一般情况统一对待，以方便执行后续的操作。而且经处理后的单链表满足循环结束条件，不会进入之后的循环。2.3其他关于树的打印：考虑到控制台的限制，不可能打印得非常形象，并且由于窗口宽度只是固定的80个字符，当树比较庞大时，可能会无法将整棵树全部打印出来。粗略计算了一下，如果单行最多打印8个节点，那么每个结点可以打印10个字符，只要不打印叶子结点对应的编码，长度是足够用的。如果打印16个结点的话，空间就有些狭窄了。这样一来，我们可以将树分层打印，先打印前4层。若第4层上存在非叶子结点，再依次打印以这些非叶子结点为根的子树，直到所有结点打印完成。显然，这是一个递归的过程。这样打印出来虽然并不是非常直观，但是至少能比较清楚的反映出树中双亲和孩子的关系。实现树的打印的核心思想是二叉树的层序遍历。使用队列的存储结构，存储待打印结点的地址。每层打印完毕，结点指针依次出队，同时其左右孩子指针依次入队，准备打印下一层。3.程序运行结果开始键盘读入任意键开始键盘读入任意键创建哈夫曼树类的对象键盘读入字符串输入为空？yes初始化哈夫曼树其他键盘读入按键按键为？结束执行对应操作no‘j’‘a’~’i’测试结果：<初始化界面模拟>哈夫曼树编码字符串程序请按任意键开始请输入要编码的字符串：IlovedataStructure,IloveComputer.IwilltrymybesttostudydataStructure.初始化完成！<选项界面模拟>请选择您要执行的操作：A.生成编码表B.对已输入的字符串进行编码C.对编码后的字符串进行解码D.打印哈夫曼树E.打印编码表F.打印字符串原码G.打印字符串编码H.打印字符串译码I.分析原码与编码的长度J.退出程序<测试结果模拟>哈夫曼树打印如下：<注：此处西文字体若设为TimesNewRoman会导致错位从而影响显示效果>A84/\BC3351/\/\DEFG16172328/\/\/\/\HIJKLMNO888911121612/\/\/\/\t/\/\HA8/\HBHC44o/\HFHG22v/\HNHO11wpIA8/\IBIC44l/\IFIG22s/\INIO11ibJA8/\JBJC44a/\JFJG22m/\JNJO11C,KA9/\KBKC45/\/\KDKEKFKG2223cS.yMA12/\MBMC66u/\MFMG33dIOA12/\OBOC66re每个结点自上至下依次为：编号、权值、对应的字符。由于窗口大小有限，无法完整地显示整棵树，故拆分显示。子树的根结点对应为上一层同编号的结点，如结点“MA”对应结点“M”，结点“KOA”对应结点“KO”等等。编码表：（每行依次为：字符，字符的值，字符的编码，字符的出现频率）3211016,440101111.46011102C670101101I73101113S83011012a9701004b980011111c99011002d100101103e10111116i1050011101l10800104m109010102o11100004p1120001111r11411106s115001102t11610011u11710106v118000102w1190001101y121011113原码为：IlovedataStructure,IloveComputer.IwilltrymybesttostudydataStructure.编码为：10111110001000000001011111101011001001000100110011011001110101001100100