數(shù)據(jù)結(jié)構(gòu)課程設計報告

1、<p><b>　　《數(shù)據(jù)結(jié)構(gòu)與算法》</b></p><p><b>　　課程設計報告</b></p><p>　　學 號： </p><p>　　班級序號： </p><p>　　姓 名： </p><p><

2、;b>　　指導教師： </b></p><p>　　成 績： </p><p>　　2011年 12 月</p><p><b>　　課程設計報告</b></p><p><b>　　題目一</b></p><p>&

3、lt;b>　　1．需求規(guī)格說明</b></p><p>　　軟件壓縮/解壓縮軟件 Szip（Huffman算法及應用）</p><p><b>　　【問題描述】</b></p><p>　　利用哈夫曼編碼進行對已有文件進行重新編碼可以大大提高減小文件大小，減少存儲空間。但是，這要求在首先對一個現(xiàn)有文件進行編碼行成新的文件，也就

4、是壓縮。在文件使用時，再對壓縮文件進行解壓縮，也就是譯碼，復原原有文件。試為完成此功能，寫一個壓縮/解壓縮軟件。</p><p><b>　　【基本要求】</b></p><p>　　一個完整的系統(tǒng)應具有以下功能：</p><p>　?。?）壓縮準備。讀取指定被壓縮文件，對文件進行分析，建立哈夫曼樹，并給出分析結(jié)果（包括數(shù)據(jù)集大小，每個數(shù)據(jù)的權(quán)

5、值，壓縮前后文件的大?。谄聊簧陷敵?。</p><p>　?。?）壓縮。利用已建好的哈夫曼樹，對文件進行編碼，并將哈夫曼編碼及文件編碼后的數(shù)據(jù)一起寫入文件中，形成壓縮文件(*.Haf)。</p><p>　　（3）解壓縮。打開已有壓縮文件(*.Haf)，讀取其中的哈夫曼編碼，構(gòu)建哈夫曼樹，讀取其中的數(shù)據(jù)，進行譯碼后，寫入文件，完成解壓縮。</p><p>　?。?

6、）程序使用命令行方式運行</p><p>　　壓縮命令 ：SZip A Test.Haf 1.doc</p><p>　　解壓縮命令：SZip X Test.Haf 2.doc 或 SZip X Test.Haf </p><p>　　用戶輸入的命令不正確時，給出提示。</p><p>　?。?）使用面向?qū)ο蟮乃枷刖幊蹋?/p>

7、壓縮/解壓縮、哈夫曼構(gòu)建功能分別構(gòu)建類實現(xiàn)。</p><p><b>　　【提高要求】</b></p><p>　?。?）基于Windows對話框界面，可選擇輸入/輸出文件名，有壓縮進度條顯示。</p><p>　?。?）采用不同的數(shù)據(jù)集，比較其壓縮比，采用最有效的壓縮方式。</p><p>　?。?）多個文件的壓縮。&

8、lt;/p><p>　　（4）試構(gòu)建程序框架，使其能添加新的壓縮/解壓縮算法（例如書上LZW壓縮算法）。</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　約40000字符左右。</p><p>　　示例數(shù)據(jù).txt， 80K， 采用WinRar壓縮后為43K；</p><p>　

9、　示例數(shù)據(jù).doc，144K，采用WinRar壓縮后為52K。</p><p><b>　　2．總體分析與設計</b></p><p><b>　　（1）設計思想：</b></p><p>　　1)添加2個類 HuffmanTree(Huffman樹的葉子結(jié)點類), Huffman（壓縮/解壓函</p>&l

10、t;p><b>　　類）</b></p><p>　　2）添加文件，完成對于指定文件的分析工作</p><p>　　所有的文件都可以看做是二進制數(shù)據(jù)組成的。以二進制方式打開文件，依次讀取8</p><p>　　長度數(shù)據(jù)，定長數(shù)據(jù)（比如：00000000）的值出現(xiàn)一次，此數(shù)據(jù)的權(quán)值加1.</p><p>　　3）根據(jù)

