北京郵電大學(xué)信通院數(shù)據(jù)結(jié)構(gòu)試驗(yàn)三-哈夫曼樹試驗(yàn)報(bào)告

1、2009級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)三一一哈夫曼編/解碼器的實(shí)現(xiàn)學(xué)生姓名：陳聰捷日 期：2010年11月28日.實(shí)驗(yàn)要求一、實(shí)驗(yàn)?zāi)康模毫私夤蚵鼧涞乃枷牒拖嚓P(guān)概念；二、實(shí)驗(yàn)內(nèi)容：利用二叉樹結(jié)構(gòu)實(shí)現(xiàn)哈夫曼編 /解碼器.初始化：能夠?qū)斎氲娜我忾L(zhǎng)度的字符串s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度，并建立哈夫曼樹。.建立編碼表：利用已經(jīng)建好的哈夫曼樹進(jìn)行編碼，并將每個(gè)字符的編碼輸出。.編碼：根據(jù)編碼表對(duì)輸入的字符串進(jìn)行編碼，并將編碼后的字符串輸出。.譯碼：利用已經(jīng)建好的哈夫曼樹對(duì)編碼后的字符串進(jìn)行譯碼，并輸出譯碼結(jié)果。.打?。阂灾庇^的方式打印哈夫曼樹。.計(jì)算輸入的字符串編碼前和編碼后的長(zhǎng)度，并進(jìn)行分析，討

2、論哈夫曼編碼的壓縮效果。.用戶界面可以設(shè)計(jì)成“菜單”方式，能進(jìn)行交互，根據(jù)輸入的字符串中每個(gè)字符出現(xiàn) 的次數(shù)統(tǒng)計(jì)頻度，對(duì)沒有出現(xiàn)的字符一律不用編碼。.程序分析存儲(chǔ)結(jié)構(gòu)二叉樹template class BiTreepublic:ThOataatccharThharcdBeeree師Tnsigiined int count*T p%enbous edvoi,d NHuemwee:Input)算法偽代碼：.初始化鏈表的頭結(jié)點(diǎn).獲得輸入字符串的第一個(gè)字符，并將其插入到鏈表尾部，n=1（n記錄的是鏈表中字符的個(gè)數(shù)）.從字符串第2個(gè)字符開始，逐個(gè)取出字符串中的字符將當(dāng)前取出的字符與鏈表中已經(jīng)存在的字符逐

