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

中南大学物理学院（数据结构课程）实验报告实验名称：哈弗曼编码和译码专业班级：电子信息科学与技术0904姓 名：秦杰学 号：1404090506指导教师：胡志坤2011年 11月 27 日 实验四：哈夫曼编码和译码一、 实验目的和要求（1） 掌握哈夫曼树的基本概念及其存储结构。（2） 掌握哈夫曼树的建立算法。（3） 掌握哈夫曼树的应用（哈夫曼编码和译码）。二、 实验内容和原理1.实验内容用下表给出的字符集和频度的数据建立哈曼树,并实现以下报文的编码和译码：“this*program*is*my*favourite”。字符*abcdefghi频度1866413223210321154757字符jklmnopqrs频度15322057631514851字符tuvwxyz频度802381811612.实验原理首先规定构建哈夫曼树，再去进行哈夫曼树的编码，接着设计函数进行字符串的编码过程，最后进行哈夫曼编码的译码。定义一个结构体，用于存放构建哈夫曼树所需要的所有变量，开辟一块地址空间，用于存放数组，数组中每个元素为之前定义的结构体。输入n个字符及其权值。构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为： 1.初始化:将ht0m-1中2n-1个结点里的三个指针均置为空，权值置为0。 2.输入:读入n个叶子的权值存于向量的前n个分量中。它们是初始森林中n个孤立的根结点上的权值。 3.合并:对森林中的树共进行n-1次合并，所产生的新结点依次放入向量ht的第i个分量中。每次合并分两步： 在当前森林ht0i-1的所有结点中，选取权最小和次小的两个根结点s1和 s2作为合并对象，这里0s1，s2i-1。 将根为hts1和hts2的两棵树作为左右子树合并为一棵新的树，新树的根是新结点hti。具体操作： 将hts1和hts2的parent置为i， 将hti的lchild和rchild分别置为s1和s2 .新结点hti的权值置为hts1和hts2的权值之和。 4.哈夫曼的编码：约定左子为0，右子为1，则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码。当用户输入字母时。就在已经找好编码的编码结构体中去查找该字母。查到该字母就打印所存的哈夫曼编码。接着就是完成用户输入0、1代码时把代码转成字母的功能。这是从树的头结点向下查找，如果当前用户输入的0、1串中是0则就走向该结点的左子。如果是1这就走向该结点的右结点，重复上面步骤。直到发现该结点属于输入了字母的结构体则打印该结构体的字母。重复上面步骤。直到找完用户输入0、1串为止。则就完成了程序所有的译码过程。三、 实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP中文操作系统 （2）VC+6.0四、 算法描述及实验步骤(1)建立哈夫曼树的算法：定义各结点类型其中应包含两类数据一是权重域weight;一是应该包括指向左右孩子和指向双亲的指针这里分别用lchild、rchild和parent来表示，因此可用静态三叉链表来实现。在实际构造中由于是叶子结点来构造新的根结点其构造过程中仅与叶子结点的权重有关而与其数据域无关，所以构造过程中不用考虑其数值域，并且在链表中从叶子开始存放，然后不断的将两个最小权值的子树合并为一个权值为其和的较大的子树，逐步生成各自内部结点直到树根。(2）编码的算法 将建立的哈夫曼树从每个叶子结点开始沿着双亲回到根结点，每走一步进行编码得到的一个编码值，由于每个叶子结点的哈夫曼编码是从根结点到相应的叶子的路径的各个分支的代码组成的0和1序列，所以先得到了低位编码后得到高位编码因此可用一维数组从后向前来存放各位编码值，并用start来记录编码的起始位置。 开始i=0start=n-1i结点的父结点子结点为左子YN编码为0编码为1start=start-1把父结点作为当前结点根结点？NYstart=start+1start=start+1start=nYi=i+1inYN哈夫曼编码完成图1.哈夫曼编码图(3)哈夫曼编码。当我们输入一些字符串，进行哈夫曼编码，然后输出0、1代码。 算法流程图如下图所示：开始i=0输入字符以回车结束c=0c=nStingi=htc.dataj=dcc.starj=n输出代码j+C+输出编码结束Y图2.字符串的哈夫曼编码图（4）、哈夫曼译码从树的头结点向下查找，如果当前用户输入的0、1串中是0则就走向该结点的左子。如果是1这就走向该结点的右结点，重复上面步骤。直到发现该结点属于输入了字母的结构体则打印该结构体的字母。重复上面步骤。直到找完用户输入0、1串为止。则就完成了程序所有的译码过程。当我们输入哈夫曼01代码时进行译码过程，输出字符串。算法如下图所示： 图3.哈夫曼译码图（5）源程序代码如下： #include #include /数组头文件 #include #define MAX 1000 /宏定义typedef struct /定义哈夫曼编码的结构数组 char data; int weight; /定义权值 int parent; int lchild; int rchild;huffmannode;typedef struct /定义保存哈夫曼结构体 char bits50; int start;huffmancode ;void main() huffmannode ht100; /定义储存权值的空间 huffmancode cd100; char string100; /定义数组存储空间 char hcd100; int i,j,x,y,s1,s2,m1,m2,n,c,f,k; printf(please input the n=); /输入字符的个数 scanf(%d,&n); printf(n=n); for(i=0;in;i+) getchar(); /获得输入的字符 printf(please input the value :); scanf(%c,&hti.data); /输入字符函数 printf(please input the weight:); scanf(%d,&hti.weight); printf(n=n); for(i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=0; /初始化父结点，左右子结点 for (i=n;i2*n-1;i+) s1=s2=0; /初始化变量 m1=m2=MAX; for (j=0;ji;j+) if (htj.weightm1 &htj.parent=0) /寻找无父结点的最小值 m2=m1; s2=s1; m1=htj.weight; s1=j; /寻找当前最小值 else if(htj.weightm2 &htj.parent=0 ) /寻找无父结点的次小值 m2=htj.weight; s2=j; /寻找次小值 hts1.parent=i; /s1的父结点为i hts2.parent=i; hti.weight=m1+m2; /最小值的权值相加为i的权值 hti.lchild=s1; /i的左子为s1 hti.rchild=s2; /i的右子为s2 for(i=0;in;i+) cdi.start=n; cdi.bitscdi.start=0; for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)if(htf.lchild=c) cdi.bits-cdi.start=0;else cdi.bits-cdi.start=1; printf(nout the huffmancode:n); for (i=0;in;i+) printf(%c:,hti.data); /输出字符 for(j=cdi.start;j=n;j+) printf(%c,cdi.bitsj); /输出字符的01代码 printf(n); printf(n=n); printf(nPlease input the message:n); scanf(%s,string); /输入字符串 for(i=0;stringi!=0;i+) for(c=0;c=n;c+) if(stringi=htc.data) /寻找与输入字符相匹配的字母 for(j=cdc.start;j=n;j+) printf(%c,cdc.bitsj); /输出字母代码 break; printf(n=n); printf(Please input the HuffmanCode:n); scanf(%s,hcd); /输入0、1代码 f=2*n-2; for(i=0;hcdi!=0;i+) if(hcdi=0) /判断输入为0，寻找左子 f=htf.lchild; else if(hcdi=1) f=htf.rchild; /判断输入为1，寻找右子 if(fn) printf(%c,htf.data); /输出字符串 f=2*n-2; printf(n); getch();五、 运行结果第一步，运行程序，首先规定结点个数n=27回车，其次我们输入每个结点的字符及每个结点对应的权值（空格用*代替），得如图： 第二步，单击回车得到每个叶子结点的编码，如下图：第三步、得到编码后我们输入字符“this*program*is*my*favourite”进行哈夫曼编码，得到28个字符的哈弗满编码。如下图示：第四步，得到哈夫曼编码后输入哈夫曼编码进行译码过程，得到输出为“this*program*is*my*favourite”，译码正确！，输出如下图所示：六、 总结通过编程，我进一步学习了哈弗曼编码的特点、存储方法和基本原理，提高了自己运用C语言正确编程及调试的能力，运用数据结构解决简单的实际问题的能力，为后续数据结构课程的学习打下基础。在此次实验中遇到了很多语句赋值的错误，还有for语句使用的不熟练，以及自己的粗心而造成的标点符号使用错误，宏语句的定义等等，主要的解决方案是，看一些关于