1、精選優質文檔-傾情為你奉上畢 業 設 計（論文）題 目：霍夫曼編碼及其應用學 院： 數 理 學 院 專業名稱： 信息與計算科學 學 號： 學生姓名： 張 浩 指導教師： 韓 海 清 2011 年 4 月 20 日摘要本文首先對二元霍夫曼編碼進行了細致研究，并對其算法進行擴展，得到了適用于多元霍夫曼編碼的算法。然后，對霍夫曼編碼的前綴性，最優性進行了證明。最后實現了霍夫曼編碼在決策論中應用。關鍵詞碼 ； 熵 ； 霍夫曼編碼 ； 決策樹ABSTRACTThis paper first studied binary Huffman coding, and conducted a detailed s

2、tudy on its algorithm suitable for expansion, get multiple Huffman coding algorithm. Meanwhile, Huffman coding prefix sex, optimality proved. Finally realized Huffman coding applied in rigorous.KEYWORDS The Coding； The Entropy； Huffman Coding； Decision tree 目 錄第一章 引言1948年，美國數學家香農（C.E.Shannon）在貝爾系統電話

3、雜志發表了題為“通信的數學理論”的長篇論文。這篇論文以概率論為工具，深刻闡述了通信工程的一系列基本理論問題，給出了計算信源信息量和信道容量的方法和一般公式，得到了一組表征信息傳遞重要關系的編碼定理，從而創立了信息論。1959年，香農在發表的“保真度準則下的離散信源編碼定理” （Coding theorems for a discrete source at the fidelity criterion）一文中系統的提出了信息率失真理論（rate-distortion theory）,為信源壓縮編碼的研究奠定了理論基礎。在信息傳輸過程中，信源序列通過信源編碼器實現對信源冗余度的壓縮，變成編碼序列

4、，編碼序列通過信源譯碼器恢復成信源序列。根據恢復序列的效果，可把信源編譯器分為兩類，即無失真信源編碼和限失真信源編碼。在無失真信源編碼的過程中，編、譯碼過程是可逆的，即信源符號可以通過編碼序列無差錯地恢復。為提高傳輸有效性，我們總是希望在保證無失真的條件下盡量壓縮碼率（編碼后傳輸每信源符號所需的二元碼符號數），但這種壓縮是否有限度是一個必須要解決的理論問題。香農第一定理也就是無失真信源編碼定理對這個問題做了明確回答。定理指出，只要信源編碼碼率不小于信源的熵就存在無失真信源編碼，同時還指出如果信源編碼的碼率大于信源編碼的熵就不存在無失真信源編碼。同時，定理還給出了進行無失真信源編碼的理論極值，論

5、證與指出了理想最佳信源編碼是存在的。但是并沒有給出信源編碼的實際構造方法和實用碼的結構。編碼的目的就是為了優化通信系統。一般來說，通信系統的性能指標是有效性、可靠性、安全性和經濟性。隨著科學技術的發展和需求，人們廣泛致力于對各種文本、圖片、圖形、語言、聲音、活動圖像和影視信號等實際信源進行了實用壓縮方法和技術研究，使信源的數據壓縮技術得以蓬勃發展和逐漸走向成熟。霍夫曼在1952年提出了一種構造最佳碼得方法，我們稱之為霍夫曼編碼。霍夫曼編碼適用于多遠獨立信源，對于多元獨立信源來說它是最佳碼。它充分利用了信源概率分布的特性進行編碼，是一種最佳的逐個符號的編碼方法。第二章 主要概念 香農定理作為信息

6、論的基礎理論，我們有必要對進行簡要介紹。下面我們給出香農三大定理：2.1香農三大定理香農三大定理是的。香農三大定理是存在性定理，雖然并沒有提供具體的編碼實現方法，但為通信信息的研究指明了方向。4香農第一定理是可變長無失真信源編碼定理。香農第二定理是有噪信道編碼定理。香農第三定理是保失真度準則下的有失真信源編碼定理。具體如下:2.1.1香農第一定理(可變長無失真信源編碼定理) 1設信源S的熵H(S),無噪離散信道的信道容量為C,于是,信源的輸出可以進行這樣的編碼,使得信道上傳輸的為每秒個信源符號.其中a可以是任意小的正數, 要使傳輸的平均速率大于是不可能的。2.1.2香農第二定理（有噪信道編碼定

