哈夫曼樹實驗報告

北京郵電大學信息與通信工程學院第9頁北京郵電大學電信工程學院第1頁2006級數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗三——樹學生姓名：王璇班級：2009211118班內(nèi)序號：29學號：09210543日期：2010年12月20日1．實驗要求利用二叉樹結(jié)構(gòu)實現(xiàn)哈夫曼編/解碼器基本要求如下:初始化:能夠?qū)斎氲娜我忾L度的字符串s進行統(tǒng)計,統(tǒng)計每個字符的頻率,并建立哈夫曼樹.建立編碼表:利用已經(jīng)建好的哈夫曼樹進行編碼,并將每個字符的編碼輸出.編碼:根據(jù)編碼表對輸入的字符串進行編碼,并將編碼后的字符串輸出.編碼:利用已經(jīng)建好的哈夫曼樹對編碼后的字符串進行譯碼,并輸出譯碼結(jié)果.計算輸入的字符串編碼前和編碼后的長度,并進行分析,討論哈夫曼編碼的壓縮效果.2.程序分析哈夫曼樹類里的成員函數(shù)聲明如下：classHuffman{private: HNode*HTree;//哈夫曼樹 HCode*HCodeTable;//哈夫曼編碼表 intnum; charaftercode[1000]; intcountcode;public: voidCreateHTree(inta[],intn);//創(chuàng)建哈夫曼樹 voidCreateCodeTable(charb[]);//創(chuàng)建編碼表 voidEncode(char*d);//編碼 voidDecode(char*d);//解碼 ~Huffman(); voidSelectMin(int&x,int&y,intend);//找最小值 voidReverse(char*code);//倒序 intCountcode();//計算編碼長};2.1存儲結(jié)構(gòu)采用數(shù)組儲存的方法:建立的哈夫曼樹由結(jié)點HNode數(shù)組組成,每個結(jié)點包括結(jié)點權(quán)值,雙親指針,左右孩子指針.建立的哈夫曼編碼表由結(jié)點HCode數(shù)組組成，每個結(jié)點包括字符值，編碼字符數(shù)組。初始化中，包括兩個數(shù)組，分別儲存輸入語句字符以及統(tǒng)計的每個字符的次數(shù)2.2關(guān)鍵算法分析[內(nèi)容要求]1、關(guān)鍵算法：比如插入、刪除等基本算法的思想，或是約瑟夫問題的基本思想等，要求使用自然語言描述和偽代碼描述，具體可參考書上的偽代碼代碼詳細分析：比如雙鏈表的插入，需要將4句關(guān)鍵代碼寫清楚，并畫出示意圖，可參考書上P69頁圖2-21。關(guān)鍵算法的時間、空間復(fù)雜度關(guān)鍵算法1：統(tǒng)計出現(xiàn)過的字符以及相應(yīng)的次數(shù) Huffmance;charsentence[100];//統(tǒng)計所有出現(xiàn)過的不同字符inttimes[100]={0};//統(tǒng)計相應(yīng)字符出現(xiàn)的次數(shù)charline[100];//輸入的字符串數(shù)組char*afterdecode=newchar[100];//在堆里申請的字符數(shù)組,用來儲存解碼后的字符串charc;cout<<"請輸入語句,以@結(jié)束"<<endl;inti=0;intj=0;intk=0;cin.getline(line,100,'@');//將輸入的字符串存在line數(shù)組里do{//統(tǒng)計函數(shù) c=line[k]; if(c!='\n'&&c!='@'&&c!='\0') {j=0;//j為定義的工作指針 while(sentence[j]!=c&&j<=i)//如果讀取的字符沒有出現(xiàn) j++;//工作指針后移 if(j==i+1)//如果該字符第一次出現(xiàn) { sentence[i]=c;//把這個新的字符儲存在統(tǒng)計字符數(shù)組里 i++;//time的工作指針同樣后移 times[i-1]++;}//相應(yīng)的次數(shù)增加1 else//如果在sentence數(shù)組里找到了已經(jīng)存儲的該字符 times[j]++;//相應(yīng)字符的統(tǒng)計次數(shù)增加1 k++;} elsebreak;}while(k<100&&c!='@');統(tǒng)計函數(shù)的實現(xiàn)圖式如下：設(shè)讀取的新字符為M，在sentence里沒有,初始時i=2MsentenceabCjjj j同時，j后移，i后移times1111ii結(jié)束時，i=j=3；如果插入的字符原本已經(jīng)存在于sentence，則在相應(yīng)的統(tǒng)計次數(shù)上加1，i的位置不變。該段代碼中，由于在循環(huán)中又嵌套了循環(huán)，時間復(fù)雜度約為O（n2）關(guān)鍵算法2：在結(jié)點中比較出兩個最小權(quán)值的結(jié)點，返回。函數(shù)如下：voidHuffman::SelectMin(int&x,int&y,intend){ intj=0; while(HTree[j].parent!=-1) j++; x=j;//先找到一個可以選用的結(jié)點 for(j=end-1;j>=0;j--) { if(HTree[j].parent==-1) x=HTree[j].weight<=HTree[x].weight?j:x;//找到權(quán)值最小的結(jié)點 } HTree[x].parent=0;//標記x結(jié)點不可再選 j=0; while(HTree[j].parent!=-1) j++; y=j;//找到另一個可用的結(jié)點 for(j=end-1;j>=0;j--) { if(HTree[j].parent==-1) y=HTree[j].weight<=HTree[y].weight?j:y;//找到剩下結(jié)點中權(quán)值最小的結(jié)點 }}該段代碼的難點：在這個函數(shù)中，需要修改返回兩個int類型的變量，所以我采用了引用的方法，使直接修改原有變量。另外，在這個函數(shù)中，如果出現(xiàn)兩個結(jié)點權(quán)值相同的情況，由于我采用的是從后往前找的方法，那我返回的一定是這兩個結(jié)點中位置靠前的節(jié)點。否則，如果采用從前往后找的方法，就將返回位置靠后的節(jié)點，與普通的思維方式不同，但是，這里仍然是一棵正確的哈夫曼樹，統(tǒng)計結(jié)果，壓縮效率均相同。也就是說，實際是哈夫曼樹的另一種組成編碼方式。時間復(fù)雜度的計算：每次需要找最小的兩個值，遍歷兩邊，約為O（n），但是，這個函數(shù)需要調(diào)用的次數(shù)與n為正比關(guān)系，所以這個函數(shù)實現(xiàn)起來的話，時間復(fù)雜度約為Ｏ（ｎ２）關(guān)鍵算法３：編碼函數(shù)與解碼函數(shù)編碼函數(shù)的代碼如下：voidHuffman::Encode(char*d)//s為編碼串，d為需要編碼的字符串{ aftercode[0]='\0';／／重要，先把ａｆｔｅｒｃｏｄｅ設(shè)為空的字符數(shù)組 while(*d!='\0') { for(inti=0;i<num;i++) { if(HCodeTable[i].data==*d) strcat(aftercode,HCodeTable[i].code);／／把ｃｏｄｅ復(fù)制到ａｆｔｅｒｃｏｄｅ后面 } d++; } cout<<"該字符串編碼為："<<endl; cout<<aftercode<<endl;}這里采用了自帶的函數(shù)ｓｔｒｃａｔ，實現(xiàn)字符串的復(fù)制，方便簡單。由于在編碼輸入的字符串過程中，每個字符需要一次查找代碼的遍歷，所以該函數(shù)的時間復(fù)雜度約為O（n）。解碼函數(shù)：voidHuffman::Decode(char*d){ inti=0; while(aftercode[i]!='\0') { intparent=2*num-1-1;//根節(jié)點在HTree中的下標 while(HTree[parent].lchild!=-1) { if(aftercode[i]=='0') parent=HTree[parent].lchild;//從根結(jié)點往左右找 else parent=HTree[parent].rchild; i++; } *d=HCodeTable[parent].data; d++; }*d='\0';}解碼查找方式為按樹查找，即每次經(jīng)過樹的一些節(jié)點。從根節(jié)點開始，每次取一位編碼，如果是0，就繼續(xù)找其左孩子，直到找到葉子節(jié)點，即左右孩子為空。如果是1，就繼續(xù)找其右孩子，直到葉子幾點為止，如初相應(yīng)的字符，寫入動態(tài)字符數(shù)組aftercode里。時間復(fù)雜度與編碼實現(xiàn)相同3.程序運行結(jié)果測試條件，每次輸入的字符串數(shù)組不超過100個字符，如果需要超過100個字符，則需要修改相應(yīng)主函數(shù)中定義的規(guī)模：將100改為更大的數(shù)目。charsentence[100];inttimes[100]={0};charline[100];char*afterdecode=newchar[100]；4.總結(jié)調(diào)試中出現(xiàn)的問題和解決：在編碼程序中的語句： strcat(aftercode,HCodeTable[i].code);出現(xiàn)了問題，在輸出時成為了許多亂碼。解決方法：通過在網(wǎng)上搜索查找，我發(fā)現(xiàn)是我在調(diào)用自帶函數(shù)strcat時出現(xiàn)了問題。這個函數(shù)一共有兩個形參，調(diào)用時，是把后一個字符串復(fù)制到前一個字符串的’\0’后面，并自動刪除原先的’\0’，再在復(fù)制后添加新的’\0’。但是，由于我沒有一開始把字符串的第一個字符初始為’\0’，導(dǎo)致字符串被復(fù)制到了第一個字符串的最后面。加上語句 aftercode[0]='\0';則解決了該問題。在解碼的過程中的亂碼：主函數(shù)里，我調(diào)用：ce.Decode(afterdecode);時出現(xiàn)了錯誤，同樣在打印出來后出現(xiàn)了許多亂碼。具體產(chǎn)生的原因我還沒有弄清楚，但是，當我把aftercode設(shè)置為堆中的動態(tài)存儲時，即修該語句為char*afterdecode=newchar[100];亂碼消失心得體會：這次哈夫曼樹的編程