【正文】 =(low+high)/2； internal_code=int(L[mid].internal_codeamp。w,intamp。n)； bool xj_Init(char*filename,HuffmanPCodeamp。s2)； void xj_Statistics(HuffmanPCodeamp。 三、程序源代碼 ifndef _COURSEDESIGN_H_ define _COURSEDESIGN_H_ //Huffman 樹存儲結(jié)構(gòu) typedef struct { char ch[3]； unsigned int weight； unsigned int parent,lchild,rchild； }HTNode,*HuffmanTree； //Huffman 編碼表存儲結(jié)構(gòu) typedef struct { char internal_code； char*code； }InternalCode； typedef struct { int count； char internal_code； InternalCode*internal_code_address； }HuffmanCode,*HuffmanPCode； //解碼表存儲結(jié)構(gòu) typedef struct { char ch[3]； unsigned int lchild,rchild； }DecodeList,*DecodePList； //輔助數(shù)組，置 /取一個字節(jié)的指定位 const static unsigned char mask[8]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01}； template class Tstatic int xj_Search_Bin(int key,T L,int low,int high)； template class Tstatic void xj_InsertSort(T L,int start,int end)； void xj_Select(const HuffmanTree HT,int n,intamp。編碼文件的結(jié)構(gòu)如下圖所示： 圖 4壓縮文件存儲結(jié)構(gòu) 程序解壓文件：打開壓縮文件，取出壓縮文件的解碼表長度 N，根據(jù) N 讀取 N條解碼表記錄，重建解碼表 HT，然后讀取壓縮數(shù)據(jù) DATA，解碼的過程是從根出 發(fā)，按 DATA數(shù)據(jù)的 0或 1 確定找左子樹還是右子樹，直至葉子結(jié)點，便求得了 DATA相應(yīng)的字符。所以需要將字符串 0101轉(zhuǎn)換為二進(jìn)制 0101寫入文件。當(dāng)字符編碼完成之后，打開壓縮文件，將赫夫曼樹 HT中除權(quán)重以外的數(shù)據(jù) (解碼無需權(quán)重信息 )寫入壓縮文件中，作為下一次解壓縮的解碼表。例如圖 2 中 把 的權(quán)值為 14，對應(yīng)的編碼為： 000。赫夫曼樹存儲結(jié)構(gòu)的初始狀態(tài)如圖3(a)，終結(jié)狀態(tài)如圖 3(b)。依次從 w中選擇權(quán)重最小并且雙親為 0的兩個結(jié)點，根據(jù)這兩個結(jié)點生成新的結(jié)點，新結(jié)點的權(quán)重為這兩個最小結(jié)點的和，新結(jié)點的左右子樹為這兩個結(jié)點在 w中的位置。否則將漢字的第一字節(jié)機內(nèi)碼按非遞減次序插入 HC 表的內(nèi)碼 1 區(qū)域，第二字節(jié)機內(nèi)碼直接插入內(nèi)碼 2處。例如 ,HC[3]中字符數(shù)為 7， HC[2]中字符數(shù)為 2，則 HC[3]存放了 5 個字符，這 5個字符擁有相同的第一字節(jié)機內(nèi)碼 176。圖 1中編碼表 HC 的內(nèi)碼 1是縱向非遞減排列，內(nèi)碼 2 是橫向非遞減排列。 圖 1編碼表 HC 的存儲結(jié)構(gòu) 這種數(shù)據(jù)結(jié)構(gòu)形式上類似于圖的鄰接表結(jié)構(gòu)，功能上類似于哈希表的鏈地址法。通過分析，采用如下數(shù)據(jù)結(jié)構(gòu)： typedef struct { char internal_code； //存放第二字節(jié)機內(nèi)碼 char*code； //存放字符的赫夫曼編碼 }InternalCode； typedef struct { int count； //已編碼字符數(shù) char internal_code； //存放第一字節(jié)機內(nèi)碼 InternalCode*internal_code_address； //第二字節(jié)機內(nèi)碼及字符的 }HuffmanCode,*HuffmanPCode； //赫夫曼編碼的地址 該結(jié)構(gòu)的優(yōu)點：當(dāng)漢字的第一字節(jié)機內(nèi)碼相同，則該第一字節(jié)機內(nèi)碼只會被存儲一次，從而消除漢字第一字節(jié)機內(nèi)碼存儲的冗余，而且可以方便的使用折半查找快速檢索編碼表來確定字符的赫夫曼編碼。如果采用如上的數(shù)據(jù)結(jié)構(gòu)建立的線性表來存放處理字符，就會存在大量數(shù)據(jù)冗余?，F(xiàn)在需要考慮使用怎樣的數(shù)據(jù)結(jié)構(gòu)來存放這些字符，如果采用如下簡單的數(shù)據(jù)結(jié)構(gòu)存放： typedef struct { char data[3]； //存放字符 int internal_code1； //存放第一字節(jié)的機內(nèi)碼 /ASCII 碼 int internal_code2； //存放第 二字節(jié)的機內(nèi)碼，英文默認(rèn)為 0 int weight； //存放字符的權(quán)重 char*code； //字符的赫夫曼編碼 }CodeList,*CodePList； 分析所要處理的字符數(shù)據(jù)會發(fā)現(xiàn)：許多的字符的第一字節(jié)的機內(nèi)碼相同，如 防 、 飛 、 方 、 份 ，第一字節(jié)機內(nèi)碼都是 表 1文件字符屬性表 字符第一字節(jié)機內(nèi)碼 /ASCII 第二字節(jié)機內(nèi)碼權(quán)重 的 18119620 a9709 把 17620914 表 1772375 班 1762241 補 1781852 百 17621417 防 18319212 飛 1832021 博 17816913 包 1762522 才 1781976 方 1831898 拜 1762213 A6503 份 1832215 必 1772165 英文字符在計算機中是以標(biāo)準(zhǔn) ASCII 碼進(jìn)行表示，一個英文字符占一個字節(jié)空間，編碼范圍為 0~127；漢字在計算機中是以 GB2312 編碼進(jìn)行表示。接著程序?qū)⒔y(tǒng)計不同字符出現(xiàn)的頻率以及建立編碼表的初步結(jié)構(gòu)。程序檢查文件是否能 夠建立。 程序執(zhí)行后，用戶按照程序的提示選擇相應(yīng)的功能選項。再次重新讀取文件中的字符，對每個字符通過查閱編碼表確定對應(yīng)的編碼，將該字符的赫夫曼編碼寫入壓縮文件。在 中聲明數(shù)據(jù)的存儲結(jié)構(gòu)以及程序所需要的處理函數(shù)； 文件實現(xiàn)在 中聲明的函數(shù)； 負(fù)責(zé)對所實現(xiàn)的函數(shù)進(jìn)行調(diào)用測試，確定是否滿足程序設(shè)計要求。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些 很少出現(xiàn)的符號，則用較長的位序列。赫夫曼壓縮屬于可變代碼長度算法一族。程序的實現(xiàn)的理論依據(jù)是赫夫曼編碼。 ，培養(yǎng)計算機科學(xué)