數(shù)據(jù)結構課程設計報告 (4)

1、<p>　　數(shù)據(jù)結構課程設計報告</p><p><b>　　壓縮軟件</b></p><p>　　---采用哈夫曼編碼技術</p><p>　　學 號： </p><p>　　姓 名： </p><p>　　指導教

2、師： </p><p>　　二○○七年九月七日星期五</p><p><b>　　目錄</b></p><p>　　目錄…………………………………………………..2</p><p>　　課程設計課題……………………………………………3</p><p>　　設計要求及分

3、析…………………………………………3</p><p>　　軟件開發(fā)…………………………………………………3</p><p>　　軟件程序基本介紹………………………………………4</p><p>　　程序代碼及功能介紹……………………………………4</p><p>　　---------建立哈夫曼樹、壓縮、解壓縮</p><

4、p>　　收獲與體會……………………………………………10</p><p>　　附錄……………………………………………………11</p><p>　　軟件使用說明及圖示…………………………………11</p><p>　　【一．】課程設計課題：</p><p><b>　　壓縮軟件</b></p><

5、;p>　　【二．】課程設計要求及分析：</p><p><b>　　要求：</b></p><p>　　準備一個文件，統(tǒng)計該文件中各種字符的頻率，對各字符進行Huffman編碼，將該文件翻譯成Huffman編碼文件，再將Huffman編碼文件翻譯成源文件。</p><p>　　數(shù)據(jù)壓縮理論及哈夫曼樹簡介：</p><p

6、>　　數(shù)據(jù)壓縮有2種基本類型：無損壓縮和有損壓縮,使用無損壓縮方法壓縮的文件不會丟失任何信息,他與原文件具有可逆性,就是可以通過解壓縮的方法恢復原來的數(shù)據(jù),通常對文本文件,字處理文件,應用程序等采用這種算法。有損壓縮算法在壓縮時回丟失一些信息，壓縮后不能完整恢復出原有信息，較多應用于音頻，視頻圖象數(shù)據(jù)的處理。</p><p>　　此處我們所實現(xiàn)的是哈夫曼算法，在計算機信息處理中，哈夫曼編碼是一種變長編碼法（

7、又稱“熵編碼法”），用于數(shù)據(jù)的無損壓縮著一術語是指用一張?zhí)厥獾木幋a表對源字符進行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個源字符出現(xiàn)的估算概率而建立起來的（出現(xiàn)頻率高的字符使用教短的編碼，出現(xiàn)頻率高的則使用教長的，使編碼后的字符串的平均期望長度降低，從而達到無損壓縮數(shù)據(jù)的目的），同時保持編碼的唯一可解性，這種方法是由美國科學家David.A.Huffman發(fā)展起來的。哈夫曼樹是哈夫曼算法的理論描述工具，也稱最優(yōu)二叉樹，是一種加權路徑

8、長度最短的二叉樹。加權路徑長度是指樹中所有葉子結點的權值乘上其到根結點的路徑長度。N個葉子結點的哈夫曼樹共有2n-1個結點，這個性質將運用于使用數(shù)組結構存儲哈夫曼樹，從根結點開始，左子結點分配0，右子結點分配1，沿著樹根到各個結點就得到了哈夫曼編碼，因為所有被編碼的字符都作為葉子結點出現(xiàn)而每個葉子結點路徑又是獨立的，保障了每個編碼都不會四其余碼的前綴，這樣的編碼又稱“哈夫曼無重復前綴編碼”，著在下面的程序段會應用到。</p>

9、<p>　　哈夫曼樹也應用于譯碼過程，譯碼過程中逐一掃描碼文，從哈夫曼的根結點開始，將掃描得到的二進制位串中的相鄰位與哈夫曼樹上的0，1匹配。</p><p><b>　　需求分析：</b></p><p>　　設計目標是要實現(xiàn)哈夫曼壓縮的編碼器和譯碼器。碼器工作如下：首先讀入待壓縮文件為了保證與原文件信息完全一致，對文件的讀寫都采用二進制的方式進行。然