11、分析的數(shù)據(jù)及其權(quán)值，構(gòu)建Huffman樹，并完成編碼。</p><p><b>　　4）創(chuàng)建壓縮文件</b></p><p>　　以二進制方式新建目標文件，比如：Encolding.haf。將Huffman樹的信息放到文件開始部分</p><p><b>　　5）形成壓縮文件</b></p><p>

12、;　　以二進制方式打開源文件與目標文件。依次讀取8位長度數(shù)據(jù)，根據(jù)讀取的數(shù)據(jù)，到對對應的編碼，把編碼寫到目標文件的尾部。</p><p><b>　　6）形成解壓文件</b></p><p>　　以二進制方式打開壓縮文件，讀取文件頭的Huffman信息，還原Huffman樹。然后每</p><p>　　次讀取一定長度的數(shù)據(jù)，根據(jù)編碼，將文件還原

13、，寫入到新文件中。</p><p><b>　?。?）設計表示：</b></p><p><b>　　函數(shù)調(diào)用圖：</b></p><p>　　CreateHuffmanTree</p><p>　　sort(T) MakeTree()</p><p>　　Hu

14、ffmanCode()</p><p>　　PreOrder(HuffmanTree *t)</p><p>　?。?）詳細設計表示：</p><p>　　class HuffmanTree</p><p><b>　　{</b></p><p><b>　　public:</b&

15、gt;</p><p>　　int value;</p><p>　　long weight;</p><p>　　HuffmanTree *lchild, *rchild, *parent;</p><p>　　int bit[256]; </p><p>　　int le

16、ngth; //哈弗曼樹長度</p><p><b>　　};</b></p><p>　　class Huffman</p><p><b>　　{</b></p><p>　　friend class C哈弗曼Dlg;</p><p&

17、gt;<b>　　public:</b></p><p>　　Huffman();</p><p>　　~Huffman();</p><p>　　void GetWeight(CString);</p><p>　　void CreateHuffmanTree();</p><p>　　void

18、 HuffmanCode();</p><p>　　void SzipA(CString); //壓縮文件</p><p>　　void SzipX(CString); //解壓文件</p><p>　　void Initialize(HuffmanTree a[],int size); //初始化最小堆

19、函數(shù)</p><p>　　void MakeTree();</p><p>　　void sort(HuffmanTree tt[]);</p><p>　　void Swap(HuffmanTree &a, HuffmanTree &b);</p><p>　　bool Bubble(HuffmanTree a[], int

20、 n);</p><p>　　void PreOrder(HuffmanTree *);</p><p><b>　　private:</b></p><p>　　HuffmanTree T[256]; </p><p>　　HuffmanTree *heap; //建立最小

21、堆的指針</p><p>　　HuffmanTree *z;</p><p>　　static int size; //最小堆的大小</p><p>　　HuffmanTree *root; //指向huffman樹的根結(jié)點</p><p>　　LinkedQueue<int>

22、L; //用來記錄哈弗曼編碼</p><p><b>　　};</b></p><p><b>　　3．編碼</b></p><p>　　問題一：由于數(shù)據(jù)結(jié)構(gòu)是自己寫的，無法使用書上的代碼，在建立Huffman樹時，一開始是打算初始化最小堆，然后再建立樹，后來只能改變這種思想，因為我的Huffman樹

23、是由葉子結(jié)點和非葉子節(jié)點組成，所以只能簡單的排序，然后構(gòu)建樹。</p><p>　　問題二：在壓縮文件時，不知道如何將Huffman樹信息與文件信息區(qū)別開來，想到的解決辦法有2種，第一種采取規(guī)定前100個字節(jié)存放Huffman信息，壓縮文件放在100個字節(jié)之后，第二種方法采取標記，規(guī)定一個標記，但讀到此標記時，則說明下面的數(shù)據(jù)是來自壓縮文件的。</p><p>　　問題三：在進行壓縮時，也

24、是滿8位一存，但可能出現(xiàn)最后的壓縮的編碼未滿8位，這樣最后的幾位無法正確還原。解決辦法是壓縮時記錄最后未滿8位的個數(shù)。然后放在文件的開頭，解壓時讀到的第一個字節(jié)則是未滿8位的個數(shù)，如果剛好滿8位，則存入0。</p><p>　　問題四：對于壓縮的數(shù)據(jù)不知道如何高效的還原，曾經(jīng)想過一一比較，看看是屬于那種編碼，但實現(xiàn)起來比較慢，不可取。解決方法：依次讀入一定長度的數(shù)據(jù)，根據(jù)數(shù)據(jù)去遍歷Huffman樹，最后遍歷到葉子

25、結(jié)點時，則輸出。 </p><p><b>　　4．程序及算法分析</b></p><p><b>　　界面：</b></p><p><b>　　添加將要壓縮的文件</b></p><p><b>　　解壓后</b></p><p&g

26、t;　　改進之處：在實習的大部分時期我都是在編寫主要程序代碼，最后一天覺得用控制臺的界面不好看，所以決定用mfc，不過由于對mfc不太熟悉，還是費了些功夫。</p><p><b>　　5．小結(jié)</b></p><p>　　經(jīng)驗與體會：這次課程實習，是這一年半中最痛苦的一次，可能你待在機房一個上午，但只做了一點點，有時候為了改一點東西，會牽扯到許多，又會費很長一段時間

27、，更特別的是，有次我坐在那一直痛苦著要不要重新來，如果不重新來后面一些代碼就必須自己寫，如構(gòu)建哈弗曼樹，如果重新來，采用書上的結(jié)構(gòu)，那么你之前寫的一切都得重新來過，對此我猶豫不決了很久，最后決定堅持下去，然后我花了很多功夫才總算編碼完成，所以通過此次我深刻的體會到數(shù)據(jù)結(jié)構(gòu)對我們C++編程的重要性。對此我深刻的體會到，編程是個很痛苦的過程，你需要不拋棄，不放棄，一直堅持到底。同時在這次實習中，我發(fā)現(xiàn)以前學知識時就應該好好學習，真正的掌握到

28、，這樣以后用起來很方便，如文件處理，在以前實習的時候，我也碰到過，不過沒有真正掌握，所以此次實習又得重新學習，mfc也是一樣?？偟膩碚f這次實習我收獲最大的就是對編程的態(tài)度發(fā)生了改變，以前碰到難題都會有為難情緒，但經(jīng)過這次我相信以后再碰到難題也不會畏懼了并且會認認真真，踏踏實實的做好每一個步驟，而且要用于探索。</p><p>　　需要改進的地方：程序需要改進的方面有很多，如分配內(nèi)存空間不合理，有些地方應該用別的數(shù)

29、據(jù)結(jié)構(gòu)來減少內(nèi)存空間的分配，此程序最大的問題在于，但文件比較大時，壓縮就會出現(xiàn)問題。</p><p><b>　　6．附錄</b></p><p><b>　　//壓縮代碼</b></p><p>　　void Huffman::SzipA(CString name)</p><p>　　{

30、ifstream rfile;</p><p>　　ofstream wfile;</p><p>　　rfile.open(name,ios::in|ios::binary);</p><p>　　wfile.open("Encolding.haf",ios::out|ios::binary);</p><p>　　co

31、nst char sign = (char)1;</p><p>　　bool neof = 1;</p><p>　　//將哈弗曼編碼寫入頭文件</p><p>　　wfile.put(sign);</p><p><b>　　//頭文件的開始</b></p><p>　　for(int i=1

32、;i<size+1;i++)</p><p>　　{ wfile.put(heap[i].value);</p><p>　　wfile.put((int)heap[i].weight);}</p><p>　　wfile.put (sign); //頭文件的結(jié)束</p><p><b>　　//

