word數(shù) 據(jù) 結(jié) 構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：哈夫曼樹(shù)學(xué)生：袁普班 級(jí)：2013211125班班序號(hào)：14號(hào)學(xué) 號(hào)：2013210681日 期：2014年12月1. 實(shí)驗(yàn)?zāi)康暮腿堇枚鏄?shù)結(jié)構(gòu)實(shí)現(xiàn)哈夫曼編/解碼器。根本要求：1、 初始化(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ù)編碼表對(duì)輸入的字符串進(jìn)展編碼，并將編碼后的字符串輸出。4、 譯碼(Decoding)：利用已經(jīng)建好的哈夫曼樹(shù)對(duì)編碼后的字符串進(jìn)展譯碼，并輸出譯碼結(jié)果。5、 打印(Print)：以直觀的方式打印哈夫曼樹(shù)選作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è)字符出現(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ǔ)樹(shù)的結(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 code100; /字符對(duì)應(yīng)的哈夫曼編碼; 2.2 程序流程 輸入字符串統(tǒng)計(jì)出現(xiàn)的字符種類和次數(shù)，構(gòu)建權(quán)值數(shù)組，初始化樹(shù)結(jié)點(diǎn)與編碼表根據(jù)哈夫曼構(gòu)建規(guī)如此構(gòu)建哈夫曼樹(shù)，根據(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ì)出現(xiàn)次數(shù)，構(gòu)建權(quán)值數(shù)組， 3 算法空間、時(shí)間復(fù)雜度分析：空間復(fù)雜度O1，要遍歷一遍字符串，時(shí)間復(fù)雜度On 4 代碼邏輯：leaf=0; /初始化葉子節(jié)點(diǎn)個(gè)數(shù)int i,j=0; int s128=0; 用于存儲(chǔ)出現(xiàn)的字符 for(i=0;stri!='0'i+) 遍歷輸入的字符串s(int)stri+; 統(tǒng)計(jì)每個(gè)字符出現(xiàn)次數(shù)for(i=0;i<128;i+) if(si!=0) dataj=(char)i; 給編碼表的字符賦值weightj=si; 構(gòu)建權(quán)值數(shù)組j+; leaf=j; /葉子節(jié)點(diǎn)個(gè)數(shù)即字符個(gè)數(shù)for(i=0;i<leaf;i+) cout<<datai<<"的權(quán)值為："<<weighti<<endl;算法2：void Init(); 1 算法功能：構(gòu)建哈弗曼樹(shù) 2 算法根本思想：根據(jù)哈夫曼樹(shù)構(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ù)雜度On，空間復(fù)雜度O1 4 代碼邏輯HTree=new HNode2*leaf-1; n2=n0-1，一共需要2n-1個(gè)結(jié)點(diǎn)空間 for(int i=0;i<leaf;i+) HTreei.weight=weighti; 給每個(gè)結(jié)點(diǎn)附權(quán)值 HTreei.lchild=-1; 初始化左右孩子和父節(jié)點(diǎn)，都為-1 HTreei.rchild=-1; HTreei.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) HTreex.parent=i; 父節(jié)點(diǎn)設(shè)置為新建立的結(jié)點(diǎn) HTreey.parent=i; HTreei.weight=HTreex.weight+HTreey.weight; 父節(jié)點(diǎn)權(quán)值為兩個(gè)相加 HTreei.lchild=x; 使父節(jié)點(diǎn)指向這兩個(gè)孩子結(jié)點(diǎn) HTreei.rchild=y; HTreei.parent=-1; 父節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為-1 算法3：void Selectmin(HNode*hTree,int 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<n;i+) /n為現(xiàn)在有的結(jié)點(diǎn)個(gè)數(shù)，是個(gè)變化值,會(huì)有相加后的新權(quán)值參加 if(hTreei.parent=-1) /父節(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)前位置開(kāi)始查找for(;i<n;i+)if(hTreei.parent=-1) i2=i; 記錄第二個(gè)沒(méi)選擇過(guò)的結(jié)點(diǎn)編號(hào)break; if(hTreei1.weight>hTreei2.weight) 進(jìn)展比擬，使I1為最小的，I2為第二小的int j=0;j=i2;i2=i1;i1=j; i+;for(;i<n;i+) 將I1 I2 與后面的結(jié)點(diǎn)進(jìn)展比擬if(hTreei.parent=-1&&hTreei.weight<hTreei1.weight) 如果結(jié)點(diǎn)小于I1i2=i1; 使I2=I1 I1=新結(jié)點(diǎn)i1=i; else if(hTreei.parent=-1&&hTreei.weight<hTreei2.weight) I1新結(jié)點(diǎn)I2，使I2為新節(jié)點(diǎn)i2=i; 算法4：void CreateTable(); 1 算法功能：對(duì)出現(xiàn)的字符進(jìn)展編碼 2 算法根本思想：根據(jù)字符在哈夫曼樹(shù)中的位置，從下到上編碼，是左孩子編0，右孩子編1 3 算法空間、時(shí)間復(fù)雜度分析：空間復(fù)雜度O(1)，要遍歷data數(shù)組，時(shí)間復(fù)雜度0(N) 4 代碼邏輯HCodeTable=new HCodeleaf; 新建編碼結(jié)點(diǎn)，個(gè)數(shù)為葉子節(jié)點(diǎn)個(gè)數(shù) for(int i=0;i<leaf;i+) HCodeTablei.data=datai; int child=i; 初始化要編碼的結(jié)點(diǎn)的位置 int parent=HTreei.parent; 初始化父結(jié)點(diǎn) int k=0; /統(tǒng)計(jì)編碼個(gè)數(shù) while(parent!=-1) if(child=HTreeparent.lchild) HCodeTablei.codek='0' /左孩子標(biāo)0 else HCodeTablei.codek='1' /右孩子標(biāo)1 k+; child=parent; 孩子結(jié)點(diǎn)上移 parent=HTreechild.parent; 父節(jié)點(diǎn)也上移 HCodeTablei.codek='0' /將編碼反向 char code100; for(int u=0;u<k;u+) codeu=HCodeTablei.codek-u-1; for(int u=0;u<k;u+) HCodeTablei.codeu=codeu; cout<<datai<<"的哈夫曼編碼為：" cout<<HCodeTablei.code<<endl; length3i=k; /每一個(gè)字符編碼的長(zhǎng)度，為求編碼總長(zhǎng)度做準(zhǔn)備 算法5：void Encoding(); 1 算法功能：對(duì)輸入的字符串進(jìn)展編碼 2 算法根本思想：找到每個(gè)字符對(duì)應(yīng)的編碼，將編碼按順序輸出 3 算法空間、時(shí)間復(fù)雜度分析：空間復(fù)雜度O(1),時(shí)間復(fù)雜度0n 4 代碼邏輯 cout<<endl<<"輸入的字符串轉(zhuǎn)化為哈夫曼編碼為:"<<endl; for (int i=0;stri!='0'i+) 遍歷輸入的每一個(gè)字符 for(int j=0;j<leaf;j+) if(stri=HCodeTablej.data) 找到字符對(duì)應(yīng)的編碼 s1=s1+HCodeTablej.code; 將所有編碼按順序加起來(lái) cout<<HCodeTablej.code; 輸出編碼 cout<<endl;算法6：void Decoding(); 1 算法功能：對(duì)編碼串進(jìn)展解碼 2 算法根本思想：找到每段編碼對(duì)應(yīng)的字符，輸出字符 3 算法空間、時(shí)間復(fù)雜度分析：時(shí)間復(fù)雜度0(N)，空間復(fù)雜度01 4 代碼邏輯可用偽代碼描述 cout<<"解碼后的字符串為: "<<endl; char *s = const_cast<char*>(s1.c_str(); 將編碼字符串轉(zhuǎn)化為char while(*s!='0') int parent=2*leaf-2; 父節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn) while(HTreeparent.lchild!=-1) /還有左子樹(shù)，不可能是葉子節(jié)點(diǎn) if(*s='0') 編碼為0，為左孩子 parent=HTreeparent.lchild; else parent=HTreeparent.rchild; 編碼為1，為右孩子 s+; cout<<HCodeTableparent.data; 輸出字符 cout<<endl;注意分析程序的時(shí)間復(fù)雜度、存申請(qǐng)和釋放，以與算法思想的表現(xiàn)。2.4 其他在此次試驗(yàn)中使用了類和STL中的string，使用string可以方便的將單個(gè)字符的編碼加起來(lái)成為總的編碼后的數(shù)值，再利用STL中的轉(zhuǎn)化函數(shù)可以直接將string轉(zhuǎn)化為char，方便進(jìn)展解碼工作?？偠灾?，使用STL使得編碼大大的簡(jiǎn)潔了。3. 程序運(yùn)行結(jié)果分析調(diào)試過(guò)程中遇到的問(wèn)題主要是執(zhí)行時(shí)有存錯(cuò)誤，檢查后發(fā)現(xiàn)是數(shù)組有越界現(xiàn)象，這提醒我在編寫(xiě)時(shí)一定要仔細(xì)，特別是在for循環(huán)條件上一定要注意圍總結(jié)首先在輸入字符串時(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)建哈夫曼樹(shù)，尋找兩個(gè)最小權(quán)值的思想主要是通過(guò)一個(gè)個(gè)的比擬來(lái)找到最小值，而且注意形參要用引用。通過(guò)此次實(shí)驗(yàn)我體會(huì)到了stl的優(yōu)越性。還有就是編碼時(shí)要注意數(shù)組的大小。再者就是有問(wèn)題時(shí)可以試著去網(wǎng)上查詢答案。12 / 12