哈夫曼树的构造方法与原理

/*——————————————————————————————
*本程序关于哈夫曼树的构造的方法与原理
*编者：04 计本（2） LGW
*编写时间：06/05/24
*最后修改时间：06/05/25
*联系方式：QQ643560001 Email scholar_ii@163.com
-----------------------------------------------------------*/
#include

#include

#define MAXSIZE 30/*自定义哈夫曼的最大个数*/

typedef struct
{
int weight;/*结点的权值*/
int parent;/*结点的双亲*/
int lchild;/*结点的左孩子*/
int rchild;/*结点的右孩子*/
int flag;/*是否用过的标志*/
}HufmTree;

int p1,p2;/*定义全局下标数字，用于Select（）函数返回当前哈夫曼树中最小
两个未用的结点/森林的下标*/
void CreatHuffman(HufmTree tree[] ,int n );/*构造哈夫曼树函数*/
void Select(HufmTree tree[] ,int i );/*选择最小两个森林的函数*/
void DisplayTree(HufmTree tree[],int Number);/*输出哈夫曼树函数*/

void main()
{
int InputNumber;/*输入森林结点的个数*/

printf("******本程序用于演示哈夫曼树的构造结果*****\n");
HufmTree mytree[MAXSIZE];/*声名一个棵哈夫曼树*/

printf("请输入结点个数：\n");
scanf("%d",&InputNumber);

CreatHuffman( mytree,InputNumber );//构造哈夫曼树
DisplayTree(mytree,InputNumber);//输出哈夫曼树
}

/*--------------------------------------------
*函数功能：构造哈夫曼树
*函数参数：自定义构造体，结构体数组
*函数返回值：没有
--------------------------------------------*/
void CreatHuffman(HufmTree tree[] ,int n )
{
int i,m;
if(n<=1)/*森林个数小于或等于一退出*/ { return; }

m=2*n;/*所建哈夫曼树最后结点的最大个数-1*/

for(i=1;i

printf("请输入结点的数值\n");/*输入有权值的结点*/
for(i=1;i<=n;i++) { scanf("%d",&tree[i].weight); }

for(i=n+1;i

/*--------------------------------------------
*函数功能：选出当前森林中的最小两个紧最小权值的结点的下标
*函数参数：参数1 自定义构造体，结构体数组。
* 参数2 当前森林结点的个数
*函数返回值：没有
--------------------------------------------*/
void Select(HufmTree tree[] ,int number )
{
int MinValue1;/*最小值*/
int MinValue2;/*第二小值*/

for(int i=1;tree[i].flag!=0;i++)/*找到前中tree[i]没有个的第一个结点*/
{ /*找到森林中的一个结点*/
}
MinValue1=tree[i].weight;/*把找到的结点当做最小的结点*/
p1=i;/*最小值结点的下标值*/

for(int j=i+1;j<=number;j++)/*与前中tree[i]中后面的结点比较*/ { if((tree[j].flag!=1)&&amp;(MinValue1>tree[j].weight))/*跳过于用过的结点（用过后不是森*/
{ /*林中的结点）*/
MinValue1=tree[j].weight;/*如果后面森林的结点值比MinValue1小*/
p1=j; /*P1就指向它*/
}
}

tree[p1].flag=1;/*把tree[p1]从森林中去掉，它已经用过*/
/*也为了p1 p2 不为同一个值*/
for( i=1;tree[i].flag!=0;i++)/*找到前中tree[i]没有个的第一个结点*/
{ /*找到森林中的一个结点*/
}
MinValue2=tree[i].weight;/*把找到的结点当做最小的结点*/
p2=i;/*第二小值结点的下标值*/

for(j=i+1;j<=number;j++) { if((tree[j].flag!=1)&&amp;(MinValue2>tree[j].weight))/*跳过于用过的结点（用过后不是森*/
{ /*林中的结点）*/
MinValue2=tree[j].weight;/*如果后面森林的结点值比MinValue1小*/
p2=j; /*P1就指向它*/
}
}
}
/*--------------------------------------------
*函数功能：输出哈夫曼树
*函数参数：参数1 自定义构造体，结构体数组。
* 参数2 输入结点的个数
*函数返回值：没有
--------------------------------------------*/
void DisplayTree(HufmTree tree[],int Number)
{
for(int i=1;i<2*number;i++)>

printf("\n");

for(i=1;i<2*number;i++) parent="%3d\n" weight="%3d\n" lchild="%3d\n" rchild="%3d\n\n">