算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告-哈夫曼編碼（含源程序）.doc

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