武漢理工大學數據結構與算法綜合實驗哈夫曼樹

1、學生學號 Xxx實驗課成績學 生 實 驗 報 告 書實驗課程名稱數據結構與算法綜合實驗開課學院計算機科學與技術學院指導教師姓名xxx學生姓名xxx學生專業(yè)班級xxxx2015-2016學年第2學期實驗課程名稱： 數據結構與算法綜合實驗 實驗項目名稱二叉樹與赫夫曼圖片壓縮報告成績實驗者xx專業(yè)班級xxx組別同組者 完成日期2016年5月2日第一部分：實驗分析與設計（可加頁）一、 實驗目的和要求1.目的 = 掌握樹的存儲結構 = 掌握二叉樹的三種遍歷方法 = 掌握 Huffman 樹、Huffman 編碼等知識和應用 = 使用 C+、文件操作和 Huffman 算法實現“圖片壓縮程序”專題編程。2

2、.要求=針對一幅 BMP 格式的圖片文件，統(tǒng)計 256 種不同字節(jié)的重復次數，以每 種字節(jié)重復次數作為權值，構造一顆有 256 個葉子節(jié)點的哈夫曼二叉樹。 =利用上述哈夫曼樹產生的哈夫曼編碼對圖片文件進行壓縮。=壓縮后的文件與原圖片文件同名，加上后綴.huf（保留原后綴），如 pic.bmp 二、 分析與設計依據上述的實驗目的與要求，可導出實現的二叉樹與赫夫曼圖片壓縮軟件的流程為： 讀取圖片文件、統(tǒng)計權值 生成 Huffman 樹 生成 Huffman 編碼 壓縮圖片文件 保存壓縮的文件1. 數據結構的設計l 記錄統(tǒng)計256種不同字節(jié)的重復次數使用整型數組。 int weight256 = 0

3、 ;l 二叉樹的存儲結構。使用結構體存儲節(jié)點，使用數組存儲樹的節(jié)點，使用靜態(tài)二叉鏈表方式存儲二叉樹。l Huffman編碼存儲結構 struct HTNodeint weight;/權值int parent;int lchild;int rchild;char zifu;string bianma;l 壓縮文件的算法的數據結構 為正確解壓文件，除了要保存原文件長度外，還要保存原文件中256種字節(jié)重復的次數，即權值。定義一個文件頭，保存相關的信息： struct HEADchar type4;int length;int weight256;壓縮文件時，定義一個內存緩沖區(qū)： typedef ch

4、ar * pBuffer; /其大小視原文件壓縮后的大小2.核心算法設計(1)生成Huffman樹和Huffman編碼的算法void Select(HTNode huffTree,int m)int min,min2,i;min=min2=1000;for(i=0;i<m;i+)if(huffTreei.parent=-1)if(min>huffTreei.weight )min2=min;min=huffTreei.weight ;x2=x1;x1=i;else if(min2>huffTreei.weight )min2=huffTreei.weight ;x2=i;vo

5、id creatHuffman(int huff)int i;int s=256;for(i=0;i<2*s-1;i+)HuffmanTreei.parent =-1;HuffmanTreei.lchild =-1;HuffmanTreei.rchild =-1;for(int i1=0;i1<s;i1+)HuffmanTreei1.weight=huffi1;for(int k=s;k<2*s-1;k+)Select(HuffmanTree,k);HuffmanTreex1.parent =k;HuffmanTreex2.parent =k;HuffmanTreek.wei

6、ght =HuffmanTreex1.weight +HuffmanTreex2.weight ;HuffmanTreek.lchild =x1;HuffmanTreek.rchild =x2;void HuffmanCoding(HTNode huffTree,int n)int i,j=0;for(i=2*(n-1);i>n-1;i-)huffTreehuffTreei.lchild .bianma ="0"huffTreehuffTreei.rchild .bianma ="1"for(i=0,j=0;j<n;j+)while(huff

7、Treei.parent !=-1)huffTreej.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;i<8;i+)b=b<<1;if(pBinStri='1')b=b|0x01;return b;bool In

