【正文】 長編碼時，必須使任何一個字符的編碼都不是另一個字符編碼的前綴，這樣才能保證譯碼的唯一性。 HuffNode[x2].parent:=n+i。 HuffNode[i].lchild=1。構造哈夫曼樹時，首先將由n個字符形成的n個葉結點存放到數(shù)組HuffNode的前n個分量中，然后根據(jù)前面介紹的哈夫曼方法的基本思想，不斷將兩個小子樹合并為一個較大的子樹，每次構成的新子樹的根結點順序放到HuffNode數(shù)組中的前n個分量的后面。如果二叉樹中的葉結點都具有一定的權值，則可將這一概念加以推廣。 鐵球分類現(xiàn)有一批球磨機上的鐵球，需要將它分成四類：直徑不大于20的屬于第一類。由于這種算法是哈夫曼最早提出的，所以將最優(yōu)二叉樹稱為哈夫曼樹。 end。 x2:=x1。 (b)所示為另一種編碼方案，用此編碼對上述電文進行編碼所建立的代碼為00010010101100，長度為14?！厩蠊蚵幋a程序段】const Maxleaf=128。 dec ()。 在本章的引入部分，兩個例子都是判定問題，這兩個判定問題都可以通過構造哈夫曼樹來優(yōu)化判定，以達到總的判定次數(shù)最少。我們知道八位二進制可以跟有相同ASCII碼值的一個字符的建立起對應關系，如果將位圖以字符的方式存儲，理想狀態(tài)下存儲空間變以原來的1/8。其實JPEG圖形格式就有類似的處理方式。顯然，此程序很簡單，只要利用條件語句便可完成。 p:=HuffNode[c].parent。 {定義最大結點數(shù)}MaxBit=10。如果在編碼時考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長的編碼，構造一種不等長編碼，則電文的代碼就可能更短。 x1:=j。var ……procedure CreatHaffmanTree(var HuffNode: HuffArr)。可以計算出其帶權路徑長度為29，由此可見，對于同一組給定葉結點所構造的哈夫曼樹，樹的形狀可能不同，但帶權路徑長度值是相同的，一定是最小的。我們可以把這個判斷過程表示為 ： 兩種判斷二叉樹示意圖那么究竟將這個判斷過程表示成哪一個判斷框，才能使其執(zhí)行時間最短呢？讓我們對上述判斷框做一具體的分析。 最優(yōu)二叉樹，也稱哈夫曼（Haffman）樹，是指對于一組帶有確定權值的葉結點，構造的具有最小帶權路徑長度的二叉樹。為了判定一個結點是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。 {輸入葉子結點個數(shù)} for i:=0 to 2*n1 do {數(shù)組HuffNode[ ]初始化} begin HuffNode[i].weight=0。 end。具體做法如下：設需要編碼的字符集合為{d1，d2，…，dn}，它們在電文中出現(xiàn)的次數(shù)或頻率集合為{w1，w2，…，wn}，以d1，d2，…，dn作為葉結點，w1，w2，…，wn作為它們的權值，構造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結點到每個葉結點所經(jīng)過的路徑分支組成的0和1的序列便為該結點對應字符的編碼，我們稱之為哈夫曼編碼。 end。HuffCode[i].start=。因為在實際中，學生的成績在五個等級上的分布是不均勻的，：分數(shù) 0－59 60－69 70－79 80－89 90－100比例數(shù) 分數(shù)段的分布頻率則80％以上的數(shù)據(jù)需進行三次或三次以上的比較才能得出結果?！据斎搿康谝恍袃蓚€數(shù)M、N，表示圖形共有M行、每行N列，N mod 8=0。如果用0～7這8個數(shù)的二進制數(shù)表示這8個字母也是一種編碼方案，試比較這兩種方法的優(yōu)劣。 對壓縮后的數(shù)據(jù)文件進行解碼則必須借助于哈夫曼樹T，其過程是：依次讀人文件的二進制碼，從哈夫曼樹的根結點(即T[m1])出發(fā)，若當前讀人0，則走向左孩子，否則走向右孩子。 c:=i。 求哈夫曼編碼，實質上就是在已建立的哈夫曼樹中，從葉結點開始，沿結點的雙親鏈域