數(shù)據(jù)結(jié)構(gòu)哈夫曼樹(shù)實(shí)驗(yàn)報(bào)告

1、第 頁(yè)2009級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)3哈夫曼樹(shù)學(xué)生姓名：陳家斌班級(jí)：2009211121班內(nèi)序號(hào)：16學(xué)號(hào)：09210619日期：2010年12月3日I.【實(shí)驗(yàn)?zāi)康摹客ㄟ^(guò)選擇下面兩個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：掌握二叉樹(shù)基本操作的實(shí)現(xiàn)方法了解赫夫曼樹(shù)的思想和相關(guān)概念學(xué)習(xí)使用二叉樹(shù)解決實(shí)際問(wèn)題的能力【題目】利用二叉樹(shù)結(jié)構(gòu)實(shí)現(xiàn)赫夫曼編/解碼器?！净疽蟆?、初始化(Init):能夠?qū)斎氲娜我忾L(zhǎng)度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立赫夫曼樹(shù)2、建立編碼表(CreateTable)：利用已經(jīng)建好的赫夫曼樹(shù)進(jìn)行編碼，并將每個(gè)字符的編碼輸出。3、編碼(Encoding)：根據(jù)編

2、碼表對(duì)輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。4、譯碼(Decoding)：利用已經(jīng)建好的赫夫曼樹(shù)對(duì)編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。5、打印(Print)：以直觀的方式打印赫夫曼樹(shù)(選作)6、計(jì)算輸入的字符串編碼前和編碼后的長(zhǎng)度，并進(jìn)行分析，討論赫夫曼編碼的壓縮效果。【測(cè)試數(shù)據(jù)】IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提示：1、用戶界面可以設(shè)計(jì)為“菜單”方式：能夠進(jìn)行交互。2、根據(jù)輸入的字符串中每個(gè)字符出現(xiàn)的次數(shù)統(tǒng)計(jì)頻度，對(duì)沒(méi)有出現(xiàn)的字符一律不用編碼?！敬a要求】1、必須要有異常處理，

3、比如刪除空鏈表時(shí)需要拋出異常；2、保持良好的編程的風(fēng)格：代碼段與段之間要有空行和縮近標(biāo)識(shí)符名稱應(yīng)該與其代表的意義一致函數(shù)名之前應(yīng)該添加注釋說(shuō)明該函數(shù)的功能關(guān)鍵代碼應(yīng)說(shuō)明其功能3、遞歸程序注意調(diào)用的過(guò)程，防止棧溢出2.【算法實(shí)現(xiàn)】程序第一遍統(tǒng)計(jì)原數(shù)據(jù)中各字符出現(xiàn)的頻率，利用得到的頻率值創(chuàng)建哈夫曼樹(shù)，并把樹(shù)的信息保存起來(lái)，以便解壓時(shí)創(chuàng)建同樣的哈夫曼樹(shù)進(jìn)行解壓；第二遍，根據(jù)第一遍掃描得到的哈夫曼樹(shù)進(jìn)行編碼，并把編碼后的碼字存儲(chǔ)。哈弗曼樹(shù)的描述如下：classHuffmanpublic:HNode*HTree;/哈夫曼樹(shù)HCode*HCodeTable;/哈弗曼編碼表voidCreateHTree(i

4、nta,intn);倉(cāng)U建哈夫曼樹(shù)voidCreateTable(charb,intn);倉(cāng)U建編碼表voidEncoding(char*s,intn);編碼voidDecoding(char*s,char*d,intn);解碼voidDestroyTree(intn);【存儲(chǔ)算法】對(duì)輸入的任意長(zhǎng)度的字符串進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立赫夫曼樹(shù)voidHuffman:CreateHTree(inta,intn)HTree=newHNode2*n-1;for(inti=0;in;i+)HTreei.weight=ai;HTreei.lchild=-1;HTreei.rchild=-1;HT