33、壓縮文件</b></p><p><b>　　char ch;</b></p><p>　　int code[8];</p><p>　　static int pp = 0;</p><p>　　while(rfile.get(ch)) </p>

34、;<p>　　{ neof = 0;</p><p>　　int va = (int)ch+128;</p><p>　　int len = T[va].length;</p><p>　　if(pp+len<8) //裝不滿八位</p><p>　　{ int

35、j = 0,i;</p><p>　　for(i=pp;i<pp+len;i++,j++)</p><p>　　{ code[i] = T[va].bit[j];}</p><p><b>　　pp = i;</b></p><p>　　neof = 1;} /

36、/有幾位沒有輸出</p><p>　　else if(pp+len == 8) //剛好裝滿位</p><p>　　{ int j = 0;</p><p>　　for(int i=pp;i<8;i++,j++)</p><p>　　{code[i]=T[va].bit[j];}</p>

37、;<p><b>　　pp = 0;</b></p><p>　　char num = code[0]*128+code[1]*64+code[2]*32+code[3]*16+code[4]*8+code[5]*4+code[6]*2+code[7];</p><p>　　wfile.put(num);}</p><p>　　e

38、lse //超過位</p><p>　　{ int j = 0;</p><p>　　while(pp+len>8)</p><p>　　{ for(int i=pp;i<8;i++,j++)</p><p>　　{code[i]=T[va].bit[j

