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

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

/*
?該程序用來對文件進行huffman編碼和解碼
?包括打印各個字符的huffman編碼

?編碼用的huffman樹的每個節點的數據結構
1.?weight:?UINT32?權重值該字符在文件中出現的次數
2.?huffman_code:?char*?該字符對應的huffman編碼?
3.?parent:??UINT16??父節點指針，0xffff表示空指針
4.?l_child:?UINT16:??左子節點指針，0xffff表示空指針
5.?r_child:?UINT16:??右子節點指針，0xffff表示空指針


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

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

4.?原始文件的huffman編碼，采用從高位到低為的順序存儲，如一個字符的huffman編碼是101001則再文件中存儲是，第一個字節的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：對雙字節組合使用單字節編碼
	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
		

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

?????文件??????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