14 -
中南大学数据结构课程
姓 名： 刘阳
班 级： 信息0703
学 号：0903070312
实验时间： 08.11.14
指导老师： 赵颖
目 录
一、实验内容……………………………………………………………2
二、实验说明……………………………………………………………2
三、结构体定义和程序结构的说明……………………………………3
1.结构体定义的说明………………………………………………3
2.程序结构的说明…………………………………………………3
四、程序设计的基本思想、部分源代码及注释………………………3
1.选择权值最小的两个结点………………………………………4
Ⅰ.判断结点是否已经被使用过……………………………………………4
Ⅱ.选出权值为最小的结点…………………………………………………4
Ⅲ.选出另一个权值为最小的结点…………………………………………5
Ⅳ.判断两个选出的最小权值的大小………………………………………5
2．构建哈夫曼树……………………………………………………6
Ⅰ.判断能否构建成哈夫曼树………………………………………………6
Ⅱ.对需要处理的结点和哈夫曼树的结点进行初始化……………………6
Ⅲ.构建哈夫曼树……………………………………………………………6
Ⅳ.对构建好的哈夫曼树进行遍历确定每个结点的编码…………………7
3．输出设置…………………………………………………………7
Ⅰ.输出每个结点的父亲、左孩子、右孩子结点…………………………7
Ⅱ.输出每个结点的哈夫曼编码……………………………………………8
五、流程图
六、实验结果演示
七、在编写程序过程中遇到的困难和解决的方法
一、实验内容
根据输入的n个带权结点，构造出哈夫曼树，并且把构造结果输出到屏幕。
二、实验说明
哈夫曼数，也称最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。
设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度WPL，记作： WPL=。在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。
在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有A，B，C，D四种字符，若这四种字符采用下表所示的编码，则电文的代码为000010000100100111 000，长度为21。
在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。并且在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，以避免反译成原文时，编码出现多义性。
在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。
采用哈夫曼树进行编码，也不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。
三、结构体定义和程序结构的说明
1、结构体定义的说明
哈夫曼树重点在于如何排列权值大小不同的结点的顺序，所以定义结构体如下：
typedef struct
{
int weight; /*weight存储结点的权值*/
int parent;
int lchild;
int rchild; /*分别保存父亲、左孩子、右孩子结点*/
}HTNode,*HuffmanTree;
而另一个重点在于将两个权值为最小的结点分别作为左、右子树，所以定义结构体如下：
typedef struct
{
unsigned int s1;
unsigned int s2; /*分别存储最小和次小的结点*/
}MinCode;
2、程序结构的说明
程序主要由以下几部分组成：
结构体 struct HTNode,*Huffmantree
结构体 struct MinCode
函数 Select ——用以选择结点中权值最小的两个结点
函数 CreateTree ——将选出来的结点按规律逐步建成哈夫曼树
函数 main ——主函数
四、程序设计的基本思想、部分源代码及注释
根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。因此，构造哈夫曼树有此种方法：
1、由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}；
2、在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；
3、在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；
4、重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
所以，构造哈夫曼树主要由两个步骤组成：一是选择所有结点中权值最小的两个结点，二是将这些结点加入到二叉树中，构建成哈夫曼树。
在所有结点中选出权值最小的两个结点。
Ⅰ、选择权值最小的两个结点并不难，难在如何判断该结点是否已经使用过，若不能正确判断前面构造的哈夫曼树中是否使用过该结点，可能造成结点重复出现在树中，出现错误。根据哈夫曼树构造的特点，当两个结点的权值为最小时就将做为新的二叉树的左（右）子树，而它们的权值之和为它们的根结点，所以可以通过判断该结点是否有父亲结点来判断它是否被使用过。
if(HT[i].parent==0) /*没有父亲结点说明该
{ 结点还未被使用过*/
min=HT[i].weight; /*给min赋初始值*/
s1=i; /*将结点的编号赋给s1*/
break;
}
tempi=i++; /*i确定下一个结点的编号*/
Ⅱ、然后利用数字排序的方法，对符合要求的结点进行判断，当存在权值更小的结点是，将该结点的内容赋给min和s1.
for(;i<=n;i++)
if(HT[i].weight<min&&HT[i].parent==0)
{ /*当结点i未被使用并且权
min=HT[i].weight; 值小于min时，将权值赋s1=i; 给min，编号赋给s1*/
}
Ⅲ、采用同样的方法可以选择出另一个权值为最小的结点。
for(i=tempi;i<=n;i++)
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=1;i<=n;i++)
{
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
}
Ⅳ、再通过判断结点s1和结点s2的权值的大小来确定权值为最小的结点和权值为第二小的结点，并将值保存再结构体中。
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
将选择出来的结点一个个逐步构建成哈夫曼树。
Ⅰ、哈夫曼树实现的功能就是将若干个结点以最优化的顺序排列出来，所以当结点数n=1时，不存在构建哈夫曼树的问题。因此，首先对可能出现的这种状况进行判断。
if(n<=1)
printf("Error：Code too small!!");
Ⅱ、因为哈夫曼树的叶子结点为n个，结点数为2*n-1个，所以可以直接定义构建的哈夫曼树的结点个数m。并对输入的结点和待构建的哈夫曼树上的结点进行初始化。
m=2*n-1; /*定义哈夫曼树的结点个数*/
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT,i=0;i<=n;i++,p++,w++) /*0号单元未用*/ {
p->weight=*w;
p->parent=0; /*给待处理的结点赋予权值，父
p->lchild=0; 亲、左孩子、右孩子均赋0值*/
p->rchild=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0; /*对待构建的哈夫曼树
p->lchild=0; 的编码进行初始化*/
p->rchild=0;
}
Ⅲ、构建哈夫曼树，通过Select函数选择还未被使用的且权值为最小的两个结点，将其加入到树中。
for(i=n+1;i<=m;i++)
{
min=Select(HT,i-1);
s1=min.s1; /*s1、s2分别存权值最小
s2=min.s2; 的两个结点的编号*/
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
Ⅳ、构建完成哈夫曼树后，为知道每个结点的具体编码，必须对哈夫曼树进行遍历，且必须从叶子结点向根结点逆序进行遍历。
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char *)); /*分配求编码的工作空间*/
cd[n-1]='\0'; /*编码结束符*/
for(i=1;i<=n;i++) /*逐个字符求赫夫曼编码*/
{
start=n-1; /*编码结束符位置*/
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) /*从叶子到根逆向求每个
if(HT[f].lchild==c) 字符的赫夫曼编码*/
cd[--start]='0'; /*左孩子赋0值*/
else cd[--start]='1'; /*右孩子赋1值*/
3、输出的设置
由于哈夫曼树的树形结构比较难在计算机屏幕上实现，而又需要明确的表示出每个结点在树中的位置，所以对输出采取了以下两种样式。
Ⅰ、输出每个结点的父亲、左孩子、右孩子结点的编号，从而确定每个结点的具体位置。由于在构建哈夫曼树的Create函数中已经完成了每个结点的父亲、左孩子、右孩子结点的赋值，所以只需要将这些值直接输出即可。
printf("HT List:\n");
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for(i=1;i<=m;i++)
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",
i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
Ⅱ、哈夫曼树的功能是将每个结点用0和1表示出来，所以将每个结点的哈夫曼编码表示出来也可以确定哈夫曼树的结构。而在Create函数中，同样已经给确定了结点的0值和1值，只需要调用一个字符串函数将每个结点的编码复制到该结点相应的编码值Code中。然后再在主函数中将其打印出来。
HC[i]=(char *)malloc((n-start)*sizeof(char *)); /*为第i个字符编码分配空间*/
strcpy(HC[i],&cd[start]); /*从cd复制编码（串）到HC*/
printf("HuffmanCode:\n");
printf("Number\t\tWeight\t\tCode\n");
for(i=1;i<=n;i++)
printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]);
五、流程图
main函数：
Select函数：
CreatTree函数：
六、实验结果演示
1、当输入的结点个数n≧2时：
2、当输入的结点数n=1时，不存在构建哈夫曼树的问题，输出错误提示：
七、在编写程序过程中遇到的困难和解决的方法
数据结构上机实验是使我们进一步掌握和深化所学知识的必不可少的内容之一，是后继专业课程的基础，是培养我们综合能力和提高我们科学素养的必不可少的部分，所以我对每次实验都抱以极其认真的态度。
在刚开始拿到程序的题目时，不知道从何入手，因为题目表现的比较抽象，并且自己在写哈夫曼树的过程中都遇到一些困难，所以感觉很难完成。百般无奈之下，回归课件，将哈夫曼树那一节仔细的看了几遍才看懂了编写哈夫曼树的基本思想。
程序的重点之一是选择权值最小的两个结点，最开始将问题考虑的太过简单，使用数字排序的冒泡法之类的就能找到最小的两个结点，然后使用完这两个结点后将它们删除掉就可以了。但是在实际操作中，结点的内容是使用数组的形式存储下来的，而数组最麻烦的操作就是在数组中进行插入和删除结点。当时怎么也想不到解决的办法。后来在翻阅C语言的书的时候，看到在判断一个数是否为素数的程序中使用了flag标志，考虑先将所有的结点的flag标志都赋为0，而使用完某个结点后就将它的flag标志改为1，这样就不会出现结点被重复使用的现象了。后来在网上查找类似的程序中发现了一个更好的办法，就是运用结点插入后的本来性质，因为在将结点加入到哈夫曼树中，它一定会有父亲结点，所以先将需要处理的结点的父亲结点全赋予0值，而加入到树中后有了父亲结点，则父亲结点不再为0，可以通过判断parent==0是否成立来判断结点是否被使用过。这样在很大程度下简化了程序。
在构建哈夫曼树的过程中，想到每两个最小权值结点的父亲结点是需要另外存储的，而最开始虽然按照课件上的内容将哈夫曼树的结点数设置成2*n-1个，却不知道如何使用。最初的想法是在选择出两个结点后将它们重新编号，从1开始，然后自然而然它们的父亲结点就为3，依此类推。同样的也是在实际操作中，发现这样做真是自己给自己找麻烦，不仅容易将原来需要处理的结点搞混，重新编号也是一项大工程。后来在同学的帮助下，发现自己思考的太复杂了，可以直接将第一个父亲结点的编号设置为n+1即可，因为只有n个结点需要处理，后面的m-n个结点都是父亲结点。
最后一个问题是输出的设置。因为是要构建哈夫曼树，所以理所当然的认为要输出一个树的结构，但是很明显根本不知道要如何实现这一类的操作，所以又一次陷入僵局。在同学的提醒下，改换了思维，只要能够表示出树的结构就可以了，并不一定要将一颗树给画出来。而表现出哈夫曼树的结构可以通过它的编码来显示，也可以通过输出它的父亲结点和孩子结点来表示。好在这两种表示方法都比较容易实现，而且实验的目的也是要输出每个结点的哈夫曼编码，但是通过父亲结点和孩子结点更能够体现出结点的位置，所以输出设置将两种都纳入其中，以便使结果更加明显透彻。
通过这次实验，我发现，人的思维一定要多元化，有时候在某个问题上想到的办法比较难以实现是可以转换一下思想，不要刻板的一定要将该办法实现。但是我们在执着于一个问题的时候很难转换思想去走另一条路，所以一定和多和同学交流，多阅读一些通过不同方法来实现同一操作的程序，比较一下它们之间的差异，了解到每个程序的这样编写的原因和好处，发散自己的思维。只有这样才能编写出更好的程序，使程序能更简单更容易实现。