7、理）1設某信道有r個輸入符號,s個輸出符號,信道容量為C,當信道的信息傳輸率R碼長N足夠長,總可以在輸入的集合中(含有rN個長度為N的碼符號序列),找到M （(,a為任意小的正數)個,分別代表M個等可能性的消息,組成一個碼以及相應的譯碼規則,使信道輸出端的最小平均錯誤譯碼概率Pmin達到任意小。2.1.3香農第三定理（保失真度準則下的有失真信源編碼定理）1設R(D)為一離散無記憶信源的信息率失真函數,并且選定有限的失真函數,對于任意允許平均失真度,和任意小的,以及任意足夠長的碼長N,則一定存在一種信源編碼W,其碼字個數為，而編碼后碼的平均失真度。 2.2霍夫曼編碼1952年David. A.

8、Huffman提出了一種構造最佳碼的方法稱之為霍夫曼碼。霍夫曼碼適用于多元獨立信源，對于多元獨立信源來說它是最佳碼。它充分利用了信源概率分布的特性進行編碼，是一種最佳的逐個符號的編碼方法。2第三章 二元霍夫曼編碼及其算法二元霍夫曼編碼方法的編碼步驟如下：1） 將q個信源符號按概率分布的大小，以遞減次序排列起來，設2） 用0和1碼分別分配給概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個新符號，并用這兩個最小概率之和作為新符號的概率，從而得到只包含q-1個符號的新信源，稱為S信源的縮減信源。3） 把縮減信源的符號仍按概率大小以遞減次序排列，再將最后兩個概率最小的符號合并成一個新符號

9、，并分別用0和1碼表示，這樣又形成q-2個符號的縮減信源。4） 依次繼續下去，直至縮減信源最后只剩兩個符號為止。再將最后兩個新符號分別用0和1碼符號表示。最后這兩個符號的概率之和比為1.然后從最后一級縮減信源開始，一編碼路徑右后向前返回，就得出各信源符號所對應的碼符號序列，即得對應的碼字。現在，給出一個具體的例子來說明這種編碼方法。【例1】設單符號離散無記憶信源如下，要求對其進行二元霍夫曼編碼。 =可以計算出該信源的熵為：H（X）= -=1.978b從而可以計算出每個符號的平均二元字符數為=10.46+20.30+30.12+40.06+50.03+60.02+60.01 =1.9900b該編

10、碼的效率為=（1.9781/1.9900）=99.4%其編碼過程如表3.1所示表3.1 二元霍夫曼編碼（1）概率 碼概率 碼概率 碼概率 碼概率 碼概率 碼0.46 10.30 000.12 0100.06 01100.03 011100.02 0.01 0.46 10.30 000.12 0100.06 01100.03 011100.03 011110.46 10.30 000.12 0100.06 01100.06 01110.46 10.30 000.12 0100.12 0110.46 10.30 000.24 010.54 00.46 1現在將看到霍夫曼編碼不是唯一的。考了最小兩個

11、概率的組合（符號和），它們的和為0.03，等于與符號對應的下一個較高的概率。那么第二步，可以選擇使這個組合搞了（比如說等于符號）高于或低于符號。假定把組合搞了放在下面，繼續進行又將發現和組合后的概率為0.06，等于符號的概率。我們又一次可以選擇是組合概率高于或低于。每次做出一種選擇時，最后導致符號的碼子改變。每次在有兩個相同概率的情況下要做出一種選擇時，我們把組合符號的概率放在上面。該信源的熵為H（X）= -=1.9781b而平均每個符號的比特數為=10.46+20.30+30.12+40.06+50.03+60.02+60.01 =1.990b該編碼的效率為 =（1.9781/1.9900）