5、reei.parent=-1;staticintk=0;intbb1000;staticintx;staticinty;intmin=1000;for(intjj=0;jjn;jj+)/創(chuàng)建第n+1個(gè)節(jié)點(diǎn)if(HTreejj.weightmin)min=HTreejj.weight;x=jj;bbk=x;k+;int_min=1000;for(intjjj=0;jjjn;jjj+)intkk;for(kk=0;kk=HTreex.weight)if(HTreejjj.weight_min)_min=HTreejjj.weight;y=jjj;bbk=y;k+;HTreex.parent=HTr

6、eey.parent=n;HTreen.weight=HTreex.weight+HTreey.weight;HTreen.lchild=x;HTreen.rchild=y;HTreen.parent=-1;for(intii=n+1;ii2*n-1;ii+)/開(kāi)始創(chuàng)建哈夫曼樹(shù)，min=1000;for(intjj=0;jjii;jj+)intkk;for(kk=0;kk=HTreey.weight)/maywrongif(HTreejj.weightmin)min=HTreejj.weight;x=jj;bbk=x;k+;int_min=1000;for(intjjj=0;jjjii;jjj

7、+)intkk;for(kk=0;kk=HTreex.weight)if(HTreejjj.weight_min)_min=HTreejjj.weight;y=jjj;bbk=y;k+;HTreex.parent=HTreey.parent=ii;HTreeii.weight=HTreex.weight+HTreey.weight;HTreeii.lchild=x;HTreeii.rchild=y;HTreeii.parent=-1;2.1哈夫曼樹(shù)是一棵正則二叉樹(shù)。根據(jù)二叉樹(shù)的性質(zhì)，一棵有個(gè)葉子的哈夫曼樹(shù)共有個(gè)結(jié)點(diǎn)，可以用一個(gè)大小為的一維數(shù)組存放哈夫曼樹(shù)的各個(gè)結(jié)點(diǎn)。由于每個(gè)結(jié)點(diǎn)同時(shí)還包含其雙親

8、信息和孩子結(jié)點(diǎn)的信息，我們可以用一個(gè)靜態(tài)三叉鏈表來(lái)存儲(chǔ)哈夫曼樹(shù)。初始化哈夫曼樹(shù)】創(chuàng)建好的哈夫曼樹(shù)】2.2【編碼】采用自下向上的方式生成編碼表，由于每一個(gè)字符對(duì)應(yīng)一個(gè)哈夫曼樹(shù)的葉子結(jié)點(diǎn)，因此，創(chuàng)建編碼表從葉子結(jié)點(diǎn)開(kāi)始，若該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左分支則編碼1；然后將該結(jié)點(diǎn)的父結(jié)點(diǎn)當(dāng)成葉子節(jié)點(diǎn)來(lái)分析，直到根結(jié)點(diǎn)為止，一個(gè)字符編碼結(jié)束。生成編碼表的描述如下：voidHuffman:CreateTable(charb,intn)HCodeTable=newHCoden;for(inti=0;in;i+)HCodeTablei.data=bi;/生成編碼表intchild=i;intparent=HTreei

9、.parent;intk=0;while(parent!=-1)if(child=HTreeparent.lchild)HCodeTablei.codek=0;左孩子標(biāo)0elseHCodeTablei.codek=T;右孩子標(biāo)1k+;child=parent;parent=HTreechild.parent;HCodeTablei.codek=0;char*b=newchark;for(intj=0;jk;j+)bj=HCodeTablei.codek-1-j;/coutbj;for(intjj=0;jjk;jj+)HCodeTablei.codejj=bjj;【解碼】從哈夫曼樹(shù)的根結(jié)點(diǎn)開(kāi)始，根據(jù)每一位是0還是1，確定選擇左分支還是右分支直到到達(dá)葉子結(jié)點(diǎn)為止，一個(gè)字符編碼結(jié)束。然后再?gòu)母Y(jié)點(diǎn)開(kāi)始下一個(gè)字符的編碼。解碼算法的描述如下：voidHuffman:Decoding(char*s,char*d,intn)/s為編碼串，while(*s!=0)intparent=2*n-1-1;/根節(jié)點(diǎn)在HTree中的下標(biāo)；while(HTreeparent.lchild!=-1)if(*s=0)parent=HTree