39、];}</p><p>　　len = len-(8-pp);</p><p><b>　　pp = 0;</b></p><p>　　char num = code[0]*128+code[1]*64+code[2]*32+code[3]*16+code[4]*8+code[5]*4+code[6]*2+code[7];</p>

40、<p>　　wfile.put(num);}</p><p>　　if(pp+len<8) </p><p>　　{ int i;</p><p>　　for(i=pp;i<pp+len;i++,j++)</p><p>　　{code[i] = T[va].bi

41、t[j];}</p><p><b>　　pp = i;</b></p><p>　　neof = 1;} //有幾位沒輸出</p><p>　　else </p><p>　　{ for(int i=pp;i<8;i++,j++){

42、</p><p>　　code[i]=T[va].bit[j];}</p><p><b>　　pp = 0;</b></p><p>　　char num = code[0]*128+code[1]*64+code[2]*32+code[3]*16+code[4]*8+code[5]*4+code[6]*2+code[7];</p>

43、;<p>　　wfile.put(num)}}}</p><p>　　//將文件尾不足位的字節(jié)記下來</p><p>　　//wfile.put(sign);</p><p><b>　　if(neof)</b></p><p>　　{//將缺位放在文件開始的地方</p><p>

44、　　wfile.seekp(0,ios::beg);</p><p>　　wfile.put(pp);</p><p>　　wfile.seekp(0,ios::end);</p><p>　　char num = code[0]*128+code[1]*64+code[2]*32+code[3]*16+code[4]*8+code[5]*4+code[6]*2+c

45、ode[7];</p><p>　　wfile.put(num);}</p><p><b>　　else</b></p><p>　　{ wfile.seekp(0,ios::beg);</p><p>　　wfile.put(0);</p><p>　　wfile.seekp(0,ios:

46、:end);}</p><p>　　rfile.close();</p><p>　　wfile.close();}</p><p><b>　　//解壓代碼</b></p><p>　　void Huffman::SzipX(CString name)</p><p>　　{ ifstrea

47、m rfile;</p><p>　　ofstream wfile;</p><p>　　rfile.open(name,ios::in|ios::binary);</p><p>　　wfile.open("Encolding.txt",ios::out|ios::binary);</p><p>　　int ii;

48、 //缺位標記</p><p>　　bool jump = 0;</p><p>　　const char sign = (char)1;</p><p><b>　　char c;</b></p><p>　　unsigned char ch;<

49、;/p><p><b>　　long l,m;</b></p><p>　　l = rfile.tellg();</p><p>　　rfile.seekg(0,ios::end);</p><p>　　m = rfile.tellg();</p><p>　　rfile.seekg(0,ios::b

50、eg);</p><p>　　static long count = m-l;</p><p><b>　　size = 0;</b></p><p>　　for(int i = 0;i<256;i++) //初始化哈弗曼樹</p><p>　　{ T[i].value =

