hafuman.cpp

哈夫曼树的建立 根据学生成绩出现的频率创建相应的哈夫曼树

#define n 5//哈夫曼树叶子结点数
#define m 2*n-1 //哈夫曼树中的结点总数
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>
typedef struct
{
	int weight;//结点权值
	int lchild,rchild,parent;
}HTNode;
typedef HTNode HuffmanTree[m+1];

void select(HuffmanTree HTree,int k,int *s1,int *s2)
{
	int i,j,min1=32767;
	for(i=1;i<=k;i++)
		if(HTree[i].weight<min1&&HTree[i].parent==0)
		{
			j=i;
			min1=HTree[i].weight;
		}
		*s1=j;
		min1=32767;
		for(i=1;i<=k;i++)
			if(HTree[i].weight<min1 && HTree[i].parent==0 && i != *s1)
			{
				j=i;
				min1=HTree[i].weight;
			}
			*s2=j;
}

void CreateHTree(HuffmanTree *HT,int wei[])
{
	int i,s1,s2;
	for(i=1;i<=m;i++)
	{
		(*HT)[i].lchild=0;
		(*HT)[i].rchild=0;
		(*HT)[i].parent=0;
		(*HT)[i].weight=0;
	}
	for(i=1;i<=n;i++)
		(*HT)[i].weight=wei[i];
	for(i=n+1;i<=m;i++)
	{
		select(*HT,i-1,&s1,&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;
	}
}




void main()
{
	int i,j,cj,curP,weight[n+1],pathL[n+1],minL,flag=1,minHN=0;
	char scoreCon[5][20]={">=90","80<=stuScore<90","70<=stuScore<80",
		"60<=stuScore<70","stuScore<60"};
	char condi[5][20]={"","","","",""};
	HuffmanTree *HT;
	for(i=1;i<=n;i++)
	{
		printf("请输入成绩为%s的学生比例\n",scoreCon[i-1]);
		scanf("%d",&weight[i]);
	}
		HT=(HuffmanTree *)malloc(sizeof(HuffmanTree));
		//CreateTree(HT,weight);
		for(i=1;i<=n;i++)
		{
			j=0;
			curP=i;
			while((*HT)[curP].parent!=0)
			{
				curP=(*HT)[curP].parent;
				j++;
			}
			pathL[i]=j;
		}
		cj=0;
		while(flag)
		{
			minL=n;
			for(i=1;i<=n;i++)
				if((pathL[i]<minL)&&(pathL[i]!=0))
				{
					minL=pathL[i];
					minHN=i;
				}
			strcpy(condi[cj],scoreCon[minHN-1]);
			cj++;
			pathL[minHN]=0;
			if((pathL[1]==0)&&(pathL[2]==0)&&
				(pathL[3]==0)&&(pathL[4]==0)&&(pathL[5]==0))
				flag=0;
		}
		printf("根据创建的最佳判定树，学生成绩判定程序的最佳判定条件顺序为：\n");
		for(j=1;j<=n;j++)
		{
			printf("%d：%s\n",j,condi[j-1]);
		}
		getch();
}