【正文】 End 。 :若哈夫曼樹中有 n個(gè)葉子結(jié)點(diǎn) ,則該哈夫曼樹中共有2n1個(gè)結(jié)點(diǎn)。 樹的引入：程序優(yōu)化問題。 樹的定義： WPL=∑wi*li最小的二叉樹稱為“最優(yōu)二叉樹”或稱 為“ 哈夫曼樹 ”。 // 從 cd復(fù)制編碼 (串 )到 HC，標(biāo)準(zhǔn)函數(shù) strcpy在頭文 件 ，故程序的最前面應(yīng)該有偽操作 include } // i從 1到 n求 n個(gè)葉子的編碼 free(cd)。 //為存放第 i個(gè)字符的編碼申請(qǐng)空間 strcpy(HC[i], amp。 //若當(dāng)前結(jié)點(diǎn)是其父親的左孩子，賦 0值 else cd[ start] = “1”。 f!=0。 ++i) { //第 i次循環(huán)時(shí)求第 i個(gè)葉子 (字符 )的哈夫曼編碼 start = n1。 for (i=1。 // 申請(qǐng)存放編碼的工作數(shù)組 (n+1個(gè)字符空間 ) cd[n1] = “\0”。 HC=(HuffmanCode)malloc((n+1)*sizeof(char*))。 HT[i].weight = HT[s1].weight + HT[s2].weight。 HT[i].lchild = s1。該子程序是一個(gè)順序查找過程 HT[s1].parent = i。s2)。 i++) { // 第 i次循環(huán)時(shí)為第 i個(gè)結(jié)點(diǎn)選擇兩個(gè)兒子結(jié)點(diǎn) s1與 s2 Select(HT, i1, amp。 } for (i=n+1。 HT[i].lchild=0。 i++) { //n1個(gè)度為 2的結(jié)點(diǎn)賦初值 HT[i].weight=0。 } for (i=n+1。 HT[i].lchild=0。 i++) { //n個(gè)葉子結(jié)點(diǎn)賦初值， n個(gè)葉子最初為 n個(gè)根結(jié)點(diǎn) HT[i].weight=w[i1]。 // 0號(hào)單元未用 for (i=1。 m = 2 * n 1。HC, int *w, int n) { //w是存放 n個(gè)字符的權(quán)值的一維數(shù)組， n為葉子個(gè)數(shù)；構(gòu)造哈夫曼樹 HT。 四、構(gòu)造哈夫曼樹并求 n個(gè)字符的哈夫曼編碼之程序 ： 算法思想： 例如： a 7 b 5 c 2 d 4 6 11 18 7 0 0 0 5 0 0 0 2 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 HT 其哈夫曼樹 HT的存儲(chǔ)結(jié)構(gòu)的初始情況如下： 針對(duì)第 i個(gè)結(jié)點(diǎn) (n+1≤i≤2n1,n=4為葉子結(jié)點(diǎn)的個(gè)數(shù) )，在1~i1號(hào)結(jié)點(diǎn)中為第 i個(gè)結(jié)點(diǎn)尋找兩個(gè)兒子結(jié)點(diǎn) (該兩個(gè)兒子應(yīng)該是 i1個(gè)節(jié)點(diǎn)中無父親且權(quán)值最小的兩個(gè)結(jié)點(diǎn) ) 四、構(gòu)造哈夫曼樹并求 n個(gè)字符的哈夫曼編碼之程序 ： 算法思想： 例如： a 7 b 5 c 2 d 4 6 11 18 7 0 0 0 5 0 0 0 2 5 0 0 4 5 0 0 6 0 3 4 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 HT 其哈夫曼樹 HT的存儲(chǔ)結(jié)構(gòu)的初始情況如下： 針對(duì)第 i個(gè)結(jié)點(diǎn) (n+1≤i≤2n1,n=4為葉子結(jié)點(diǎn)的個(gè)數(shù) )，在1~i1號(hào)結(jié)點(diǎn)中為第 i個(gè)結(jié)點(diǎn)尋找兩個(gè)兒子結(jié)點(diǎn) (該兩個(gè)兒子應(yīng)該是 i1個(gè)節(jié)點(diǎn)中無父親且權(quán)值最小的兩個(gè)結(jié)點(diǎn) ) 四、構(gòu)造哈夫曼樹并求 n個(gè)字符的哈夫曼編碼之程序 ： 算法思想： 例如： a 7 b 5 c 2 d 4 6 11 18 7 0 0 0 5 6 0 0 2 5 0 0 4 5 0 0 6 6 3 4 11 0 2 5 0 0 0 0 1 2 3 4 5 6 7 HT 其哈夫曼樹 HT的存儲(chǔ)結(jié)構(gòu)的初始情況如下： 針對(duì)第 i個(gè)結(jié)點(diǎn) (n+1≤i≤2n1,n=4為葉子結(jié)點(diǎn)的個(gè)數(shù) )，在1~i1號(hào)結(jié)點(diǎn)中為第 i個(gè)結(jié)點(diǎn)尋找兩個(gè)兒子結(jié)點(diǎn) (該兩個(gè)兒子應(yīng)該是 i1個(gè)節(jié)點(diǎn)中無父親且權(quán)值最小的兩個(gè)結(jié)點(diǎn) ) 四、構(gòu)造哈夫曼樹并求 n個(gè)字符的哈夫曼編碼之程序 ： 算法思想： 例如： a 7 b 5 c 2 d 4 6 11 18 7 7 0 0 5 6 0 0 2 5 0 0 4 5 0 0 6 6 3 4 11 7 2 5 18 0 1 6 1 2 3 4 5 6 7 HT 其哈夫曼樹 HT的存儲(chǔ)結(jié)構(gòu)的初始情況如下： 針對(duì)第 i個(gè)結(jié)點(diǎn) (n+1≤i≤2n1,n=4為葉子結(jié)點(diǎn)的個(gè)數(shù) )，在1~i1號(hào)結(jié)點(diǎn)中為第 i個(gè)結(jié)點(diǎn)尋找兩個(gè)兒子結(jié)點(diǎn) (該兩個(gè)兒子應(yīng)該是 i1個(gè)節(jié)點(diǎn)中無父親且權(quán)值最小的兩個(gè)結(jié)點(diǎn) ) 四、構(gòu)造哈夫曼樹并求 n個(gè)字符的哈夫曼編碼之程序 ： void HuffmanCoding(HuffmanTree amp。 // HaffmanCode是指向一個(gè) 字符型數(shù)組的指針類型 n個(gè)字符型數(shù)組存放 n個(gè)葉子的哈夫曼編碼 這 n個(gè)字符數(shù)組的頭指針 HC[i](1≤i≤n)分別指向一個(gè)字符型數(shù)組的首地址，又構(gòu)成一個(gè)指針類型的一維數(shù)組； “0“ “1“ “1“ “0“ “\0” “1“ “0“ “\0” . . . . “0“ “0“ “1“ “1“ “1“ “\0” HC[1] HC[2] HC[n] . . . . 則 n個(gè)字符串?dāng)?shù)組的頭指針 HC[i](1 ≤i≤n)可以如此定義： HC=(HuffmanCode)malloc((n+1)*sizeof(char *)。 //該指針用以申請(qǐng)數(shù)組時(shí)作為數(shù)組名 C語言定義： 例如： 7 7 0 0 5 6 0 0 2 5 0 0 4 5 0 0 6 6 3 4 a 7 b 5 c 2 d 4 11 7 2 5 6 11 18 18 0 1 6 1 2 3 4 5 6 7 HT 哈夫曼樹 HT的存儲(chǔ)結(jié)構(gòu)如下 (HT為 HuffmanTree類型 )： HT是一個(gè) HTNode類型的一維數(shù)組，用以存放 m個(gè)結(jié)點(diǎn)元素 (m=2n1,其中 n為葉子個(gè)數(shù) )； 即采用靜態(tài)二叉鏈表存放哈夫曼樹； 故 HT可以用如下語句為其申請(qǐng)空間： HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode))。