武漢理工大學(xué)數(shù)據(jù)結(jié)構(gòu)及算法綜合實驗哈夫曼樹

1、-. z.學(xué)生*實驗課成績學(xué)生實驗報告書實驗課程名稱數(shù)據(jù)構(gòu)造與算法綜合實驗開課學(xué)院計算機科學(xué)與技術(shù)學(xué)院指導(dǎo)教師*學(xué)生*學(xué)生專業(yè)班級*2015-2016學(xué)年第2學(xué)期-. z.實驗課程名稱：數(shù)據(jù)構(gòu)造與算法綜合實驗實驗工程名稱二叉樹與赫夫曼圖片壓縮報告成績實驗者*專業(yè)班級*組別同組者完成日期2016年5月2日第一局部：實驗分析與設(shè)計可加頁實驗?zāi)康暮鸵?.目的掌握樹的存儲構(gòu)造掌握二叉樹的三種遍歷方法掌握 Huffman 樹、Huffman 編碼等知識和應(yīng)用使用 C+、文件操作和 Huffman 算法實現(xiàn)圖片壓縮程序?qū)ｎ}編程。2.要求針對一幅 BMP 格式的圖片文件，統(tǒng)計 256 種不同字節(jié)的重復(fù)次數(shù)

2、，以每 種字節(jié)重復(fù)次數(shù)作為權(quán)值，構(gòu)造一顆有 256 個葉子節(jié)點的哈夫曼二叉樹。利用上述哈夫曼樹產(chǎn)生的哈夫曼編碼對圖片文件進展壓縮。壓縮后的文件與原圖片文件同名，加上后綴.huf保存原后綴，如 pic.bmp分析與設(shè)計依據(jù)上述的實驗?zāi)康呐c要求，可導(dǎo)出實現(xiàn)的二叉樹與赫夫曼圖片壓縮軟件的流程為：讀取圖片文件、統(tǒng)計權(quán)值生成 Huffman 樹 生成 Huffman 編碼 壓縮圖片文件 保存壓縮的文件數(shù)據(jù)構(gòu)造的設(shè)計記錄統(tǒng)計256種不同字節(jié)的重復(fù)次數(shù)使用整型數(shù)組。int weight256 = 0 ;二叉樹的存儲構(gòu)造。使用構(gòu)造體存儲節(jié)點，使用數(shù)組存儲樹的節(jié)點，使用靜態(tài)二叉鏈表方式存儲二叉樹。Huffman

3、編碼存儲構(gòu)造struct HTNodeint weight;/權(quán)值int parent;int lchild;int rchild;char zifu;string bianma;壓縮文件的算法的數(shù)據(jù)構(gòu)造為正確解壓文件，除了要保存原文件長度外，還要保存原文件中256種字節(jié)重復(fù)的次數(shù)，即權(quán)值。定義一個文件頭，保存相關(guān)的信息：struct HEADchar type4;int length;int weight256;壓縮文件時，定義一個內(nèi)存緩沖區(qū)：typedef char * pBuffer;/其大小視原文件壓縮后的大小2.核心算法設(shè)計(1)生成Huffman樹和Huffman編碼的算法void

4、 Select(HTNode huffTree,int m)int min,min2,i;min=min2=1000;for(i=0;ihuffTreei.weight )min2=min;min=huffTreei.weight ;*2=*1;*1=i;else if(min2huffTreei.weight )min2=huffTreei.weight ;*2=i;void creatHuffman(int huff)int i;int s=256;for(i=0;i2*s-1;i+)HuffmanTreei.parent =-1;HuffmanTreei.lchild =-1;Huffm

5、anTreei.rchild =-1;for(int i1=0;i1s;i1+)HuffmanTreei1.weight=huffi1;for(int k=s;kn-1;i-)huffTreehuffTreei.lchild .bianma =0;huffTreehuffTreei.rchild .bianma =1;for(i=0,j=0;jn;j+)while(huffTreei.parent !=-1)huffTreej.bianma =huffTreehuffTreei.parent.bianma +huffTreej.bianma ;i=huffTreei.parent ;i=j+1

6、;(2)壓縮編碼算法struct HEADchar type4;int length;int weight256;char Str2byte(const char * pBinStr)char b=0*00;for(int i=0;i8;i+)b=b1;if(pBinStri=1)b=b|0*01;return b;bool InitHead(const char *pFilename,HEAD &sHead)char ch;/初始化文件strcpy(sHead.type,HUF);sHead.length=0;for(int i=0;i256;i+)sHead.weighti=0;ifstr

7、eam in;in.open(pFilename,ios:binary);while(in.get(ch) sHead.weight(unsigned char)ch+;sHead.length+; coutsHead.length字節(jié)endl;return true;int Encode(const char *pFilename,char * &pBuffer,const int nSize) pBuffer=(char *)malloc(nSize * sizeof(char)+10);if(!pBuffer)cout開辟緩沖區(qū)失敗=8)/coutcd Str2byte(cd) ;pBu