12、=99.4%因此兩種編碼同樣有效。 表3.1 二元霍夫曼編碼（2）概率 碼概率 碼概率 碼概率 碼概率 碼概率 碼0.46 10.30 000.12 0110.06 01010.03 010010.02 0.01 0.46 10.30 000.12 0100.06 0110.03 010000.03 010010.46 10.30 000.12 0100.6 01000.06 01010.46 10.30 000.12 0100.12 0110.46 10.30 000.24 010.54 00.46 1第四章 一般霍夫曼編碼及其算法 下面我們再舉個例子，討論一下一般情況下霍夫曼編碼算法的步驟

13、。由于信源字母的選取不影響對應編碼方案的平均碼字長度，它只與信源概率分布有關，因此在下文中用概率分布=（，）直接表示信源。【例2】已給信源概率分布為=(0.24,0.20,0.18,0.13,0.10,0.06,0.05,0.03,0.01)，信號字母表U=0,1,2,3求信源的霍夫曼編碼。解 霍夫曼編碼方案的主要運算步驟是構造霍夫曼數據壓縮表與霍夫曼編碼表。它的運算步驟如下。1. 參照表4.1構造霍夫曼數據壓縮表（1）首先把概率分布的概率按降序排列，并把它們作為霍夫曼數據壓縮表的第一列，該列長度為a=9。第二列、第四列、第六列為碼元，暫空。（2）把第一列的三個最小概率相加，得到新的一列的概率

14、分布，重新安降序排列，成為霍夫曼數據壓縮表中的第三列。這時第三列的長度為7，相加后的數為0.09，我們將其用方框標出。（3）把第三列的4個最小的概率相加得到新的一列概率分布，重新安將序排列，成為霍夫曼數據壓縮表中的第五列。這時的長度為4，相加后的數為0.38，我們用方框標出。這樣霍夫曼數據壓縮表構造完成，有關計算于列表結果見表4.1表4.1概率 碼概率 碼概率 碼0.240.200.180.130.100.060.050.030.010.240.200.180.130.100.060.240.200.182. 用霍夫曼數據壓縮表構造霍夫曼編碼表（1）因霍夫曼數據壓縮表1的第五列的概率分布只有4

15、行，因此他們的編碼正好是0,1,2,3。把這四個數填入霍夫曼編碼表的第六列。因此，第六列是一個碼長為1的編碼。（2）在第五列中，帶方框的概率為0.38，它對應的第六列的編碼為0，而0.38是由第三列的0.13,0.10,0.09,0.06這四個數相加而成。這樣我們構造第三列概率分布的編碼為：第三列的0.13,0.10,0.09,0.06這四個數的編碼是在0.38的編碼后邊延長1個數，它們分別為00,01,02,03.第三列中0.24, 0.20, 0.18這三個數的編碼與第五列的編碼相同，仍為1, 2, 3,不變。把0.24, 0.20, 0.18, 0.13, 0.10, 0.19, 0.0

16、6這7個數的編碼1,2,3,00,01,02,03列入霍夫曼編碼表的第四列。（3）在表的第三列中，帶方框的概率為0.09它對應的第四列的編碼為02，而0.09是由第一列的0.05,0.03,0.01這三個數相加而成。這樣我們構造第一列概率分布的編碼為第一列的前六個數的編碼與第三列所對應的編碼相同。第一列中0.05,0.03,0.01這三個數的編碼是在第三列的0.09的編碼02后面延長1個數，因此他們分別為020,021,022.把第一列個概率的編碼列入霍夫曼編碼表的第二列，最終完成霍夫曼編碼表，各項計算結果見表4.2表4.2概率 碼概率 碼概率 碼0.24 10.20 20.18 30.13

17、000.10 010.06 030.05 0200.03 0210.01 0220.24 10.20 20.18 30.13 000.10 01 020.06 03 00.24 10.20 20.18 3 下面考慮一般情形。令碼字母表為U=0，1,2,3，r-1，信源概率分布=（，），對此構造霍夫曼編碼的運算步驟如下。1) 簡單情形下的霍夫曼編碼 如果ar，那么稱信源為簡單情形下的編碼。這時直接取每個消息元的編碼為信號元，如取，這樣我們只考慮ar的情形。2) 霍夫曼數據壓縮表a) 設計并構造霍夫曼壓縮表如下。由ar確定霍夫曼數據壓縮表的行、列數。如記2k+2是數據壓縮表的列數，那么k為使的最大

