#include
#include
#include
#include“data_structure.h“

/*
根據給定的n個權值構造一棵赫夫曼樹wet中存放n個權值
*/
HuffmanTree?create_HuffmanTree（int?*wetint?n）
{
	//一棵有n個葉子節點的赫夫曼樹共有2n-1個節點
	int?total?=?2*n-1;
	HuffmanTree?HT?=?（HuffmanTree）malloc（total*sizeof（HTNode））;
	if（!HT）
	{
		printf（“HuffmanTree?malloc?faild!“）;
		exit（-1）;
	}
	int?i;

	//以下初始化序號全部用-1表示，
	//這樣在編碼函數中進行循環判斷parent或lchild或rchild的序號時，
	//不會與HT數組中的任何一個下標混淆而造成誤判

	//HT[0]HT[1]...HT[n-1]中存放需要編碼的n個葉子節點
	for（i=0;i	{
		HT[i].parent?=?-1;
		HT[i].lchild?=?-1;
		HT[i].rchild?=?-1;
		HT[i].weight?=?*wet;
		wet++;
	}

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

	int?min1min2;?//用來保存每一輪選出的兩個weight最小且parent為0的節點
	//每一輪比較后選擇出min1和min2構成一課二叉樹最后構成一棵赫夫曼樹
	for（i=n;i	{
		select_minium（HTimin1min2）;
		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;
}

/*
從HT數組的前k個元素中選出weight最小且parent為-1的兩個，分別將其序號保存在min1和min2中
*/
void?select_minium（HuffmanTree?HTint?kint?&min1int?&min2）
{
	min1?=?min（HTk）;
	min2?=?min（HTk）;
}

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

	//先將第一個parent為-1的元素的weight值賦給min_weight留作以后比較用。
	//注意，這里不能按照一般的做法，先直接將HT[0].weight賦給min_weight，
	//因為如果HT[0].weight的值比較小，那么在第一次構造二叉樹時就會被選走，
	//而后續的每一輪選擇最小權值構造二叉樹的比較還是先用HT[0].weight的值來進行判斷，
	//這樣又會再次將其選走，從而產生邏輯上的錯誤。
	while（HT[i].parent?!=?-1）
		i++;
	min_weight?=?HT[i].weight;
	min?=?i;

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

????//選出weight最小的元素后，將其parent置1，使得下一次比較時將其排除在外。
	HT[min].parent?=?1;?

	return?min;
}

/*
從葉子節點到根節點逆向求赫夫曼樹HT中n個葉子節點的赫夫曼編碼，并保存在HC中
*/
void?HuffmanCoding（HuffmanTree?HTHuffmanCode?&HCint?n）
{
	//用來保存指向每個赫夫曼編碼串的指針
	HC?=?（HuffmanCode）malloc（n*sizeof（char?*））;
	if（!HC）
	{
		printf（“HuffmanCode?malloc?faild!“）;
		exit（-1）;
	}

	//臨時空間，用來保存每次求得的赫夫曼編碼串
	//對于有n個葉子節點的赫夫曼樹，各葉子節點的編碼長度最長不超過n-1
	//外加一個‘\0‘結束符，因此分配的數組長度最長為n即可
	char?*code?=?（char?*）malloc（n*sizeof（char））;
	if（!code）
	{
		printf（“code?malloc?faild!“）;
		exit（-1）;
	}

	code[n-1]?=?‘\0‘;??//編碼結束符，亦是字符數組的結束標志
	//求每個字符的赫夫曼編碼
	int?i;
	for（i=0;i	{
		int?current?=?i;???????????//定義當前訪問的節點
		int?father?=?HT[i].parent;?//當前節點的父節點
		int?start?=?n-1;???????????//每次編碼的位置，初始為編碼結束符的位置
		//從葉子節點遍歷赫夫曼樹直到根節點
		while（father?!=?-1）
		{
			if（HT[father].lchild?==?current）???//如果是左孩子，則編碼為0
				code[--start]?=?‘0‘;????
			else??????????????????????????????//如果是右孩子，則編碼為1???????
				code[-

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2014-02-15?20:14??Huffman?tree\
?????文件????????6170??2014-02-15?20:02??Huffman?tree\Function.cpp
?????目錄???????????0??2014-02-15?20:14??Huffman?tree\HuffmanCoding\
?????目錄???????????0??2014-02-15?20:14??Huffman?tree\HuffmanCoding\Debug\
?????文件????????7974??2014-02-15?20:02??Huffman?tree\HuffmanCoding\Debug\Function.obj
?????文件??????184403??2014-02-15?20:02??Huffman?tree\HuffmanCoding\Debug\HuffmanCoding.exe
?????文件??????237916??2014-02-15?20:02??Huffman?tree\HuffmanCoding\Debug\HuffmanCoding.ilk
?????文件??????227172??2014-02-15?19:46??Huffman?tree\HuffmanCoding\Debug\HuffmanCoding.pch
?????文件??????451584??2014-02-15?20:02??Huffman?tree\HuffmanCoding\Debug\HuffmanCoding.pdb
?????文件????????3575??2014-02-15?20:02??Huffman?tree\HuffmanCoding\Debug\main.obj
?????文件???????50176??2014-02-15?20:02??Huffman?tree\HuffmanCoding\Debug\vc60.idb
?????文件???????53248??2014-02-15?20:02??Huffman?tree\HuffmanCoding\Debug\vc60.pdb
?????文件????????4490??2014-02-13?20:27??Huffman?tree\HuffmanCoding\HuffmanCoding.dsp
?????文件?????????534??2014-02-13?13:12??Huffman?tree\HuffmanCoding\HuffmanCoding.dsw
?????文件???????50176??2014-02-15?20:14??Huffman?tree\HuffmanCoding\HuffmanCoding.ncb
?????文件???????48640??2014-02-15?20:14??Huffman?tree\HuffmanCoding\HuffmanCoding.opt
?????文件?????????260??2014-02-15?20:02??Huffman?tree\HuffmanCoding\HuffmanCoding.plg
?????文件?????????983??2014-02-15?19:46??Huffman?tree\data_structure.h
?????文件?????????784??2014-02-15?20:02??Huffman?tree\main.cpp