资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
1.实验要求利用二叉树结构实现哈夫曼编/解码器。基本要求:1. 初始化(Init):能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并 建立哈夫曼树2建立编码表(CreateTable):利用已经建好的哈夫曼树进行编码,并将每个字符的编码输 出。3. 编码(Encoding):根据编码表对输入的字符串进行编码,并将编码后的字符串输出。4. 译码(Decoding):利用已经建好的哈夫曼树对编码后的字符串进行译码,并输出译码结 果。5计算输入的字符串编码前和编码后的长度,并进行分析,讨论赫夫曼编码的压缩效果。2. 程序分析2. 1存储结构静态三叉链表WeightLehi IdRchildparent2.2程序流程(或程序结构、或类关系图等表明程序构成的容,一般为流程图等)2. 2. 1 流程图初始化各节点的Lchild, Rchild和parem2. 2. 1.伪代码1. 输入进行编码的字符串2. 遍历字符串,并为叶子节点权重赋值3依次对各字符进行哈弗曼编码,自下往上,若是双亲节点左孩子则编码前插入0, 若是双亲节点右孩子则编码钱插入1。4.显示各字符的哈弗曼编码。5对字符串进行编码,挨个遍历字符,找到相应的编码,复制到总的编码里,最后输出 字符串的编码。6对字符串的哈弟曼码进行译码。自上往下,若是0,则递归到左孩子,若是T, 则递归到右孩子,知道叶子节点,输出该叶子节点代表字符,再继续遍历。7分析存占用情况。若用ASCII编码,每个字符占1个字节,即8bit,该情况下占用存 就是(字符长度)*8。若用哈弗曼编码,占用存是各(字符频度)* (每个字符占用位数) 之和。2.3关键算法分析该程序关键算法即哈弗曼编码,语句如下:void CHTree::huffmancode()int i;if(n=1)return;m=2*n-l;for(i=l;i=n; i+) /叶子节点的初始化 hti. parent=0;hti. lchild二0;hti. rchiId二0;for (: i=m; i+) /非叶子节点的初始化hti weight二0;hti parent=0;hti lchild二0;hti. rchild=0;for(i=n+l; i=m;+i)/构造哈夫曼树sl=select (i-1) ;/函数在 ht 1到 ht i-1中选择 parent 为 0 且 weight 最小的结点, 并将结点序号返s,并将htsl. parent设为Ts2二select (iT);htsi parent=i:hts2 parent=i;hti. lchild=sl;hti. rchild=s2;hti weight=htsl weight+hts2. weight;int c,f;for(i=l;i=n;+i) for (c=i.f=ht i. parent; f!=0;c=ftf=htf. parent)/逆向求叶子结点的 哈夫曼编码if(htfj. lchild=c) stri. insert (0, ,0,1); 在字符串 stri的第 0 位置插 入字符“0”elsestri. insert(0, ,0,1); 在字符串 stri的第 0 位置插 入字符“1”分析:这段语句实现的功能是根据统计出来的各字符的频度,建立哈弗曼。建立哈弗曼 树的过程如程序所展示,每次选取权重最小且无双亲节点的节点组合,并将其权重之和赋绐 其双亲节点,加入到总结中进行下次判断。哈弗曼树建立完全以后,开始对各字符进行编码, 从下往上,以叶子节点为起始点,若它是双亲节点的左孩子,其编码前插入0,若是右孩 子则插入T。再判断双亲节点使其双亲节点的左孩子还是右孩子,以此类推直到根节点。 依次对每个字符进行上述过程编码。算法复杂度:最好情况为只有根结点和叶子节点:0 (n)最坏情况为满二叉树情况:0 (n*logn/2)3 程序运行结果分析3編阳译码后所得字符:usnniscrhocrh手苻編 A刃为 mii0ni 1 ii in 1 win wwHii 1 wi uni 1 wn m wibki i h幘输入进行編码的宇符串:h (us n ru ge r hae rhhu茫zn娜期下字符 M哈夫曼编码Mil1031116111100101119010碍鬣篇瑚点內悝滋2kU huffxn茹码所占丙存数为4讣込 请按拄意键妣取首先,要求用户输入进行编码的字符串,遍历字符串,并为叶子节点权重赋值。然后,依次 对各字符进行哈弟曼编码,自下往上,若是双亲节点左孩子则编码前插入0,若是双亲节 点右孩子则编码钱插入T。屏幕上显示各字符的哈弟曼编码。接下来对字符串进行编码, 挨个遍历字符,找到相应的编码,复制到总的编码里,最后输出字符串的编码。对字符串的 哈弗曼码进行译码。自上往下,若是0,则递归到左孩子,若是1,则递归到右孩子, 知道叶子节点,输出该叶子节点代表字符,再继续遍历。最后分析存占用情况。若用ASCII 编码,每个字符占1个字节,即8bit,该情况下占用存就是(字符长度)*8。若用哈弗曼 编码,占用存是各(字符频度)* (每个字符占用位数)之和。3.总结4. 1实验的难点和关键点本实验的难点和关键点是进行哈弟.曼的编码与译码。编码之前先要遍历字符串,并统计 各字符出现的频度。这里就要区分目前的字符是否出现过,若出现过则字符权重加一,若没 有出现则在结构体数组的当前末尾添加该元素。统计完频度以后开始编码。根据哈弗曼树的 特点,每次选取结点里权重最小,且双亲不为0的节点结合,依次添加直至根节点。编码过 程是从下往上。对于某字符所在叶子节点,若是双亲节点左孩子则编码前插入0,若是双 亲节点右孩子则编码钱插入T。直到双亲节点移动到根节点,所得到的编码即为该字符的 编码。译码过程是编码的逆过程。依次读取哈弗曼码,自上往下,若是0,则递归到左孩 子,若是T,则递归到右孩子,知道叶子节点,输出该叶子节点代表字符,再继续遍历。4. 2心得体会通过哈弗曼树的程序编写,更加深入了解了树这种数据结构的特点,并且熟悉了这种数 据结构的应用。同时,也对哈弗曼编码的优越性能有了根本的解释。附:程序代码#include#includeusing namespace std;define max 1000/哈夫曼数存储的最大叶子节点数 int judge;/初始化过程中用于判断字符是否出现过 struct HTNodechar c;int weight;int lchiId,rchiId,parent;;class CHTreepublic:CHTree()ht=NULL;void Init();void huffmancode();int select(int i);void Display();void canculateO ;void encodingO ;void decodingO ;private:HTNode* ht;int m;int n;/叶子结点数int si:int s2;string 3;/存储输入的字符串string code;/存储对字符串的编码string str max ; /存储叶子结点的哈夫曼编码;void CHTree::Init()int i=l;/用于记录叶子节点个数int j=0;int x=0t ru;cout请输入进行编码的字符串:endl;cina;int l=a.1 ength():ht = (HTNode*)malloc(max)*sizeof (HTNode) ;/分配 MAXSIZE 个叶子结点的存储空间 while(xl) /统计字符出现的次数judge=l;for(j=0;ji;j+) if(htj.c=ax)/如果字符ax已经出现过,则记录,权值加1 htj weight+;judge=0;break;if(judge) /若字符没有出现过,字符入列,且权值设为1n=i;/记录叶子节点数hti. weiht=l;hti. c=ax;i+; x+;int CHTree: : select (int i)函数在 ht 1到 ht i中选择 parent 为 0 且 weight 最小的结 点,并将结点序号返回int j=l:int k=l:int s;while(htj. parent!=0)j+;S=j;k二j+1;while(ki)return s;if(htj. weighthtkJ. weight)htj. parents;/如果第二次和第二次以后循环中发现有比htj权值还小的,将htj. parent 重新设为 0j=k;/始终令“htj“为二者中权值小的那一个 s=j;htj. parent=-l;/如果 ht j是权值较小的,将 htj的 parent 记为T,elseS=j;htj parent=-l;k+;return s; void CHTree: :huffmancodeOint i;if(n=l)return;m=2*n-l;for(i=l; i=n; i+)/叶子节点的初始化 htiparent=0;hti. lchild=0;hti. rchild=0;for(: i=m; i+) /非叶子节点的初始化hti weight二0;hti parent=0;hti lchild二0;hti. rchild=0;for(i=n+l; i=m;+i)/构造哈夫曼树sl=select (i-1) ;/函数在 ht 1到 ht i-1中选择 parent 为 0 且 weight 最小的结点, 并将结点序号返s,并将htsl. parent设为Ts2=select(i-1);ht si parent=i;hts2 parent=i;hti. lchild=sl;hti. rchild=s2;hti. weight=htsi, weight+hts2. weight;int c,f;for(i=l;i=n;+i) for(c=i,f=ht i. parent; f !=0;c=f,f=htf. parent)/逆向求叶子结点的哈夫曼编码if(htf. lchild=c) stri.
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号