----------------------Huffman 算法的不同實(shí)現(xiàn)----------------------王詠剛，2003年7月。本目錄下的源代碼均屬示例、教學(xué)性質(zhì)。作者不對這些代碼的功能和性能作任何擔(dān)保或承諾。--------功能說明--------本目錄下的程序用8種不同的方式實(shí)現(xiàn)了Huffman編碼算法，這8種方式分別是* huffman_a 使用鏈表結(jié)構(gòu)生成Huffman樹的算法，這是最基本的實(shí)現(xiàn)方法，效率最低。* huffman_b 使用《數(shù)據(jù)結(jié)構(gòu)》（嚴(yán)蔚敏，吳偉民，1997，C語言版）中給出的算法，將二叉樹存放在連續(xù)空間里（靜態(tài)鏈表），空間的每個(gè)結(jié)點(diǎn)內(nèi)仍有左子樹、右子樹、雙親等指針。* huffman_c 使用Canonical Huffman編碼，同時(shí)對huffman_b的存儲結(jié)構(gòu)進(jìn)行改造，將二叉樹存放在連續(xù)空間tree里，空間的每個(gè)結(jié)點(diǎn)類型都和結(jié)點(diǎn)權(quán)值的數(shù)據(jù)類型相同，空間大小為2*num，tree[0]未用，tree[1..num]是每個(gè)元素的權(quán)值，生成Huffman后，tree[1..2*num-1]中是雙親結(jié)點(diǎn)索引。* huffman_d 在huffman_c的基礎(chǔ)上，增加預(yù)先排序的功能先用QuickSort算法對所有元素的權(quán)值從小到大排序，這樣，排序后最前面的兩個(gè)元素就是最小的一對元素了。我們可以直接將它們挑出來，組合成一個(gè)子樹。然后再子樹的權(quán)值用折半插入法插到已排序的元素表中， 保證所有結(jié)點(diǎn)有序。為了保證初始元素的順序不變，我們另外使用了一個(gè)索引數(shù)組，所有排序中的交換操作都是在索引數(shù)組中進(jìn)行的。* huffman_e 在huffman_d的基礎(chǔ)上，將索引數(shù)組放在tree的內(nèi)部。為編碼方便，將元素權(quán)值放在tree[num..2*num-1]處。將tree[0..num-1]作為索引數(shù)組。排序改為從大到小。對索引數(shù)組排序后，每次從最后選出2個(gè)最小值，相加后的結(jié)點(diǎn)權(quán)值放在索引數(shù)組最后，結(jié)點(diǎn)索引放在索引數(shù)組中倒數(shù)第2個(gè)位置，然后索引數(shù)組大小減1，并將最后一個(gè)索引值插入到前面的有序表中，保證索引數(shù)組仍然有序。* huffman_f 在huffman_e的基礎(chǔ)上，將排序改為利用堆排序原理選擇最小的兩個(gè)權(quán)值。也即，將所有元素的權(quán)值組織成堆后，每次堆內(nèi)的根結(jié)點(diǎn)就是最小值了。每取出一個(gè)根結(jié)點(diǎn)后，就把堆尾元素調(diào)到根結(jié)點(diǎn)重建堆。取出兩個(gè)最小值合并成一個(gè)子樹后，再把子樹作為葉子結(jié)點(diǎn)放到堆中，并讓其上升到合適的位置，保持堆性質(zhì)不變。因?yàn)槊看尾槐赝瓿烧麄€(gè)排序過程，而只是組織成堆，因此，這種方法要比使用快速排序更快。上述算法參考了mg-1.2.1中Huffman編碼的實(shí)現(xiàn)，見http://www.cs.mu.oz.au/mg/* huffman_g 當(dāng)元素權(quán)值已經(jīng)有序時(shí)，可以使用A. Moffat和J. Katajainen設(shè)計(jì)的在權(quán)值數(shù)組內(nèi)部構(gòu)建Huffman的方法。A. Moffat和J. Katajainen對該算法的描述見http://www.cs.mu.oz.au/~alistair/abstracts/inplace.html* huffman_h 在huffman_f的基礎(chǔ)上，增加限制碼長的功能。限制碼長的算法參考了zlib-1.1.4中構(gòu)造限制碼長的Huffman編碼的源代碼。zlib的源代碼見http://www.gzip.org/zlib/，其中限制長度的算法在tree.c的gen_bitlen()函數(shù)中。上述8種算法分別對應(yīng)于8個(gè)同名C++類，這些類都是由huffman_base類派生的。huffman_base類提供了與Huffman算法相關(guān)的大多數(shù)通用功能，如編碼轉(zhuǎn)換、Canonical Huffman編碼生成、Huffman編碼驗(yàn)證等等。main.cpp中的tester類提供了用隨機(jī)數(shù)據(jù)測試上述8種算法，并顯示算法的運(yùn)行時(shí)間及運(yùn)行結(jié)果的功能。----------編譯和運(yùn)行----------Windows: 使用Visual Studio .NET（建議使用VS .NET 2003或以上版本）打開Huffman.sln，編譯生成并運(yùn)行huffman.exe即可。Linux: 系統(tǒng)中應(yīng)已安裝GNU gcc（建議安裝gcc 3.2.2或以上版本）。本目錄下的Makefile是Linux下的工程文件，直接在本目錄下執(zhí)行make命令即可生成可執(zhí)行程序Huffman。