數(shù)據(jù)結(jié)構(gòu)課設(shè)-赫夫曼樹講解

1、塔里木大學(xué)信息工程學(xué)院課程設(shè)計(jì)目錄 前言1正文21課程設(shè)計(jì)目的及意義21.1課程設(shè)計(jì)目的21.2課程設(shè)計(jì)的意義22設(shè)計(jì)方案論證22.1 問題描述22.1.1赫夫曼樹的基本概念22.1.2赫夫曼樹的應(yīng)用32.1.3哈夫曼樹在數(shù)據(jù)編碼中的應(yīng)用42.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)52.3.1功能模塊圖62.3.2功能模塊圖思路設(shè)計(jì)72.4 詳細(xì)設(shè)計(jì)82.4.2 算法設(shè)計(jì)102.5設(shè)計(jì)程序133 課程設(shè)計(jì)運(yùn)行結(jié)果與分析16設(shè)計(jì)總結(jié)17參考文獻(xiàn)18 前言數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對象以及它們之間的關(guān)系的操作的學(xué)科。它是介于數(shù)學(xué)、計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專業(yè)的核心課程，是計(jì)算機(jī)

2、程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對象在計(jì)算機(jī)中表示出來并對它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高我們的思維能力，促進(jìn)我們綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。隨著計(jì)算機(jī)的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡單的數(shù)值運(yùn)算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及設(shè)計(jì)最短路線等復(fù)雜的非數(shù)值處理和操作。 算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)就是為以后利用計(jì)算機(jī)資源高效地開發(fā)非數(shù)值處理的計(jì)算機(jī)程序打下堅(jiān)實(shí)的理論、方法和技術(shù)基礎(chǔ)。算法與數(shù)據(jù)結(jié)構(gòu)旨在分析研究計(jì)算機(jī)加工的數(shù)據(jù)對象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，從而

3、使建立在其上的解決問題的算法達(dá)到最優(yōu)。數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。 數(shù)據(jù)結(jié)構(gòu)主要介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲表示，以及在其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對算法的效率進(jìn)行簡單的分析和討論。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專業(yè)的核心課程

4、，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對象在計(jì)算機(jī)中 此次課程設(shè)計(jì)通過對赫夫曼樹的概念、構(gòu)造算法的理解，進(jìn)行建立赫夫曼樹從而掌握赫夫曼樹，同時(shí)了解赫夫曼樹在解決實(shí)際問題中的重要地位。本文采用了數(shù)組和結(jié)構(gòu)體結(jié)合的存儲方式，通過對二叉樹結(jié)點(diǎn)以及帶權(quán)路徑長度等的學(xué)習(xí)和探究，通過建立最優(yōu)二叉樹函數(shù)，實(shí)現(xiàn)了赫夫曼樹的建立和輸出的功能。正文1課程設(shè)計(jì)目的及意義 1.1課程設(shè)計(jì)目的 (1)掌握算法的編寫方法。(2)掌握C語言的算法轉(zhuǎn)換成C程序并上機(jī)調(diào)試的基本方法。(3)根據(jù)建立好的函數(shù)輸入二叉樹，

5、對其輸入的字符出現(xiàn)的頻率作為權(quán)值輸出其相對應(yīng)的赫夫曼樹。 1.2課程設(shè)計(jì)的意義通過熟練使用c+語言編寫程序，解決實(shí)際問題；了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；練習(xí)樹和赫夫曼樹的有關(guān)操作，和各個(gè)算法程序，理解赫夫曼樹的構(gòu)造與應(yīng)用，熟悉赫夫曼樹的基本操作，掌握赫夫曼樹的實(shí)現(xiàn)以及實(shí)際應(yīng)用。 2設(shè)計(jì)方案論證2.1 問題描述2.1.1赫夫曼樹的基本概念相關(guān)概念：路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)所經(jīng)過的分支序列或者說結(jié)點(diǎn)序列。路徑長度：路徑上面的

