北邮数据结构实验报告实验三哈夫曼.pdf

《北邮数据结构实验报告实验三哈夫曼.pdf》由会员分享，可在线阅读，更多相关《北邮数据结构实验报告实验三哈夫曼.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、北京邮电大学信息与通信工程学院第 1页数据结构实验报告实验名称：实验三哈夫曼编/解码器的实现学生姓名：侯在鹏班级：2012211120班内序号：13学号：2012210583日期：2013 年 12 月 10 日1实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化(Init)：能够对输入的任意长度的字符串 s 进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的

2、赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：I love data Structure,I love Computer。I will try my best to study data Structure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2.程序分析北京邮电大学信息与通信工程学院第 2页2.1 存储结构程序实现了基本的编解码功能输入字符串选择

3、工作目标编码解码相关树，表显示编码上根节点向下，左 0 右 1根据不同字符在尾端相应排位,获得自己的编码，存储。解码上依次读取数据 0 或 1，循序寻找，最后在存储中找到对应编码的字符，输出再重新读取下一数字开始的数码在哈夫曼树编码这个程序中，所有数据用的存储结构都是顺序存储结构，其中包括顺序表和树（三叉树）树的存储结构如下：（输入的字符串为 assddddffffffffgggggggggggggggg）012345678ASC9115100102103weight124816371531lchild-1-1-1-110234rchild111111567parent-55-6-7-8678

4、0上结构图中，填充为黄色的部分为写入内存中的部分。每一行的部分为数组的下标，左边部分为所定义的结构的成员。其中有的结点的父节点的下标是一个负数，用来说明该节点是该节点的父节点的左孩子，正数说明的是该节点的父节点的右孩子。父节点这零的节点说明该节点是该哈夫曼树的根节点。画出树的结构如下画所示：（结点中第一个数表示这个字符的 ASC编码，第二个数字表示权值）北京邮电大学信息与通信工程学院第 3页37153116102897110041152876543210000010111红色箭头表示父指针，黑色箭头表示孩子指针由上面的图可知，原字符串编码后的二进制编码为11101111111111011011

5、011010101010101010100000000000000000字符串中出现的所有的字符的编码如下：a1110；s1111；d110；f10；g02.2 关键算法分析2.2.12.2.1 选择两个最小权值的函数选择两个最小权值的函数算法伪代码：算法伪代码：(1)初始化最小权值 min1,min2.可引用变量 x,y。(2)遍历哈夫曼树，比较字符的权值与 min1,min2 的大小。若小于 min1，则将 min1 值赋给min2,字符权值赋给 min1,同时改变权值最小的结点编号 x,y.若大于 min1 同时小于 min2,则将字符权值赋给 min2，改变 y 值。源代码：源代码：v

6、oid Huffman:SelectMin(int&x,int&y,int a,int b)/选出两个权值最小的结点int j,min1,min2;min1=min2=-1;for(j=a;jb;j+)if(HTreej.parent=-1)if(HTreej.weightmin1|min2=-1)if(min1!=-1)北京邮电大学信息与通信工程学院第 4页min2=min1;y=x;min1=HTreej.weight;x=j;elseif(HTreej.weightmin2|min2=-1)min2=HTreej.weight;y=j;时间复杂度：时间复杂度：遍历链表，时间复杂度为 O（

7、n）2.2.2.2.2.2.创建哈夫曼树创建哈夫曼树算法伪代码：算法伪代码：(1)创建一个长度为 2*n-1 的三叉链表(2)将存储字符及其权值的链表中的字符逐个写入三叉链表的前 n 个结点的 data 域，并将对应结点的孩子域和双亲域赋为空(3)从三叉链表的第 n 个结点开始，i=n(3.1)从存储字符及其权值的链表中取出两个权值最小的结点 x,y，记录其下标 x,y。(3.2)将下标为 x 和 y 的哈夫曼树的结点的双亲设置为第 i 个结点(3.3)将下标为 x 的结点设置为 i 结点的左孩子，将下标为 y 的结点设置为 i 结点的右孩子，i 结点的权值为 x 结点的权值加上 y 结点的权

8、值，i 结点的双亲设置为空(4)根据哈夫曼树创建编码表void Huffman:CreateHTree(int a,int n)HTree=new HNode2*n-1;for(int i=0;in;i+)HTreei.weight=ai;HTreei.LChild=-1;HTreei.RChild=-1;HTreei.parent=-1;int x,y;for(int i=n;i2*n-1;i+)SelectMin(x,y,0,i);/从0i中选出两个权值最小的结点HTreex.parent=HTreey.parent=i;/用两个权值最小的结点生成新结点，新节点为其双北京邮电大学信息与通信

