数据结构-赫夫曼树-课程设计

数据结构课程设计题目：赫夫曼树的建立一、需求分析众所周知，最优二叉树（赫夫曼树）在解决很多判定问题时，有着无可比拟的优势。同时，在目前，进行快速远距离通信的主要手段主要是电报，即将需传送的文字转换成由二进制的字符组成的字符串。而在文字的转换编码中，也必然要用到赫夫曼算法才能使传送的电文尽可能地短。所以，本程序主要目的就是是利用赫夫曼算法快速生成一个普通二叉树的最优二叉树（赫夫曼树），同时本程序还可以生成对每个结点对应的赫夫曼编码。在这个程序中主要有3个函数：InitHaffman函数：完成对树的结点进行初始化。Haffman函数：用于构造赫夫曼树并生成相应的赫夫曼编码。OutputHaffman函数：输出赫夫曼树和编码。二、概要设计赫夫曼算法的叙述过程：（1）根据给定的n个权值w1,w2,，wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。（3）在F中删除这两棵树，同时将新得到的二叉树加入F中。（4）重复（2）和（3），直到F只含一棵树为止。这棵树便是赫夫曼树。程序大体设计流程：定义全局变量构造赫夫曼树的存储结构定义InitHaffman函数定义Haffman函数定义OutputHaffman函数利用主程序调用函数赫赫夫曼树的存储结构typedef structint data;/结点值int Weight;/权值 int Flag;/标识是否待构结点 ，是的话用0表示，否则为1 int Parent;/父结点 int Lchild;/左结点int Rchild;/右结点hnodetype;2、构造树初始化的函数InitHaffman三、详细设计1、定义程序所需的全局变量，以便在程序中使用。代码如下： #define MAXVALUE 10000#define MAXLEAF 30#define MAXNODE 60#define MAXBIT 102、构建赫夫曼树的存储结构。赫夫曼树中主要包括结点个数，每个结点对应的权值，父结点及左右孩子结点这几个元素。所以其存储结构的可以表示代码如下： typedef structint data;/结点值int Weight;/权值 int Flag;/标识是否待构结点 ，是的话用0表示，否则为1 int Parent;/父结点 int Lchild;/左结点int Rchild;/右结点hnodetype;3、编写赫夫曼树结点初使化函数。主要是使用for循环来实现，详细代码如下所示：void InitHaffman(hnodetype HuffNode,hcodetype HuffCode,int n)int i;for(i=0;i=2*n-1;i+)/把生成的结点初始化，把指向父亲的指针先置空HuffNodei.Weight=0;HuffNodei.Parent=0;HuffNodei.Flag=0;HuffNodei.Lchild=-1;HuffNodei.Rchild=-1;for(i=0;in;i+)/输入树的结点 getchar();printf(输入第%d个叶结点值：,i+1);scanf(%c,&HuffNodei.data);printf(n);for(i=0;in;i+) /输入树结点对应的权值 getchar();printf(输入第%d个叶子结点对应的权值:,i+1);scanf(%d,&HuffNodei.Weight);printf(n);4、构造赫夫曼树函数。按照赫夫曼算法，我们先找对应权值最小的两个结点，再将这两个结点提出构成一个二叉树，此二叉树的根权值为两子结点权值之和，再将此根结点和其它结点权值比较，找最小的两个权对应结点，再构成一个二叉树。以此类推最后就能得出所要的赫夫曼树。 对于每一父子间，约定其左孩子则为字符0，右孩子为字符1。则可以从根结点到叶子结点的路径上分支组成的字符串作为该叶子结点字符的编码，就可以输出每个叶子结点的赫夫曼编码。主要代码如下：void Haffman(hnodetype HuffNode,hcodetype HuffCode,int n)int i ,j,m1,m2,x1,x2,c,p;hcodetype cd;for(i=0;in-1;i+)/选择权值最小的两个结点构成一棵二叉树m1=m2=MAXVALUE;x1=x2=0;/x1和x2为权值最小的两个结点for(j=0;jn+i;j+)if(HuffNodej.Weightm1 & HuffNodej.Flag=0)m2=m1;x2=x1;m1=HuffNodej.Weight;x1=j;else if(HuffNodej.Weightm2 & HuffNodej.Flag=0)m2=HuffNodej.Weight;x2=j;/把找到的两个结点按照赫夫曼树的规则构建成一个二叉树， x1为左孩子，x2为右孩子HuffNodex1.Parent=n+i;HuffNodex2.Parent=n+i;HuffNodex1.Flag=1;HuffNodex2.Flag=1;HuffNoden+i.Weight=HuffNodex1.Weight+HuffNodex2.Weight;HuffNoden+i.Lchild=x1;HuffNoden+i.Rchild=x2;for(i=0;in;i+)/根据赫夫曼树生成赫夫曼编码cd.Start=n-1;c=i;p=HuffNodec.Parent;while(p!=0)/当父结点不为根结点的时候，逆序往上找/如果当前是左孩子，则编码为0，是右孩子为1if(HuffNodep.Lchild=c)cd.Bitcd.Start=0;else cd.Bitcd.Start=1;cd.Start-;c=p;p=HuffNodec.Parent;for(j=cd.Start+1;jn;j+)HuffCodei.Bitj=cd.Bitj;HuffCodei.Start=cd.Start;5、编写输出函数OutputHaffman函数。具体代码为：void OutputHaffman(hnodetype HuffNode,hcodetype HuffCode,int n)int i,j;printf(n);printf(2.输出赫夫曼树:n);printf(n);printf(%d个叶子节点对应编码为：n,n);for(i=0;in;i+)printf(%c-,HuffNodei.data);for(j=HuffCodei.Start+1;jn;j+)printf(%d,HuffCodei.Bitj);printf(n);四、调试分析1、程序运行后界面如下所示：2、输入结点个数后对每个结点进行初始化： 图2 结点初始化3、程序运行结果如下图所示： 图3 程序最终于运行结果 程序输出的赫夫曼树为：权为34权为64433512权为2权为12权为54、存在问题分析和解决方案。 虽然程序的基本功能能够实现，但还是存在很多问题1、对于二叉树的输出还是没有做出来。解决方案：深入理解树的遍历，利用三种遍历方式把二叉树表示出来2、对于树的存储结构理解的不深刻。解决方案：再加强对栈、队列、链表这些常见存储结构的学习，把这些与树结合起来。5、算法改进方案。 利用树的三种遍历方式将赫夫曼树表示出来，再输出结点的赫夫曼编码能使程序更加完善，也使输出的结果更加清楚明了。更能体现程序的功能。8