6、分支個(gè)數(shù)。樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。結(jié)點(diǎn)的權(quán)值：在某些應(yīng)用中，樹中結(jié)點(diǎn)往往要和一定的數(shù)值聯(lián)系起來，那么這個(gè)數(shù)值通常稱為該結(jié)點(diǎn)的權(quán)值，簡稱權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長度：該結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。最優(yōu)二叉樹（哈夫曼樹）：給定n個(gè)權(quán)值w1,w2,wn，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi。構(gòu)造出來的二叉樹的形態(tài)可以有多個(gè)，我們把其中帶權(quán)路徑長度WPL最小的二叉樹稱作最優(yōu)二叉樹或者哈夫曼樹。按照結(jié)構(gòu)體來存放樹的結(jié)點(diǎn)的權(quán)值，雙親、左孩子、右孩子。通過建立赫夫曼樹函數(shù)輸入二叉樹，并輸出其赫夫曼樹各節(jié)

7、點(diǎn)編碼。哈夫曼算法的語言描述根據(jù)給定的n個(gè)權(quán)值w1,w2,wn構(gòu)成n棵二叉樹的集合F=T1,T2,Tn,其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹為空。在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。重復(fù)和，直到F只含一棵樹為止。這棵樹便是哈夫曼樹。2.1.2赫夫曼樹的應(yīng)用哈夫曼樹的應(yīng)用十分廣泛，在不同的應(yīng)用中，對葉子結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度有不同的解釋。哈夫曼樹的應(yīng)用之一是用于優(yōu)化判斷過程，利用哈夫曼樹得到最佳判定算法。例如，將百分制轉(zhuǎn)換成五級制的算法

8、。顯然，此算法很簡單，只需利用if語句描述即可。if ( x60)score=不及格;else if ( x70) score=及格;else if ( x80)score=中;else if ( x90)score=良;elsescore=優(yōu);如果學(xué)生規(guī)模很大，該算法需反復(fù)多次執(zhí)行，就應(yīng)該考慮算法執(zhí)行的時(shí)間問題。在實(shí)際應(yīng)用中，學(xué)生的成績呈正態(tài)分布，大部分在7089分之間，優(yōu)秀和不及格的概率較小。假設(shè)不及格、及格、中、良、優(yōu)的百分比為5、12%、40%、35%、8%，則上述算法80%以上的成績需要進(jìn)行三次或三次以上的比較才能得到結(jié)果。若以這些百分比值5,12,40,35,8為權(quán)值，使用哈夫曼算

9、法來構(gòu)造一棵判定樹，則得到判定過程，可使多數(shù)成績經(jīng)過較少的比較即可得到結(jié)果。但由于每個(gè)判定框都有兩次比較，將兩次比較分開，得到判定樹，按此判定樹構(gòu)造程序，顯然可以大大減少比較次數(shù)。2.1.3哈夫曼樹在數(shù)據(jù)編碼中的應(yīng)用在數(shù)據(jù)通信中，需要將傳送的文字轉(zhuǎn)換成二進(jìn)制的字符串，用0，1碼的不同排列來表示字符。例如，需傳送的報(bào)文為“AFTER DATA EAR ARE ART AREA”，這里用到的字符集為“A，E，R，T，F(xiàn)，D”，各字母出現(xiàn)的次數(shù)為8，4，5，3，1，1?，F(xiàn)要求為這些字母設(shè)計(jì)編碼。要區(qū)別6個(gè)字母，最簡單的二進(jìn)制編碼方式是等長編碼，固定采用3位二進(jìn)制，可分別用000、001、010、01

10、1、100、101對“A，E，R，T，F(xiàn)，D”進(jìn)行編碼發(fā)送，當(dāng)對方接收報(bào)文時(shí)再按照三位一分進(jìn)行譯碼。顯然編碼的長度取決報(bào)文中不同字符的個(gè)數(shù)。若報(bào)文中可能出現(xiàn)26個(gè)不同字符，則固定編碼長度為5。然而，傳送報(bào)文時(shí)總是希望總長度盡可能短。在實(shí)際應(yīng)用中，各個(gè)字符的出現(xiàn)頻度或使用次數(shù)是不相同的，如A、B、C的使用頻率遠(yuǎn)遠(yuǎn)高于X、Y、Z，自然會想到設(shè)計(jì)編碼時(shí)，讓使用頻率高的用短碼，使用頻率低的用長碼，以優(yōu)化整個(gè)報(bào)文編碼。但這樣長短不等的編碼又會產(chǎn)生一個(gè)新問題，即如何解譯成原文？除非設(shè)計(jì)時(shí)能夠保證任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴，符合此要求的編碼稱為前綴編碼。為使不等長編碼為前綴編

