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

1、.學(xué)生學(xué)號(hào) Xxx實(shí)驗(yàn)課成績(jī)學(xué) 生 實(shí) 驗(yàn) 報(bào) 告 書(shū)實(shí)驗(yàn)課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)與算法綜合實(shí)驗(yàn)開(kāi)課學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院指導(dǎo)教師姓名xxx學(xué)生姓名xxx學(xué)生專(zhuān)業(yè)班級(jí)xxxx2015-2016學(xué)年第2學(xué)期；.實(shí)驗(yàn)課程名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu)與算法綜合實(shí)驗(yàn) 實(shí)驗(yàn)項(xiàng)目名稱(chēng)二叉樹(shù)與赫夫曼圖片壓縮報(bào)告成績(jī)實(shí)驗(yàn)者xx專(zhuān)業(yè)班級(jí)xxx組別同組者 完成日期2016年5月2日第一部分：實(shí)驗(yàn)分析與設(shè)計(jì)（可加頁(yè)）一、 實(shí)驗(yàn)?zāi)康暮鸵?.目的 = 掌握樹(shù)的存儲(chǔ)結(jié)構(gòu) = 掌握二叉樹(shù)的三種遍歷方法 = 掌握 Huffman 樹(shù)、Huffman 編碼等知識(shí)和應(yīng)用 = 使用 C+、文件操作和 Huffman 算法實(shí)現(xiàn)“圖片壓縮程序”專(zhuān)題編

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

3、 int weight256 = 0 ;l 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。使用結(jié)構(gòu)體存儲(chǔ)節(jié)點(diǎn)，使用數(shù)組存儲(chǔ)樹(shù)的節(jié)點(diǎn)，使用靜態(tài)二叉鏈表方式存儲(chǔ)二叉樹(shù)。l Huffman編碼存儲(chǔ)結(jié)構(gòu) struct HTNodeint weight;/權(quán)值int parent;int lchild;int rchild;char zifu;string bianma;l 壓縮文件的算法的數(shù)據(jù)結(jié)構(gòu) 為正確解壓文件，除了要保存原文件長(zhǎng)度外，還要保存原文件中256種字節(jié)重復(fù)的次數(shù)，即權(quán)值。定義一個(gè)文件頭，保存相關(guān)的信息： struct HEADchar type4;int length;int weight256;壓縮文件時(shí)，定義一

4、個(gè)內(nèi)存緩沖區(qū)： typedef char * pBuffer; /其大小視原文件壓縮后的大小2.核心算法設(shè)計(jì)(1)生成Huffman樹(shù)和Huffman編碼的算法void Select(HTNode huffTree,int m)int min,min2,i;min=min2=1000;for(i=0;ihuffTreei.weight )min2=min;min=huffTreei.weight ;x2=x1;x1=i;else if(min2huffTreei.weight )min2=huffTreei.weight ;x2=i;void creatHuffman(int huff)int

5、 i;int s=256;for(i=0;i2*s-1;i+)HuffmanTreei.parent =-1;HuffmanTreei.lchild =-1;HuffmanTreei.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.

6、bianma =huffTreehuffTreei.parent.bianma +huffTreej.bianma ;i=huffTreei.parent ;i=j+1;(2)壓縮編碼算法struct HEADchar type4;int length;int weight256;char Str2byte(const char * pBinStr)char b=0x00;for(int i=0;i8;i+)b=b1;if(pBinStri=1)b=b|0x01;return b;bool InitHead(const char *p &sHead)char ch;/初始化文件strcpy(s

7、Head.type,HUF);sHead.length=0;for(int i=0;i256;i+)sHead.weighti=0;ifstream in;in.open(p);while(in.get(ch) sHead.weight(unsigned char)ch+;sHead.length+; coutsHead.length字節(jié)endl;return true;int Encode(const char *p * &pBuffer,const int nSize) pBuffer=(char *)malloc(nSize * sizeof(char)+10);if(!pBuffer)

8、cout開(kāi)辟緩沖區(qū)失敗=8)/coutcd Str2byte(cd) ;pBufferpos+=Str2byte(cd);/coutpBufferpos-1endl;for(int i=0;i0)pBufferpos+=Str2byte(cd);return 1;int Write char * p ,const HEAD sHead, char * pBuffer,const int nSize)/生成文件名char 256=0;strcpy();int i;for( i=strlen();i!=.;i-); i=0;strcat(,.huf);/以二進(jìn)制流的形式打開(kāi)文件FILE *out

9、=fopen( ,wb);/寫(xiě)文件頭fwrite( & sHead,sizeof(HEAD),1,out);/寫(xiě)壓縮后的編碼fwrite(pBuffer,sizeof(char),nSize,out);/關(guān)閉文件釋放文件指針fclose(out);out=NULL;cout生成壓縮文件endl;int len=sizeof(HEAD)+strlen(p)+1+nSize;return len;int compress(const char *p weight256,const HEAD sHead)/計(jì)算緩沖區(qū)的大小int nSize=0;for(int i=0;i256;i+)nSize+=

