數(shù)據(jù)結(jié)構(gòu)-赫夫曼樹-課程設(shè)計

1、1《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計題目：赫夫曼樹的建立 題目：赫夫曼樹的建立一、需求分析 一、需求分析眾所周知，最優(yōu)二叉樹（赫夫曼樹）在解決很多判定問題時，有著無可比 擬的優(yōu)勢。同時，在目前，進(jìn)行快速遠(yuǎn)距離通信的主要手段主要是電報，即將 需傳送的文字轉(zhuǎn)換成由二進(jìn)制的字符組成的字符串。而在文字的轉(zhuǎn)換編碼中， 也必然要用到赫夫曼算法才能使傳送的電文盡可能地短。所以，本程序主要目的就是是利用赫夫曼算法快速生成一個普通二叉樹的 最優(yōu)二叉樹（赫夫曼樹） ，同

2、時本程序還可以生成對每個結(jié)點對應(yīng)的赫夫曼編 碼。在這個程序中主要有 3 個函數(shù)：InitHaffman 函數(shù)：完成對樹的結(jié)點進(jìn)行初始化。 Haffman 函數(shù)：用于構(gòu)造赫夫曼樹并生成相應(yīng)的赫夫曼編碼。 OutputHaffman 函數(shù)：輸出赫夫曼樹和編碼。二、概要設(shè)計 二、概要設(shè)計赫夫曼算法的敘述過程：（1）根據(jù)給定的 n 個權(quán)值{w1,w2,……，wn}構(gòu)成 n 棵二叉樹的集合 F={T1,T2,……,Tn},其中每棵二叉樹 Ti 中

3、只有一個帶權(quán)為 wi 的根結(jié)點，其 左右子樹均空。（2）在 F 中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新 的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán) 值之和。（3）在 F 中刪除這兩棵樹，同時將新得到的二叉樹加入 F 中。 （4）重復(fù)（2）和（3） ，直到 F 只含一棵樹為止。這棵樹便是赫夫曼 樹。 程序大體設(shè)計流程：3typedef struct {int data; //結(jié)點值int Weight;

4、 //權(quán)值 int Flag; //標(biāo)識是否待構(gòu)結(jié)點 ，是的話用 0 表示，否則為 1 int Parent; //父結(jié)點 int Lchild; //左結(jié)點int Rchild; //右結(jié)點}hnodetype; 3、編寫赫夫曼樹結(jié)點初使化函數(shù)。主要是使用 for 循環(huán)來實現(xiàn)，詳細(xì)代碼如下 所示： void InitHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n) { i

5、nt i; for(i=0;i<=2*n-1;i++) //把生成的結(jié)點初始化，把指向父親的指針先置空{(diào) HuffNode[i].Weight=0; HuffNode[i].Parent=0; HuffNode[i].Flag=0; HuffNode[i].Lchild=-1; HuffNode[i].Rchild=-1;} for(i=0;i<n;i++) //輸入樹的結(jié)點 {getchar(); printf(“輸入第

6、%d 個葉結(jié)點值：“,i+1); scanf(“%c“,} printf(“\n“); for(i=0;i<n;i++) //輸入樹結(jié)點對應(yīng)的權(quán)值 {getchar(); printf(“輸入第%d 個葉子結(jié)點對應(yīng)的權(quán)值:“,i+1); scanf(“%d“,} printf(“\n“);} 4、構(gòu)造赫夫曼樹函數(shù)。按照赫夫曼算法，我們先找對應(yīng)權(quán)值最小的兩個結(jié)點， 再將這兩個結(jié)點提出構(gòu)成一個二叉樹，此二叉樹的根權(quán)值