搜索
北京邮电大学电信工程学院第1页2008级数据结构实验报告实验名称：实验三树学生姓名：班级：班内序号：学号：日期：20013年11月26日1．实验要求实验目的通过选择下面两个题目之一进行实现，掌握如下内容：掌握二叉树基本操作的实现方法了解赫夫曼树的思想和相关概念学习使用二叉树解决实际问题的能力实验内容利用二叉树结构实现赫夫曼编/解码器。基本要求：1.初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2.建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3.编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4.译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5.打印(Print)：以直观的方式打印赫夫曼树（选作）6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。2.程序分析哈夫曼树结点的储存结构除了二叉树所有的双亲域parents，左子树域lchild，右子树域rchild。还需要有字符域word，权重域weight，编码域code。其中由于编码是一串由0和1组成的字符串，所以code是一个字符数组。进行哈夫曼编码首先要对用户输入的信息进行统计，将每个字符作为哈夫曼树的叶子结点。统计每个字符出现的次数（频度）作为叶子的权重，统计次数可以根据每个字符不同的ASCII码。并根据叶子结点的权重建立一个哈夫曼树。建立每个叶子的编码从根结点开始，规定通往左子树路径记为0，通往右子树路径记为1.由于编码要求从根结点开始，所以需要前序遍历哈夫曼树，故编码过程是以前序遍历二叉树北京邮电大学电信工程学院第2页为基础的。同时注意递归函数中能否直接对结点的编码域进行操作。编码信息只要遍历字符串中每个字符，从哈夫曼树中找到相应的叶子结点，取得相应的编码。最后再将所有找到的编码连接起来即可。译码则是将编码串从左到右诸位判别，直到确定一个字符。这可以用生成哈夫曼树的逆过程实现。由于每个字符的编码各不相同，且编码也是个字符串，所以只要遍历编码串，从哈夫曼树中找到相应的叶子结点，取得相应的字符再将找到的字符连接起来即可。2.1存储结构哈夫曼树结点储存结构wordweightparentLChildRChild哈夫曼树顺序存储结构wordweightlchildparentsrchild0A35-13-11B25-13-12C15-14-13\0400414\0753-122.2关键算法分析1、统计字符的频度自然语言描述：1)取出字符串中的一个字符2)遍历所有初始化的哈夫曼树结点3)如果结点中有记录代表的字符且字符等于取出的字符，说明该字符的叶子存在，则将该结点的权加一。4)如果所有结点均没有记录字符与取出字符一致，说明该字符的叶子不存在，则将结点的字符记为取出字符，并将权重设为1.5)重复（1）（2）（3）（4）步骤，如此遍历字符串中的所有字符。伪代码：1.for(inti=0;i字符长度;i++)1.1for(intj=0;j字符长度;j++)1.1.1if(WordStr[i]==HuffTree[j].word)1.1.1.1权重++1.1.1.2break;1.1.2否则取字符域为空的结点1.1.2.1HuffTree[j].word=WordStr[i];1.1.2.2HuffTree[j].weight=1;1.1.2.3叶子数++;1.1.2.4break;结束时间复杂度O(n2),空间复杂度S(0)2、构造哈夫曼树北京邮电大学电信工程学院第3页自然语言描述：1)将n个权值的叶子结点存放到数组huffTree的前n个分量中2)通过统计字符频度的算法给n个结点赋权值3)将数组huffTree中出叶子结点外的结点初始化：左右子树、双亲域为-1；权值为0；字符编号域为\0。4)不断将两棵子树合并为一棵子树，并将新子树的根节点顺序存放到数组huffTree的前n个分量的后面。伪代码描述：1.数组huffTree初始化，除叶子节点外，所有元素结点左右子树、双亲域为-1；权值为0；字符编号域为\0。2.进行n-1次合并2.1在二叉树集合中选取两个权值最小的根结点，其下标分别即为j1和j22.2将二叉树j1和j2合并为一棵新的二叉树结点k时间复杂度O(n)，空间复杂度S(2)3、为每个叶子结点编码自然语言描述：1)初始化一个字符数组Code暂存每个叶子结点的编码。2)从叶子结点开始，如果是哈夫曼树的左孩子，则将编码表中的code值赋为0，否则为13)将指针层层上移，重复2）直到根结点4)将所得编码逆置，并将编码最后一位赋为’\0’5)进行下一叶子结点的编码算法时间复杂度O(n2)，空间复杂度S(60)4、为信息编码自然语言描述：1)定义字符串str1储存编码2)遍历信息字符串中的每一个字符3)对每一个字符，将其与huffTree前n个叶子结点的word域逐个比较，发现相同的则将该结点的编码串code连接到str1串的末尾。4)遍历信息字符串结束，输出str1算法时间复杂度O(n2)，空间复杂度S(2)5、译码自然语言描述：1)从编码串str1第一个字符开始和数组huffTree第一个结点的编码域第一个字符进行比较。2)若相等，则继续比较两者的后续字符3)否则，从str1第一个字符与huffTree第二个节点的编码域第一个字符进行比较。4)重复上述过程，当huffTree结点中的字符全部比较完毕则说明本趟匹配成功，输出huffTree结点的word域值。5)重复上述过程，当str1中的字符全部比较完毕，译码结束。本趟匹配开始位置i主串CodeStr回溯。。。。。北京邮电大学电信工程学院第4页huffTree[k+1]huffTree[k]j回溯算法时间复杂度O(n2)1.程序运行结果测试主函数流程：测试条件：问题规模n的数量级为1。测试内容：IlovedataStructure,IloveComputer,IwilltrymybesttostudydataStructure.测试结论：测试的功能有：建立哈夫曼树、对每个字符进行编码、对信息字符串进行编码、对编码串进行译码。各项功能均能正常运行。界面的跳转也能实现。编码前信息总长度为400bits，编码后的长度为320bits。由于哈夫曼编码采用不开始测试的字符串为：Ilovedatastructure,Ilovecomputer.Iwilltrymybesttostudydatastructure建立哈夫曼树建立编码表编码解码输出长度，比较压缩效果结束北京邮电大学电信工程学院第5页等长编码，有效缩短了编码长度，节省了空间。2.总结调试时出现的问题及解决的方法（1）字符串在函数中的存储在给字符进行编码时，由于对于字符串储存的理解不清楚，以致于在生成解决方案是出现了“屯屯屯”的字样，经过查阅相关资料得知，是因为字符串末尾没有加’\0’所致。（2）字符串编码的位数由于对于字符串存储位数的不够清晰，走入了以往的经验错误，在储存编码时总是少一位，经检查发现是在逆置时数组的个数没有搞清楚（3）字符串的输入输出问题最初字符串是用cin输入，后来发现此种方式只适用于单个次，遇到’\0’即停止，后来调用了cin.getline才有效的解决了这个问题心得体会哈夫曼树又称做最优二叉树，它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。在n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优二叉树。权值越大的结点离树根越近的二叉树才是最优二叉树。哈夫曼树是根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。再做本实验的过程中，也出现了很多问题，主要是要编写程序，因为程序比较长，再编写的过程中，经常会出现一些错误，比如：把一些字母编写错误，没区分大小写，漏句，符号写错或漏写等等。我想这些都是一些比较低级的错误，主要是自己对程序还不是很熟悉，再做实验的时候还不够细心所导致的吧。这些都是要求我们再做实验的过程中不断总结经验教训，加深对程序的了解和喜爱，不要粗心大意。通过本实验我也总结了一些经验，那就是再修改程序的时候，不要死转牛角尖，要从大处着手，逐步深入，逐个修改，还要用联系的观点来看程序，有时候一个地方错了，会引起很多个错误，而显示错误的句子本身可能会没有错误，只是与之相关联的一些语句发生了错误而引起的错误。这时我们就不要死盯着原来的地方不放，而应该找出与之相关联的语句。哈夫曼树的应用非常广泛，在通信中，采用0,1的不同排列来表示不同的字符，而哈夫曼树在数据编码中的应用，若每个字符出现的频率相同，则可以采用等长的二进制编码，若频率不同，则可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种最优二叉树，它的编码也是一种最优编码，在哈夫曼树中，规定往左编码为0，往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。通过这次试验，感觉自己有了很大的提高，再看程序时也没有以前那样不知所云了，修改程序也有了一定的提高，虽然本课程是有点难，但相信功夫不负有心人，只要付出努力，一定会取得成功。下一步的改进（1）程序中多次使用了遍历数组或对数据进行逐个比对，循环的次数可以通过计算再减少，提高时间效率。（2）下次争取使用菜单选择工具，选择要进行的功能，