51、 i;</p><p>　　T[i].weight = 0;</p><p>　　T[i].lchild = 0;</p><p>　　T[i].rchild = 0;</p><p>　　T[i].parent = 0;}</p><p><b>　　//還原哈弗曼樹</b></p>

52、<p>　　while(count)</p><p>　　{ rfile.get(c);</p><p><b>　　count--;</b></p><p><b>　　ii = c;</b></p><p>　　while(count)</p><p>

53、　　{ rfile.get(c);</p><p><b>　　count--;</b></p><p>　　if(c!=sign)</p><p>　　{ ch = c;</p><p>　　int i = ch;</p><p>　　T[i].value = ch;</p>

54、<p>　　rfile.get(c);</p><p><b>　　count--;</b></p><p><b>　　ch = c;</b></p><p>　　T[i].weight = (long)ch;}</p><p><b>　　else</b><

55、;/p><p><b>　　break;}</b></p><p>　　CreateHuffmanTree();</p><p><b>　　break;}</b></p><p><b>　　//解壓文件</b></p><p>　　static int

56、pp,ss=-1; //記錄位置 pp正待訪問的位置，ss字節(jié)末尾</p><p>　　int bt[16];</p><p><b>　　pp = 0;</b></p><p>　　while(count)</p><p>　　{ rfile.get(c);</p&

57、gt;<p><b>　　count--;</b></p><p>　　if(count==0)</p><p>　　{ ch = c;</p><p><b>　　int i;</b></p><p>　　for(i = ss+8;ch>0;i--)</p>

58、<p>　　{ bt[i] = ch%2;</p><p>　　ch = ch/2;}</p><p><b>　　if(i!=ss)</b></p><p>　　{ for(;i>=0;i--)</p><p>　　{bt[i] = 0;}}</p><p>　　bt[s

59、s+ii] = '#';</p><p>　　ss = ss+ii;}</p><p><b>　　else</b></p><p>　　{ ch = c;</p><p><b>　　int i;</b></p><p>　　for(i = ss+8;c

60、h>0;i--)</p><p>　　{ bt[i] = ch%2;</p><p>　　ch = ch/2;}</p><p><b>　　if(i!=ss)</b></p><p>　　{for(;i>ss;i--){</p><p>　　bt[i] = 0;}}</p&

61、gt;<p>　　ss = ss+8;}</p><p>　　HuffmanTree *pointer;</p><p>　　while(pp<8)</p><p>　　{ pointer = root; //指向根結(jié)點</p><p>　　while(pointer->

62、;lchild&&pointer->rchild)</p><p>　　{ if(bt[pp]== 1)</p><p>　　{pointer = pointer->lchild;}</p><p>　　else if(bt[pp]==0)</p><p>　　{pointer = pointer->rc

63、hild;}</p><p><b>　　else</b></p><p>　　{ jump =1;</p><p><b>　　break;}</b></p><p><b>　　pp++;</b></p><p>　　if(pp == ss+1)

64、 //如果字節(jié)末尾已訪問則再讀入字節(jié)</p><p>　　{ pp = 0;</p><p><b>　　int i;</b></p><p>　　rfile.get(c);</p><p><b>　　count--;</b></p>

65、;<p>　　if(count==0)</p><p>　　{ ch = c;</p><p>　　for(i = 7;ch>0;i--)</p><p>　　{ bt[i] = ch%2;</p><p>　　ch = ch/2;}</p><p><b>　　if(i!=-1)

66、</b></p><p>　　{ for(;i>=0;i--)</p><p>　　{bt[i] = 0;}}</p><p>　　bt[ii] = '#';</p><p><b>　　ss = ii;}</b></p><p><b>　　els

67、e</b></p><p>　　{ int i;</p><p><b>　　ch = c;</b></p><p>　　for(i = 7;ch>0;i--)</p><p>　　{ bt[i] = ch%2;</p><p>　　ch = ch/2;}</p&g

68、t;<p><b>　　ss = 7;</b></p><p><b>　　if(i!=-1)</b></p><p>　　{for(;i>=0;i--){</p><p>　　bt[i] = 0;}}}}}</p><p><b>　　if(ss>7)</

