#include
#include
#include
const?int?maxn=100;

typedef?struct?Node{
	int?weight;//權值
	int?parent;//父節點的序號，為0表示根節點
	int?lchildrchild;//左右孩子節點的序號，為0的是葉子節點
}HTNode*HuffmanTree;//用來存儲每個葉子節點的霍夫曼編碼

char?HC[maxn][maxn+5];//用來存儲每個節點的霍夫曼編碼

struct?Ans{
	char?ch;
	int?wet;
}ans[maxn];

//從HT數組的前k個元素中選出weight最小且parent為0的元素，并將該元素的下標返回
int?min（HuffmanTree?HTint?k）
{
	int?i=0;
	int?min;//用來存放weight最小且parent為0的元素的下標
	int?min_weight;//用來存放weight最小且parent為0的元素的weight值的temp

	//注意應先將第一個parent為0的元素的weight值賦給min_weight留作以后比較用
	//不要直接將HT[0].weight賦給min_weight了（這是個常用的技巧）
	while（HT[i].parent!=0）?i++;
	min_weight=HT[i].weight;
	min=i;

	//選出weight最小且parent為0的元素，并將其序號賦給min
	for（;i		if（HT[i].weight			min_weight=HT[i].weight;
			min=i;
		}
	}

	//注意，選出weight最小的元素后，將其parent置1，使得下一次求第二小時將其排除在外
	HT[min].parent=1;
	return?min;//返回下標
}

void?select_min（HuffmanTree?HTint?kint?&min1int?&min2）//&為引用
{
	min1=min（HTk）;
	min2=min（HTk）;
}

HuffmanTree?create_HuffmanTree（struct?Ans?*pint?n）
{
	//一顆有n個葉子節點的霍夫曼樹共有2n-1個節點（特點）
	int?total=2*n-1;
	HuffmanTree?HT=（HuffmanTree）malloc（total*sizeof（HTNode））;
	if（!HT）{
		printf（“HuffmanTree?malloc?failed!\n“）;
	}

	int?i;
	for（i=0;i		HT[i].parent=0;//parent后面會改變
		HT[i].lchild=0;
		HT[i].rchild=0;
		HT[i].weight=p->wet;
		p++;
	}

	//HT[n]HT[n+1]...HT[2n-2]中存放的是中間構造出的每棵二叉樹的根節點
	for（;i		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
		HT[i].weight=0;
	}

	int?min1min2;//用來保存每一輪選出的兩個weight最小且parent為0的節點下標


	//每一輪比較后選擇出min1和min2構成一課二叉樹最后構成一棵赫夫曼樹
	for（i=n;i		select_min（HTimin1min2）;//尋找i之前的結點
		HT[min1].parent=i;
		HT[min2].parent=i;//兩個最小權值的結點構成子樹

		//注意這里左孩子和右孩子可以反過來，構成的也是一棵赫夫曼樹，只是所得的編碼不同
		HT[i].lchild=min1;
		HT[i].rchild=min2;
		HT[i].weight=HT[min1].weight+HT[min2].weight;
	}
	return?HT;
}

void?HuffmanCoding（HuffmanTree?HTint?n）
{
	char?temp[maxn+5];//臨時空間，用來保存每次求得的一個赫夫曼編碼串
	temp[maxn]=‘\0‘;//編碼結束符，亦是字符數組的結束標志

	//下面求每個字符的赫夫曼編碼
	for（int?i=0;i		int?current=i;//定義當前訪問的結點
		int?fa=HT[i].parent;//定義當前節點的父節點
		int?start=maxn;//每次編碼的位置，初始為編碼結束符的位置
		//從葉子節點遍歷赫夫曼樹直到根節點
		while（fa!=0）
		{
			if（HT[fa].lchild==current）
				temp[--start]=‘0‘;
			else?temp[--start]=‘1‘;
			current=fa;
			fa=HT[current].parent;
		}
		strcpy（HC[i]temp+start）;//將編碼串從最后的start編碼~\0復制到HC上
	}
}

int?n;//需要編碼的字符數
void?Initialzation（）
{
	FILE?*fp1;
	fp1=fopen（“DataFile.txt““rb“）;
	printf（“從文件DataFile.txt中讀取編碼的字符種類個數\n“）;
	fscanf（fp1“%d“&n）;

	printf（“以及這%d個字符及其權值（整型）\n“n）;
	for（int?i=0;i		fscanf（fp1“?%c?%d“&ans[i].ch&ans[i].wet）;//注意%c前面有空格
	}
	HuffmanTree?HT=create_HuffmanTree（ansn）;//用數組生成霍夫曼樹
	HuffmanCoding（HTn）;//求解每個字符的霍夫曼編碼

	printf（“各字符對應權值的霍夫曼編碼為（按照輸入順序）:\n“）;
	for（int?i=0;i		printf（“%c?:“ans[i].ch）;
		puts（HC[i]）;
	}
	fclose（fp1）;
	print

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????551??2017-06-21?15:56??項目四\Code.txt

?????文件????????551??2017-06-21?14:28??項目四\CodeFile.txt

?????文件????????124??2017-06-21?14:01??項目四\DataFile.txt

?????文件????????150??2017-06-21?15:56??項目四\Textfile.txt

?????文件????????150??2017-06-21?13:59??項目四\ToBeTran.txt

?????文件???????7030??2017-06-21?15:56??項目四\4.cpp

?????文件???????5647??2017-06-21?15:56??項目四\4.o

?????文件??????34210??2017-06-21?15:56??項目四\4.exe

?????目錄??????????0??2017-06-21?15:53??項目四

-----------?---------??----------?-----??----

????????????????48413????????????????????9