10、后建立并分析字母表，最多只有256種可能的符，對每種字符出現(xiàn)的頻度進行統(tǒng)計，以頻度作為建立哈夫曼樹的權值。頻度表建立好以后，可以建立哈夫曼樹，對出現(xiàn)的每種字符進行哈夫曼編碼。此時再讀入原文件，逐個字節(jié)進行編碼，將得到的編碼流逐個寫入文件。譯碼過程相對簡單：讀入被壓縮文件，將其解釋為比特流，根據(jù)哈夫曼樹對比特流逐個譯碼，將譯碼結果逐個寫到磁盤文件。</p><p><b>　　【三．】軟件開發(fā)：</

11、b></p><p>　　該軟件是在Visual C++6.0環(huán)境下編譯和運行的,運行時可以直接雙擊圖標: 。Visual C++6.0是在Windows環(huán)境下運行C++的集成環(huán)境。Visual C++6.0由許多組件組成，包括編輯器、調試器以及程序向導AppWizard、類向導Class Wizard等開發(fā)工具。 這些組件通過一個名為Developer Studio的組件集成為和諧的開發(fā)環(huán)境。</p

12、><p>　　【四．】軟件程序基本介紹：</p><p>　　該壓縮軟件程序結構采用的是1個CPP文件和一個HEAD文件,界面采用菜單提示輸入。</p><p>　　【五．】程序代碼及功能介紹：</p><p><b>　　1．函數(shù)結構</b></p><p>　　在head.h文件中共有3個函數(shù)，分

13、別為：void Select(int k,int &s1,int &s2)</p><p>　　void compress()</p><p>　　void uncompress()</p><p>　　其中void Select(int k,int &s1,int &s2)是在void compress()中調用的，他的功能是在K個

14、元素中選擇權值最小的兩個結點S1，S2；</p><p>　　void compress()和void uncompress()是在a.cpp的main函數(shù)中被調用的，他們的功能分別是壓縮和解壓縮。</p><p>　　2．函數(shù)結構圖如下：</p><p><b>　　3．數(shù)據(jù)結構設計</b></p><p>　　哈夫曼