8、fferpos+=Str2byte(cd);/coutpBufferpos-1endl;for(int i=0;i0)pBufferpos+=Str2byte(cd);return 1;int WriteFile(const char * pFilename ,const HEAD sHead, char * pBuffer,const int nSize)/生成文件名char filename256=0;strcpy(filename,pFilename);int i;for( i=strlen(filename);filenamei!=.;i-); filenamei=0;strcat(f

9、ilename,.huf);/以二進制流的形式翻開文件FILE *out =fopen(filename ,wb);/寫文件頭fwrite( & sHead,sizeof(HEAD),1,out);/寫壓縮后的編碼fwrite(pBuffer,sizeof(char),nSize,out);/關(guān)閉文件釋放文件指針fclose(out);out=NULL;cout生成壓縮文件filenameendl;int len=sizeof(HEAD)+strlen(pFilename)+1+nSize;return len;int press(const char *pFilename,int weigh

10、t256,const HEAD sHead)/計算緩沖區(qū)的大小int nSize=0;for(int i=0;i256;i+)nSize+=weighti*HuffmanTreei.bianma.length();nSize=(nSize%8)nSize/8+1:nSize/8;/coutnSizenSizeendl;char *pBuffer=NULL;Encode(pFilename,pBuffer,nSize);/if(pBuffer=NULL)/ cout wrongendl;if(!pBuffer)return 0;int result=WriteFile(pFilename,sHe

11、ad,pBuffer,nSize);return result;3.測試用例設(shè)計使用一個文本文件作為壓縮的例，觀察其壓縮比；通過屏幕截圖形成一個BMP圖片文件，觀察其壓縮比；在互聯(lián)網(wǎng)上搜索下載任意格式的圖片文件，觀察其壓縮比。三、主要儀器設(shè)備及耗材1.安裝了Windows 10或其它版本的Windows操作系統(tǒng)的PC機1臺2.PC機系統(tǒng)上安裝了Microsoft Visual Studio 2010開發(fā)環(huán)境第二局部：實驗過程和結(jié)果可加頁實現(xiàn)說明在Microsoft Visual Studio 2010集成開發(fā)環(huán)境中新建一個Win32控制臺應(yīng)用程序工程HfmpressConsole。 Hfmpr

12、essConsole工程中新建2組相關(guān)文件。第1組是實現(xiàn)依據(jù)圖片文件構(gòu)建其Huffman編碼的頭文件Huffman.h和源程序文件Huffman.cpp。第2組是實現(xiàn)圖片文件壓縮編碼和寫磁盤等功能的頭文件press.h和源程序文件press.cpp。 Huffman.h存放與Huffman.cpp相關(guān)函數(shù)需要的數(shù)據(jù)類型的定義，函數(shù)原型的聲明等。press.h存放與press.cpp相關(guān)函數(shù)需要的數(shù)據(jù)類型的定義，函數(shù)原型的聲明等。 最后新建一個main.cpp源文件，實現(xiàn)main函數(shù)按分析與設(shè)計中規(guī)定的流程調(diào)用Huffman.cpp和press.cpp的功能函數(shù)。調(diào)試說明調(diào)試手段、過程及結(jié)果分析

13、調(diào)試主要內(nèi)容為編寫程序的語法正確性與否，程序邏輯的正確性與否。調(diào)試手段主要采用了Microsoft Visual Studio 2010集成開發(fā)環(huán)境中調(diào)試D菜單中的調(diào)試方法或手段。即：F5：啟動調(diào)試；F11：逐語句調(diào)試；F12：逐過程調(diào)試；F9：切換斷點；ctrl+B：新建斷點等。例如在統(tǒng)計圖片文件中0-255取值的256個字節(jié)出現(xiàn)的次數(shù)函數(shù)中，設(shè)置斷點并使用簡單的文本文件進展測試，發(fā)現(xiàn)了沒有掃描完整個文件而是中途跳出的問題。通過斷點出查看weight數(shù)組的值以及通過逐語句跳出的處定位錯誤所在之處。找出問題的原因是以流的形式讀入的字符定義問題，char ch；ch=fgetcin；Weight

14、ch+;字符變量ch在轉(zhuǎn)換成int時出現(xiàn)了負數(shù)。當(dāng)將ch的定義修改Unsigned char ch；問題解決。 再例：文件編碼壓縮Encode函數(shù)會產(chǎn)生編碼后的一個緩沖區(qū)char *pBuffer；寫文件函數(shù)會使用它直接寫磁盤文件。調(diào)試過程中并沒發(fā)現(xiàn)任何問題，就是不能成功地寫后綴為.huf的文件。在相關(guān)函數(shù)中設(shè)置斷點，觀察緩沖區(qū)的情況，且編寫屏幕輸出緩沖區(qū)數(shù)據(jù)的程序段，發(fā)現(xiàn)緩沖區(qū)是空的。通過在Encode函數(shù)中以及WriteFile函數(shù)中做同樣的跟蹤調(diào)試，發(fā)現(xiàn)在Encode函數(shù)中建立的緩沖區(qū)數(shù)據(jù)并沒有帶出來，通過分析發(fā)現(xiàn)是緩沖區(qū)空間構(gòu)建位置的問題，即不能放在Encode函數(shù)中。軟件測試測試效果.界面、綜合分析和結(jié)論1測試效果.界面2綜合分析和結(jié)論試驗在壓縮t*t文件的時候沒有問題，可以通過編譯生成可執(zhí)行