#include?

int?s1?s2;
const?int?maxn?=?101;
typedef?struct{
	int?weight;
	int?leftchild?rightchild?parent;
}huffuman;

void?select（huffuman?tree[]?int?k）;
void?huffumantree（huffuman?tree[]?int?w[]?int?n）;
void?huffumancode（huffuman?tree[]?int?n）;

int?main（）
{
	int?n;
	int?x;
	int?w[maxn];
	char?cha[maxn];
	huffuman?tree[maxn];
	printf?（“-----來建立一棵huffumantree吧！！！-----\n“）;
	while?（1）?{
		
		printf?（“	1.建立哈夫曼樹\n“）;
		printf?（“	2.輸出哈夫曼樹\n“）;
		printf?（“	3.退出\n“）;
		printf?（“請輸入選項：“）;		
		scanf?（“%d“?&x）;	
//		printf?（“x?=?%d\n“?x）;
			
		if?（x?==?1）{
			printf?（“***開始建樹操作***\n“）;
			printf?（“請輸入帶編碼字符個數：“）;?
			scanf?（“%d“?&n）;
			getchar（）;
			printf?（“開始輸入字符和對應的權值：\n“）;
			for?（int?i=1;?i<=n;?i++）?{
				printf?（“字符?對應的權值：\n“）;
				scanf?（“%c%d“?&cha[i]?&w[i]）;
				getchar（）;
			}
			huffumantree（tree?w?n）;
		}
		
		if?（x?==?2）?{
			printf?（“***開始輸出操作***\n“）;
			huffumancode（tree?n）;	
		}
		?
		if?（x?==?3）?{
			return?0;
		}
		
		if?（x?!=?1?&&?x?!=?2?&&?x!=?3）
			printf?（“請輸入正確的選項！！！\n“）;
	}
	return?0;	
}?

void?select?（huffuman?tree[]?int?k）
{
	int?i;
	for?（i=1;?i<=k?&&?tree[i].parent?!=?0;?i++）;
	s1?=?i;
	
	for?（i=1;?i<=k;?i++）?{
		if?（tree[i].weight?			s1?=?i;
	}
	
	for?（i=1;?i<=k;?i++）
		if?（i?!=?s1?&&?tree[i].parent?==?0）
			break;
	s2?=?i;
	
	for?（i=1;?i<=k;?i++）?{
		if?（i?!=?s1?&&?tree[i].parent?==?0）
			if?（tree[i].weight?				s2?=?i;
	}
}

void?huffumantree（huffuman?tree[]?int?w[]?int?n）
{
	if?（n?<=?1）
		return;
	int?i;
	int?m?=?2?*?n?-?1;
	for?（i=1;?i<=n;?i++）?{
		tree[i].weight?=?w[i];
		tree[i].parent?=?0;
		tree[i].leftchild?=?0;
		tree[i].rightchild?=?0;
	}
	
	for?（i=n+1;?i<=m;?i++）?{
		tree[i].weight?=?0;
		tree[i].parent?=?0;
		tree[i].leftchild?=?0;
		tree[i].rightchild?=?0;		
	}
	
	for?（i=n+1;?i<=m;?i++）?{
		select（tree?i-1）;
		tree[s1].parent?=?i;
		tree[s2].parent?=?i;
		tree[i].leftchild?=?s1;
		tree[i].rightchild?=?s2;
		tree[i].weight?=?tree[s1].weight?+?tree[s2].weight;
	}
	
}

void?huffumancode（huffuman?tree[]?int?n）
{
	printf?（“***i***weight***parent***leftchild***rightchild***\n“）;
	for?（int?i=1;?i<=2*n-1;?i++）?{
		printf?（“--%2d???%6d???%6d???%9d???%10d---\n“?i?tree[i].weight?
			tree[i].parent?tree[i].leftchild?tree[i].rightchild）;
	}
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2018-08-10?12:40??數據結構huffumantree課程設計\
?????文件????????2506??2018-07-03?10:16??數據結構huffumantree課程設計\huffuman.cpp
?????文件??????239104??2018-08-10?12:39??數據結構huffumantree課程設計\課程設計報告書.doc