#include?
#include?
#include?
#include?

/*?
Author:?Baocheng?Liang
E-mail:?liangbch@263.net???All?rights?reserved.?May?2012.
Homepage:?http://blog.csdn.net/liangbch
*/

/*
?該程序用來(lái)對(duì)文件進(jìn)行huffman編碼和解碼
?包括打印各個(gè)字符的huffman編碼

?編碼用的huffman樹(shù)的每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
1.?weight:?UINT32?權(quán)重值該字符在文件中出現(xiàn)的次數(shù)
2.?huffman_code:?char*?該字符對(duì)應(yīng)的huffman編碼?
3.?parent:??UINT16??父節(jié)點(diǎn)指針，0xffff表示空指針
4.?l_child:?UINT16:??左子節(jié)點(diǎn)指針，0xffff表示空指針
5.?r_child:?UINT16:??右子節(jié)點(diǎn)指針，0xffff表示空指針


采用huffman編碼后的文件格式
文件包括4個(gè)部分，文件頭單字節(jié)和雙字節(jié)的轉(zhuǎn)化表，huffman解碼樹(shù)原始文件的huffman編碼。
1.文件頭：共24個(gè)字節(jié)
1.1.?偏移0:?標(biāo)記：4個(gè)字節(jié)，他們是BCHM
1.2.?偏移4?UINT32：4個(gè)字節(jié)，huffman?解碼樹(shù)的非葉子節(jié)點(diǎn)數(shù)若原始文件包含n個(gè)互不相同的字符，則huffman數(shù)共有n個(gè)葉子節(jié)點(diǎn)，n-1個(gè)非葉子節(jié)點(diǎn)
1.3.?偏移8?UINT32:?4個(gè)字節(jié)，原始文件的字節(jié)數(shù)記為bc
1.4.?偏移12UINT32:?4個(gè)字節(jié)，the?huffman?編碼包含的總bit數(shù)
1.5.?偏移16：UINT32:?4個(gè)字節(jié)，單字節(jié)和雙字節(jié)的轉(zhuǎn)化表長(zhǎng)度，轉(zhuǎn)化表長(zhǎng)度最多為256，當(dāng)使用普通方法壓縮是，轉(zhuǎn)化表長(zhǎng)度為0
1.6.?偏移20：保留字符：BYTE:?1個(gè)字節(jié)
1.7??編譯21-23：?不使用：

2.單雙字節(jié)轉(zhuǎn)化表，僅僅用于與高級(jí)算法
每個(gè)節(jié)點(diǎn)共2個(gè)字節(jié)，
??tab[i*2]:表示ASCII為i的字符表示對(duì)應(yīng)的雙字節(jié)的第1個(gè)字節(jié)。
??tab[i*2+1]:表示ASCII為i的字符表示對(duì)應(yīng)的雙字節(jié)的第2個(gè)字節(jié)。
??
3.huffman解碼樹(shù)的非葉子節(jié)
每個(gè)節(jié)點(diǎn)包含3個(gè)域，flagleftright共3個(gè)字節(jié)，其數(shù)據(jù)結(jié)構(gòu)如下
3.1.?flag:?UINT8實(shí)際上只使用2個(gè)比特?
??????00b：左右子節(jié)點(diǎn)均為非葉子節(jié)點(diǎn)
??????01b：左子節(jié)點(diǎn)為葉子節(jié)點(diǎn)，此時(shí)，left字段存儲(chǔ)右子節(jié)點(diǎn)的ASCII碼
??????10b：右子節(jié)點(diǎn)為葉子節(jié)點(diǎn)，此時(shí)，right字段存儲(chǔ)左子節(jié)點(diǎn)的ASCII碼
	??11b：左右子節(jié)點(diǎn)均為葉子節(jié)點(diǎn)，此時(shí)left和right字段存儲(chǔ)左/右子節(jié)點(diǎn)的ASCII碼?
3.2.?left:?UINT8?左子節(jié)點(diǎn)的指針或左子節(jié)點(diǎn)的ASCII碼，需要查表，將編碼換成單字節(jié)或者雙字節(jié)編碼
3.3.?right:UINT8?右子節(jié)點(diǎn)的指針或右子節(jié)點(diǎn)的ASCII碼，需要查表，將編碼換成單字節(jié)或者雙字節(jié)編碼

4.?原始文件的huffman編碼，采用從高位到低為的順序存儲(chǔ)，如一個(gè)字符的huffman編碼是101001則再文件中存儲(chǔ)是，第一個(gè)字節(jié)的bit0-bit5依次是
??101001
*/

