昆明理工大學信息工程與自動化學院學生實驗報告（ 2011 2012 學年 第 1 學期 ）課程名稱：算法設計與分析 開課實驗室：信自樓機房445 2011 年11月 2日年級、專業、班計科092學號200910405201姓名劉召成績實驗項目名稱哈夫曼編碼指導教師 張晶教師評語該同學是否了解實驗原理：a.了解b.基本了解c.不了解該同學的實驗能力：a.強 b.中等 c.差 該同學的實驗是否達到要求：a.達到b.基本達到c.未達到實驗報告是否規范：a.規范b.基本規范c.不規范實驗過程是否詳細記錄：a.詳細b.一般 c.沒有 教師簽名： 年 月 日一、上機目的及內容1.上機內容設需要編碼的字符集為d1, d2, , dn，它們出現的頻率為w1, w2, , wn，應用哈夫曼樹構造最短的不等長編碼方案。2.上機目的（1）了解前綴編碼的概念，理解數據壓縮的基本方法；（2）掌握最優子結構性質的證明方法；（3）掌握貪心法的設計思想并能熟練運用。二、實驗原理及基本技術路線圖（方框原理圖或程序流程圖）（1）證明哈夫曼樹滿足最優子結構性質；證明：設c為一給定的字母表，其中每個字母cc都定義有頻度fc。設x和y是c中具有最低頻度的兩個字母。并設d為字母表移去x和y，再加上新字符z后的字母表，d=c-x，yz；如c一樣為d定義f，其中fz=fx+fy。設t為表示字母表d上最優前綴編碼的任意一棵樹。那么，將t中的葉子節點z替換成具有x和y孩子的內部節點所得到的樹t，表示字母表c上的一個最優前綴編碼。（2） 設計貪心算法求解哈夫曼編碼方案；解：哈弗曼編碼是以貪心法為基礎的，可以從最優子結構中求得問題的解。所以，需要從一個問題中選出一個當前最優的解，再把這些解加起來就是最終問題的解。可以構造一個優先隊列priority_queue，每次求解子問題的解時，從優先級隊列priority_queue中選取頻率最小的兩個字母（x、y）進行合并得到一個新的結點z，把x與y從優先級隊列priority_queue中彈出，把壓入到優先級隊列priority_queue中。如此反復進行，直到優先級隊列priority_queue中只有一個元素（根節點）為止。（3） 設計測試數據，寫出程序文檔。共設計了兩組測試數據，他們的哈弗曼樹如下圖所示：圖（1）測試數據的哈弗曼樹圖表一：第一組測試數據字符出現的頻率a1b3c6d14e58表二：第二組測試數據字符出現的頻率d4b3f5g6h14m16由圖（1）可知各個字符的哈弗曼編碼如下表：表三：表一中各元素的哈弗曼編碼字符出現的頻率a0000b0001c001d01e1表四：表二中各元素的哈弗曼編碼字符出現的頻率d001b000f010g011h10m11三、所用儀器、材料（設備名稱、型號、規格等或使用軟件）1臺pc及visual c+6.0軟件億圖程序流程圖繪制軟件四、實驗方法、步驟（或：程序代碼或操作過程） 下面源代碼可以在visual c+6.0平臺上運行！/author劉召 at 2011-11-18/this program is edited and compiled on visual studio 10 platform/huffman編碼/#include stdafx.h/在visual studio中運行，應取消該句的注釋！#include #include #include #include #include #includeusing namespace std;struct codeinformationdouble priority;char codename;int lchild,rchild,parent;bool test;bool operator (const codeinformation& x) const return !(priorityx.priority);bool check(vector qa,const char c)for (int i=0 ;i(int)(qa.size();i+)if(qai.codename=c) return true; return false;void aline(char c,int n)for (int i=0;in;i+)coutc;int inputelement(vector* harffcode,priority_queue* pq)int i=1,j=1;codeinformation wk;while(i)aline(-,80);cout請輸入第j個元素的字符名稱（ascll碼）：wk.codename;while(check(* harffcode,wk.codename)coutwk.codename;cout請輸入第j個元素的概率（權值）：wk.priority;wk.lchild=wk.rchild=wk.parent=-1;wk.test=false;harffcode-push_back(wk);pq-push(wk);j+;cout1繼續輸入下一個元素信息！endl;cout2已完成輸入，并開始構造哈弗曼樹！i;if (i=2) i=0;int count=1;j=harffcode-size();int selectelement(vector*,priority_queue*);for (int k=j;k2*j-1;k+)aline(*,80);cout第count次合并：push(wk);count+;cout所合成的節點名稱：#（虛節點）t概率（權值）：(*harffcode)k.priorityendl;aline(*,80);return j;void showchar(const char c)if(isspace(c)cout#;coutc;int selectelement(vector*harffcode,priority_queue*qurgh)for (int i=0;i(int)(*harffcode).size();i+)if (*harffcode)i.priority=(*qurgh).top().priority)&(*harffcode)i.test=false)cout所選擇的節點的信息：頻率（權值）：setw(5)(*qurgh).top().priorityt名為：;showchar(*qurgh).top().codename);coutendl;(*qurgh).pop();(*harffcode)i.test=true;return i;void huffmancode(vector harffcode,int n)for (int i1=0;i1(int)harffcode.size();i1+)coutarrayi1的概率（權值）：harffcodei1.priorityt名為:;showchar(harffcodei1.codename);coutt父節點的數組下標索引值：harffcodei1.parentendl;aline(&,80);for (int i=0;i=0)if (harffcodeharffcodej.parent.lchild=j)s=s+0;else s=s+1;j=harffcodej.parent;coutn概率（權值）為:setw(8)harffcodei.priority 名為:;showchar(harffcodei.codename);cout0;i-)coutsi-1;void choise()coutendl;aline(+,80);coutn1繼續使用該程序endl;cout2退出系統endl;void welcome()coutnsetw(56)歡迎使用赫夫曼編碼簡易系統nendl;couttttt學 校：昆明理工大學endl;couttttt學 院：信息工程與自動化學院endl;couttttt專 業：計算機科學與技術endl;couttttt指導老師：張晶endl;couttttt制 作 人：劉召endl;couttttt學 號：200910405201endl;coutttttqq 郵箱：329245767endl;int main()welcome();system(color d1); int i=1,n;vectorhufftree; priority_queueqptree; while(i!=2) n=inputelement(&hufftree,&qptree); huffmancode(hufftree, n);choise();cini;hufftree.clear(); while(qptree.empty() qptree.pop(); return 0;程序說明：在機器（內存）條件較好的情況下，原則上本程序可以對任意多個字符進行編碼，本程序是動態擴展的，雖然不能很清晰地表述哈弗曼樹種每一個節點的位置，不過可以根據合并過程輸出的結果畫出相應的哈弗曼樹。本程序對哈弗曼樹種的虛節點的名稱統一用#表示。五、實驗過程原始記錄( 測試數據、圖表、計算等)程序測試結果及分析：圖（2）輸入第一組測試數據開始輸入第一組測試數據，該組數據信息如表一所示。其實，由于字母表中的各個字符是相互唯一的，在該程序中，若輸入了一個與當前字母表中已存在的字符，則會提示重新輸入該字符。圖（3）對第一組數據進行合并，并計算各個字符的哈弗曼編碼對第一組測試數據進行哈弗曼編碼，并輸出了各個結點合并的過程，及產生的新結點的信息，以便可以較為容易地手工畫出該字母表的哈弗曼樹。通過與表三對照可知，對各個字符的編碼與最初的分析相符合。圖（4）輸入第二組測試數據在完成對第一組數據測試后，可以輸入1 繼續對下一組要編碼的字母表進行哈弗曼編碼。第二組要測試的數據信息如表2所示。圖（5）對第二組數據進行哈弗曼編碼的運行結果圖把第二組數據進行哈弗曼編碼的運行結果與表4對比可知，程序的運行結果與原來設計的結果相同。6、 實驗結果、分析和結論（誤差分析與數據處理、成果總結等。其中，繪制曲線圖時必須用計算紙或程序運行結果、改進、收獲）在實驗過程中，當選擇概率最小的結點時，要返回原數組下標的索引值，我一開始設想把結點分為兩組進行存儲，一組存儲在向量里，另一組存儲在優先級隊列中，通過優先級隊列可以較為容易地實現應該選擇哪個結點，通過對向量操作，可以較為容易地實現對數組的操作，并且還具有動態的擴展性。通過優先級隊列中頂層結點元素的頻率與向量中結點