3、個(gè)比較，如果當(dāng)前取出的字符與鏈表中已經(jīng)存在的某個(gè)字符相同，則鏈表中該字符的權(quán)值加1。如果當(dāng)前取出的字符與鏈表中已經(jīng)存在的字符都不相同，則將其加入到鏈表尾部，同時(shí)n+ =n(tSize記錄鏈表中字符總數(shù)，即哈夫曼樹中葉子節(jié)點(diǎn)總數(shù)).創(chuàng)建哈夫曼樹 6.銷毀鏈表 源代碼：void HuffmanTree:Init(string Input) (Node *front=new Node;建哈夫曼樹(void HuffmanTree:CreateCodeTable(Node *p)算法偽代碼：.創(chuàng)建一個(gè)長(zhǎng)度為 2*tSize-1的三叉鏈表.將存儲(chǔ)字符及其權(quán)值的鏈表中的字符逐個(gè)寫入三叉鏈表的前tSize個(gè)

4、結(jié)點(diǎn)的data域，并將對(duì)應(yīng)結(jié)點(diǎn)的孩子域和雙親域賦為空.從三叉鏈表的第tSize個(gè)結(jié)點(diǎn)開始，i=tSize從存儲(chǔ)字符及其權(quán)值的鏈表中取出兩個(gè)權(quán)值最小的結(jié)點(diǎn)x,y,記錄其下標(biāo) x,y。將下標(biāo)為x和y的哈夫曼樹的結(jié)點(diǎn)的雙親設(shè)置為第i個(gè)結(jié)點(diǎn)將下標(biāo)為x的結(jié)點(diǎn)設(shè)置為i結(jié)點(diǎn)的左孩子，將下標(biāo)為y的結(jié)點(diǎn)設(shè)置為i 結(jié)點(diǎn)的右孩子，i結(jié)點(diǎn)的權(quán)值為x結(jié)點(diǎn)的權(quán)值加上y結(jié)點(diǎn)的權(quán)值，i結(jié) 點(diǎn)的雙親設(shè)置為空.根據(jù)哈夫曼樹創(chuàng)建編碼表源代碼：void HuffmanTree:CreateHTree(Node *p,int n) (root= new BiNode2*n-1;ata=front-count;rooti.lchild=

5、-1;rooti.rchild=-1;rooti.parent=-1;front=front-next; front=p; int New1,New2; for(i=n;icharacter; arent;odek=0; k+; while(parent!=-1) child) odek=0; else HCodeTablei.codek=1; k+; child=parent; parent=rootchild.parent; HCodeTablei.codek=0; Reverse(HCodeTablei.code); ata HCodeTablei.codeendl; 時(shí)間復(fù)雜度： 需要

6、遍歷哈夫曼樹獲取編碼，時(shí)間復(fù)雜度為O (n2)4.選擇兩個(gè)最小權(quán)值的函數(shù)( void HuffmanTree二SelectMin(int &New1,int &New2,int begin,int end) 算法偽代碼： 1.從下標(biāo)為begin的結(jié)點(diǎn)開始，尋找第一個(gè)沒用過的結(jié)點(diǎn) 2.遍歷哈夫曼樹中從下標(biāo)為begin到下標(biāo)為end的結(jié)點(diǎn)序列，尋找沒用過的同時(shí)權(quán)值又是最小的結(jié)點(diǎn)。 3.暫時(shí)改變找到的權(quán)值最小結(jié)點(diǎn)的雙親域，防止第2次找到相同的結(jié)點(diǎn)。4.將權(quán)值最小結(jié)點(diǎn)的下標(biāo)記錄下來。 5.重復(fù)步驟14,找到第2個(gè)權(quán)值最小的結(jié)點(diǎn) 源代碼：void HuffmanTree:SelectMin(int &N

7、ew1,int &New2,int begin,int end) ( int min; for(int j=0；j2；j+)arent=-1)ata;sign=i;break;)for(i=begin;irooti.data) ( min=rooti.data; sign=i; ) ) )rootsign.parent=0;將字符串倒序的函數(shù)(void HuffmanTree:Reverse(char *pch) 算法偽代碼：.得到字符串的長(zhǎng)度.初始化兩個(gè)記錄下標(biāo)的變量，一個(gè)為字符串開頭字符所在的下標(biāo)i,另一個(gè)為字符串結(jié)尾字符所在的下標(biāo)j.將下標(biāo)為i和j的字符交換. i+,j -時(shí)間復(fù)雜度：時(shí)

8、間復(fù)雜度為O (n)6.編碼函數(shù)(void HuffmanTree:Encode(string &s,string &d) 算法偽代碼：.從s開頭的字符開始，逐一對(duì)s中的字符進(jìn)行編碼.在編碼表中查找與當(dāng)前字符對(duì)應(yīng)的字符.如果找到了與當(dāng)前字符對(duì)應(yīng)的編碼表中的字符，將其編碼追加到解碼串的末 尾。.重復(fù)以上步驟，直到所有待編碼串中的字符都編碼完畢.輸出編碼后的字符串 源代碼：void HuffmanTree:Encode(string &s,string &d) ( for(int j=0;j();j+)ata)(HCodeTablei.code); 碼函數(shù) (void HuffmanTree:De

9、code(string &s,string &d) 算法偽代碼：.得到指向哈夫曼樹的根結(jié)點(diǎn)的指針和指向待解碼串中的第1個(gè)字符的指針.逐個(gè)讀取待解碼串中的字符，若為0,則指向哈夫曼樹當(dāng)前結(jié)點(diǎn)的指針指向當(dāng)前結(jié)點(diǎn)的左孩子，若為 1,則指向當(dāng)前結(jié)點(diǎn)的右孩子.指向待解碼串的指針指向解碼串中的下一個(gè)字符，直到指向哈夫曼樹結(jié)點(diǎn) 的指針的孩子結(jié)點(diǎn)為空.如果哈夫曼樹只有一個(gè)葉子結(jié)點(diǎn)，直接將待解碼串中的編碼轉(zhuǎn)換為對(duì)應(yīng)的 字符.如果指向哈夫曼樹結(jié)點(diǎn)的指針的孩子結(jié)點(diǎn)已經(jīng)為空，則將葉子結(jié)點(diǎn)下標(biāo)對(duì) 應(yīng)的字符追加到解碼串中。.輸出解碼串源代碼：void HuffmanTree:Decode(string &s,string

10、 &d) (for(int i=0;i();)(child!=-1) child;child;ata);計(jì)算 哈夫曼編碼的壓縮比(voidint parent=2*tSize-1-1; elsei+;if(tSize=1)HuffmanTree:Calculate(string s1,string s2)算法偽代碼：.獲得編碼前字符串的長(zhǎng)度，即其占用的字節(jié)數(shù).獲得編碼后的字符串的長(zhǎng)度，將其除以8然后向上取整，得到其占用的字節(jié)數(shù).壓縮比將兩個(gè)相除源代碼：void HuffmanTree:Calculate(string s1,string s2)(int cal1=();int cal2=();

11、cal2=ceill(float)cal2/8);打印哈夫曼樹 (voidHuffmanTree:PrintTree(int TreeNode,int layer) )算法偽代碼：.如果待打印結(jié)點(diǎn)為空，則返回.遞歸調(diào)用函數(shù)打印當(dāng)前結(jié)點(diǎn)的右子樹.根據(jù)當(dāng)前結(jié)點(diǎn)所在的層次確定其前面要輸出多少空格，先輸出空格，在打 印當(dāng)前結(jié)點(diǎn)的權(quán)值.遞歸調(diào)用函數(shù)打印當(dāng)前結(jié)點(diǎn)的左子樹源代碼：void HuffmanTree:PrintTree(int TreeNode,int layer)(if(TreeNode=-1)child,layer+1); ataendl;child,layer+1);菜單函數(shù)(void H

12、uffmanTree:Menu()算法偽代碼：.逐一讀取鍵盤緩存區(qū)中的字符，并將它們逐一追加到記錄輸入字符串的 string變量中，直到讀到回車輸入符為止.刪除string變量末尾的回車輸入符.利用string變量創(chuàng)建哈夫曼樹，初始化編碼表。.直觀打印哈夫曼樹.對(duì)輸入的字符串進(jìn)行編碼.對(duì)編碼后的字符串進(jìn)行解碼.計(jì)算編碼前后的壓縮比并輸出源代碼：void HuffmanTree:Menu()(cout請(qǐng)輸入你要編碼的文本，按回車鍵確定輸入endl;string Input;char letter;do于題目要求能輸入任意長(zhǎng)的字符串，所以本程序采用了 string變量來記錄輸入的字符串，并采用 s

13、tring類的類成員函數(shù)來完成 各項(xiàng)任務(wù).打印哈夫曼樹時(shí)采用了遞歸函數(shù)，且采用了凹凸表的形式打印哈夫曼樹。.為了輸入空格，輸入時(shí)采取逐個(gè)字符輸入的方式3.程序運(yùn)行結(jié)果主函數(shù)流程圖:結(jié)束運(yùn)行結(jié)果:請(qǐng)輸入傷要編制的文本K按回車鍵確定輸入 I loue data st met Lire, I loue camputep. 1 will try1 叫 best to study lata struc tu re.編石裱為：I 11B00111 1 000t n 0016 v EJHW1 e 0111 d 11M01 a 0011 t S 0100 r 1310 u 1011 c UB10 ,B1100

14、Q m 01010 p 11gMi .R1R11 u 011010 i nilA11 y 11011 b 06B00直觀打印哈夫曼樹IS271250612 G231183 GIQ21182428433484is47231編43后的字符串為阻n0闌1豳1面目硼1目阻110曲“u工m 隨1日01日ioignuswi日阻口iu日H01 itmtinii（Miiiubt）iaimiiii m 的身 i mhihi 時(shí)on11110001110110100110110001000111110010161101111101010110111110000001110100100111Q10Q111Q1Q11帆碼后的字符串i laue datra si-ruic-tLive, I Iovb computrei* I