69、b></p><p>　　{ int j = 0;</p><p>　　for(int i = pp;i<=ss;i++,j++)</p><p>　　{bt[j] = bt[i];}</p><p><b>　　ss = --j;</b></p><p><b>　　p

70、p = 0;}</b></p><p><b>　　if(jump)</b></p><p>　　{if(bt[pp]=='#'){</p><p><b>　　break;}}</b></p><p><b>　　else</b></p>

71、;<p>　　{ wfile.put(char(pointer->value-128));}}//while(pp<8}</p><p>　　rfile.close();</p><p>　　wfile.close();}</p><p><b>　　題目二</b></p><p><b&

72、gt;　　1．需求規(guī)格說明</b></p><p>　　灰度圖像壓縮/解壓縮類的實現(xiàn)（動態(tài)規(guī)劃算法的應用）</p><p><b>　　【問題描述】</b></p><p>　　灰度圖像的像素值范圍在[0，255]之間，如果采用一個像素一個字節(jié)的存儲方式，勢必會造成空間的浪費。如果采用一定的無損壓縮算法，可以大大提高減小文件大小，減

73、少存儲空間。本課題要求針對提供的256色（8位）位圖數(shù)據(jù)，采用教材上第15章動態(tài)規(guī)劃中圖像壓縮算法（圖像分段合并的思想），設計一個類，實現(xiàn)灰度位圖數(shù)據(jù)的壓縮和解壓過程。</p><p><b>　　【基本要求】</b></p><p>　　一個完整的灰度圖像類應具有以下功能：</p><p>　?。?）對8位位圖數(shù)據(jù)的讀功能，提供ReadBit

74、map方法。</p><p>　　ReadBitmap方法有一個參數(shù)為輸入位圖文件名(*.bmp)，它能解析8位位圖文件格式，獲取位圖BITMAPINFOHEADER信息和每個像素的數(shù)據(jù)信息，放入內(nèi)存中。</p><p>　?。?）對8位位圖數(shù)據(jù)的寫功能，提供WriteBitmap方法。</p><p>　　WriteBitmap方法有一個參數(shù)為輸出位圖文件名(*.

75、bmp)，它能將內(nèi)存中的位圖文件信息，按照位圖格式，寫到位圖文件中保存。</p><p>　?。?）灰度圖像壓縮功能，提供Compress方法。</p><p>　　Compress方法有一個參數(shù)為輸出壓縮文件名(*.img) ，它能將已經(jīng)裝入到內(nèi)存中的8位位圖信息，進行壓縮，形成段標題和以變長格式存儲的像素的二進制串，寫入到文件中（注意：Img文件格式自行定義）。</p>

76、<p>　?。?）灰度圖像解壓功能，提供UnCompress方法。</p><p>　　UnCompress方法有一個參數(shù)為輸入壓縮文件名(*.img)，它能解析Img文件格式，將其在內(nèi)存中解壓縮為8位位圖信息，以便輸出為位圖文件。</p><p>　?。?）以上是該灰度圖像類基本的四個方法，在實現(xiàn)時可根據(jù)需要擴充其他方法。在設計時，要使用面向?qū)ο蟮乃枷?，考慮各個成員的訪問權(quán)限。

77、</p><p><b>　　【提高要求】</b></p><p>　　（1）基于Windows對話框界面，可選擇輸入/輸出文件名，有壓縮進度條顯示。</p><p>　　（2）采用不同的數(shù)據(jù)集，比較其壓縮比，采用最有效的壓縮方式。</p><p><b>　　【測試數(shù)據(jù)】</b></p>

78、;<p>　　數(shù)字化.bmp，636*455*8</p><p>　　紋理.bmp， 512*512*8</p><p><b>　　【測試用例】</b></p><p><b>　　類的測試用例如下：</b></p><p>　　CCompressImage Test;</

