#include?
#include?
#include?
#include?
#include?
#include?
using?namespace?std;
//?統計字符頻度的臨時結點
typedef?struct?{
	unsigned?char?uch;			//?以8bits為單元的無符號字符
	unsigned?long?weight;		//?每類（以二進制編碼區分）字符出現頻度
}?TmpNode;

//?哈夫曼樹結點
typedef?struct?{
	unsigned?char?uch;				//?以8bits為單元的無符號字符
	unsigned?long?weight;			//?每類（以二進制編碼區分）字符出現頻度
	char?*code;						//?字符對應的哈夫曼編碼（動態分配存儲空間）
	int?parent?lchild?rchild;		//?定義雙親和左右孩子
}?HufNode?*HufTree;

//?選擇最小和次小的兩個結點，建立哈夫曼樹調用
void?select（HufNode?*huf_tree?unsigned?int?n?int?*s1?int?*s2）
{
	//?找最小
	unsigned?int?i;
	unsigned?long?min?=?ULONG_MAX;
	for?（i?=?0;?i?		if?（huf_tree[i].parent?==?0?&&?huf_tree[i].weight?		{
			min?=?huf_tree[i].weight;
			*s1?=?i;
		}
	huf_tree[*s1].parent?=?1;???//?標記此結點已被選中

								//?找次小
	min?=?ULONG_MAX;
	for?（i?=?0;?i?		if?（huf_tree[i].parent?==?0?&&?huf_tree[i].weight?		{
			min?=?huf_tree[i].weight;
			*s2?=?i;
		}
}

//?建立哈夫曼樹
void?CreateTree（HufNode?*huf_tree?unsigned?int?char_kinds?unsigned?int?node_num）
{
	unsigned?int?i;
	int?s1?s2;
	for?（i?=?char_kinds;?i?	{
		select（huf_tree?i?&s1?&s2）;		//?選擇最小的兩個結點
		huf_tree[s1].parent?=?huf_tree[s2].parent?=?i;
		huf_tree[i].lchild?=?s1;
		huf_tree[i].rchild?=?s2;
		huf_tree[i].weight?=?huf_tree[s1].weight?+?huf_tree[s2].weight;
	}
}

//?生成哈夫曼編碼
void?HufCode（HufNode?*huf_tree?unsigned?char_kinds）
{
	unsigned?int?i;
	int?cur?next?index;
	char?*code_tmp?=?（char?*）malloc（256?*?sizeof（char））;		//?暫存編碼，最多256個葉子，編碼長度不超多255
	code_tmp[256?-?1]?=?‘\0‘;

	for?（i?=?0;?i?	{
		index?=?256?-?1;	//?編碼臨時空間索引初始化

							//?從葉子向根反向遍歷求編碼
		for?（cur?=?i?next?=?huf_tree[i].parent;?next?!=?0;
			cur?=?next?next?=?huf_tree[next].parent）
			if?（huf_tree[next].lchild?==?cur）
				code_tmp[--index]?=?‘0‘;	//?左‘0’
			else
				code_tmp[--index]?=?‘1‘;	//?右‘1’
		huf_tree[i].code?=?（char?*）malloc（（256?-?index）?*?sizeof（char））;			//?為第i個字符編碼動態分配存儲空間?
		strcpy（huf_tree[i].code?&code_tmp[index]）;?????//?正向保存編碼到樹結點相應域中
	}
	free（code_tmp）;		//?釋放編碼臨時空間
}

//?壓縮函數
int?compress（char?*ifname?char?*ofname）
{
	unsigned?int?i?j;
	unsigned?int?char_kinds;		//?字符種類
	unsigned?char?char_temp;		//?暫存8bits字符
	unsigned?long?file_len?=?0;
	unsigned?long?length1?length2?pt;
	//unsigned?long?size;
	double?div;
	FILE?*infile?*outfile;
	TmpNode?node_temp;
	unsigned?int?node_num;
	HufTree?huf_tree;
	char?code_buf[256]?=?“\0“;		//?待存編碼緩沖區
	unsigned?int?code_len;
	/*
	**?動態分配256個結點，暫存字符頻度，
	**?統計并拷貝到樹結點后立即釋放
	*/
	TmpNode?*tmp_nodes?=?（TmpNode?*）malloc（256?*?sizeof（TmpNode））;

	//?初始化暫存結點
	for?（i?=?0;?i?	{
		tmp_nodes[i].weight?=?0;
		tmp_nodes[i].uch?=?（unsigned?char）i;		//?數組的256個下標與256種字符對應
	}

	//?遍歷文件，獲取字符頻度
	infile?=?fopen（ifname?“rb“）;
	//?判斷輸入文件是否存在
	if?（infile?==?NULL）
		return?-1;
	fread（（char?*）&char_temp?sizeof（unsigned?char）?1?infile）;		//?讀入一個字符
	while?（!feof（infile））
	{
		++tmp_nodes[char_temp].weight;		//?統計下標對應字符的權重，利用數組

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2017-08-01?18:31??哈夫曼文件壓縮\
?????目錄???????????0??2017-08-01?18:31??哈夫曼文件壓縮\.vs\
?????目錄???????????0??2017-08-01?18:31??哈夫曼文件壓縮\.vs\哈夫曼文件壓縮\
?????目錄???????????0??2017-08-01?18:31??哈夫曼文件壓縮\.vs\哈夫曼文件壓縮\v14\
?????文件???????25088??2017-07-08?17:10??哈夫曼文件壓縮\.vs\哈夫曼文件壓縮\v14\.suo
?????目錄???????????0??2017-08-01?18:31??哈夫曼文件壓縮\Debug\
?????文件???????59392??2017-07-08?15:13??哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.exe
?????文件??????404480??2017-07-08?15:13??哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.ilk
?????文件?????1052672??2017-07-08?15:13??哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.pdb
?????目錄???????????0??2017-08-01?18:31??哈夫曼文件壓縮\哈夫曼文件壓縮\
?????文件????????1345??2017-07-08?08:30??哈夫曼文件壓縮\哈夫曼文件壓縮.sln
?????文件????29028352??2017-07-08?17:10??哈夫曼文件壓縮\哈夫曼文件壓縮.VC.db
?????文件???????14621??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\1.cpp
?????目錄???????????0??2017-08-01?18:31??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\
?????文件??????102947??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\1.obj
?????文件??????789504??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\vc140.idb
?????文件??????495616??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\vc140.pdb
?????文件????????1552??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.Build.CppClean.log
?????文件?????????829??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.log
?????目錄???????????0??2017-08-01?18:31??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.tlog\
?????文件?????????796??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.tlog\CL.command.1.tlog
?????文件???????26826??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.tlog\CL.read.1.tlog
?????文件?????????664??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.tlog\CL.write.1.tlog
?????文件????????1334??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.tlog\link.command.1.tlog
?????文件????????2618??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.tlog\link.read.1.tlog
?????文件?????????648??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.tlog\link.write.1.tlog
?????文件?????????241??2017-07-08?15:13??哈夫曼文件壓縮\哈夫曼文件壓縮\Debug\哈夫曼文件壓縮.tlog\哈夫曼文件壓縮.lastbuildstate
?????文件????????7412??2017-07-08?14:33??哈夫曼文件壓縮\哈夫曼文件壓縮\哈夫曼文件壓縮.vcxproj
?????文件?????????942??2017-07-08?08:47??哈夫曼文件壓縮\哈夫曼文件壓縮\哈夫曼文件壓縮.vcxproj.filters