9、工程学院第 5页亲HTreei.weight=HTreex.weight+HTreey.weight;/新结点的权值为其孩子的权值的和HTreei.LChild=x;HTreei.RChild=y;HTreei.parent=-1;时间复杂度：时间复杂度：在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为 O(n),故该函数的时间复杂度为 O（n2）2.2.32.2.3 编码函数编码函数算法伪代码：算法伪代码：（1）从 a 开头的字符开始，逐一对 a 中的字符进行编码（2）在编码表中查找与当前字符对应的字符（3）如果找到了与当前字符对应的编码表中的字符，将其编码追加到解码串的末尾。（4）

10、重复以上步骤，直到所有待编码串中的字符都编码完毕（5）输出编码后的字符串void Huffman:Encode(char a,char*d,int n,int j)/a为原始字符串，d 为编码后的哈夫曼编码字符串，n 为编码表长度，j 为原始字符串的长度for(int m=0;mj;m+)for(int i=0;in;i+)if(am=HCodeTablei.data)d=strcat(d,HCodeTablei.code);cout编码后的哈夫曼编码字符串为：dendl;时间复杂度：时间复杂度：设待编码字符串长度为 n，编码表中字符个数为 m，则复杂度为 O（n*m）2.2.42.2.4 解

11、码函数解码函数算法伪代码：算法伪代码：(1)得到指向哈夫曼树的根结点的指针和指向待解码串中的第 1 个字符的指针(2)逐个读取待解码串中的字符，若为 0，则指向哈夫曼树当前结点的指针指向当前结点的左孩子，若为 1，则指向当前结点的右孩子(3)指向待解码串的指针指向解码串中的下一个字符，直到指向哈夫曼树结点的指针的孩子结点为空(4)如果指向哈夫曼树结点的指针的孩子结点已经为空，则将叶子结点下标对应北京邮电大学信息与通信工程学院第 6页的字符追加到解码串中。(5)输出解码串源代码：源代码：void Huffman:Decode(char*s,char*d,int n)/解码。s 为编码后的数组，d

12、 为解码后的数组while(*s!=0)int parent=2*n-1-1;/根结点while(HTreeparent.LChild!=-1)if(*s=0)parent=HTreeparent.LChild;elseparent=HTreeparent.RChild;s+;*d=HCodeTableparent.data;d+;时间复杂度：时间复杂度：设待解码串长度为 n，则复杂度为 O(n)2.2.52.2.5 统计字符权值统计字符权值算法伪代码：算法伪代码：（1）取出字符串第一个字符，与 data中元素比较。若字符与 data中元素相同，权值+1，若不同，则将该字符加入 data中。（

13、2）取出下一个字符，重复步骤（1）。直到字符串末尾。源代码：源代码：Huffman:Huffman(char str,char dat,int wei,int n,int&t)/str为原始字符串，dat为 data数据，wei数据相应的权值，n 为字符串长度t=0;/计数器datt=str0;weit=0;for(int m=0;mn;m+)bool sign=0;for(int x=0;xt+1;x+)if(strm=datx)weix+;sign=1;北京邮电大学信息与通信工程学院第 7页if(sign=0)t+;datt=strm;weit=1;t+;datt=0;时间复杂度：时间复杂

14、度：O（n）2.3 其他3.程序运行结果主函数流程图：开始调用菜单函数等待用户输入字符串利用用户输入的字符串创建哈夫曼树和编码表对输入的字符串编码对编码串解码输出解码后字符串北京邮电大学信息与通信工程学院第 8页测试条件：输入I love data Structure,I love Computer。I will try my best to study dataStructure.测试结论：能正确的编码、解码、输出解码后的字符串，并计算出压缩比为 0.518519.4.总结本次实验将书上的哈夫曼只是实践在程序中，通过编写，修改等等繁复的工作，我对哈夫曼树相关知识记得更牢，学的更扎实了。只看书上的只是难以了解很多意想不到的问题。编写前先看了一遍书，然后在网上看了一些相关知识，最后编写，中间遇到了一些逻辑错误较为麻烦，其他错误花了一些时间。程序上大体结构较为清晰，功能比较齐全。程序还有很多不足，时间以及个人能力关系，一些功能没有实现，代码上不够简洁，有些部分效率低，都有待改进。计算编码前后的压缩比结束