79、p><p>　　Test. ReadBitmap(“數(shù)字化.bmp”); 讀原始位圖</p><p>　　Test. Compress(“Out.img”); 壓縮</p><p>　　Test. UnCompress(“Out.img”); 解壓</p><p>　　Test. WriteBitmap(“

80、Out.bmp”); 還原位圖信息</p><p><b>　　測試結(jié)果：</b></p><p>　　可以使用ACDSee打開兩幅位圖，比較其屬性信息及文件大小，驗證你所實現(xiàn)的灰度圖像類是否做到了無損壓縮。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　有關8位

81、的位圖格式可以參考MSDN中BITMAPINFOHEADER結(jié)構(gòu)的說明文檔，注意其中biBitCount=8的說明。</p><p><b>　　2．總體分析與設計</b></p><p><b>　?。?）設計思想：</b></p><p>　　存儲結(jié)構(gòu)主要是采取動態(tài)分配內(nèi)存的方法用數(shù)組進行存儲主要算法思想是動態(tài)規(guī)劃思想

82、和移位，拼接。</p><p>　　先讀位圖，將里面的Fileheader，Infoheader和調(diào)色板讀出來，然后將位圖的灰度值讀出來，放進一個GLubyte型的數(shù)組里，然后進行第一次分段，把像素存儲位相同的分在一起，并記錄下段的長度和存儲的位數(shù)，再利用動態(tài)規(guī)劃的思想進行第二次分段，找出每段中存儲位數(shù)最長的，然后算出總的位數(shù)，再計算出所需int型數(shù)組的長度，將每個灰度值按其需要的長度拼成32位然后一次性寫進文件

83、，在此之前還需要將Fileheader，Infoheader和調(diào)色板寫進文件。這就是壓縮過的圖像。解碼的時候先從壓縮的文件中將Fileheader，Infoheader和調(diào)色板讀出來，然后根據(jù)前面記錄下來的段的長度和存儲位數(shù)進行解碼。</p><p><b>　　（2）設計表示：</b></p><p>　　MFC是基于對話框的，工程名字叫做BitMapCompres

84、s，調(diào)用過程比較簡單，就兩個類，由BitMapCompressDlg來調(diào)用類MyMap，MyMap里有讀位圖，壓縮，寫文件和解壓，具體調(diào)用如下圖：</p><p>　　BitMapCompressDlg</p><p><b>　　MyMap </b></p><p>　　表示它們之間的調(diào)用關系。）</p><p>　　

85、（3）詳細設計表示：</p><p>　　class Huffman</p><p><b>　　{</b></p><p>　　friend BinaryTree HuffmanTree(int a[],int n);</p><p><b>　　public:</b></p>&

86、lt;p>　　operator int()const{return weight;}</p><p><b>　　public:</b></p><p>　　Huffman(){}</p><p>　　~Huffman(){}</p><p>　　BinaryTree HuffmanTree(int a[],int

87、 n)</p><p><b>　　{</b></p><p>　　Huffman *w=new Huffman[n+1];</p><p>　　BinaryTree z;</p><p>　　BinaryTree zero;</p><p>　　for(int i=1;i<=n;i++)&

88、lt;/p><p><b>　　{</b></p><p>　　z.MakeTree(i,zero,zero);</p><p>　　w[i].weight=a[i-1];</p><p>　　w[i].tree=z;</p><p><b>　　}</b></p>

89、<p>　　MinHeap<Huffman> H(1);</p><p>　　H.Initialize(w,n,n);</p><p>　　Huffman x,y;</p><p>　　for(int i=1;i<n;i++)</p><p><b>　　{</b></p>&

90、lt;p>　　H.DeleteMin(x);</p><p>　　H.DeleteMin(y);</p><p>　　z.MakeTree(0,x.tree,y.tree);</p><p>　　x.weight+=y.weight;</p><p><b>　　x.tree=z;</b></p>&

91、lt;p>　　H.Insert(x);</p><p><b>　　}</b></p><p>　　H.DeleteMin(x);</p><p>　　H.Deactivate();</p><p>　　delete []w;</p><p>　　return x.tree;</p&g

92、t;<p><b>　　}</b></p><p><b>　　private:</b></p><p>　　BinaryTree tree;</p><p>　　int weight;</p><p><b>　　};</b></p><p&

