数据结构实验报告2

1、!-实验名称:学生姓名:数据结构实验三树题目2班 级:班内序号:学 号:日 期:1. 实验要求实验目的：掌握二叉树基本操作的实现方法 了解哈夫曼树的思想和相关概念 培养使用二叉树解决实际问题的能力实验内容：利用二叉树结构实现赫夫曼编/解码器。基本要求如下：1、 初始化（Init）:能够对输入的任意长度的字符串s进行统计，统计每个字符的 频度，并建立赫夫曼树2、 建立编码表（CreateTable）:利用已经建好的赫夫曼树进行编码，并将每个字符 的编码输出。3、编码（Encoding）:根据编码表对输入的字符串进行编码，并将编码后的字符串 输出。4、译码（Decoding）:利用已经建好的赫夫曼

2、树对编码后的字符串进行译码，并输 出译码结果。5、打印（Print）:以直观的方式打印赫夫曼树（选作）测试数据：1 love data Structure, I love Compu ter Structure.提示：12。I will try my best to study data6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压 缩效果。、用户界面可以设计为“菜单”方式：能够进行交互。、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。2. 程序分析2.1存储结构静态三叉链表存储：weightLChildRChildparent0123

3、哈夫曼编码的存储结构2.2程序流程（或程序结构、或类关系图等表明程序构成的内容，一般为流程图2.3关键算法分析1. 建立了一个类 class Huffma n p rivate:HNode* HTree;HCode* HCodeTable;p ublic:void SelectMin(int &x,int &y,int a,int b); / 权值最小的两个字符void CreateHTree(i nt realcou nts,i nt n);/ 创建哈夫曼树!-void CreateCodeTable(char counts,int n);/ 创建哈夫曼编码表编码void R

4、everse(char c);/ 逆序void En code(char * s,char * d);void Decode(char * s, char *d,int n);解码-Huffma n()delete HTree;delete HCodeTable; 析构函数；2. 建立哈夫曼树 void Huffma n:CreateHTree(i nt realco un ts,i nt n)HTree=new HNode2* n-1;/根据权重数组初始化哈夫曼树for(i nt i=0;i vn ;i+)HTreei.weight=realco un tsi;HTreei.LChild=-

5、1;HTreei.RChild=-1;HTreei. paren t=-1;int x,y;if(n >1)/因为如果只有一种字符就直接它自个儿了for( i=n ;iv2* n-1;i+)/建立哈夫曼树!-SelectMi n(x,y,O,i);找出最小权重的两个字符HTreex. paren t=HTreey. paren t=i;HTreei.weight=HTreex.weight+HTreey.weight;HTreei丄Child=x;HTreei.RChild=y;HTreei. paren t=-1;时间复杂度：n3. 选取权值最小的两个值 void Huffma n:S

6、electMi n(i nt &x,i nt &y,i nt a,i nt b)int j,mi n1,mi n2;min 1=mi n2=-1;for(j=a;j<b;j+)if(HTreej. paren t=-1)if(HTreej.weight<mi n1|mi n2=-1)if(mi n1!=-1)!-mi n2=mi n1;y=x;min 仁HTree|j.weight;x=j;elseif(HTreej.weight<mi n2|mi n2=-1)min 2=HTreej.weight;y=j;时间复杂度：n4. 哈夫曼编码表 void Huff

7、ma n:CreateCodeTable(char coun ts,i nt n) int i;HCodeTable = new HCode n;if(nv2)!-HCodeTable0.data=cou ntsO;HCodeTable0.code0='0'HCodeTable0.code1='0'coutvv"字符及其编码："vvcounts0vv" 0"<<endl;elsefor(i=0;i vn ;i+)HCodeTablei.data=cou ntsi;Hcoutvv"字符及其编码：&quo

