軟件技術(shù)基礎(chǔ)論文

《軟件技術(shù)基礎(chǔ)論文》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、《數(shù)據(jù)結(jié)構(gòu)》課程論文報(bào)告書題冃：哈夫曼樹與哈夫曼編碼系別：機(jī)電系學(xué)號：學(xué)生姓名:1、基本概念什么是哈弗曼樹什么是哈夫曼編碼2、基本操作構(gòu)造哈弗曼樹的基本步驟構(gòu)造哈弗曼樹的代碼哈夫曼編碼的基本介紹3、總結(jié)一、基本術(shù)語1.什么是哈夫曼樹給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹（Huffmantree）。例如：有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7,5,2,4,構(gòu)造有4個(gè)葉子結(jié)點(diǎn)WPL二7*1+5*2+2*3+4*3=35帶權(quán)路徑WPL值最小。所以此二叉樹為哈夫曼樹。哈夫曼樹的特點(diǎn)：1?權(quán)值越小的葉子節(jié)點(diǎn)越遠(yuǎn)離根節(jié)點(diǎn)，反Z,貝i

2、j越靠近根節(jié)點(diǎn)；2.只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn)。路徑和路徑長度在一棵樹中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長度為L-1。結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長度若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積。樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為WPLo2?什么是哈夫曼編碼哈夫曼編碼：對一棵具有n個(gè)葉子的哈夫曼樹，若對樹中的

3、每個(gè)左分支賦予0,右分支賦予1,則從根到每個(gè)葉子的通路上，各分支的賦值分別構(gòu)成一個(gè)二進(jìn)制串，該二進(jìn)制串就稱為哈夫曼編碼。例要傳輸?shù)淖址疍二{A,B,C,D}字符出現(xiàn)頻率w二{4,3,2,1}根據(jù)哈弗曼樹的構(gòu)造特點(diǎn)權(quán)值越大越靠近根節(jié)點(diǎn)的原則，得到下面這哈弗曼樹。A(0>B(10)C(110)11X111):、基本操作1?哈弗曼樹構(gòu)造的基本步驟W二｛5,3,2,4｝哈弗曼樹的基本構(gòu)造過程第一步：初始化｛5,324｝第二步：選取與合并從當(dāng)中選取兩個(gè)數(shù)一個(gè)數(shù)字最小另外一個(gè)較小第三步：刪除與加入｛5,4,重復(fù)二三步就構(gòu)成了最優(yōu)二叉樹。哈夫曼樹的類型定義：哈夫曼樹是一種二叉樹，由于哈夫曼樹

4、中沒有度為1的結(jié)點(diǎn)，則一棵有n個(gè)葉子的哈夫曼樹共有2Xn—l個(gè)結(jié)點(diǎn)，可以用一個(gè)大小為2Xn-l的一維數(shù)組存放哈夫曼樹的各個(gè)結(jié)點(diǎn)。由于每個(gè)結(jié)點(diǎn)同吋還包含其雙親信息和孩子結(jié)點(diǎn)的信息，所以構(gòu)成一個(gè)靜態(tài)三叉鏈表。靜態(tài)三叉鏈表中:每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：權(quán)值雙親左孩了序號右孩子序號各結(jié)點(diǎn)存儲在一維數(shù)組中，0號單元不使用，從1號位置開始使用。AdataparentLChildRChild1A0232B1003C1454D3005E300typedefstructHFTreeNodeintweight;/*結(jié)點(diǎn)的權(quán)值*/intparent;/*雙親的下標(biāo)*/intlchild;/*左孩子結(jié)點(diǎn)的下標(biāo)*

5、/intrchild;/右孩子結(jié)點(diǎn)的下標(biāo)*/}HFTreeNode,HuffmanTree;2?構(gòu)造哈弗曼樹代碼:#defineMaxSize100〃葉子數(shù)目#includetypedefstructHFTreeNodeintweight;/*結(jié)點(diǎn)的權(quán)值*/intparent;丿/*雙親的下標(biāo)*/intlchild;/*左孩子結(jié)點(diǎn)的下標(biāo)*/intrchild;!*右孩子結(jié)點(diǎn)的下標(biāo)*/}HFTreeNode,HuffmanTree;voidSelect(HuffmanTree*HT,intg,ints[]);voidprint(HuffmanTree*HT,int

6、m);voidCreatHuffmanTree(HuffmanTreeT[MaxSize],intn){inti,p[2],lc,rc;if(n<1){printf(”結(jié)點(diǎn)大小不能小于ln);return;}intm=2*n;〃計(jì)算哈夫曼樹的結(jié)點(diǎn)大小for(i=1;i

7、].weight=5;T[2].weight=7;T[3J.weight=3;T[4J.weight=2;T[5].weight=&*/print(T,m);for(i=n4-1;i