15、算法的實現(xiàn)可以采用鏈表結構生成哈夫曼樹，但是效率比較低，也可以使用堆排序，這里采用的是線形表的順序存儲結構：</p><p>　　struct head </p><p><b>　　{</b></p><p>　　unsigned char b; //記錄字符在數(shù)組中的位置</p><p>　　l

16、ong count; //字符出現(xiàn)頻率（權值） </p><p>　　long parent,lch,rch; //定義哈夫曼樹指針變量 </p><p>　　char bits[256]; //定義存儲哈夫曼編碼的數(shù)組</p><p><b>　　} </b></p><p&g

17、t;　　該存儲結構在二叉樹中的結點結構如下：</p><p><b>　　4．功能設計</b></p><p>　　compress函數(shù)：</p><p>　　該函數(shù)將完成壓縮目標文件的功能，首先輸入文件名，讀取目標文件ifp=fopen(filename,"rb")，這里”rb”是按二進制方式進行讀操作，輸入壓縮后的文件名

18、fopen(outputfile,"wb")，其中”wb”是打開或建立一個二進制文件，只允許寫數(shù)據(jù)。(filename為需要壓縮的文件名，outputfile為完成壓縮后的文件名)</p><p>　　while(!feof(ifp))</p><p><b>　　{</b></p><p>　　fread(&c,1

19、,1,ifp); </p><p>　　fread(buffer,size,count,fp),</p><p>　　header[c].count++; //字符重復出現(xiàn)頻率加1</p><p>　　flength++; //出現(xiàn)字符則原文長度加1</p><p><b>　　}</b><

20、;/p><p>　　feof()為文件檢測函數(shù)，若文件沒有結束返回是0，當文件結束時返回1。</p><p>　　fread（）是從一個流中讀數(shù)據(jù)，fread(buffer,size,count,fp),其中buffer是一個指針，在fread函數(shù)中，它表示存放輸入數(shù)據(jù)的首地址。 size 表示數(shù)據(jù)塊的字節(jié)數(shù)。count 表示要讀寫的數(shù)據(jù)塊塊數(shù)。fp 表示文件指針。 </p>&

21、lt;p>　　for(i=0;i<512;i++) </p><p><b>　　{</b></p><p>　　if(header[i].count!=0) header[i].b=(unsigned char)i; //如果該字符出現(xiàn)過，將他的哈夫曼碼值及其對應的ASCII碼存放在一維數(shù)組header[i]中，且編碼表中的下標和ASCII碼滿足順序存放

22、關系。</p><p>　　else header[i].b=0; </p><p>　　header[i].parent=header[i].lch=header[i].rch=-1; //是對結點進行初始化。</p><p><b>　　} </b></p><p><b>　　建立哈夫曼樹：</b&

23、gt;</p><p>　　for(i=0;i<256;i++) //根據(jù)頻率（權值）大小，對結點進行排序，選擇較小的結點進樹。</p><p><b>　　{</b></p><p>　　for(j=i+1;j<256;j++)</p><p><b>　　{</b></p

24、><p>　　if(header[i].count<header[j].count)</p><p><b>　　{</b></p><p>　　tmp=header[i];</p><p>　　header[i]=header[j]; </p><p>　　header[j]=tmp; <

25、;/p><p><b>　　} </b></p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　根據(jù)哈夫曼樹的性質，n個葉子結點（權）需要2n-1個結點來構建一棵哈夫曼樹：</p><p>　　for(i=n;

26、i<m;i++) </p><p><b>　　{</b></p><p>　　Select(i-1,s1,s2);</p><p>　　header[s1].parent=header[s2].parent=i;</p><p>　　header[i].lch=s1;</p><p>

27、　　header[i].rch=s2;</p><p>　　header[i].count=header[s1].count+header[s2].count;</p><p><b>　　}</b></p><p>　　header[i].lch=s1; //計算左分支權值大小；</p><p>　　head

28、er[i].rch=s2; //計算右分支權值大??；</p><p>　　header[s1].parent=header[s2].parent=i;依據(jù)parent域值（結點層數(shù)）確定樹中結點之間的關系；</p><p>　　header[i].count=header[s1].count+header[s2].count; //父結點的權值為其左孩子和右孩子權值之和；<

29、/p><p>　　構建哈夫曼樹時用到了一個Select()函數(shù)：在K個元素中選擇父結點不為-1的權值最小的兩個結點S1，S2；</p><p>　　void Select(int k,int &s1,int &s2)</p><p><b>　　{</b></p><p><b>　　s1,s2=0

30、;</b></p><p>　　long min1=9999999;</p><p>　　for(int j=1;j<k;j++)</p><p>　　if (header[j].parent!=-1) </p><p><b>　　{</b></p><p>　　if (hea

31、der[j].count<header[s1].count)</p><p><b>　　{</b></p><p><b>　　s2=s1;</b></p><p><b>　　s1=j;</b></p><p><b>　　}</b></p

32、><p>　　elseif(header[j].count<header[s2].count)</p><p><b>　　s2=j;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　lon

33、g min1=9999999;假設字符出現(xiàn)頻率的最大值（最大權值），比較如下圖：</p><p>　　哈夫曼無重復前綴編碼：</p><p>　　for(i=0;i<n;i++) </p><p><b>　　{</b></p><p><b>　　f=i; </b></p>

34、<p>　　header[i].bits[0]=0; </p><p>　　while(header[f].parent!=-1) </p><p><b>　　{</b></p><p><b>　　j=f; </b></p><p>　　f=header[f].parent; &l

35、t;/p><p>　　if(header[f].lch==j) //置左分支編碼0；</p><p><b>　　{</b></p><p>　　j=strlen(header[i].bits); </p><p>　　memmove(header[i].bits+1,header[i].bits,j+1); //依次存

36、儲連接”0””1”編碼；</p><p>　　header[i].bits[0]='0'; </p><p><b>　　}</b></p><p>　　else //置右分支編碼1</p><p><b>　　{</b></p><p>　　j=strle

37、n(header[i].bits); </p><p>　　memmove(header[i].bits+1,header[i].bits,j+1); </p><p>　　header[i].bits[0]='1'; </p><p><b>　　} </b></p><p><b>　　}

38、</b></p><p><b>　　}</b></p><p>　　其中header[i].bits[0]=0;根結點編碼0。</p><p>　　將編碼好的數(shù)據(jù)寫入文件：</p><p>　　fseek(ifp,0,SEEK_SET); 從文件開始位置向前移動0字節(jié)，即定位到文件開始位置</p&

39、gt;<p>　　fwrite(&flength,sizeof(int),1,ofp); 用來將數(shù)據(jù)寫入文件流中，參數(shù)flength指向欲寫入的數(shù)據(jù)地址， 總共寫入的字符數(shù)以參數(shù)size*int來決定，返回實際寫入的int數(shù)目；</p><p>　　buf[0]=0;定義緩沖區(qū),它的二進制表示00000000。</p><p>　　while(!feof(ifp))

40、</p><p><b>　　{</b></p><p>　　c=fgetc(ifp); </p><p><b>　　f++; </b></p><p>　　for(i=0;i<n;i++) </p><p><b>　　{</b></p&

41、gt;<p>　　if(c==header[i].b) break; </p><p><b>　　}</b></p><p>　　strcat(buf,header[i].bits); </p><p>　　j=strlen(buf);</p><p><b>　　c=0; </b>

42、</p><p>　　下面對哈夫曼編碼位操作進行壓縮存儲：</p><p>　　while(j>=8) </p><p><b>　　{</b></p><p>　　for(i=0;i<8;i++) </p><p><b>　　{</b></p>

43、;<p>　　if(buf[i]=='1') c=(c<<1)|1; </p><p>　　else c=c<<1; </p><p><b>　　}</b></p><p>　　fwrite(&c,1,1,ofp); </p><p><b>　　

44、pt1++; </b></p><p>　　strcpy(buf,buf+8); </p><p>　　j=strlen(buf); </p><p><b>　　}</b></p><p>　　if(f==flength) break; </p><p><b>　　}

45、</b></p><p>　　其中strcpy(buf,buf+8);是將一個字節(jié)一個字節(jié)地拼接起來，pt1是統(tǒng)計壓縮以后文件長度的。</p><p>　　對哈夫曼編碼位操作進行壓縮存儲：</p><p><b>　　if(j>0) </b></p><p><b>　　{</b>

46、;</p><p>　　strcat(buf,"00000000"); </p><p>　　for(i=0;i<8;i++) </p><p><b>　　{</b></p><p>　　if(buf[i]=='1') c=(c<<1)|1; </p>

47、<p>　　else c=c<<1; </p><p><b>　　}</b></p><p>　　fwrite(&c,1,1,ofp); </p><p><b>　　pt1++; </b></p><p><b>　　}</b></p&

48、gt;<p><b>　　數(shù)據(jù)寫入：</b></p><p>　　for(i=0;i<n;i++) </p><p><b>　　{</b></p><p>　　fwrite(&(header[i].b),1,1,ofp); </p><p>　　c=strlen(hea

49、der[i].bits); </p><p>　　fwrite(&c,1,1,ofp); </p><p>　　j=strlen(header[i].bits); </p><p>　　if(j%8!=0) 若存儲的位數(shù)不是8的倍數(shù)，則補0；</p><p><b>　　{</b></p><

50、;p>　　for(f=j%8;f<8;f++) </p><p>　　strcat(header[i].bits,"0"); </p><p><b>　　}</b></p><p>　　while(header[i].bits[0]!=0) </p><p><b>　　{&l

51、t;/b></p><p><b>　　c=0; </b></p><p>　　for(j=0;j<8;j++) //字符的有效存儲不超過8位，則對有效位數(shù)左移實現(xiàn)兩字符編碼的連接</p><p><b>　　{</b></p><p>　　if(header[i].bits[j]

52、=='1') c=(c<<1)|1; // |1不改變原位置上的"0""1"值；</p><p>　　else c=c<<1; </p><p><b>　　}</b></p><p>　　strcpy(header[i].bits,header[i].bits+

53、8); //把字符的編碼按原先存儲順序連接。</p><p>　　fwrite(&c,1,1,ofp); </p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　uncompress函數(shù)：</p><p>　　該函數(shù)

54、完成的功能是將一個目標壓縮文件解壓還原，首先輸入文件名，讀取目標文件ifp=fopen(filename,"rb")，這里”rb”是按二進制方式進行讀操作，輸入壓縮后的文件名fopen(outputfile,"wb")，其中”wb”是打開或建立一個二進制文件，只允許寫數(shù)據(jù)。</p><p>　　fread(&flength,sizeof(long),1,ifp);讀

55、取原文件長度，對文件進行定位。</p><p>　　fread(&f,sizeof(long),1,ifp); </p><p>　　fseek(ifp,f,SEEK_SET); </p><p>　　fread(&n,sizeof(long),1,ifp); </p><p>　　for(i=0;i<n;i++) &l

56、t;/p><p><b>　　{</b></p><p>　　fread(&header[i].b,1,1,ifp); </p><p>　　fread(&c,1,1,ifp); </p><p>　　p=(long)c; 讀取原文件字符的權值；</p><p>　　header[i

57、].count=p; </p><p>　　header[i].bits[0]=0; </p><p>　　if(p%8>0) m=p/8+1; </p><p>　　else m=p/8; </p><p>　　for(j=0;j<m;j++) </p><p><b>　　{</b>

58、;</p><p>　　fread(&c,1,1,ifp); </p><p><b>　　f=c; </b></p><p>　　itoa(f,buf,2); //將f轉換為二進制表示的字符串</p><p>　　f=strlen(buf); </p><p>　　for(l=8;l&g

59、t;f;l--) </p><p><b>　　{</b></p><p>　　strcat(header[i].bits,"0"); </p><p><b>　　}</b></p><p>　　strcat(header[i].bits,buf); </p>&

60、lt;p><b>　　} </b></p><p>　　header[i].bits[p]=0; </p><p><b>　　}</b></p><p>　　for(i=0;i<n;i++) //根據(jù)哈夫曼編碼的長短，對結點進行排序：</p><p><b>　　{<

61、;/b></p><p>　　for(j=i+1;j<n;j++) </p><p><b>　　{</b></p><p>　　if(strlen(header[i].bits)>strlen(header[j].bits)) </p><p><b>　　{</b></p

62、><p>　　tmp=header[i]; </p><p>　　header[i]=header[j]; </p><p>　　header[j]=tmp; </p><p><b>　　} </b></p><p><b>　　} </b></p><p&

63、gt;<b>　　} </b></p><p><b>　　解碼：</b></p><p>　　通過哈夫曼編碼的長短，依次解碼，從原來的位存儲還原到字節(jié)存儲</p><p><b>　　while(1) </b></p><p><b>　　{</b>&l

64、t;/p><p>　　while(strlen(bx)<(unsigned int)p) </p><p><b>　　{</b></p><p>　　fread(&c,1,1,ifp); </p><p><b>　　f=c; </b></p><p>　　ito

65、a(f,buf,2); </p><p>　　f=strlen(buf); </p><p>　　for(l=8;l>f;l--) //在單字節(jié)內對相應位置補0</p><p><b>　　{</b></p><p>　　strcat(bx,"0"); </p><p>

66、<b>　　}</b></p><p>　　strcat(bx,buf); </p><p><b>　　}</b></p><p>　　for(i=0;i<n;i++) </p><p><b>　　{</b></p><p>　　if(memc

67、mp(header[i].bits,bx,header[i].count)==0) break; </p><p><b>　　}</b></p><p>　　strcpy(bx,bx+header[i].count); //從壓縮文件中的按位存儲還原到按字節(jié)存儲字符，字符位置不改變；</p><p>　　c=header[i].b; <

68、;/p><p>　　fwrite(&c,1,1,ofp); </p><p>　　m++; //m是用來統(tǒng)計解壓后的文件長度</p><p>　　if(m==flength) break; //flength是原文件長度； </p><p><b>　　}</b></p><p>　　fc

69、lose(ifp); </p><p>　　fclose(ofp);關閉文件。</p><p><b>　　【六】收獲與體會</b></p><p>　　1．靜態(tài)哈夫曼編碼方法有一些缺點：對于過短的文件進行編碼的意義不大，因為光以4BYTES的長度存儲哈夫曼樹的信息就需1024Bytes的存儲空間；</p><p>　　

70、2．對較大的文件進行編碼時，頻繁的磁盤讀寫訪問會降低數(shù)據(jù)編碼的速度。經過網(wǎng)上查詢已經有了改進之法--動態(tài)的哈夫曼編碼方法。動態(tài)哈夫曼編碼使用一棵動態(tài)變化的哈夫曼樹，對第t+1個字符的編碼是根據(jù)原始數(shù)據(jù)中前t個字符得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字符，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字符所需的時間與該字符的編碼長度成正比，所以動態(tài)哈夫曼編碼可

71、實時進行。動態(tài)哈夫曼編碼比靜態(tài)哈夫曼編碼復雜的多；</p><p>　　3．哈夫曼樹是哈夫曼編碼的應用，也是編碼和譯碼的核心，是連接編碼和譯碼的紐帶。該壓縮軟件采用的正是哈夫曼算法，建立哈夫曼樹，對原文件中的字符進行哈夫曼編碼，通過將哈夫曼算法應用與壓縮軟件，更進一步理解哈夫曼樹的建立和對各個葉子結點的編碼。哈夫曼壓縮技術對文本文件壓縮效率很高，對于2進制文件這種方法也很成功，但壓縮比沒有那么顯著；</p&

72、gt;<p>　　4．編碼不是唯一的，但用你的代碼算出來的是唯一的，所以傳輸一定要用自己的代碼解碼，構造好哈夫曼樹后，就可根據(jù)哈夫曼樹進行編碼。例如：字符根據(jù)其出現(xiàn)的概率作為權值構造一棵哈夫曼樹后，經哈夫曼編碼得到的對應的碼值。只要使用同一棵哈夫曼樹，就可把編碼還原成原來那組字符；</p><p>　　5．該程序中因為涉及文件操作，多次讀寫文件，為了保證操作后的文件與原文件的一致性，在打開或者建立新

73、文件時都是以二進制進行操作，著不僅加深了我們對文件操作的理解，也在程序中體現(xiàn)了完整性，并且將解壓后的文件和原文件相比較具有一致性，體現(xiàn)的程序的健壯性。</p><p><b>　　【七】附錄</b></p><p><b>　　源程序文件名清單：</b></p><p>　　head.h

74、 //完成壓縮和解壓功能函數(shù)</p><p>　　a.cpp //主函數(shù)</p><p>　　附：軟件使用說明及圖示：</p><p>　　一．使用說明：該壓縮軟件的使用界面十分簡明，運行環(huán)境為DOS操作系統(tǒng)，進入界面后，就會提示輸入字符串的輸入形式，結束符為“回車符”。分3個功能選項：1壓縮 2解壓 3退出，選擇1或者2時都會有

75、語句提醒你輸入被壓縮（解壓）的目標文件名及壓縮（解壓）后的生成文件名。</p><p>　　二．使用注意：壓縮的目標文檔需要在當前文件夾下，使用時可以直接輸入文件名（加后綴），解壓后的文件名同理。</p><p><b>　　三．圖示：</b></p><p><b>　　原始菜單界面：</b></p>&l