18、值，因此取，其中Int（z）是正數z的整數部分，而數據壓縮表的第1,2,3，2k-1，2k+1列的行數（或列的長度）分別為a,kr-k+1,(k-1)r-k+2,3r-2,2r-1,r.這時除了第1,3列之外，后一列比前一列的長度少r-1，因此它的行數可用公式表示。b) 霍夫曼壓縮表的第一列由概率分布（，）確定，并按將序排列。c) 霍夫曼壓縮表的第三列由第一列確定，它將第一列的最后a-kr+k-1=0,那么第三列與第一列相同。d) 霍夫曼壓縮表的第五列由第三列確定，它將第三列的最后r-1個分量相加，并按大小次序重新排列，相加所得到的數框出。e) 霍夫曼壓縮表的第七列由第五列確定，它將第五列的最

19、后r-1個分量相加，并按大小次序重新排列，相加所得到的數框出。f) 以此類推，由此得到霍夫曼壓縮表的第九，十一，列，最后一列長度為r，它由前一列確定。依次構成霍夫曼壓縮表。3) 霍夫曼壓縮表的有關記號由以上霍夫曼壓縮表的構造，引進一下記號。記 ， （4.01）為霍夫曼壓縮表的第2j-1列概率分布，其中前面已給定。且記 （4.02）是2j-1列的最后r-1個分量之和，在第j列的行上。4) 霍夫曼編碼表由霍夫曼壓縮表及以上式子，用遞推法可以構造霍夫曼編碼表，在霍夫曼編碼表中，奇數列為概率分布列，已由霍夫曼壓縮表確定，因此只要確定霍夫曼編碼表中的偶數列即可。3遞推運算步驟如下。a) 霍夫曼壓縮表的最

20、后一列r個分量，因此賦予他們的編碼是（0,1,，r-1），而且可自上而下排列，并填寫在第2k+2列的空格內，因此霍夫曼編碼表的第2k+1，2k+2列確定。b) 如果第2j+1，2j+2列確定，其中2j+1列是概率分布列，而2j+2列是編碼列，記第2j+2列的碼元分別為，其中是不定長碼元。c) 在2j+1列中，是由式（1.02）所給定的數，他相應的編碼確定為，這時第2j列的編碼確定為前個的碼元與第2j+2列說對應的概率的碼元相同。最后r個的碼元分別為（，0），（，1），.，（，r-1）。其中（，u）表示在碼元后面增加一個信號字符u。這樣第2j-1,2j列的概率分布與它的編碼完全確定。d) 以此類

21、推，得到霍夫曼編碼表中的全體編碼，這時第二列的編碼由第四列的編碼確定，他的最后b個概率的碼元由做延伸，相應的碼元為 （，0），（，1），.（，b-1）其中b=a-(kr-k+1)。第五章 霍夫曼編碼的性能分析5.1霍夫曼編碼的前綴性定理4.1（霍夫曼碼的前綴性）由霍夫曼編碼算法所得到的霍夫曼碼是前綴碼。證明 由霍夫曼編碼算法中的各步驟所知，第2k+2列中各碼元各不相同，且第2k列中各碼元與第2k+2列中碼元相同或是某各碼元的延伸，因此第2k列中各碼元互不相同，且每個碼元不能成為另一碼元的前綴。一般情形，如果第t列中各碼元各不相同，且第t-1列中各碼元與第t列中碼元相同或是某個碼元的延伸，那么第

