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

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

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

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

4、 //權(quán)值 int Flag; //標(biāo)識(shí)是否待構(gòu)結(jié)點(diǎn) ，是的話用 0 表示，否則為 1 int Parent; //父結(jié)點(diǎn) int Lchild; //左結(jié)點(diǎn)int Rchild; //右結(jié)點(diǎn)}hnodetype; 3、編寫(xiě)赫夫曼樹(shù)結(jié)點(diǎn)初使化函數(shù)。主要是使用 for 循環(huán)來(lái)實(shí)現(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ǎn)初始化，把指向父親的指針先置空{(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++) //輸入樹(shù)的結(jié)點(diǎn) {getchar(); printf(“輸入第

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