#include
#include
#include
#include

#define?MAXNUM?60

typedef?struct
{
	char?ch;
	int?weight;?//權值，這個字符出現的頻率
	int?parent;
	int?left;
	int?right;
}HuffNode;

typedef?struct
{
	char?code[MAXNUM];
	int?start;
}HuffCode;

HuffNode?ht[MAXNUM*2];?//存放哈夫曼樹

HuffCode?hcd[MAXNUM];??//存放ht數組中對應的字符的編碼

int?n;?????????????????//字符的個數

//初始化哈夫曼樹ht
void?initHt（）
{
	FILE?*?fp;
	char?ch;
	int?i=0;
	//從文件document/character.txt中讀出要編碼的字符和權值
	if（（fp=fopen（“document/character.txt““r“））==NULL）{
		printf（“can?not?open?the?file?character.txt“）;
		exit（0）;
	}
	ht[i].left=ht[i].right=ht[i].parent=-1;
	while（（ch=fgetc（fp））!=EOF）{
		if（ch==‘\n‘）{
			i++;
			ht[i].left=ht[i].right=ht[i].parent=-1;		
		}
		else?if（（ch>=‘a‘?&&?ch<=‘z‘）||（ch>=‘A‘?&&?ch<=‘Z‘））
			ht[i].ch=ch;
		else?if（ch>=‘0‘&&ch<=‘9‘）
			ht[i].weight=ht[i].weight*10+ch-‘0‘;
	}
	n=i+1;
	if（fclose（fp））{
		printf（“can?not?close?the?file?character.txt“）;
		exit（0）;
	}
}

//構造哈夫曼樹看成有n棵樹，選擇權值最小的兩棵樹合并
void?createHuffTree（）
{

	int?i=0k;
	int?minIminJ;
	int?f=0;
	minI=minJ=-1;?//minI	for（k=n;k<2*n-1;k++）{
		//尋找ht中權值最小且無父結點的兩個結點
		i=0;
		f=0;
????	while（ht[i].ch!=‘\0‘）{
????		if（ht[i].parent==-1）{
	????		if（f==0）{
????????????		minI=i;
		??????????	f++;
				}else?if（f==1）{
					if（ht[i].weight						minJ=minI;
						minI=i;
					}else
			????		minJ=i;
					f++;
				}else{
			????	if（ht[i].weight			????		minJ=minI;
			????		minI=i;
					}else?if（ht[i].weight						minJ=i;
				}
			}
????		i++;
		}
		//合并兩個結點
		ht[k].ch=‘#‘;
		ht[k].left=minI;
		ht[k].right=minJ;
		ht[k].weight=ht[minI].weight+ht[minJ].weight;
		ht[k].parent=-1;
		ht[minI].parent=ht[minJ].parent=k;
	}
}

//將一個字符串反轉
void?reverse（char?*str）
{
	int?ij;
	char?ch;
	for（i=0j=strlen（str）-1;i		ch=str[i];
		str[i]=str[j];
		str[j]=ch;
	}
}

//哈夫曼編碼，通過父節點從下往上找
void?createHuffCode（）
{
????int?ijlength;
	FILE?*?fp;
	for（i=0;i		length=0;
		j=i;
		//給每個字符進行編碼
		while（ht[j].parent!=-1）{
????		if（ht[ht[j].parent].left==j）{
		????	hcd[i].code[length++]=0+‘0‘;
			}else
		????	hcd[i].code[length++]=1+‘0‘;
			j=ht[j].parent;
		}

		hcd[i].start=hcd[i].code[length-1]-‘0‘;
		hcd[i].code[length]=‘\0‘;
		reverse（hcd[i].code）;
	}
	//把hcd字符編碼寫入文件document/code.txt中
	if（（fp=fopen（“document/code.txt““w“））==NULL）{
		printf（“can?not?open?the?file?character.txt“）;
		exit（0）;
	}
????for（i=0;i		fputc（ht[i].chfp）;
		fputs（“????“fp）;
		fputs（hcd[i].codefp）;
		fputc（‘\n‘fp）;
	}
	if（fclose（fp））{
		printf（“can?not?close?the?file?character.txt“）;
		exit（0）;
	}
}

//哈夫曼解碼，每次都從根節點開始搜索
int?releaseHuffCode（char?*strchar*?code）
{
	int?root=2*n-2;
	int?length=0i=0;
	while（code[i]）{
		if（code[i]==‘0‘+0）
			root=ht[root].left;
		else?if（code[i]==‘0‘+1）
			root=ht[root].right;
		else
			return?0;
	

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

?????文件????????328??2011-05-26?07:25??源代碼\document\character.txt

?????文件????????694??2011-05-26?07:30??源代碼\document\code.txt

?????文件???????5049??2011-05-26?07:22??源代碼\Huffman.c

?????目錄??????????0??2011-05-26?07:34??源代碼\document

?????目錄??????????0??2011-05-26?07:34??源代碼

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

?????????????????6071????????????????????5