11、碼，可用字符集中的每個(gè)字符作為葉子結(jié)點(diǎn)生成一棵編碼二叉樹，為了獲得傳送報(bào)文的最短長度，可將每個(gè)字符的出現(xiàn)頻率作為字符結(jié)點(diǎn)的權(quán)值賦予該結(jié)點(diǎn)上，求出此樹的最小帶權(quán)路徑長度就等于求出了傳送報(bào)文的最短長度。因此，求傳送報(bào)文的最短長度問題轉(zhuǎn)化為求由字符集中的所有字符作為葉子結(jié)點(diǎn)，由字符出現(xiàn)頻率作為其權(quán)值所產(chǎn)生的哈夫曼樹的問題。利用哈夫曼樹來設(shè)計(jì)二進(jìn)制的前綴編碼，既滿足前綴編碼的條件，又保證報(bào)文編碼總長最短。我們用上述各字母出現(xiàn)的次數(shù)8，4，5，3，1，1作為權(quán)構(gòu)造哈夫曼樹，如圖6.36所示。約定左分支表示字符“0”，右分支表示字符“1”，則可以從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑的分支上的字符組成的字符串作為該葉子

12、對應(yīng)字符的編碼?？梢宰C明，如此得到的必為二進(jìn)制前綴編碼，而且是一種最優(yōu)前綴編碼。我們稱這樣的樹為哈夫曼編碼樹，由此得到的編碼稱為哈夫曼編碼。本例中字母A、E、R、T、F、D的哈夫曼編碼分別為11、00、01、011、0100、0101。可以看出，出現(xiàn)次數(shù)較多的字母A、E、R，具有最短的編碼，長度均為2；而出現(xiàn)次數(shù)最少的字母F、D，具有最長的編碼，長度均為4。報(bào)文的最短傳送長度為：6 L=WPL=S(wklk)=42+52+82+33+14+14=51 k=1若采用等長編碼，報(bào)文的傳送長度為 L=83+43+53+33+13+13=66顯然，哈夫曼編碼比等長編碼所得到的報(bào)文長度要短得多。哈夫曼編

13、碼是最優(yōu)前綴編碼。一個(gè)任意長度的編碼序列可被唯一地翻譯為一個(gè)字符序列（單詞）。依次取出編碼序列中的0或1，從哈夫曼編碼樹的根結(jié)點(diǎn)開始尋找一條路徑。若為0，則沿著左分支向下走；若為1，則沿著右分支向下走。每到達(dá)一個(gè)葉子外結(jié)點(diǎn)時(shí)，就譯出一個(gè)相應(yīng)的字符，然后再回到哈夫曼樹的根結(jié)點(diǎn)處，依次譯出余下的字符，最后得到一個(gè)單詞。2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 通過建立一個(gè)赫夫曼樹的簡易程序，可以實(shí)現(xiàn)建立最優(yōu)二叉樹函數(shù)，并且可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹。此程序是線性鏈表式存儲結(jié)構(gòu)，這種存儲結(jié)構(gòu)便于數(shù)據(jù)的插入和刪除，同時(shí)還節(jié)約存儲空間。各種編碼方式(1)定長編碼根據(jù)出現(xiàn)的字符種數(shù)進(jìn)行編碼(2)變長編碼采取這種

14、變長編碼方式，需要遵循一個(gè)原則，即每一個(gè)字符的編碼都不應(yīng)該是另一個(gè)字符編碼的前綴。否則就會出現(xiàn)二義性。一個(gè)可用的編碼必須滿足每個(gè)字符的編碼不能是其他編碼的前綴。也可以看出，每一個(gè)可用的編碼都可以轉(zhuǎn)化成二叉樹的形式，這樣編碼理論便可以與二叉樹的一些性質(zhì)結(jié)合起來，就可以應(yīng)用二叉樹的理論知識來解決編碼問題。那么總的編碼長度為：WPL=w1*L1+w2*L2+w3*L3+w4*L4可以看出，該公式與哈夫曼樹滿足的公式一模一樣，那么我們可以采取構(gòu)造哈夫曼樹的方式來求編碼的長度。對哈夫曼樹進(jìn)行編碼，每一個(gè)結(jié)點(diǎn)的左分支上面標(biāo)0，右分支上面標(biāo)1,從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)，所經(jīng)分支上面的0、1序列，就是該葉子結(jié)點(diǎn)

