名:信息0703实验时间:指导老师:08.11.14一、实验内容2二、实验说明2三、结构体定义和程序结构的说明31. 结构体定义的说明32. 程序结构的说明3四、程序设计的基本思想、部分源代码及注释31. 选择权值最小的两个结点4I. 判断结点是否已经被使用过4II. 选出权值为最小的结点4III. 选出另一个权值为最小的结点5W.判断两个选出的最小权值的大小52. 构建哈夫曼树6I.判断能否构建成哈夫曼树6II. 对需要处理的结点和哈夫曼树的结点进行初始化6III. 构建哈夫曼树6IV. 对构建好的哈夫曼树进行遍历确定每个结点的编码73. 输出设置7I输出每个结点的父亲、左孩子、右孩子结点7II.输出每个结点的哈夫曼编码8五、流程图六、实验结果演示七、在编写程序过程中遇到的困难和解决的方法、实验内容根据输入的n个带权结点，构造出哈夫曼树，并且把构造结果输出到屏幕。二、实验说明哈夫曼数，也称最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度WPL,记作：WPL=工WL。在给定一组具有确定权值的叶结点，可以构造出不同的带权二kkk,1叉树。根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA,电文中只含有A，B，C，D四种字符，若这四种字符采用下表所示的编码，则电文的代码为000010000100100111000,长度为21。在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。并且在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，以避免反译成原文时，编码出现多义性。在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。采用哈夫曼树进行编码，也不会产生上述二义性问题。因为，在哈夫曼树中,每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。三、结构体定义和程序结构的说明1、结构体定义的说明哈夫曼树重点在于如何排列权值大小不同的结点的顺序，所以定义结构体如下：typedefstructintweight;/*weight存储结点的权值*/intparent;intlchild;intrchild;/*分别保存父亲、左孩子、右孩子结点*/HTNode,*HuffmanTree;而另一个重点在于将两个权值为最小的结点分别作为左、右子树，所以定义结构体如下：typedefstructunsignedints1;unsignedints2;/*分别存储最小和次小的结点*/MinCode;2、程序结构的说明程序主要由以下几部分组成：结构体structHTNode,*Huffmantree结构体structMinCode函数Select用以选择结点中权值最小的两个结点函数CreateTree将选出来的结点按规律逐步建成哈夫曼树函数main主函数四、程序设计的基本思想、部分源代码及注释根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。因此，构造哈夫曼树有此种方法：1、由给定的n个权值Wl,W2,，Wn构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F=T1,T2,，Tn；2、在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和;3、在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；4、重复(2)(3)两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。所以，构造哈夫曼树主要由两个步骤组成：一是选择所有结点中权值最小的两个结点，二是将这些结点加入到二叉树中，构建成哈夫曼树。1、在所有结点中选出权值最小的两个结点。I、选择权值最小的两个结点并不难，难在如何判断该结点是否已经使用过,若不能正确判断前面构造的哈夫曼树中是否使用过该结点，可能造成结点重复出现在树中，出现错误。根据哈夫曼树构造的特点，当两个结点的权值为最小时就将做为新的二叉树的左(右)子树，而它们的权值之和为它们的根结点，所以可以通过判断该结点是否有父亲结点来判断它是否被使用过。if(HTi.parent=O)/*没有父亲结点说明该结点还未被使用过*/min=HTi.weight;/*给min赋初始值*/s1=i;/*将结点的编号赋给s1*/break;tempi=i+;/*i确定下一个结点的编号*/II、然后利用数字排序的方法，对符合要求的结点进行判断，当存在权值更小的结点是，将该结点的内容赋给min和s1.for(;i=n;i+)if(HTi.weightmin&HTi.parent=0)/*当结点i未被使用并且权min=HTi.weight;值小于min时，将权值赋s1=i;给min,编号赋给s1*/III、采用同样的方法可以选择出另一个权值为最小的结点。for(i=tempi;iv=n;i+)if(HTi.parent=O&i!=sl)secmin=HTi.weight;s2=i;break;for(i=1;is2)temp=s1;s1=s2;s2=temp;code.s1=s1;code.s2=s2;returncode;2、将选择出来的结点一个个逐步构建成哈夫曼树。I、哈夫曼树实现的功能就是将若干个结点以最优化的顺序排列出来，所以当结点数n=1时，不存在构建哈夫曼树的问题。因此，首先对可能出现的这种状况进行判断。if(nv=l)printf(Error：Codetoosmall!);II、因为哈夫曼树的叶子结点为n个，结点数为2*n-1个，所以可以直接定义构建的哈夫曼树的结点个数m。并对输入的结点和待构建的哈夫曼树上的结点进行初始化。m=2*n-1;/*定义哈夫曼树的结点个数*/HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT,i=O;iv=n;i+,p+,w+)/*0号单元未用*/p-weight=*w;p-parent=0;/*给待处理的结点赋予权值，父p-lchild=0;亲、左孩子、右孩子均赋0值*/p-rchild=0;for(;iweight=0;p-parent=0;/*对待构建的哈夫曼树p-lchild=0;的编码进行初始化*/p-rchild=0;III、构建哈夫曼树，通过Select函数选择还未被使用的且权值为最小的两个结点，将其加入到树中。for(i=n+1;i=m;i+)min=Select(HT,i-1);s1=min.s1;/*s1、s2分别存权值最小s2=min.s2;的两个结点的编号*/HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTsl.weight+HTs2.weight;W、构建完成哈夫曼树后，为知道每个结点的具体编码，必须对哈夫曼树进行遍历，且必须从叶子结点向根结点逆序进行遍历。HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char*);/*分配求编码的工作空间*/cdn-1=0;/*编码结束符*/for(i=1;i=n;i+)/*逐个字符求赫夫曼编码*/start=n-1;/*编码结束符位置*/for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/*从叶子到根逆向求每个if(HTf.lchild=c)字符的赫夫曼编码*/cd-start=0;/*左孩子赋0值*/elsecd-start=T;/*右孩子赋1值*/3、输出的设置由于哈夫曼树的树形结构比较难在计算机屏幕上实现，而又需要明确的表示出每个结点在树中的位置，所以对输出采取了以下两种样式。I、输出每个结点的父亲、左孩子、右孩子结点的编号，从而确定每个结点的具体位置。由于在构建哈夫曼树的Create函数中已经完成了每个结点的父亲、左孩子、右孩子结点的赋值，所以只需要将这些值直接输出即可。printf(HTList:n);printf(Numberttweightttparentttlchildttrchildn);for(i=1;i=m;i+)printf(%dtt%dtt%dtt%dtt%dn,i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);II、哈夫曼树的功能是将每个结点用0和1表示出来，所以将每个结点的哈夫曼编码表示出来也可以确定哈夫曼树的结构。而在Create函数中，同样已经给确定了结点的0值和1值，只需要调用一个字符串函数将每个结点的编码复制到该结点相应的编码值Code中。然后再在主函数中将其打印出来。HCi=(char*)malloc(n-start)*sizeof(char*);/*为第i个字符编码分配空间*/strcpy(HCi,&cdstart);/*从cd复制编码(串)到HC*/printf(HuffmanCode:n);printf(NumberttWeightttCoden);for(i=l;iv=n;i+)printf(%dtt%dtt%sn,i,wi,HCi);五、流程图main函数：Select函数:CreatTree函数:0六、实验结果演示1、当输入的结点个数n2时:2、当输入的结点数n=1时，不存在构建哈夫曼树的问题，输出错误提示:七、在编写程序过程中遇到的困难和解决的方法数据