北郵 大數(shù)據(jù)結(jié)構(gòu) 哈夫曼樹報(bào)告材料

《北郵 大數(shù)據(jù)結(jié)構(gòu) 哈夫曼樹報(bào)告材料》由會(huì)員分享，可在線閱讀，更多相關(guān)《北郵 大數(shù)據(jù)結(jié)構(gòu) 哈夫曼樹報(bào)告材料（12頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、word 數(shù) 據(jù) 結(jié) 構(gòu) 實(shí) 驗(yàn) 報(bào) 告 實(shí)驗(yàn)名稱：哈夫曼樹 學(xué)生：袁普 班 級(jí)：2013211125班 班序號(hào)：14號(hào) 學(xué) 號(hào)：2013210681 日 期：2014年12月 1. 實(shí)驗(yàn)?zāi)康暮腿? 利用二叉樹結(jié)構(gòu)實(shí)現(xiàn)哈夫曼編/解碼器。 基本要求： 1、 初始化(Init)：能夠?qū)斎氲娜我忾L(zhǎng)度的字符串 s進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)每個(gè)字符的頻度， 并建立哈夫曼樹 2、 建立編碼表(CreateTable)：利用已經(jīng)建好的哈夫曼樹進(jìn)行編碼，并將每個(gè)字符的編碼輸出。 3、 編碼(Encoding)：根據(jù)編碼表對(duì)輸入的字符串進(jìn)行編

2、碼，并將編碼后的字符串輸 出。 4、 譯碼(Decoding)：利用已經(jīng)建好的哈夫曼樹對(duì)編碼后的字符串進(jìn)行譯碼，并輸出 譯碼結(jié)果。 5、 打印(Print)：以直觀的方式打印哈夫曼樹（選作） 6、 計(jì)算輸入的字符串編碼前和編碼后的長(zhǎng)度，并進(jìn)行分析，討論赫夫曼編碼的壓 縮效果。 7、 可采用二進(jìn)制編碼方式（選作） 測(cè)試數(shù)據(jù)： I love data Structure, I love puter。I will try my best to study data Structure. 提示： 1、用戶界面可以設(shè)計(jì)為“菜單”方式：能夠進(jìn)行交互。 2、根據(jù)輸入的字符串中每個(gè)字符

3、出現(xiàn)的次數(shù)統(tǒng)計(jì)頻度，對(duì)沒(méi)有出現(xiàn)的字符一律不用編碼 2. 程序分析 2.1 存儲(chǔ)結(jié)構(gòu) 用struct結(jié)構(gòu)類型來(lái)實(shí)現(xiàn)存儲(chǔ) 樹的結(jié)點(diǎn)類型 struct HNode { int weight; //權(quán)值 int parent; //父節(jié)點(diǎn) int lchild; //左孩子 int rchild; //右孩子 }; struct HCode //實(shí)現(xiàn)編碼的結(jié)構(gòu)類型 { char data; //被編碼的字符 char code[100]; //字符對(duì)應(yīng)的

4、哈夫曼編碼 }; 2.2 程序流程 輸入字符串 統(tǒng)計(jì)出現(xiàn)的字符種類和次數(shù)，構(gòu)建權(quán)值數(shù)組，初始化樹結(jié)點(diǎn)與編碼表 根據(jù)哈夫曼構(gòu)建規(guī)則構(gòu)建哈夫曼樹，根據(jù)編碼規(guī)則對(duì)出現(xiàn)字符進(jìn)行編碼，構(gòu)建編碼表 將輸入的字符挨個(gè)編碼 對(duì)編碼后的字符進(jìn)行解碼 分析存儲(chǔ)大小 2.3 關(guān)鍵算法分析 算法1：void Huffman::Count() [1] 算法功能：對(duì)出現(xiàn)字符的和出現(xiàn)字符的統(tǒng)計(jì)，構(gòu)建權(quán)值結(jié)點(diǎn)，初始化編碼表 [2] 算法基本思想：對(duì)輸入字符一個(gè)一個(gè)的統(tǒng)計(jì)，并統(tǒng)計(jì)

5、出現(xiàn)次數(shù)，構(gòu)建權(quán)值數(shù)組， [3] 算法空間、時(shí)間復(fù)雜度分析：空間復(fù)雜度O（1），要遍歷一遍字符串，時(shí)間復(fù)雜度O（n） [4] 代碼邏輯： leaf=0; //初始化葉子節(jié)點(diǎn)個(gè)數(shù) int i,j=0; int s[128]={0}; 用于存儲(chǔ)出現(xiàn)的字符 for(i=0;str[i]!='\0';i++) 遍歷輸入的字符串 s[(int)str[i]]++; 統(tǒng)計(jì)每個(gè)字符出現(xiàn)次數(shù) for(i=0;i<128;i++) if(s[i]!=0) { da

6、ta[j]=(char)i; 給編碼表的字符賦值 weight[j]=s[i]; 構(gòu)建權(quán)值數(shù)組 j++; } leaf=j; //葉子節(jié)點(diǎn)個(gè)數(shù)即字符個(gè)數(shù) for(i=0;i

7、夫曼樹構(gòu)建要求，選取權(quán)值最小的兩個(gè)結(jié)點(diǎn)結(jié)合，新結(jié)點(diǎn)加入數(shù)組，再繼續(xù)選取最小的兩個(gè)結(jié)點(diǎn)繼續(xù)構(gòu)建。 [3] 算法空間、時(shí)間復(fù)雜度分析：取決于葉子節(jié)點(diǎn)個(gè)數(shù)，時(shí)間復(fù)雜度O（n），空間復(fù)雜度O（1） [4] 代碼邏輯 HTree=new HNode[2*leaf-1]; n2=n0-1，一共需要2n-1個(gè)結(jié)點(diǎn)空間 for(int i=0;i

8、ild=-1; 初始化左右孩子和父節(jié)點(diǎn)，都為-1 HTree[i].rchild=-1; HTree[i].parent=-1; } int x,y; //用于記錄兩個(gè)最小權(quán)值 for(int i=leaf;i<2*leaf-1;i++) { Selectmin(HTree,i,x,y); 選出兩個(gè)最小權(quán)值的結(jié)點(diǎn) HTree[x].parent=i;