15、所代表字符的編碼。假設(shè)有n個(gè)權(quán)值w1，w2，wn，每個(gè)權(quán)值賦給一個(gè)葉子，可以構(gòu)造出多棵含n個(gè)葉子結(jié)點(diǎn)的二叉樹。其中，必存在一棵其帶權(quán)路徑長度WPL取最小值的二叉樹，稱為最優(yōu)二叉樹。因?yàn)闃?gòu)造這種樹的算法最早是哈夫曼1952年提出來的，所以被稱為哈夫曼樹(Huffman Tree)。如何構(gòu)造哈夫曼樹？D.A.Huffman 最早研究出一個(gè)帶有一般規(guī)律的構(gòu)造算法，俗稱哈夫曼算法，其基本思想是讓權(quán)值最大的葉子離根最近。構(gòu)造方法如下：(1) 由給定的n個(gè)權(quán)值w1, w2, , wn，構(gòu)造n棵擴(kuò)充二叉樹的集合F = T1, T2, , Tn，其中每棵擴(kuò)充二叉樹中均只含一個(gè)帶權(quán)值wi的根結(jié)點(diǎn),其左、右子樹均

16、為空；(2) 重復(fù)下列步驟，直到F中只含一棵樹為止：j 在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵擴(kuò)充二叉樹，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和;k 從F中刪去這兩棵樹，同時(shí)加入剛生成的新樹；(3) 按上述步驟得到的二叉樹就是哈夫曼樹。2.3 設(shè)計(jì)思路及算法設(shè)計(jì) 2.3.1功能模塊圖 赫夫曼樹的建立查找最小的兩個(gè)權(quán)統(tǒng)計(jì)字符出現(xiàn)的頻率構(gòu)造赫夫曼樹并輸出圖1功能模塊圖2.3.2功能模塊圖思路設(shè)計(jì)設(shè)需要編碼的字符集合為d1,d2,dn,各個(gè)字符在電文中出現(xiàn)的次數(shù)集合為w1,w2,wn，以d1,d2,dn作為葉結(jié)點(diǎn)，以w1,w2,wn作為各葉結(jié)

17、點(diǎn)的權(quán)值構(gòu)造一棵二叉樹，規(guī)定赫夫曼樹中的左分支為0，右分支為1，則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過的分支對應(yīng)的0和1組成的序列便為該結(jié)點(diǎn)對應(yīng)字符的編碼。這樣的代碼總長度最短的不等長編碼稱為赫夫曼編碼。赫夫曼算法：根據(jù)給定的n個(gè)權(quán)值w1，w2，w3，wn構(gòu)成n棵二叉樹的集合F=T1，T2，T3，Tn，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為Wi的根結(jié)點(diǎn)，其左右樹均空。在F中選取兩棵根結(jié)點(diǎn)的 權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為期左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這棵樹，同時(shí)將新得到的二叉樹加入F中。重復(fù)(2)和(3)的過程，直到F只含一棵樹為止。這棵樹便是哈夫曼樹