22、t-1列中各碼元互不相同，且每個碼元不能成為另一個碼元的前綴。由此遞推，最后得到第一列中各碼元互不能成為另一碼元的前綴。由此定理得證。5.2 霍夫曼編碼的最優性定理定理4.2 （霍夫曼編碼的最優性定理）由霍夫曼編碼算法所得到的霍夫曼編碼一定是最優碼。對同一信源，分別是霍夫曼碼與任一前綴碼，那么必有成立。4第六章 霍夫曼編碼的應用上面討論了霍夫曼碼，并且證明了霍夫曼碼是最佳碼。當N不是很大時，它能使無失真編碼的效率接近于1.但霍夫曼碼是分組碼（或稱塊碼），在實際應用時設備較復雜。首先，每個信源符號所對應的碼長不同。一般情況下，信源符號以恒速輸出，信道也是恒速傳輸的。通過編碼后，會造成編碼輸出每秒

23、的比特數不是常量，因而不能直接由信道來傳送。其次，信源符號與碼字之間不能用某種有規律的數學方法對應起來。在對信源進行霍夫曼編碼后，形成一個霍夫曼編碼表，必須通過查表的方法來進行編、譯碼5。在信源存儲與傳輸過程中必須首先存儲這一霍夫曼編碼表，這樣就會影響實際信源的壓縮效率。有時為了實用，嘗嘗先基于大量概率統計，建好霍夫曼編碼表。這樣編碼時不需進行概率統計和建立編碼表；另外在接收端和發送端可以先固定建好的霍夫曼碼表，傳輸時也不用傳輸編碼表。但當N增大時，信源符號數目增多，所需存儲碼表的容量增大，使設備復雜化，同時也是編、譯碼時查表搜索時間增大。6盡管如此，霍夫曼方法還是一種較具體和有效的無失真信源

24、編碼方法，它便于硬件實現和計算機上軟件實現。所以它仍應用于文件傳真，語聲處理和圖像處理的數據壓縮中。（霍夫曼編碼在線性表中的編程實現見附錄1）而今，霍夫曼編碼還可以用來做決策樹。如果有n個互斥隨機事件，概率分別為，現用某種測試方法分步對所選擇的目標事件進行識別，要求具有最小的決策平均次數，可以通過對這些事件進行霍夫曼編碼來實現，因為霍夫曼編碼具有最小平均碼長。霍夫曼編碼形成的碼樹可以視為決策樹，方向從根到葉，其中每個節點都是決策節點。決策樹被廣泛應用在企業數據處理、系統分析以及數據挖掘等領域中。下面我們舉個例子說明。【例3】甲手中有4張紙牌，點數分別為1,2,3,4，要求乙猜：乙可以向甲提問題

25、，甲只能用是否來回答。求乙平均最少問幾個問題可以猜到紙牌的點數和相應的策略。（1）1,2,3,4,的概率均為1/4的決策樹（2）1,2,3,4,的概率分別為1/2,1/4，1/8,1/8的決策樹。解對于決策樹問題，我們要首先進行霍夫曼編碼，然后將霍夫曼編碼碼樹變成決策樹決策的設計方法：沒步決策結果應該與節點分支的概率匹配。（1） 由于各點數概率相同，因此得到如圖6.1所示的決策樹（2） 各點數概率不同，依據霍夫曼編碼得到如圖6.2所示的決策樹。n2? n3? n1? n=1 n=2 n=3 n=4N(1/2)Y(1/2)N(1/4)Y(1/4)N(1/4)Y(1/4)圖6.1決策樹n2? n3

26、? n1? n=1 n=2 n=3 n=4Y(1/2)Y(1/8)N(1/2)N(1/4)N(1/8)Y(1/8)圖6.2決策樹第七章 總結與展望本文先通過對二元霍夫曼編碼進行研究，得出了二元霍夫曼編碼算法：將q個信源符號按概率分布的大小，以遞減次序排列起來，設；用0和1碼分別分配給概率最小的兩個信源符號，并將這兩個概率最小的信源符號合并成一個新符號，并用這兩個最小概率之和作為新符號的概率，從而得到只包含q-1個符號的新信源，稱為S信源的縮減信源。把縮減信源的符號仍按概率大小以遞減次序排列，再將最后兩個概率最小的符號合并成一個新符號，并分別用0和1碼表示，這樣又形成q-2個符號的縮減信源。依次