8、t;vvcountsivv"int child=i;int paren t=HTreei. parent;int k=0;while( paren t!=-1)if (child=HTree pare ntLChild)HCodeTablei.codek='0'elseHCodeTablei.codek='1'k+;child=parent;paren t=HTreechild. parent;HCodeTablei.codek='0'Reverse(HCodeTablei.code);k=0;while(HCodeTablei.cod

9、ek!='0')cout<<HCodeTablei.codek;k+;coutvve ndl;时间复杂度：n5.逆序 void Huffma n:Reverse(char c)int i=0,j=0;int temp;while(cj+1!='0')j+;while(i<j)temp=ci;ci=cj;cj=te mp;i+； j-；时间复杂度：n6。对输入的字符串进行编码void Huffma n:E ncode(char * s,char * d)/ 编码coutvv"哈夫曼编码为："float sum=0;/统计字节数

10、int n=0;while(*s!='0') int i=0;!-while(HCodeTablei.data!=*s)i+;for (i nt j=0;HCodeTablei.codej!='0'j+)*d=HCodeTablei.codej;cout<<*d;d+;sum+=1;s+;n+;*d='0'coutvve ndl;coutvv"编码前字符串所占比特位为："<<8* nvve ndl;coutvv"编码后的字符串所占比特位为"vvsumvvendl;coutvv&quo

11、t;压缩比为："vvsum/(8* n)vve ndl;7。对已编译好的字符串进行解码coutvve ndl;!-void Huffma n:Decode(char * d, char *s,i nt n) 解码coutvv"解码为:H.cout<<*s;if(nv2) while(*d!='0') coutvvHCodeTable0.data;d+;while(*d!='0')int parent=2*n-1-1 ; / 根节点在 HTree 中的下标while(HTree pare ntLChild!=-1)if(*d=

12、9;0')paren t=HTree paren t.LChild;elseparen t=HTree paren t.RChild;d+;*s=HCodeTable paren t.data;S+；!-coutvve ndl;&主函数，包含了交互的操作。void main()stri ng buffer;char*d;char*s;int i,q,j=O, n=Ojealco un tsN;char cou ntsN, cN;d=&c0;in t cou nt127;for(i=0;i<127;i+)coun ti=0;coutvv"请输入初始化的字符

13、串（英文）:n"vvendl;getli ne(ci n,buffer);s=&buffer0;while(bufferj!='0')!-count bufferj+;/不同字符的个数j+； for(i=0;iv127;i+)if(cou nti!=0)realcou ntsj=cou nti;/提取出真正存在的字符的权值 coun tsj=i;/ j+;n+;Huffma n h;menu: cout<<"2-察看编译前的内容"<<endl;docout<<"1-察看编译后的文字（包含压缩比）

14、"vvendl;!-coutvv"请输入想要的操作的编号"<<endl;cin>>q;switch(q)case 1:h.CreateHTree(realco unts,n);h.CreateCodeTable(co unts,n);h.E ncode(s,d);break;case 2:d=&c0;s=&buffer0;h.Decode(d,s, n);break;丽i人 初贻化的字符串决丈|鶴勲while (q);goto menu;3. 程序运行结果分析 loue data stvueture I laue canpu

15、tev, I ul 11 t iy ny Lest t d study data stT'ueturc 霸麟h09111 OOtlaioeeUOHiM11 Bl1010Q10009LIMHia1911101010meikiuianil1010110110lUHUaieaiiiioeiinum mniteo00O00iiii0iiiiieQLiioiieGiae9iQiieiQi81101001109301001190111000eiQisail101laieiiiieQiAQisdeeoeeiiiieii11leaniQLieoi90091111113910101011eiiieie LUllUllULlUUWUlUUUUUUUlllUHUlUldltllllUlllUHUlUlklblllbMUULlblUlLUULtblHULltlUllUlUUl teiiieeoainmeioiiiiQeiiQdnieQiiiemieeeeiieoieeeiaiiQieioiioiaeiieaeAiAQiieai tiooeaiotQOiiieiLQtoiiioioae謁码前节鴻所占*4丰年664蕃f