《數(shù)據(jù)結(jié)構(gòu)（C語言描述）（第2版）》教學(xué)課件4-13構(gòu)造哈夫曼樹的算法

1、2016數(shù)據(jù)結(jié)構(gòu)Data structure講授：劉斌構(gòu)造哈夫曼樹的算法常州信息職業(yè)技術(shù)學(xué)院02教學(xué)目標(biāo)123哈夫曼樹結(jié)點(diǎn)的結(jié)構(gòu)03哈夫曼樹的描述構(gòu)造哈夫曼樹的步驟4構(gòu)造哈夫曼樹具體算法三、鏈表的插入04構(gòu)造哈夫曼樹的算法1.33哈夫曼樹及哈夫曼編碼3、構(gòu)造哈夫曼樹的算法1哈夫曼樹結(jié)點(diǎn)的結(jié)構(gòu)哈夫曼樹的結(jié)點(diǎn)用一個(gè)大小為2n-1的向量來存儲，每個(gè)結(jié)點(diǎn)包含權(quán)值域weight、指示左右孩子結(jié)點(diǎn)在向量中下標(biāo)的整型量lchild和rchild、指示雙親結(jié)點(diǎn)在向量中下標(biāo)的整型量parent。lchildweightparentrchild圖4-26 結(jié)點(diǎn)結(jié)構(gòu)weightlchildrchildparent0

2、5構(gòu)造哈夫曼樹的算法1.3122哈夫曼樹的描述#define n 100 /葉子數(shù)目#define m 2*n-1/樹中結(jié)點(diǎn)總數(shù)typedef struct /定義結(jié)點(diǎn)類型 double weight; /定義權(quán)值域 int lchild,rchild,parent; /定義左右孩子及雙親指針HTNode;typedef HTNode HuffmanTreem; /*定義HuffmanTree為新的類型標(biāo)識符，用該標(biāo) 符定義的變量是具有HTNode類型的含有m個(gè)元素的向量。*/C數(shù)組的下界為0，故用-1表示空指針。樹中某結(jié)點(diǎn)的lchild、rchild和parent不等于-1時(shí)，它們分別是該結(jié)

3、點(diǎn)的左、右孩子和雙親結(jié)點(diǎn)在向量中的下標(biāo)。設(shè)置parent域有兩個(gè)作用：其一是使查找某結(jié)點(diǎn)的雙親變得簡單；其二是可通過判定parent的值是否為-1來區(qū)分根與非根結(jié)點(diǎn)。（iii）新結(jié)點(diǎn)Ti的權(quán)值置為Tp1和Tp2的權(quán)值之和。 06構(gòu)造哈夫曼樹的算法1.33構(gòu)造哈夫曼樹T的步驟（1）初始化：將T0m-1中2n-1個(gè)結(jié)點(diǎn)里的三個(gè)指針均置為空（即置為-1），權(quán)值置為0。（2）輸入：讀入n個(gè)葉子的權(quán)值存于向量的前n個(gè)分量（即T0 n-1）中。它們是初始森林中n個(gè)孤立的根結(jié)點(diǎn)上的權(quán)值。（3）合并：對森林中的樹共進(jìn)行n-1次合并，所產(chǎn)生的新結(jié)點(diǎn)依次放入向量T的第i個(gè)分量中（nim-1）。每次合并分兩步：在當(dāng)

4、前森林T0 i-1的所有結(jié)點(diǎn)中，選取權(quán)最小和次小的兩個(gè)根結(jié)點(diǎn)Tp1和Tp2作為合并對象，這里0p1，p2i-1。 將根為Tp1和Tp2的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結(jié)點(diǎn)Ti。（iii）新結(jié)點(diǎn)Ti的權(quán)值置為Tp1和Tp2的權(quán)值之和。 06構(gòu)造哈夫曼樹的算法1.3具體操作:（i）將Tp1和Tp2的parent置為i;（ii）將Ti的lchild和rchild分別置為p1和p2;（iii）新結(jié)點(diǎn)Ti的權(quán)值置為Tp1和Tp2的權(quán)值之和。 合并后Tpl和Tp2在當(dāng)前森林中已不再是根，因?yàn)樗鼈兊碾p親指針均已指向了Ti，所以下一次合并時(shí)不會被選中為合并對象。07構(gòu)造哈夫曼樹的算法1.3構(gòu)