18、。設(shè)給定的權(quán)值集合為5，4，7，2，構(gòu)造哈夫曼樹的過程如圖6.34 所示。首先構(gòu)造每棵樹只有一個(gè)結(jié)點(diǎn)的森林，如圖2(a)所示；然后每次選擇兩個(gè)根結(jié)點(diǎn)權(quán)值最小的二叉樹，以它們?yōu)樽?、右子樹?gòu)造新的二叉樹，步驟參看圖2(b)，(c)和(d)，最后得到一棵擴(kuò)充二叉樹 圖2 哈夫曼樹的構(gòu)造過程2.4 詳細(xì)設(shè)計(jì)2.4.1 程序流程圖 開 始創(chuàng)建一個(gè)空的赫夫曼樹判斷PHt是否為空輸入m判斷m是否比1大找兩個(gè)最小權(quán)的無父結(jié)點(diǎn)的結(jié)點(diǎn)構(gòu)造新的二叉樹得到新的結(jié)點(diǎn)NYY輸入外部結(jié)點(diǎn)個(gè)數(shù)及權(quán)值所有結(jié)點(diǎn)生成樹得到赫夫曼樹編碼輸出結(jié)束N圖3 流程圖2.4.2 算法設(shè)計(jì)(1)建立最優(yōu)二叉樹函數(shù)由于赫夫曼樹種沒有度為的結(jié)點(diǎn)（這

19、類又稱嚴(yán)格的（strict）(或正則的)二叉樹），則一顆有n個(gè)葉子結(jié)點(diǎn)的赫夫曼樹共有2n-1個(gè)結(jié)點(diǎn)，可以存儲在一個(gè)大小為2n-1的一維數(shù)組中。如何選定結(jié)點(diǎn)結(jié)構(gòu)？由于在構(gòu)成赫夫曼樹之后，為求編碼需要從葉子結(jié)點(diǎn)出發(fā)走一條從葉子到根的路徑；而為譯碼需要從根出發(fā)走一條從根到葉子的路徑。則對每個(gè)節(jié)點(diǎn)而言，既需知雙親的信息，又需知孩子結(jié)點(diǎn)的信息。由此：二叉樹的存儲結(jié)構(gòu)：#define MAXINT 2147483647 #define MAXNUM 50 /* 數(shù)組w中最多容納的元素個(gè)數(shù)，注意 m=MAXNUM */ #define MAXNODE 100 /* 哈夫曼樹中的最大結(jié)點(diǎn)數(shù)，注意 2*m-1M

20、AXNODE */ struct HtNode /* 哈夫曼樹結(jié)點(diǎn)的結(jié)構(gòu) */ int ww; int parent,llink,rlink; ; (2)赫夫曼樹的構(gòu)造算法根據(jù)給定的n個(gè)權(quán)值w1，w2，w3，wn構(gòu)成n棵二叉樹的集合F=T1，T2，T3，Tn，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為Wi的根結(jié)點(diǎn)，其左右樹均空。在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這棵樹，同時(shí)將新得到的二叉樹加入F中。重復(fù)操作直到所有結(jié)點(diǎn)生成樹。PHtTree huffman(int m, int *w) PHtTre