8、itHead(const char *pFilename,HEAD &sHead)char ch;/初始化文件strcpy(sHead.type,"HUF");sHead.length=0;for(int i=0;i<256;i+)sHead.weighti=0;ifstream in;in.open(pFilename,ios:binary);while(in.get(ch) sHead.weight(unsigned char)ch+;sHead.length+; cout<<sHead.length<<"字節(jié)"

9、<<endl;return true;int Encode(const char *pFilename,char * &pBuffer,const int nSize) pBuffer=(char *)malloc(nSize * sizeof(char)+10);if(!pBuffer)cout<<"開辟緩沖區(qū)失敗"<<endl;char cd256=0;int pos=0;int ch;FILE *in=fopen(pFilename,"rb");while(ch=fgetc(in)!=EOF)strcat

10、(cd,HuffmanTreech.bianma.c_str();while(strlen(cd)>=8)/cout<<cd<<" "<<Str2byte(cd)<<" "pBufferpos+=Str2byte(cd);/cout<<pBufferpos-1<<endl;for(int i=0;i<256-8;i+)cdi=cdi+8;if(strlen(cd)>0)pBufferpos+=Str2byte(cd);return 1;int WriteFile(c

11、onst 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(filename,".huf");/以二進制流的形式打開文件FILE *out =fopen(filename ,"wb");/寫文件頭fwr

12、ite( & sHead,sizeof(HEAD),1,out);/寫壓縮后的編碼fwrite(pBuffer,sizeof(char),nSize,out);/關閉文件釋放文件指針fclose(out);out=NULL;cout<<"生成壓縮文件"<<filename<<endl;int len=sizeof(HEAD)+strlen(pFilename)+1+nSize;return len;int compress(const char *pFilename,int weight256,const HEAD sHead)/

13、計算緩沖區(qū)的大小int nSize=0;for(int i=0;i<256;i+)nSize+=weighti*HuffmanTreei.bianma.length();nSize=(nSize%8)?nSize/8+1:nSize/8;/cout<<"nSize"<<nSize<<endl;char *pBuffer=NULL;Encode(pFilename,pBuffer,nSize);/if(pBuffer=NULL)/ cout<<" wrong"<<endl;if(!pBuff

14、er)return 0;int result=WriteFile(pFilename,sHead,pBuffer,nSize);return result;3.測試用例設計l 使用一個文本文件作為壓縮的例，觀察其壓縮比； l 通過屏幕截圖形成一個BMP圖片文件，觀察其壓縮比； l 在互聯網上搜索下載任意格式的圖片文件，觀察其壓縮比。三、主要儀器設備及耗材1.安裝了Windows 10或其它版本的Windows操作系統(tǒng)的PC機1臺2.PC機系統(tǒng)上安裝了Microsoft Visual Studio 2010開發(fā)環(huán)境第二部分：實驗過程和結果（可加頁）一、 實現說明在Microsoft Visual

15、 Studio 2010集成開發(fā)環(huán)境中新建一個Win32控制臺應用程序工程HfmCompressConsole。 HfmCompressConsole工程中新建2組相關文件。第1組是實現依據圖片文件構建其Huffman編碼的頭文件Huffman.h和源程序文件Huffman.cpp。第2組是實現圖片文件壓縮編碼和寫磁盤等功能的頭文件Compress.h和源程序文件Compress.cpp。 Huffman.h存放與Huffman.cpp相關函數需要的數據類型的定義，函數原型的聲明等。Compress.h存放與Compress.cpp相關函數需要的數據類型的定義，函數原型的聲明等。 最后新建一個

16、main.cpp源文件，實現main函數按分析與設計中規(guī)定的流程調用Huffman.cpp和Compress.cpp的功能函數。二、 調試說明（調試手段、過程及結果分析）調試主要內容為編寫程序的語法正確性與否，程序邏輯的正確性與否。調試手段主要采用了Microsoft Visual Studio 2010集成開發(fā)環(huán)境中“調試（D）”菜單中的調試方法或手段。即：F5：啟動調試；F11：逐語句調試；F12：逐過程調試；F9：切換斷點；ctrl+B：新建斷點等。 例如在統(tǒng)計圖片文件中0-255取值的256個字節(jié)出現的次數函數中，設置斷點并使用簡單的文本文件進行測試，發(fā)現了“沒有掃描完整個文件而是中途

17、跳出”的問題。通過斷點出查看weight數組的值以及通過逐語句跳出的處定位錯誤所在之處。找出問題的原因是以流的形式讀入的字符定義問題，char ch；ch=fgetc（in）；Weightch+;字符變量ch在轉換成int時出現了負數。當將ch的定義修改Unsigned char ch；問題解決。 再例：文件編碼壓縮Encode（）函數會產生編碼后的一個緩沖區(qū)char *pBuffer；寫文件函數會使用它直接寫磁盤文件。調試過程中并沒發(fā)現任何問題，就是不能成功地寫后綴為.huf的文件。在相關函數中設置斷點，觀察緩沖區(qū)的情況，且編寫屏幕輸出緩沖區(qū)數據的程序段，發(fā)現緩沖區(qū)是空的。通過在Encode函數中以及WriteFile函數中做同樣的跟蹤調試，發(fā)現在Encode函數中建立的緩沖區(qū)數據并沒有帶出來，通過分析發(fā)現是緩沖區(qū)空間構建位置的問題，即不能放在Encode函數中。三、 軟件測試（測試效果.界面、綜合分