10、weighti*HuffmanTreei.bianma.length();nSize=(nSize%8)?nSize/8+1:nSize/8;/coutnSizenSizeendl;char *pBuffer=NULL;Encode(p);/if(pBuffer=NULL)/ cout wrongendl;if(!pBuffer)return 0;int result=Write);return result;3.測(cè)試用例設(shè)計(jì)l 使用一個(gè)文本文件作為壓縮的例，觀察其壓縮比； l 通過(guò)屏幕截圖形成一個(gè)BMP圖片文件，觀察其壓縮比； l 在互聯(lián)網(wǎng)上搜索下載任意格式的圖片文件，觀察其壓縮比。三、主要

11、儀器設(shè)備及耗材1.安裝了Windows 10或其它版本的Windows操作系統(tǒng)的PC機(jī)1臺(tái)2.PC機(jī)系統(tǒng)上安裝了Microsoft Visual Studio 2010開(kāi)發(fā)環(huán)境第二部分：實(shí)驗(yàn)過(guò)程和結(jié)果（可加頁(yè)）一、 實(shí)現(xiàn)說(shuō)明在Microsoft Visual Studio 2010集成開(kāi)發(fā)環(huán)境中新建一個(gè)Win32控制臺(tái)應(yīng)用程序工程HfmCompressConsole。 HfmCompressConsole工程中新建2組相關(guān)文件。第1組是實(shí)現(xiàn)依據(jù)圖片文件構(gòu)建其Huffman編碼的頭文件Huffman.h和源程序文件Huffman.cpp。第2組是實(shí)現(xiàn)圖片文件壓縮編碼和寫(xiě)磁盤(pán)等功能的頭文件Comp

12、ress.h和源程序文件Compress.cpp。 Huffman.h存放與Huffman.cpp相關(guān)函數(shù)需要的數(shù)據(jù)類(lèi)型的定義，函數(shù)原型的聲明等。Compress.h存放與Compress.cpp相關(guān)函數(shù)需要的數(shù)據(jù)類(lèi)型的定義，函數(shù)原型的聲明等。 最后新建一個(gè)main.cpp源文件，實(shí)現(xiàn)main函數(shù)按分析與設(shè)計(jì)中規(guī)定的流程調(diào)用Huffman.cpp和Compress.cpp的功能函數(shù)。二、 調(diào)試說(shuō)明（調(diào)試手段、過(guò)程及結(jié)果分析）調(diào)試主要內(nèi)容為編寫(xiě)程序的語(yǔ)法正確性與否，程序邏輯的正確性與否。調(diào)試手段主要采用了Microsoft Visual Studio 2010集成開(kāi)發(fā)環(huán)境中“調(diào)試（D）”菜單中的

13、調(diào)試方法或手段。即：F5：?jiǎn)?dòng)調(diào)試；F11：逐語(yǔ)句調(diào)試；F12：逐過(guò)程調(diào)試；F9：切換斷點(diǎn)；ctrl+B：新建斷點(diǎn)等。 例如在統(tǒng)計(jì)圖片文件中0-255取值的256個(gè)字節(jié)出現(xiàn)的次數(shù)函數(shù)中，設(shè)置斷點(diǎn)并使用簡(jiǎn)單的文本文件進(jìn)行測(cè)試，發(fā)現(xiàn)了“沒(méi)有掃描完整個(gè)文件而是中途跳出”的問(wèn)題。通過(guò)斷點(diǎn)出查看weight數(shù)組的值以及通過(guò)逐語(yǔ)句跳出的處定位錯(cuò)誤所在之處。找出問(wèn)題的原因是以流的形式讀入的字符定義問(wèn)題，char ch；ch=fgetc（in）；Weightch+;字符變量ch在轉(zhuǎn)換成int時(shí)出現(xiàn)了負(fù)數(shù)。當(dāng)將ch的定義修改Unsigned char ch；問(wèn)題解決。 再例：文件編碼壓縮Encode（）函數(shù)會(huì)產(chǎn)生編碼后的一個(gè)緩沖區(qū)char *pBuffer；寫(xiě)文件函數(shù)會(huì)使用它直接寫(xiě)磁盤(pán)文件。調(diào)試過(guò)程中并沒(méi)發(fā)現(xiàn)任何問(wèn)題，就是不能成功地寫(xiě)后綴為.huf的文件。在相關(guān)函數(shù)中設(shè)置斷點(diǎn)，觀察緩沖區(qū)的情況，且編寫(xiě)屏幕輸出緩沖區(qū)數(shù)據(jù)的程序段，發(fā)現(xiàn)緩沖區(qū)是空的。通過(guò)在Encode函數(shù)中以及WriteFile函數(shù)中做同樣的跟蹤調(diào)試，發(fā)現(xiàn)在Encode函數(shù)中建立的緩沖區(qū)數(shù)據(jù)并沒(méi)有帶出來(lái)，通過(guò)分析發(fā)現(xiàn)是緩沖區(qū)空間構(gòu)建位置的問(wèn)題，即不能放在Encode函數(shù)中。三、 軟件測(cè)試（測(cè)試效果.界面、綜合分析和結(jié)論）1測(cè)試效果.界面2綜合分析和結(jié)論試驗(yàn)在壓縮txt文件的時(shí)候沒(méi)有問(wèn)題，可以通過(guò)編譯生成可執(zhí)行文件，但