9、 父節(jié)點(diǎn)設(shè)置為新建立的結(jié)點(diǎn) HTree[y].parent=i; HTree[i].weight=HTree[x].weight+HTree[y].weight; 父節(jié)點(diǎn)權(quán)值為兩個(gè)相加 HTree[i].lchild=x; 使父節(jié)點(diǎn)指向這兩個(gè)孩子結(jié)點(diǎn) HTree[i].rchild=y; HTree[i].parent=-1; 父節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為-1 } 算法3：void Selectmin(HNode*hTree,int

10、n,int&i1,int &i2); [1] 算法功能：從現(xiàn)有的結(jié)點(diǎn)中選擇出兩個(gè)最小的結(jié)點(diǎn)，返回其位置 [2] 算法基本思想：先選出兩個(gè)沒(méi)有構(gòu)建的結(jié)點(diǎn)，然后向后依次比較，篩選出最小的兩個(gè)結(jié)點(diǎn) [3] 算法空間、時(shí)間復(fù)雜度分析：空間復(fù)雜度O(1)，要遍歷所有結(jié)點(diǎn)，時(shí)間復(fù) 雜度O(N) [4] 代碼邏輯 int i; for(i=0;i

11、 //父節(jié)點(diǎn)不是-1意味著這個(gè)結(jié)點(diǎn)還沒(méi)有被選擇過(guò) { i1=i; 記錄結(jié)點(diǎn)位置 break; } } i++; //執(zhí)行一遍for循環(huán)就加1，意為下次查找從當(dāng)前位置開始查找 for(;ihTree[i2].weight) 進(jìn)行比較，使I1為最小

12、的，I2為第二小的 { int j=0; j=i2; i2=i1; i1=j; } i++; for(;i

13、ght

14、=new HCode[leaf]; 新建編碼結(jié)點(diǎn)，個(gè)數(shù)為葉子節(jié)點(diǎn)個(gè)數(shù) for(int i=0;i

15、 while(parent!=-1) { if(child==HTree[parent].lchild) HCodeTable[i].code[k]='0'; //左孩子標(biāo)‘0’ else HCodeTable[i].code[k]='1'; //右孩子標(biāo)‘1’ k++; child=parent; 孩子結(jié)點(diǎn)上移

16、 parent=HTree[child].parent; 父節(jié)點(diǎn)也上移 } HCodeTable[i].code[k]='\0'; //將編碼反向 char code[100]; for(int u=0;u

17、[u]; cout<

18、(1),時(shí)間復(fù)雜度0（n） [4] 代碼邏輯 cout<

19、 cout<

20、s = const_cast(s1.c_str()); 將編碼字符串轉(zhuǎn)化為char while(*s!='\0') { int parent=2*leaf-2; 父節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn) while(HTree[parent].lchild!=-1) //還有左子樹，不可能是葉子節(jié)點(diǎn) { if(*s=='0') 編碼為0，為左孩子

21、 parent=HTree[parent].lchild; else parent=HTree[parent].rchild; 編碼為1，為右孩子 s++; } cout<

22、以方便的將單個(gè)字符的編碼加起來(lái)成為總的編碼后的數(shù)值，再利用STL中的轉(zhuǎn)化函數(shù)可以直接將string轉(zhuǎn)化為char，方便進(jìn)行解碼工作?？偠灾褂肧TL使得編碼大大的簡(jiǎn)潔了。 3. 程序運(yùn)行結(jié)果分析 調(diào)試過(guò)程中遇到的問(wèn)題主要是執(zhí)行時(shí)有存錯(cuò)誤，檢查后發(fā)現(xiàn)是數(shù)組有越界現(xiàn)象，這提醒我在編寫時(shí)一定要仔細(xì)，特別是在for循環(huán)條件上一定要注意圍 總結(jié) 4.1實(shí)驗(yàn)的難點(diǎn)和關(guān)鍵點(diǎn) 首先在輸入字符串時(shí)我發(fā)現(xiàn)直接用cin無(wú)法輸入空格，在上網(wǎng)查詢后找到了getline函數(shù)解決了這個(gè)問(wèn)題。然后還有就是如何存儲(chǔ)編碼后總的那個(gè)字符串，因?yàn)槊恳粋€(gè)字符編碼的長(zhǎng)度不定，無(wú)法用char數(shù)組來(lái)存儲(chǔ)，于是用了string的相加函數(shù)來(lái)將所有編碼加起來(lái)。最后由于在解碼時(shí)要用char數(shù)組，又上網(wǎng)查詢到了string轉(zhuǎn)化成char的函數(shù)解決了這個(gè)問(wèn)題，實(shí)驗(yàn)難點(diǎn)也在于如何找到兩個(gè)最小權(quán)值來(lái)構(gòu)建哈夫曼樹，尋找兩個(gè)最小權(quán)值的思想主要是通過(guò)一個(gè)個(gè)的比較來(lái)找到最小值，而且注意形參要用引用。 4.2心得體會(huì) 通過(guò)此次實(shí)驗(yàn)我體會(huì)到了stl的優(yōu)越性。還有就是編碼時(shí)要注意數(shù)組的大小。再者就是有問(wèn)題時(shí)可以試著去網(wǎng)上查詢答案。 12 / 12