27、繼續下去，直至縮減信源最后只剩兩個符號為止。再將最后兩個新符號分別用0和1嘛符號表示。最后這兩個符號的概率之和比為1.然后從最后一級縮減信源開始，一編碼路徑右后向前返回，就得出各信源符號所對應的碼符號序列，即得對應的碼字。再推廣至一般霍夫曼編碼即多元霍夫曼編碼并得到多元霍夫曼編碼算法：將q個信源符號按概率分布的大小，以遞減次序排列起來，設；用0，1,2.m-1碼分別分配給概率最小的m個信源符號，并將這兩個概率最小的信源符號合并成一個新符號，并用這m個最小概率之和作為新符號的概率，從而得到只包含q-（m-1）個符號的新信源，稱為S信源的縮減信源。把縮減信源的符號仍按概率大小以遞減次序排列，再將最

28、后m個概率最小的符號合并成一個新符號，并分別用0，1,2.m-1碼表示，這樣又形成q-2（m-1）個符號的縮減信源。依次繼續下去，直至縮減信源最后只剩m個符號為止。再將最后兩個新符號分別用0，1,2.m-1嘛符號表示。最后這m個符號的概率之和比為1.然后從最后一級縮減信源開始，一編碼路徑右后向前返回，就得出各信源符號所對應的碼符號序列，即得對應的碼字。霍夫曼編碼廣泛應用于文件傳真，語聲處理和圖像處理的數據壓縮中。但是霍夫曼算法的應用卻更為廣泛，例如上面提到的霍夫曼編碼在決策中的應用，以及我最初的設想：將霍夫曼編碼應用到生命科學中，使有上百萬個脫氧核糖核酸構成的DNA序列存儲起來更為迅速，更為節

29、約空間，但是由于種種原因只停留在設想階段。未來如有幸接觸到這方面的工作，我將努力將這個設想變為現實。參考文獻1 Shannon, Claude. A Mathematical Theory of Communication. Bell System Technical Journal 27 (July and October, 1948): 379-423 and 623-656.2陳運. 信息論與編碼M. 北京：電子工業出版社，20073 Richard B Wells. Applied Coding and Information Theory for EngineersM. Person

30、 Education North Asia Limited and China Machine Press, 20034關可，王建新，亓淑敏. 信息論與編碼技術M.北京：清華大學出版社，20095曹雪虹，張宗橙.信息論與編碼M.北京：清華大學出版社20096田寶玉，楊潔，賀志強，王曉湘.信息論基礎M.北京：人民郵電出版社，20087 沈世鎰，陳魯生. 編碼理論基礎M.北京：科學出版社，20028 Robort J.McEliece. Information theory and coding theory . Beijing publishing house of electronics in

31、dustry .2007附錄1#include#include#include#include#include#define LIST_INT_SIZE 100/線性表儲存空間的初始分配量#define LISTINCREMENT 10/線性表儲存空間的分配增量typedef struct/讀取的字母的結構體，包含字母及頻率char data;int ASCII;int rate;ELEM;char RFC; /保存文件中所有內容的字符串double CD=0;/*=讀取文件=*/void readfile()FILE *fp;fp=fopen(RFCdoc.txt,r);char ch;in

