数据结构实验哈夫曼编译码.docx

1、数据结构实验哈夫曼编译码实验九 哈夫曼编译码1.实验目的（1）掌握哈夫曼树的特性。（2）掌握哈夫曼树的建立算法。（3）掌握哈夫曼编码算法。（4）掌握哈夫曼译码算法。2.实验内容（1）建立哈夫曼树。（2）输出哈夫曼编码。（3）根据输入串进行哈夫曼译码3.实验要求（1）根据实验内容编写程序，上机调试并获得运行结果（2）撰写实验报告4.关键步骤思路与算法(1)构造哈弗曼树算法思路；若已知有n个叶结点，则构造的哈夫曼树有2n-1个结点。先输入字符集中的n个字符（叶结点）和表示其概率分布的权值，存储在ht(HuffNode型）数组的前n个数组元素中.然后将2n-1个结点的双亲和左右孩子均置为0。在所有的

2、结点中，选取双亲为0，且具有最小权值m1和次小权值m2的两个结点，用p1和p2指示这两个结点在数组中的位置.将根为htp1和htp2的两棵树合并，使其成为新结点hti的左右孩子，hti的权值为最小权值m1和次小权值m2之和；htp1和htp2的双亲指向i。重复上述过程，共进行n-1次合并就构造了一棵Huffman树。当进行n-1次合并时，产生n-1个结点，次放入ht数组中，数组的下标从n到2n-2算法如下；1./构造哈弗曼树2.intHuffman(HuffNode*hf)3.4.inti,k,n,m1,m2,p1,p2;5.printf(请输入元素的个素:);6.scanf(%d,&n);7

3、.for(i=1;int节点值：,i);11.scanf(%c,&(hfi.data);/hf可以当做数组来用,因为hfi在这里不是一个指针，而是一个结构体，所以可以直接使用.运算符来调用data12.printf(t权重:);13.scanf(%d,&(hfi.weight);14.15.for(i=1;i=2*n-1;i+)/*对数组的父节点以及左右节点进行初始化,总共有2n-1个结点，初始权值结点n个，父节点n-1个*/16.17.hfi.parent=0;18.hfi.lch=0;19.hfi.rch=0;20.21.for(i=n+1;i=2*n-1;i+)22.23.m1=m2=3

4、2767;/假设这两个权值一开始为int的最大值24.p1=p2=1;/位置初始值设为第一个节点的位置25.for(k=1;ki;k+)26.27.if(hfk.parent=0)28.29.if(hfk.weightm1)30.31.m2=m1;/重新置次小值32.p2=p1;/重新置次小值对应的位置33.m1=hfk.weight;/重新置最小值34.p1=k;/重新置最小值的位置35.36.elseif(hfk.weightm2)37.38.m2=hfk.weight;/重新置次小值39.p2=k;/重新置次小值的位置40.41.42.43.hfp1.parent=i;/把最小的位置的节

5、点的父节点位置设为i44.hfp2.parent=i;/把次小的位置的节点的父节点位置设为i45.hfi.weight=m1+m2;/置新的生成的父节点的权重46.hfi.lch=p1;/设置新生成的节点的左节点47.hfi.rch=p2;/设置新生成的节点的左节点48.49.printf(Huffman树已经建立成功!);50.returnn;51.(2)编码算法思路；从Huffman树的叶结点hti（1in）出发，通过双亲parent找到其双亲htf，通过htf的left和right域，可知htihtf的左分支还是右分支，若是左分支，生成代码0；若是右分支，生成代码1，代码存放在数组cds

6、tart中，然后把htf作为出发点，重复上述过程，直到找到树根为止。显然，这样生成的代码序列与要求的编码次序相反，为了得到正确的代码，把最先生成的代码存放在数组的第n（虽然各个字符的编码长度不同，但都不会超过n）个位置处，再次生成的代码放在数组的第n-1个位置处，依此类推。用变量start指示编码在数组cd中的起始位置，start初始值为n，生成一个代码后，start的值就减1算法如下；1.voidEncoding(HuffNodeht,HuffCodehcd,intn)/这里的hcd存有n个初始权值节点代码数组的数组，n是初始权值节点的个数;2.3.HuffCoded;/存储每一个初始权值节

7、点的代码数组4.inti,c,f,k;5.for(i=1;i=n;i+)6.7.d.start=n+1;/把d的start下标设为代码数组的末尾位置，因为存储代码时是从最下面的叶子结点到根，所以在存储是需要倒序存储的，且这里start一开始设为n+1，是因为尽管各个字符的代码长度不同，但都不可能超过n8.c=i;/从叶节点开始向上9.f=hti.parent;10.while(f!=NULL)/这里的循环是通过判断父节点是否为空为终止条件的11.12.if(htf.lch=c)13.d.cd-d.start=0;14.else15.d.cd-d.start=1;16.c=f;17.f=htf.

8、parent;18.19.hcdi=d;20.21.printf(输出Huffma编码如下：n);22.for(i=1;i=n;i+)23.24.printf(%c对应Huffman编码为:,hti.data);25.for(k=hcdi.start;k=n;k+)26.printf(%c,hcdi.cdk);27.printf(n);28.29.(3)译码算法思路；首先输入二进制代码串，存放在数组ch中，以“”为结束标志。接下来，将代码与编码表比较，如果为0，转向左子树若为1，转向右子树，直到叶结点结束，此时输出叶结点的数据域，即所对应的字符。继续译码，直到代码结束。算法如下；1./译码2.

9、voidDecoding(HuffNodeht,HuffCodehcd,intn)3.4.intf,m,k;5.DataTypec,ch200;6.printf(请输入电文(0or1),以输入#截止:);7.c=getchar();8.k=1;9.while(c!=#)10.11.chk=c;12.c=getchar();13.k+;14.15.m=k;16.f=2*n-1;/代表树根节点17.k=1;18.printf(输出哈夫曼译码如下:n);19.while(km)20.21.while(htf.lch!=0)/初始权值节点的标志22.23.if(chk=1)24.f=htf.rch;2

10、5.if(chk=0)26.f=htf.lch;27.k+;28.29.printf(%c,htf.data);30.f=2*n-1;/重置f31.32.printf(n);33.5.源代码1.#include2.#include3.#include4.#include5.#include6.#include7.#include8.#defineTRUE19.#defineFALSE010.#defineMAXNUM5011.typedefcharDataType;12.13./Huffman树节点的存储结构定义14.typedefstruct15.16.DataTypedata;17.int

11、weight;18.intparent;19.intlch;20.intrch;21.HuffNode;22.typedefstruct23.24.DataTypecdMAXNUM;25.intstart;26.HuffCode;27.28./构造哈弗曼树29.intHuffman(HuffNode*hf)30.31.inti,k,n,m1,m2,p1,p2;32.printf(请输入元素的个素:);33.scanf(%d,&n);34.for(i=1;int节点值：,i);38.scanf(%c,&(hfi.data);/hf可以当做数组来用,因为hfi在这里不是一个指针，而是一个结构体，所

12、以可以直接使用.运算符来调用data39.printf(t权重:);40.scanf(%d,&(hfi.weight);41.42.for(i=1;i=2*n-1;i+)/*对数组的父节点以及左右节点进行初始化,总共有2n-1个结点，初始权值结点n个，父节点n-1个*/43.44.hfi.parent=0;45.hfi.lch=0;46.hfi.rch=0;47.48.for(i=n+1;i=2*n-1;i+)49.50.m1=m2=32767;/假设这两个权值一开始为int的最大值51.p1=p2=1;/位置初始值设为第一个节点的位置52.for(k=1;ki;k+)53.54.if(hfk

13、.parent=0)55.56.if(hfk.weightm1)57.58.m2=m1;/重新置次小值59.p2=p1;/重新置次小值对应的位置60.m1=hfk.weight;/重新置最小值61.p1=k;/重新置最小值的位置62.63.elseif(hfk.weightm2)64.65.m2=hfk.weight;/重新置次小值66.p2=k;/重新置次小值的位置67.68.69.70.hfp1.parent=i;/把最小的位置的节点的父节点位置设为i71.hfp2.parent=i;/把次小的位置的节点的父节点位置设为i72.hfi.weight=m1+m2;/置新的生成的父节点的权重7

14、3.hfi.lch=p1;/设置新生成的节点的左节点74.hfi.rch=p2;/设置新生成的节点的左节点75.76.printf(Huffman树已经建立成功!);77.returnn;78.79.80./编码81.voidEncoding(HuffNodeht,HuffCodehcd,intn)/这里的hcd存有n个初始权值节点代码数组的数组，n是初始权值节点的个数;82.83.HuffCoded;/存储每一个初始权值节点的代码数组84.inti,c,f,k;85.for(i=1;i=n;i+)86.87.d.start=n+1;/把d的start下标设为代码数组的末尾位置，因为存储代码时

15、是从最下面的叶子结点到根，所以在存储是需要倒序存储的，且这里start一开始设为n+1，是因为尽管各个字符的代码长度不同，但都不可能超过n88.c=i;/从叶节点开始向上89.f=hti.parent;90.while(f!=NULL)/这里的循环是通过判断父节点是否为空为终止条件的91.92.if(htf.lch=c)93.d.cd-d.start=0;94.else95.d.cd-d.start=1;96.c=f;97.f=htf.parent;98.99.hcdi=d;100.101.printf(输出Huffma编码如下：n);102.for(i=1;i=n;i+)103.104.pr

16、intf(%c对应Huffman编码为:,hti.data);105.for(k=hcdi.start;k=n;k+)106.printf(%c,hcdi.cdk);107.printf(n);108.109.110.111./译码112.voidDecoding(HuffNodeht,HuffCodehcd,intn)113.114.intf,m,k;115.DataTypec,ch200;116.printf(请输入电文(0or1),以输入#截止:);117.c=getchar();118.k=1;119.while(c!=#)120.121.chk=c;122.c=getchar();1

17、23.k+;124.125.m=k;126.f=2*n-1;/代表树根节点127.k=1;128.printf(输出哈夫曼译码如下:n);129.while(km)130.131.while(htf.lch!=0)/初始权值节点的标志132.133.if(chk=1)134.f=htf.rch;135.if(chk=0)136.f=htf.lch;137.k+;138.139.printf(%c,htf.data);140.f=2*n-1;/重置f141.142.printf(n);143.144.145./主函数146.intmain()147.148.intn,select,flag=FA

18、LSE;149.HuffNodeht2*MAXNUM;150.HuffCodehcdMAXNUM;151.while(TRUE)152.153.printf(t请选择您所想要实现的功能:(请输入1-4号数字)n);154.printf(t1-建立Huffman树n);155.printf(t2-编码n);156.printf(t3-译码n);157.printf(t4-退出系统!n);158.scanf(%d,&select);159.if(select!=1&select!=4&flag=FALSE)160.161.printf(请先建立Huffman树再进行编码译码操作!n);162.continue;/进入下一次循环163.164.flag=TRUE;165.switch(select)166.167.case1:168.n=Huffman(ht);169.break;170.case2:171.Encoding(ht,hcd,n);172.break;173.case3:174.Decoding(ht,hcd,n);175.break;176.case4:177.exit(0);178.