【正文】 i=1 n 作業(yè) : 6個字母 {A,B,C,D,E,F}組成 ,這6個字母在電文中出現(xiàn)的頻率高低依次為： 3,4,5,8,9,4,試為這 6個字母設(shè)計哈夫曼編碼。 } //若當(dāng)前結(jié)點是其父親的右孩子，則賦 1值 HC[i]=(char *)malloc((nstart)*sizeof(char))。 // 當(dāng)前字符的編碼工作數(shù)組的最后一個單元存放一個結(jié)束符。 HT[s2].parent = i。 HT[i].rchild=0。 HT[i].parent=0。HT, HuffmanCode amp。 //定義一個數(shù)組 四、構(gòu)造哈夫曼樹并求 n個字符的哈夫曼編碼之程序 ： weight parent lchild rchild Typedef struct HTNode{ unsigned int weight 。 二、哈夫曼樹及其應(yīng)用 ③ 無前綴 壓縮編碼（既哈夫曼編碼）： *思想 ：利用哈夫曼樹設(shè)計出來的不等長的編碼方案一定是無前綴的。 a 40 b 30 c 5 d 10 e 15 15 30 60 求解過程 二、哈夫曼樹及其應(yīng)用 ③ 實例：已知有 5個葉子結(jié)點的權(quán)值分別為： 5 , 15 , 40 , 30 , 10 ；試畫出一棵相應(yīng)的哈夫曼樹。 求解過程 二、哈夫曼樹及其應(yīng)用 ② 方法： 步驟 1:構(gòu)造一個具有 n棵二叉樹的森林 F={T1,T2,......,Tn}，其中 Ti是只有一個根結(jié)點且根結(jié)點的權(quán)值為 wi的二叉樹。第六章 （續(xù)） 哈夫曼樹及其應(yīng)用 設(shè)有 10000個學(xué)生某門課程的考試成績的分布如下表所示： 一、問題的提出 分?jǐn)?shù) 0~59 60~69 70~79 80~89 90~100 學(xué)生比例數(shù) 學(xué)生成績數(shù)據(jù)分布情況表 *問題： 現(xiàn)在要編寫程序依次根據(jù)每個學(xué)生的成績打印出該學(xué)生的成績等級。 步驟 2:在 F中選取兩棵其根結(jié)點的權(quán)值最小的二叉樹，從 F中刪除這兩棵樹，并以這兩棵二叉樹為左右子樹構(gòu)造一棵新的二叉樹添加到 F中，該新的二叉樹的根結(jié)點的權(quán)值為其左右孩子二叉樹的根結(jié)點的權(quán)值之和。 a 40 b 30 c 5 d 10 e 15 15 30 60 100 二、哈夫曼樹及其應(yīng)用 ① 等長 編碼： 以英文字符編碼為例，一般英文字符編碼是采用 7位二進制數(shù)編碼（ ASCII碼）。 *方法 ： 步驟 1：將各字符按照其“出現(xiàn)頻率”的統(tǒng)計數(shù)字安排一個“權(quán)值”并作為“葉子”，然后求出相應(yīng)的哈夫曼樹； 步驟 2：樹中各結(jié)點到其左孩子的邊上的權(quán)值設(shè)為 0、到其右孩子的邊上的權(quán)值設(shè)為 1（即所謂左 0右 1）； 步驟 3：從根開始到“葉子”所經(jīng)歷的邊上的數(shù)值的序列即為該“葉子”所對應(yīng)的字符的編碼。 unsigned int parent, lchild, rchild 。HC, int *w, int n) { //w是存放 n個字符的權(quán)值的一維數(shù)組， n為葉子個數(shù)；構(gòu)造哈夫曼樹 HT。 HT[i].lchild=0。 } for (i=n+1。 HT[i].lchild = s1。 for (i=1。 //為存放第 i個字符的編碼申請空間 strcpy(HC[i], amp。 :若哈夫曼樹中有 n個葉子結(jié)點 ,則該哈夫曼樹中共有2n1個結(jié)點。 樹的引入：程序優(yōu)化問題。 //若當(dāng)前結(jié)點是其父親的左孩子，賦 0值 else cd[ start] = “1”。 // 申請存放編碼的工作數(shù)組 (n+1個字符空間 ) cd[n1] = “\0”。該子程序是一個順序查找過程 HT[s1].parent = i。 HT[i].lchild=0。 i++) { //n個葉子結(jié)點賦初值， n個葉子最初為 n個根結(jié)點 HT[i].weight=w[i1]。 四、構(gòu)造哈夫曼樹并求 n個字符的哈夫曼編碼之程序 ： 算法思想： 例如： 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的存儲結(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 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個字符的哈夫曼編碼之程序 ：