實驗2 huffman編碼對英文文本的壓縮和解壓縮

1、《信息論與編碼》《信息論與編碼》實驗報告實驗報告班級：學號：姓名：完成時間：2011年6月2日二叉樹存放在連續(xù)空間里（靜態(tài)鏈表），空間的每個結點內仍有左子樹、右子樹、雙親等指針。3.huffman_c使用CanonicalHuffman編碼，同時對huffman_b的存儲結構進行改造，將二叉樹存放在連續(xù)空間tree里，空間的每個結點類型都和結點權值的數據類型相同，空間大小為2num，tree[0]未用，tree[1..num]是每個元素

2、的權值，生成Huffman后，tree[1..2num1]中是雙親結點索引。4.huffman_d在huffman_c的基礎上，增加預先排序的功能先用QuickSt算法對所有元素的權值從小到大排序，這樣，排序后最前面的兩個元素就是最小的一對元素了。我們可以直接將它們挑出來，組合成一個子樹。然后再子樹的權值用折半插入法插到已排序的元素表中，保證所有結點有序。為了保證初始元素的順序不變，我們另外使用了一個索引數組，所有排序中的交換操作都是在

3、索引數組中進行的。5.huffman_e在huffman_d的基礎上，將索引數組放在tree的內部。為編碼方便，將元素權值放在tree[num..2num1]處。將tree[0..num1]作為索引數組。排序改為從大到小。對索引數組排序后，每次從最后選出2個最小值，相加后的結點權值放在索引數組最后，結點索引放在索引數組中倒數第2個位置，然后索引數組大小減1，并將最后一個索引值插入到前面的有序表中，保證索引數組仍然有序。6.huffman

4、_f在huffman_e的基礎上，將排序改為利用堆排序原理選擇最小的兩個權值。也即，將所有元素的權值組織成堆后，每次堆內的根結點就是最小值了。每取出一個根結點后，就把堆尾元素調到根結點重建堆。取出兩個最小值合并成一個子樹后，再把子樹作為葉子結點放到堆中，并讓其上升到合適的位置，保持堆性質不變。因為每次不必完成整個排序過程，而只是組織成堆，因此，這種方法要比使用快速排序更快。上述算法參考了mg1.2.1中Huffman編碼的實現(xiàn)，見:ww

5、w.cs.mu.oz.aumg7.huffman_g當元素權值已經有序時，可以使用A.Moffat和J.Katajainen設計的在權值數組內部構建Huffman的方法。A.Moffat和J.Katajainen對該算法的描述見:www.cs.mu.oz.au~alistairabstractsinplace.html8.huffman_h在huffman_f的基礎上，增加限制碼長的功能。限制碼長的算法參考了zlib1.1.4中構造限制