【正文】 兩個兒子應(yīng)該是 i1個節(jié)點中無父親且權(quán)值最小的兩個結(jié)點 ) 四、構(gòu)造哈夫曼樹并求 n個字符的哈夫曼編碼之程序 ： 算法思想： 例如： 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的存儲結(jié)構(gòu)的初始情況如下： 針對第 i個結(jié)點 (n+1≤i≤2n1,n=4為葉子結(jié)點的個數(shù) )，在1~i1號結(jié)點中為第 i個結(jié)點尋找兩個兒子結(jié)點 (該兩個兒子應(yīng)該是 i1個節(jié)點中無父親且權(quán)值最小的兩個結(jié)點 ) 四、構(gòu)造哈夫曼樹并求 n個字符的哈夫曼編碼之程序 ： 算法思想： 例如： 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的存儲結(jié)構(gòu)的初始情況如下： 針對第 i個結(jié)點 (n+1≤i≤2n1,n=4為葉子結(jié)點的個數(shù) )，在1~i1號結(jié)點中為第 i個結(jié)點尋找兩個兒子結(jié)點 (該兩個兒子應(yīng)該是 i1個節(jié)點中無父親且權(quán)值最小的兩個結(jié)點 ) 四、構(gòu)造哈夫曼樹并求 n個字符的哈夫曼編碼之程序 ： 算法思想： 例如： 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的存儲結(jié)構(gòu)的初始情況如下： 針對第 i個結(jié)點 (n+1≤i≤2n1,n=4為葉子結(jié)點的個數(shù) )，在1~i1號結(jié)點中為第 i個結(jié)點尋找兩個兒子結(jié)點 (該兩個兒子應(yīng)該是 i1個節(jié)點中無父親且權(quán)值最小的兩個結(jié)點 ) 四、構(gòu)造哈夫曼樹并求 n個字符的哈夫曼編碼之程序 ： void HuffmanCoding(HuffmanTree amp。HT, HuffmanCode amp。HC, int *w, int n) { //w是存放 n個字符的權(quán)值的一維數(shù)組， n為葉子個數(shù)；構(gòu)造哈夫曼樹 HT。 if (n=1) return。 m = 2 * n 1。 //n即為葉子數(shù) n0,由二叉樹性質(zhì) 3,n0=n2+1,故樹中結(jié)點數(shù)為 2*n1 HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode))。 // 0號單元未用 for (i=1。 i=n。 i++) { //n個葉子結(jié)點賦初值， n個葉子最初為 n個根結(jié)點 HT[i].weight=w[i1]。 HT[i].parent=0。 HT[i].lchild=0。 HT[i].rchild=0。 } for (i=n+1。 i=m。 i++) { //n1個度為 2的結(jié)點賦初值 HT[i].weight=0。 HT[i].parent=0。 HT[i].lchild=0。 HT[i].rchild=0。 } for (i=n+1。 i=m。 i++) { // 第 i次循環(huán)時為第 i個結(jié)點選擇兩個兒子結(jié)點 s1與 s2 Select(HT, i1, amp。s1, amp。s2)。 // 在 i1棵子樹中也即 HT[1..i1]中選擇無父親 (parent為 0) //且權(quán)值最小的兩個結(jié)點 (其序號分別為 s1和 s2)。該子程序是一個順序查找過程 HT[s1].parent = i。 HT[s2].parent = i。 HT[i].lchild = s1。 HT[i].rchild = s2。 HT[i].weight = HT[s1].weight + HT[s2].weight。 //建立父子關(guān)系 } //哈夫曼樹 HT構(gòu)造完畢 四、構(gòu)造哈夫曼樹并求 n個字符的哈夫曼編碼之程序 ： //從葉子到根逆向求每個字符的哈夫曼編碼 。 HC=(HuffmanCode)malloc((n+1)*sizeof(char*))。 //申請 n個字符編碼的頭指針數(shù) 組的存儲空間 cd = (char *)malloc(n*sizeof(char))。 // 申請存放編碼的工作數(shù)組 (n+1個字符空間 ) cd[n1] = “\0”。 // 當前字符的編碼工作數(shù)組的最后一個單元存放一個結(jié)束符。 for (i=1。 i=n。 ++i) { //第 i次循環(huán)時求第 i個葉子 (字符 )的哈夫曼編碼 start = n1。 // start指向 cd數(shù)組 (即工作數(shù)組 )中編碼結(jié)束符的位置 for (c=i, f=HT[i].parent。 f!=0。 c=f, f=HT[f].parent) { // 從葉子到根逆向求編碼 if (HT[f].lchild==c) cd[ start] = “0”。 //若當前結(jié)點是其父親的左孩子，賦 0值 else cd[ start] = “1”。 } //若當前結(jié)點是其父親的右孩子，則賦 1值 HC[i]=(char *)malloc((nstart)*sizeof(char))。 //為存放第 i個字符的編碼申請空間 strcpy(HC[i], amp。cd[start])。 // 從 cd復(fù)制編碼 (串 )到 HC，標準函數(shù) strcpy在頭文 件 ，故程序的最前面應(yīng)該有偽操作 include } // i從 1到 n求 n個葉子的編碼 free(cd)。 //求編碼結(jié)束， 釋放工作數(shù)組 cd所占用的存儲空間 } // HuffmanCoding 五、小結(jié) : 樹的應(yīng)用：哈夫曼編碼的設(shè)計問題。 樹的定義： WPL=∑wi*li最小的二叉樹稱為“最優(yōu)二叉樹”或稱 為“ 哈夫曼樹 ”。 樹求解的算法思想： 3個步驟。 樹的引入：程序優(yōu)化問題。 i=1 n 作業(yè) : 6個字母 {A,B,C,D,E,F}組成 ,這6個字母在電文中出現(xiàn)的頻率高低依次為： 3,4,5,8,9,4,試為這 6個字母設(shè)計哈夫曼編碼。 :若哈夫曼樹中有 n個葉子結(jié)點 ,則該哈夫曼樹中共有2n1個結(jié)點。（提示：哈夫曼樹中無度數(shù)為 1的結(jié)點 ,則利用教材第 124頁二叉樹的性質(zhì) 3即可得證） C語言實現(xiàn)根據(jù) n個字符（結(jié)點）的權(quán)值求哈夫曼樹及 n個字符的哈夫曼編碼的子程序，并編制主程序main{}調(diào)用該子程序?qū)ζ湔_性進行驗證。 End