#define?NIL_PT		0xffff
#define?LEFT_IDX	0
#define?RIGHT_IDX???1
#define?LEFT_MASK	（1<#define?RIGHT_MASK	（1<#define?SLICE_ARRAY_SIZE（slice_arr）??（slice_arr.tail-slice_arr.head+1）
#define?GET_VALUE（ch1ch2）		?（（（UINT16）ch1<<8）?+?（UINT16）ch2）
#define?FREE_CODE_LOW_LIMIT		128

#define?CH_TYPE_CTR????0	//control?char?the?ASCII<32
#define?CH_TYPE_SYM	???1	//space?“““+““（“?“:“?and?so?on
#define?CH_TYPE_NUM????2	//‘0‘?to?‘9‘
#define?CH_TYPE_LET	???3	//letter?of?the?alphabet

typedef?unsigned?long??UINT32;
typedef?unsigned?short?UINT16;
typedef?unsigned?char??BYTE;

typedef?struct{
	UINT32?weight;
	char*??huffman_code;
	BYTE???bytes[2];
	UINT16?parent;
	UINT16?l_child;
	UINT16?r_child;
}HM_ENCODE_NODE;

typedef?struct{
	UINT32?weight;
	BYTE???bytes[2];
	BYTE???no;
}DOUBLE_BYTES_CODE;	


typedef?struct{
	DOUBLE_BYTES_CODE?*data;
	int?len;
}SEARCH_ARRAY;	//double?bytes?to?single?byte?convert?table


typedef?struct{
	SEARCH_ARRAY?arr;	
	int??coding_space;		//2?byte?encoding?space
	int??encode_mode;		//1:普通方式編碼，2：對(duì)雙字節(jié)組合使用單字節(jié)編碼
	BYTE?reserve_char;		//保留字符
}MAP_2BYTES_1BYTE;


typedef?struct{
	BYTE?flag;
				//:?UINT8only?use?2?bits
				//?00b：Both?left?child?node?and?right?child?node?are?non-leaf?node
				//?01b：Left?child?node?is?leaf?node?in?this?case?the?left?field?means?ASCII?of?left?child?node
				//?10b：Right?child?node?is?leaf?node?in?this?case?the?Right?field?means?ASCII?of?Right?child?node
		

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件??????24061??2012-05-09?14:40??huffmanCoding\huffmanCoding\huffmanCoding.c

?????文件???????8192??2012-05-08?07:35??huffmanCoding\huffmanCoding\huffmanCoding.suo

?????文件???????4091??2012-05-09?13:56??huffmanCoding\huffmanCoding\huffmanCoding.vcproj

?????文件????????910??2012-05-08?07:35??huffmanCoding\huffmanCoding.sln

????..A..H.??????9728??2012-05-09?14:59??huffmanCoding\huffmanCoding.suo

?????文件??????13312??2012-05-09?14:59??huffmanCoding\huffzip.exe

?????文件????1322392??2012-05-09?14:26??huffmanCoding\pi.txt

?????文件????1176511??2012-05-08?07:35??huffmanCoding\pi_data.txt

?????文件????????950??2012-05-09?14:56??huffmanCoding\ReadMe.txt

?????文件??????36352??2012-05-09?15:38??huffmanCoding\test_result.doc

?????目錄??????????0??2012-05-09?15:03??huffmanCoding\huffmanCoding

?????目錄??????????0??2012-05-09?15:38??huffmanCoding

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

??????????????2596499????????????????????12