1、數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)(哈夫曼樹(shù)的建立和編碼)班 級(jí)：學(xué) 號(hào)：姓 名：李佳莉?qū)嶒?yàn)四 哈夫曼樹(shù)的建立和編碼一 問(wèn)題的提出如何進(jìn)行如下操作：1.借助哈夫曼樹(shù)模型來(lái)對(duì)不同的字符進(jìn)行編碼,以及以哈夫曼樹(shù)形式輸出哈夫曼樹(shù)。2. 根據(jù)每個(gè)字符不同的權(quán)值建立哈夫曼樹(shù)，并對(duì)輸入的字符進(jìn)行編碼處理，并存入文件中。二Huffman樹(shù)及編碼算法的主要思想哈夫曼樹(shù)（Huffman樹(shù)）是帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。根據(jù)哈夫曼樹(shù)的定義，一棵二叉樹(shù)要使其帶權(quán)路徑長(zhǎng)度最小，必須使權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。哈夫曼依據(jù)這一特點(diǎn)提出了哈夫曼算法，其基本思想是： 初始化：由給定的n個(gè)權(quán)值w1，w2，w

2、n構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二叉樹(shù)集合FT1，T2，Tn； 選取與合并：在F中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹(shù)分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，這棵新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和； 刪除與加入：在集合F中刪除作為左、右子樹(shù)的兩棵二叉樹(shù)，并將新建立的二叉樹(shù)加入到集合F中； 重復(fù)、兩步，當(dāng)集合F中只剩下一棵二叉樹(shù)時(shí)，這棵二叉樹(shù)便是哈夫曼樹(shù)。通過(guò)上述Huffman樹(shù)的構(gòu)造過(guò)程，我們可以得到如下要點(diǎn)： 當(dāng)有n個(gè)權(quán)值（相應(yīng)的Huffman樹(shù)中有n個(gè)葉子），共需合并n-1次； 每合并一次產(chǎn)生一個(gè)分支結(jié)點(diǎn)，經(jīng)過(guò)n-1次合并后得到的Huffman樹(shù)中共有2n-1個(gè)結(jié)點(diǎn)

3、，其中有n-1個(gè)分支結(jié)點(diǎn)； 在Huffman樹(shù)中只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn)； 算法要求選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，但并沒(méi)有要求哪一棵作左子樹(shù)，哪一棵作右子樹(shù)，所以左右子樹(shù)的順序是任意的，一般情況下權(quán)值小的作為左子樹(shù)。 對(duì)同一組權(quán)值可以構(gòu)造出不同的huffman樹(shù)，但是他們的帶權(quán)路徑長(zhǎng)度相同。Huffman編碼的主要思想：在建好的huffman樹(shù)中左孩子的邊賦值均為0，右孩子的邊賦值均為1，然后從根節(jié)點(diǎn)遍歷到所求節(jié)點(diǎn)，依次將遇到的0或1寫(xiě)出就是所求的點(diǎn)的編碼。三、算法的設(shè)計(jì)和實(shí)現(xiàn)#include#includestrin

4、g.husing namespace std;#define MAX 100#define N 26typedef struct/哈夫曼樹(shù)的結(jié)點(diǎn) unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*Huffmantree; typedef struct /字符存儲(chǔ)結(jié)點(diǎn)信息 char data; /待編碼的字符 int weight; /字符的權(quán)值 char codeN; /字符的編碼 HTCode;/初始化結(jié)點(diǎn)信息void InitCode(HTCode *Hr,int &n) coutn; cout請(qǐng)輸入字符編碼以及相

5、應(yīng)的權(quán)值：endl; for(int i = 1;i (Hr+i)-data(Hr+i)-weight; void Select(Huffmantree &HT,int end,int *s1,int *s2)/在0end之間,找出最小和次小的兩個(gè)結(jié)點(diǎn)序號(hào),返回S1,S2 int i; int min1 = MAX; int min2; for (i = 1;i parent = 0 & (HT+i)-weightweight; min2 = MAX; for(i = 1;i parent = 0 & *s1 != i & min2 = (HT+i)-weight) *s2 = i; min2

6、 = (HT+i)-weight; /初始化哈夫曼樹(shù),并把信息存入Hrvoid InitHfmtree(Huffmantree &Ht,HTCode Hr,int &n) if(n = 1) return; int m,start,i,j,f; int s1,s2; m = 2*n-1; Ht = new HTNodem+1; Huffmantree P; P = Ht+1; for(i = 1;i = m;i+,P+) if(i weight = Hri.weight; else P-weight = 0; P-lchild = 0; P-rchild = 0; P-parent = 0;

7、for(i = n+1;i parent = i; (Ht+s2)-parent = i; (Ht+i)-lchild = s1; (Ht+i)-rchild = s2; (Ht+i)-weight = (Ht+s1)-weight + (Ht+s2)-weight; char *code; code = new charn; coden-1 = 0; for(i = 1;i code start = n-1; for(j = i,f = Htj.parent;f != 0;j = f,f = Htf.parent) if(Htf.lchild = j) code-start = 0; els

8、e code-start = 1; strcpy(Hri.code,&codestart); cout字符編碼初始化完成！endl; void Encoding(HTCode *Hr,int n)/編碼 int i,j; char *encode; encode = new charn; cout請(qǐng)選擇編碼的字符：encode; for(i = 0;encodei!=0;i+) j = 1; while(encodei != Hrj.data) j+; if(jn) cout輸入編碼encodei錯(cuò)誤！endl; else coutHrj.data的編碼是Hrj.codeendl; cout字符串 ; for(i = 0;encodei!=0;i+) coutencodei; cout 的編碼是：n) cout輸入編碼encodei錯(cuò)誤！endl; else coutHrj.code; coutendl; cout編碼已經(jīng)結(jié)束！endl;int main() Huffmantree Ht; HTCode HrN; int n = 0; char cmd; do cout初始化赫夫曼樹(shù)（I） 編碼（E） 離開(kāi)（Q） cmd; switch(cmd) case I: InitCode(Hr,n); InitHfmtree(H