32、t i=0;while(!feof(fp)ch=fgetc(fp);RFCi=ch;i+;CD+;fclose(fp);/*=線性表=*/typedef structELEM *elem; /儲存空間基址int length; /當前長度int listsize; /當前分配的儲存容量Sqlist;int SearchBin(Sqlist ST,int key,int &flag) /折半查找int low,high,mid;low=0;high=ST.length-1;mid=(low+high)/2;while(lowkey)high=mid-1;else if(ST.elemmid.AS

33、CIIkey)low=mid+1;return low;void CreatList(Sqlist &L) /創建一個順序表int flag,xb,asc;char ch;L.elem=(ELEM *)malloc(LIST_INT_SIZE*sizeof(ELEM);if(!L.elem)printf(分配空間失敗!);exit(0);L.length=0; /空表長度為0L.listsize=LIST_INT_SIZE;for(int i=0;i=L.listsize)/判斷空間是否足夠ELEM *newbase=(ELEM *)realloc(L.elem,(L.listsize+LIS

34、TINCREMENT)*sizeof(ELEM);if(!newbase)printf(分配空間失敗!);exit(0);L.elem=newbase;L.listsize+=LISTINCREMENT;Elsefor(int j=L.length-1;j=xb;j-)L.elemj+1=L.elemj;L.elemxb.data=ch; L.elemxb.ASCII=asc;L.elemxb.rate=1;L.length+;ElseL.elemxb.rate+;void PrintList(Sqlist L) /輸出順序表for(int i=0;iL.length;i+)printf( %

35、c,%d ,L.elemi.data,L.elemi.rate);/*=赫夫曼編碼=*/typedef structchar data;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;void Select(HuffmanTree HT,int n,int &s1,int &s2)int i,j;int temp;for(j=1;j=n;j+)for(i=1;iHTi+1.weight)temp=HTi.weight;HTi.weight=HTi+1.weight;HTi+1.w

36、eight=temp;for(i=1,j=1;i0)，構造哈夫曼樹HT， / 并求出n個字符的哈夫曼編碼HC int i, j, n,m, s1, s2, start; char *cd; int c, f; n=L.length; if (n=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0號單元未用 for (i=1; i=n; i+) /初始化HTi.weight=L.elemi-1.rate;HTi.data=L.elemi-1.data; HTi.parent=0; HTi.lc

37、hild=0; HTi.rchild=0; for (i=n+1; i=m; i+) /初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; printf(n哈夫曼樹的構造過程如下所示：n); printf(HT初態:n 結點 weight parent lchild rchild); for (i=1; i=m; i+) printf(n%4d%8d%8d%8d%8d,i,HTi.weight, HTi.parent,HTi.lchild, HTi.rchild); printf( 按任意鍵，繼續 .); getch(); f

38、or (i=n+1; i=m; i+) / 建哈夫曼樹 / 在HT1.i-1中選擇parent為0且weight最小的兩個結點， / 其序號分別為s1和s2。 Select(HT, i-1, s1, s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; printf(nselect: s1=%d s2=%dn, s1, s2); printf( 結點 weight parent lchild rchild); for (j=

39、1; ji; j+) printf(n%4d%8d%8d%8d%8d%8c,j,HTj.weight, HTj.parent,HTj.lchild, HTj.rchild,HTj.data); printf( 按任意鍵，繼續 .); getch(); /- 從葉子到根逆向求每個字符的哈夫曼編碼 - HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd = (char *)malloc(n*sizeof(char); / 分配求編碼的工作空間 cdn-1 = 0; / 編碼結束符。 for (i=1; i=n; +i) / 逐個字符求哈夫曼編碼start

40、= n-1; / 編碼結束符位置 for (c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) / 從葉子到根逆向求編碼 if (HTf.lchild=c) cd-start = 0; else cd-start = 1; HCi = (char *)malloc(n-start)*sizeof(char); / 為第i個字符編碼分配空間 strcpy(HCi, &cdstart); / 從cd復制編碼(串)到HC free(cd); / 釋放工作空間 / HuffmanCoding/*=保存編碼=*/typedef struct/讀取的字母的結構體，包含字

41、母及頻率char data;char *code;int ASCII;CODE;CODE *list;int Search(Sqlist ST,int key)int low,high,mid;low=0;high=ST.length-1;mid=(low+high)/2;while(lowkey)high=mid-1;else if(listmid.ASCIIkey)low=mid+1;return -1;void save(HuffmanTree HT, HuffmanCode HC,Sqlist L)int i,n,k;list=(CODE *)malloc(L.length*sizeof(CODE);for(i=0;iL.length;i+)/初始化listi.data=L.elemi.data;listi.ASCII=L.elemi.ASCII;for(i=1;i=L.length;i+)k=(int)HTi.data;n=Search