93、gt;　　struct ReInfo1</p><p><b>　　{</b></p><p>　　BYTE data;</p><p>　　BYTE *code;</p><p>　　BYTE number;</p><p><b>　　};</b></p>

94、<p>　　struct ReInfo2</p><p><b>　　{</b></p><p>　　BYTE data;</p><p>　　WORD *code;</p><p>　　BYTE number;</p><p><b>　　};</b></p

95、><p>　　struct ReInfo3</p><p><b>　　{</b></p><p>　　BYTE data;</p><p>　　unsigned int *code;</p><p>　　BYTE number;</p><p><b>　　};&l

96、t;/b></p><p>　　class MyTree</p><p><b>　　{</b></p><p><b>　　public:</b></p><p><b>　　MyTree();</b></p><p>　　~MyTree();&

97、lt;/p><p>　　bool Read(CString c);</p><p>　　void MakeHuffmanTree(BinaryTree &m_tree);</p><p>　　void InOrderTree();</p><p>　　bool Write(CString c,CProgressCtrl *progress

98、);</p><p>　　void Depress(CString c);</p><p>　　void Decode(CString c,CProgressCtrl *progress);</p><p><b>　　private:</b></p><p>　　CFile m_rfile;</p>&l

99、t;p>　　CFile m_wfile;</p><p>　　CFile m_rf;</p><p>　　int arry[256];</p><p>　　Huffman m_hfm;</p><p>　　BinaryTree m_r;</p><p>　　ReInfo1 *m_refo1;</p>

100、<p>　　ReInfo2 *m_refo2;</p><p>　　ReInfo3 *m_refo3;</p><p>　　Info *info;</p><p>　　BYTE *pnt;</p><p>　　unsigned int *re;</p><p><b>　　int gn;</

101、b></p><p><b>　　BYTE n1;</b></p><p><b>　　BYTE n2;</b></p><p><b>　　BYTE n3;</b></p><p><b>　　int nb;</b></p><

102、p>　　BYTE more;</p><p><b>　　};</b></p><p><b>　　3．編碼</b></p><p>　　問題一：不知道怎么讀位圖，后來看了ppt上面講了一點點，然后上網(wǎng)查了點資料才確位圖的函數(shù)。</p><p>　　問題二：在調(diào)試代碼的時候，中間有一次出現(xiàn)了死

103、循環(huán)，后來才知道自己犯了一個錯誤是把將灰度值為0的表示位數(shù)寫成了0。</p><p>　　問題三：壓縮時我想利用題目一中壓縮的辦法，就得把每個m_data每個位數(shù)都記錄下來，可是一開始我把段數(shù)和m_data的個數(shù)給弄混了，所以就花了很長時間。</p><p>　　問題四：解碼時在記錄每段長度的類型，因為要寫進文件，所以希望它盡可能的小，所以一開始采用的是BYTE型，但是一旦大于256，就會

104、出錯，變成了另外的一個數(shù)，但是用int存又太大，所以就把每個位數(shù)都減1，這樣就不會出現(xiàn)之前那樣的問題了，但是用的時候要加1。</p><p><b>　　4．程序及算法分析</b></p><p><b>　　界面</b></p><p><b>　　壓縮</b></p><p&g

105、t;<b>　　解壓</b></p><p><b>　　【參考資料】</b></p><p>　　Sartaj Sahni著，《數(shù)據(jù)結(jié)構(gòu)、算法與應用》，機械工業(yè)出版社</p><p>　　殷人昆 等編著，數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++語言描述)》，清華大學出版社</p><p>　　嚴蔚敏，吳偉