----
Huffman 算法的不同實(shí)現(xià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語(yǔ)言版）中給出的算法，將二叉樹存放在連續(xù)空間里（靜態(tài)鏈表），空間的每個(gè)結(jié)點(diǎn)內(nèi)仍有左子樹、右子樹、雙親等指針。
* huffman_c 使用Canonical Huffman編碼，同時(shí)對(duì)huffman_b的存儲(chǔ)結(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算法對(duì)所有元素的權(quán)值從小到大排序，這樣，排序后最前面的兩個(gè)元素就是最小的一對(duì)元素了。我們可以直接將它們挑出來(lái)，組合成一個(gè)子樹。然后再子樹的權(quán)值用折半插入法插到已排序的元素表中， 保證所有結(jié)點(diǎn)有序。為了保證初始元素的順序不變，我們另外使用了一個(gè)索引數(shù)組，所有排序中的交換操作都是在索引數(shù)組中進(jìn)行的
標(biāo)簽：
Huffman
算法
目錄
方式
上傳時(shí)間：
2015-06-12
上傳用戶：xg262122
