数据结构实验哈夫曼树编码

1、实验四哈夫曼树编码一、实验目的1、掌握哈夫曼树的一般算法；2、掌握用哈夫曼树对字符串进行编码；3、掌握通过哈夫曼树对字符编码进行译码得过程。二、实验基本要求1、设计数据结构；2、设计编码算法；3、分析时间复杂度和空间复杂度三、程序实现此程序中包含六个函数：Select()、HuffmanTree()、BianMa()、BianMa2()、YiMa()、Sum(),其功能及实现过程如下：#includestructelement/哈夫曼树结点类型intweight;intlchild,rchild,parent;structChar/字符编码表信息charnode;intweight;charc

2、ode20;voidSelect(elementhT,int&il,int&i2,intk)在hT中查找最小值及次小值intminl=9999,min2=9999;il=i2=0;for(inti=0;ik;i+)if(hTi.parent=-l)if(hTi.weightminl)min2=minl;i2=il;minl=hTi.weight;il=i;elseif(hTi.weightmin2)min2=hTi.weight;i2=i;voidHuffmanTree(elementhuffTree,Charzifuma,intn)/构建哈夫曼树inti,k,i1,i2;for(i=0;i2

3、*n-1;i+)/初始化huffTreei.parent=-1;huffTreei.lchild=-1;huffTreei.rchild=-1;for(i=0;in;i+)/构造n棵只含有根结点的二叉树huffTreei.weight=zifumai.weight;for(k=n;k2*n-1;k+)/n-1次合并Select(huffTree,i1,i2,k);/在huffTree中找权值最小的两个结点i1和i2huffTreei1.parent=k;/将i1和i2合并，则i1和i2的双亲是khuffTreei2.parent=k;huffTreek.weight=huffTreei1.we

4、ight+huffTreei2.weight;huffTreek.lchild=i1;huffTreek.rchild=i2;voidBianMa(elementhuffTree,Charzifuma,intn)根据哈夫曼树编码inti,m,k,j,l;chartemp20;if(n=1)zifuma0.code0=0;zifuma0.code1=0;elsefor(i=0;in;i+)j=0;k=huffTreei.parent;l=i;while(k!=-1)if(huffTreek.lchild=l)tempj+=0;elsetempj+=1;l=k;k=huffTreek.parent

5、;k=j-1;for(m=0;mj;m+)zifumai.codem=tempk-;zifumai.codem=0;voidBianMa2(Charzifuma,charzifu,charbianma,intn)根据编码表对字符串编码inti,j,k,m;i=k=0;while(zifui)for(j=0;jn;j+)if(zifui=zifumaj.node)m=0;while(zifumaj.codem)bianmak+=zifumaj.codem+;i+;bianmak=0;voidYiMa(elementhuffTree,Charzifuma,charbianma,charyima,i

6、ntn)根据编号的码元译成字符串inti,j,k;i=j=0;if(n=1)while(bianmai+)yimaj+=zifuma0.node;elsewhile(bianmai)k=2*(n-1);while(!(huffTreek.lchild=-1&huffTreek.rchild=-1)if(bianmai+=0)k=huffTreek.lchild;elsek=huffTreek.rchild;yimaj+=zifumak.node;yimaj=0;voidSum(charzifu,Charbianma,int&n)计算字符串中字符种类的个数及其出现次数inti,j;i=j=0;w

7、hile(zifui)for(intk=0;kj;k+)if(bianmak.node=zifui)bianmak.weight+;break;if(k=j)bianmaj.node=zifui;bianmaj+.weight=1;i+;n=j;voidmain()intn,i;chara50,b200,c50;elementhuffTree100;Charw50;coutvv请输入需要编码的字符串:n;cin.getline(a,49);Sum(a,w,n);coutvv该字符串中共有vvnvv类字符。其表示及出现频率分别为：n;coutvv字符t频率n;for(i=0;ivn;i+)cou

8、tvvwi.nodevvtvvwi.weightvvn;HuffmanTree(huffTree,w,n);coutvv哈夫曼树结点排列为:n;coutvvnumtweighttparenttlchildtrchildn;for(i=0;iv2*n-1;i+)coutvvivvtvvhuffTreei.weightvvt;coutvvhuffTreei.parentvvtvvhuffTreei.lchildvvtvvhuffTreei.rchildvvn;coutvv该字符的编码表为:n;BianMa(huffTree,w,n);coutvvnodetweighttcoden;for(i=0;

9、ivn;i+)coutwi.nodetwi.weightt;intj=0;while(wi.codej)coutwi.codej+;coutn;BianMa2(w,a,b,n);coutvv该字符串编码后为:n;coutbendl;YiMa(huffTree,w,b,c,n);coutvv该字符串经编码后译码得:n;coutcendl;四、运行结果假设输入的一串字符串为：abcbcaddabbacda则编译后它的编码为：111000100011010111101011000111根据它的编码译码结果为：abcbcaddabbacda晴输入需要编码的字符串：DDiello该字符串匸了共有4娄字符.匡表尹政已现顷率分别询：字符我e112p1旳夫曼树结点排列为:riniTiweightparenCLuhildrLliild014-1一丄114-1一丄”z5-1-1315-1-14269q19pJ65C-1J45叵字符的编怕袤为:nodewbiglitcodeli160e1011211p1IS陆字符弗编阳后为，0001111113陰宁符串经编码万译码-争htlluPressanykeytocontinue