21、e pht; int i, j, x1, x2, m1, m2; pht = (PHtTree)malloc(sizeof(struct HtTree); /* 創(chuàng)建空哈夫曼樹 */ if (pht = NULL) printf(Out of space! n); return pht; for (i = 0; i hti.llink = -1; pht-hti.rlink = -1; pht-hti.parent = -1; if (i hti.ww = wi; else pht-hti.ww = -1; for ( i = 0; i m-1; i+) /* 每循環(huán)一次構(gòu)造一個(gè)內(nèi)部結(jié)點(diǎn) */

22、 m1 = MAXINT; m2 = MAXINT;/* 相關(guān)變量賦初值 */ x1 = -1; x2 = -1; for (j= 0; j htj.ww htj.parent = -1) m2 = m1; x2 = x1; m1= pht-htj.ww; x1 = j; else if (pht-htj.ww htj.parent = -1) m2 = pht-htj.ww; x2 = j; pht-htx1.parent = m+i; /* 構(gòu)造一個(gè)內(nèi)部結(jié)點(diǎn) */ pht-htx2.parent = m+i; pht-htm+i.ww = m1+m2; pht-htm+i.llink =

23、x1; pht-htm+i.rlink = x2; pht-root = m+i; return pht; (3)字符的赫夫曼編碼的算法向量HT的前n個(gè)分量表示葉子結(jié)點(diǎn)，最后一個(gè)分量表示根結(jié)點(diǎn)。各字符的編碼長度不等，所以按實(shí)際長度分配空間。求每個(gè)字符的赫夫曼編碼是從葉子到根的逆向處理。也可以從根出發(fā)遍歷整棵赫夫曼樹，求得各葉子結(jié)點(diǎn)所表示的字符的赫夫曼編碼。算法如下：int main() int m = 0, j = 0, i = 0, parent = 0; int* w; PHtTree pht; printf(please input m = );/*輸入外部結(jié)點(diǎn)個(gè)數(shù)*/ scanf(%d

24、, &m); if (m 1) printf(m is not reasonable!n); return 1; w = (int *)malloc(sizeof(int)*m); if (w = NULL) printf(overflow!n); return 1; printf(please input the %d numbers：n,m);/*輸入權(quán)值*/ for (j= 0; j m; j+) scanf(%d, w+j); pht = huffman(m, w); for (j = 0; j hti.parent != -1) parent = pht-hti.parent; if

25、 (pht-htparent.llink = i) printf(0); else printf(1); i = parent; printf(n); return 0; (4)查找權(quán)值最小的兩個(gè)結(jié)點(diǎn)的函數(shù)選擇二叉樹的根結(jié)點(diǎn)，使達(dá)最小構(gòu)造次優(yōu)二叉樹的算法，首先標(biāo)價(jià)所有結(jié)點(diǎn)，依次編號，判斷結(jié)點(diǎn)的權(quán)值的大小，將所判斷的結(jié)點(diǎn)賦值給一個(gè)變量，然運(yùn)用比較算法，選擇權(quán)值較小的一個(gè)結(jié)點(diǎn)，賦值給的變量不變，另一個(gè)變量釋放其所賦的值。應(yīng)用循環(huán)語句進(jìn)行新的賦值，繼續(xù)比較，直到所有結(jié)點(diǎn)比較完畢。s1 、s2所有值就是全職最小的兩個(gè)結(jié)點(diǎn)。依此算法比較完全部的結(jié)點(diǎn)由此構(gòu)成一顆赫夫曼樹。算法如下:void Select(

26、HuffmanTree HT, int n, int &s1, int &s2)unsigned int weight;int i;s1=0; s2=0; weight=100;for(i=1;iweight)continue;else weight=HTi.weight; s1=i;HTs1.parent=s1;/暫時(shí)改寫HTs1.parent的值 weight=100;for(i=1;iweight) continue; else weight=HTi.weight; s2=i;2.5設(shè)計(jì)程序#include #include #define MAXINT 2147483647#defin

27、e MAXNUM 50#define MAXNODE 100struct HtNode int ww; int parent,llink,rlink; ; struct HtTree int root; struct HtNode htMAXNODE; ; typedef struct HtTree *PHtTree; PHtTree huffman(int m, int *w) PHtTree pht; int i, j, x1, x2, m1, m2; pht = (PHtTree)malloc(sizeof(struct HtTree); if (pht = NULL) printf(O

28、ut of space! n); return pht; for (i = 0; i hti.llink = -1; pht-hti.rlink = -1; pht-hti.parent = -1; if (i hti.ww = wi; else pht-hti.ww = -1; for ( i = 0; i m-1; i+) m1 =MAXINT; m2 =MAXINT; x1 =-1; x2 =-1; for (j = 0; jhtj.ww htj.parent = -1) m2 = m1; x2 = x1; m1 = pht-htj.ww; x1 = j; else if (pht-ht

29、j.ww htj.parent = -1) m2 = pht-htj.ww; x2 = j; pht-htx1.parent = m+i; pht-htx2.parent = m+i; pht-htm+i.ww = m1+m2; pht-htm+i.llink = x1; pht-htm+i.rlink = x2; pht-root = m+i; return pht; int main() int m = 0, j = 0, i = 0, parent = 0; int* w; PHtTree pht; printf(please input m = ); scanf(%d,&m); if

30、(m 1) printf(m is not reasonable!n); return 1; w = (int *)malloc(sizeof(int)*m); if (w = NULL) printf(overflow!n); return 1; printf(please input the %d numbers：n,m); for (j = 0; j m; j+) scanf(%d, w+j); pht = huffman(m, w); for (j = 0; j hti.parent != -1) parent = pht-hti.parent; if (pht-htparent.llink = i) printf(0); else printf(1); i = parent; printf(n); return 0;3 課程設(shè)計(jì)運(yùn)行結(jié)果與分