5、造哈夫曼樹T具體算法示例：給定5個(gè)葉子結(jié)點(diǎn)a，b，c， d和e，分別帶權(quán)7，6，12，15和1007構(gòu)造哈夫曼樹的算法1.3void InitHuffmanTree(HuffmanTree T) /初始化 int i; for (i=0; im; i+) Ti.weight=0;Ti.lchild=-1;Ti.rchild=-1;Ti.parent=-1; 構(gòu)造哈夫曼樹T具體算法初始化函數(shù)weightlchildrchildparent0-1-1-10-1-1-10-1-1-10-1-1-10-1-1-10-1-1-10-1-1-10-1-1-10-1-1-107構(gòu)造哈夫曼樹的算法1.3構(gòu)造哈

6、夫曼樹T具體算法void InputWeight(HuffmanTree T)/輸入權(quán)值double w;int i;for (i=0; in;i+) printf(n輸入第%d個(gè)權(quán)值:,i+1); scanf(%lf,&w); Ti.weight=w;輸入權(quán)值函數(shù)weightlchildrchildparent7-1-1-16-1-1-112-1-1-115-1-1-110-1-1-10-1-1-10-1-1-10-1-1-10-1-1-108構(gòu)造哈夫曼樹的算法1.3void SelectMin(HuffmanTree T, int i, int *p1,int *p2)/選擇兩個(gè)小的結(jié)點(diǎn)d

7、ouble min1=999999;/定義并初始化最小權(quán)值double min2=999999;/定義并初始化次小權(quán)值int j;for (j=0;j=i;j+) if(Tj.parent=-1)選擇兩個(gè)權(quán)最小的根結(jié)點(diǎn)函數(shù)if(Tj.weightmin1) min2=min1; /改變最小權(quán),次小權(quán)及其位置 min1=Tj.weight; /找出最小的權(quán)值 *p2=*p1; *p1=j;else if(Tj.weightmin2) min2=Tj.weight;/改變次小權(quán)及位置 *p2=j;weightlchildrchildparent7-1-1-16-1-1-112-1-1-115-1-

8、1-110-1-1-10-1-1-10-1-1-10-1-1-10-1-1-109構(gòu)造哈夫曼樹的算法1.3void CreateHuffmanTree(HuffmanTree T)/構(gòu)造哈夫曼樹，Tm-1為其根結(jié)點(diǎn)int i,p1,p2;InitHuffmanTree(T); /將T初始化InputWeight(T); /輸入葉子權(quán)值至weight域for(i=n;im;i+)/共n-1次合并,新結(jié)點(diǎn)存于Ti中SelectMin(T,i-1,&p1,&p2); /選建立哈夫曼樹函數(shù)。擇權(quán)最小的根結(jié)點(diǎn)Tp1.parent=Tp2.parent=i;Ti.lchild=p1; /最小權(quán)根結(jié)點(diǎn)是新結(jié)

9、點(diǎn)左孩子Ti.rchild=p2; /次小權(quán)根結(jié)點(diǎn)是新結(jié)點(diǎn)右孩子Ti.weight=Tp1.weight+Tp2.weight;weightlchildrchildparent7-1-1-16-1-1-112-1-1-115-1-1-110-1-1-10-1-1-10-1-1-10-1-1-10-1-1-1weightlchildrchildparent7-1-156-1-1512-1-1-115-1-1-110-1-1-11310-10-1-1-10-1-1-10-1-1-1weightlchildrchildparent7-1-156-1-1512-1-1615-1-1-110-1-161310-12242-10-1-1-10-1-1-1weightlchildrchildparent7-1-15