哈夫曼编码实验报告
- 格式：doc
- 大小：53.00 KB
- 文档页数：11
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中。然后再在主函数中将其打印出来。
Ⅲ.选出另一个权值为最小的结点…………………………………………5
Ⅳ.判断两个选出的最小权值的大小………………………………………5
2．构建哈夫曼树……………………………………………………6
Ⅰ.判断能否构建成哈夫曼树………………………………………………6
Ⅱ.对需要处理的结点和哈夫曼树的结点进行初始化……………………6
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)/*从叶子到根逆向求每个
在刚开始拿到程序的题目时，不知道从何入手，因为题目表现的比较抽象，并且自己在写哈夫曼树的过程中都遇到一些困难，所以感觉很难完成。百般无奈之下，回归课件，将哈夫曼树那一节仔细的看了几遍才看懂了编写哈夫曼树的基本思想。
三、
1、结构体定义的说明
哈夫曼树重点在于如何排列权值大小不同的结点的顺序，所以定义结构体如下：
typedef struct
{
int weight;/*weight存储结点的权值*/
int parent;
int lchild;
int rchild;/*分别保存父亲、左孩子、右孩子结点*/
}HTNode,*HuffmanTree;
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号单元未用*/{
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
Ⅳ、构建完成哈夫曼树后，为知道每个结点的具体编码，必须对哈夫曼树进行遍历，且必须从叶子结点向根结点逆序进行遍历。
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
而另一个重点在于将两个权值为最小的结点分别作为左、右子树，所以定义结构体如下：
typedef struct
{
unsigned int s1;
unsigned int s2;/*分别存储最小和次小的结点*/
}MinCode;
2、程序结构的说明
程序主要由以下几部分组成：
结构体 struct HTNode,*Huffmantree
if(HT[i].parent==0)/*没有父亲结点说明该
{结点还未被使用过*/
min=HT[i].weight;/*给min赋初始值*/
s1=i;/*将结点的编号赋给s1*/
break;
}
tempi=i++;/*i确定下一个结点的编号*/
Ⅱ、然后利用数字排序的方法，对符合要求的结点进行判断，当存在权值更小的结点是，将该结点的内容赋给min和s1.
在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有A，B，C，D四种字符，若这四种字符采用下表所示的编码，则电文的代码为00001 000，长度为21。
在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。并且在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，以避免反译成原文时，编码出现多义性。
4、重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
所以，构造哈夫曼树主要由两个步骤组成：一是选择所有结点中权值最小的两个结点，二是将这些结点加入到二叉树中，构建成哈夫曼树。
1、在所有结点中选出权值最小的两个结点。
Ⅰ、选择权值最小的两个结点并不难，难在如何判断该结点是否已经使用过，若不能正确判断前面构造的哈夫曼树中是否使用过该结点，可能造成结点重复出现在树中，出现错误。根据哈夫曼树构造的特点，当两个结点的权值为最小时就将做为新的二叉树的左（右）子树，而它们的权值之和为它们的根结点，所以可以通过判断该结点是否有父亲结点来判断它是否被使用过。
p->rchild=0;
}
Ⅲ、构建哈夫曼树，通过Select函数选择还未被使用的且权值为最小的两个结点，将其加入到树中。
for(i=n+1;i<=m;i++)
{
min=Select(HT,i-1);
s1=;/*s1、s2分别存权值最小
s2=;的两个结点的编号*/
HT[s1].parent=i;
HT[s2].parent=i;
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;的编码进行初始化*/
2.程序结构的说明…………………………………………………3
四、程序设计的基本思想、部分源代码及注释………………………3
1.选择权值最小的两个结点………………………………………4
Ⅰ.判断结点是否已经被使用过……………………………………………4
Ⅱ.选出权值为最小的结点…………………………………………………4
}
}
Ⅳ、再通过判断结点s1和结点s2的权值的大小来确定权值为最小的结点和权值为第二小的结点，并将值保存再结构体中。
if(s1>s2)
{s2=temp;
}
=s1;
=s2;
return code;
2、将选择出来的结点一个个逐步构建成哈夫曼树。
Ⅰ、哈夫曼树实现的功能就是将若干个结点以最优化的顺序排列出来，所以当结点数n=1时，不存在构建哈夫曼树的问题。因此，首先对可能出现的这种状况进行判断。
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;
Ⅰ、输出每个结点的父亲、左孩子、右孩子结点的编号，从而确定每个结点的具体位置。由于在构建哈夫曼树的Create函数中已经完成了每个结点的父亲、左孩子、右孩子结点的赋值，所以只需要将这些值直接输出即可。
printf("HT List:\n");
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
结构体 struct MinCode
函数Select ——用以选择结点中权值最小的两个结点
函数CreateTree ——将选出来的结点按规律逐步建成哈夫曼树
函数 main ——主函数
四
根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。因此，构造哈夫曼树有此种方法：
五、流程图
六、实验结果演示
七、在编写程序过程中遇到的困难和解决的方法
一、实验内容
根据输入的n个带权结点，构造出哈夫曼树，并且把构造结果输出到屏幕。
二、实验说明
哈夫曼数，也称最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。
设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度WPL，记作：WPL= 。在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。
Ⅲ.构建哈夫曼树……………………………………………………………6
Ⅳ.对构建好的哈夫曼树进行遍历确定每个结点的编码…………………7
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中。然后再在主函数中将其打印出来。
Ⅲ.选出另一个权值为最小的结点…………………………………………5
Ⅳ.判断两个选出的最小权值的大小………………………………………5
2．构建哈夫曼树……………………………………………………6
Ⅰ.判断能否构建成哈夫曼树………………………………………………6
Ⅱ.对需要处理的结点和哈夫曼树的结点进行初始化……………………6
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)/*从叶子到根逆向求每个
在刚开始拿到程序的题目时，不知道从何入手，因为题目表现的比较抽象，并且自己在写哈夫曼树的过程中都遇到一些困难，所以感觉很难完成。百般无奈之下，回归课件，将哈夫曼树那一节仔细的看了几遍才看懂了编写哈夫曼树的基本思想。
三、
1、结构体定义的说明
哈夫曼树重点在于如何排列权值大小不同的结点的顺序，所以定义结构体如下：
typedef struct
{
int weight;/*weight存储结点的权值*/
int parent;
int lchild;
int rchild;/*分别保存父亲、左孩子、右孩子结点*/
}HTNode,*HuffmanTree;
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号单元未用*/{
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
Ⅳ、构建完成哈夫曼树后，为知道每个结点的具体编码，必须对哈夫曼树进行遍历，且必须从叶子结点向根结点逆序进行遍历。
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
而另一个重点在于将两个权值为最小的结点分别作为左、右子树，所以定义结构体如下：
typedef struct
{
unsigned int s1;
unsigned int s2;/*分别存储最小和次小的结点*/
}MinCode;
2、程序结构的说明
程序主要由以下几部分组成：
结构体 struct HTNode,*Huffmantree
if(HT[i].parent==0)/*没有父亲结点说明该
{结点还未被使用过*/
min=HT[i].weight;/*给min赋初始值*/
s1=i;/*将结点的编号赋给s1*/
break;
}
tempi=i++;/*i确定下一个结点的编号*/
Ⅱ、然后利用数字排序的方法，对符合要求的结点进行判断，当存在权值更小的结点是，将该结点的内容赋给min和s1.
在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有A，B，C，D四种字符，若这四种字符采用下表所示的编码，则电文的代码为00001 000，长度为21。
在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。并且在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，以避免反译成原文时，编码出现多义性。
4、重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
所以，构造哈夫曼树主要由两个步骤组成：一是选择所有结点中权值最小的两个结点，二是将这些结点加入到二叉树中，构建成哈夫曼树。
1、在所有结点中选出权值最小的两个结点。
Ⅰ、选择权值最小的两个结点并不难，难在如何判断该结点是否已经使用过，若不能正确判断前面构造的哈夫曼树中是否使用过该结点，可能造成结点重复出现在树中，出现错误。根据哈夫曼树构造的特点，当两个结点的权值为最小时就将做为新的二叉树的左（右）子树，而它们的权值之和为它们的根结点，所以可以通过判断该结点是否有父亲结点来判断它是否被使用过。
p->rchild=0;
}
Ⅲ、构建哈夫曼树，通过Select函数选择还未被使用的且权值为最小的两个结点，将其加入到树中。
for(i=n+1;i<=m;i++)
{
min=Select(HT,i-1);
s1=;/*s1、s2分别存权值最小
s2=;的两个结点的编号*/
HT[s1].parent=i;
HT[s2].parent=i;
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;的编码进行初始化*/
2.程序结构的说明…………………………………………………3
四、程序设计的基本思想、部分源代码及注释………………………3
1.选择权值最小的两个结点………………………………………4
Ⅰ.判断结点是否已经被使用过……………………………………………4
Ⅱ.选出权值为最小的结点…………………………………………………4
}
}
Ⅳ、再通过判断结点s1和结点s2的权值的大小来确定权值为最小的结点和权值为第二小的结点，并将值保存再结构体中。
if(s1>s2)
{s2=temp;
}
=s1;
=s2;
return code;
2、将选择出来的结点一个个逐步构建成哈夫曼树。
Ⅰ、哈夫曼树实现的功能就是将若干个结点以最优化的顺序排列出来，所以当结点数n=1时，不存在构建哈夫曼树的问题。因此，首先对可能出现的这种状况进行判断。
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;
Ⅰ、输出每个结点的父亲、左孩子、右孩子结点的编号，从而确定每个结点的具体位置。由于在构建哈夫曼树的Create函数中已经完成了每个结点的父亲、左孩子、右孩子结点的赋值，所以只需要将这些值直接输出即可。
printf("HT List:\n");
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
结构体 struct MinCode
函数Select ——用以选择结点中权值最小的两个结点
函数CreateTree ——将选出来的结点按规律逐步建成哈夫曼树
函数 main ——主函数
四
根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。因此，构造哈夫曼树有此种方法：
五、流程图
六、实验结果演示
七、在编写程序过程中遇到的困难和解决的方法
一、实验内容
根据输入的n个带权结点，构造出哈夫曼树，并且把构造结果输出到屏幕。
二、实验说明
哈夫曼数，也称最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。
设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度WPL，记作：WPL= 。在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。
Ⅲ.构建哈夫曼树……………………………………………………………6
Ⅳ.对构建好的哈夫曼树进行遍历确定每个结点的编码…………………7
