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

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

2、;b>　　指導(dǎo)教師： </b></p><p>　　成 績： </p><p>　　2011年 12 月</p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p><b>　　題目一</b></p><p>&

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

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

5、值，壓縮前后文件的大?。?，在屏幕上輸出。</p><p>　?。?）壓縮。利用已建好的哈夫曼樹，對文件進(jìn)行編碼，并將哈夫曼編碼及文件編碼后的數(shù)據(jù)一起寫入文件中，形成壓縮文件(*.Haf)。</p><p>　?。?）解壓縮。打開已有壓縮文件(*.Haf)，讀取其中的哈夫曼編碼，構(gòu)建哈夫曼樹，讀取其中的數(shù)據(jù)，進(jìn)行譯碼后，寫入文件，完成解壓縮。</p><p>　?。?

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

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

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．總體分析與設(shè)計(jì)</b></p><p><b>　　（1）設(shè)計(jì)思想：</b></p><p>　　1)添加2個(gè)類 HuffmanTree(Huffman樹的葉子結(jié)點(diǎn)類), Huffman（壓縮/解壓函</p>&l

10、t;p><b>　　類）</b></p><p>　　2）添加文件，完成對于指定文件的分析工作</p><p>　　所有的文件都可以看做是二進(jìn)制數(shù)據(jù)組成的。以二進(jìn)制方式打開文件，依次讀取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>　　以二進(jìn)制方式新建目標(biāo)文件，比如：Encolding.haf。將Huffman樹的信息放到文件開始部分</p><p><b>　　5）形成壓縮文件</b></p><p>

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

13、，寫入到新文件中。</p><p><b>　?。?）設(shè)計(jì)表示：</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>　?。?）詳細(xì)設(shè)計(jì)表示：</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é)點(diǎn)</p><p>　　LinkedQueue<int>

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

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

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

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

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

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

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

29、據(jù)結(jié)構(gòu)來減少內(nèi)存空間的分配，此程序最大的問題在于，但文件比較大時(shí)，壓縮就會出現(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、 //缺位標(biāo)記</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é)點(diǎn)</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>　　灰度圖像壓縮/解壓縮類的實(shí)現(xiàn)（動(dòng)態(tài)規(guī)劃算法的應(yīng)用）</p><p><b>　　【問題描述】</b></p><p>　　灰度圖像的像素值范圍在[0，255]之間，如果采用一個(gè)像素一個(gè)字節(jié)的存儲方式，勢必會造成空間的浪費(fèi)。如果采用一定的無損壓縮算法，可以大大提高減小文件大小，減

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

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

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

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

77、</p><p><b>　　【提高要求】</b></p><p>　?。?）基于Windows對話框界面，可選擇輸入/輸出文件名，有壓縮進(jìn)度條顯示。</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打開兩幅位圖，比較其屬性信息及文件大小，驗(yàn)證你所實(shí)現(xiàn)的灰度圖像類是否做到了無損壓縮。</p><p><b>　　【實(shí)現(xiàn)提示】</b></p><p>　　有關(guān)8位

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

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

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

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

85、（3）詳細(xì)設(shè)計(jì)表示：</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上面講了一點(diǎn)點(diǎn)，然后上網(wǎng)查了點(diǎn)資料才確位圖的函數(shù)。</p><p>　　問題二：在調(diào)試代碼的時(shí)候，中間有一次出現(xiàn)了死

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

104、出錯(cuò)，變成了另外的一個(gè)數(shù)，但是用int存又太大，所以就把每個(gè)位數(shù)都減1，這樣就不會出現(xiàn)之前那樣的問題了，但是用的時(shí)候要加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īng)用》，機(jī)械工業(yè)出版社</p><p>　　殷人昆 等編著，數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC++語言描述)》，清華大學(xué)出版社</p><p>　　嚴(yán)蔚敏，吳偉