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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：13 大小：113.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩12頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告　　壓縮軟件　　---采用哈夫曼編碼技術(shù)　　學(xué) 號： 　　姓名： 　　指導(dǎo)教

2、師： 　　二○○七年九月七日星期五　　目錄　　目錄…………………………………………………..2　　課程設(shè)計課題……………………………………………3　　設(shè)計要求及分

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

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

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

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

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

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

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

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

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

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

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

14、元素中選擇權(quán)值最小的兩個結(jié)點(diǎn)S1，S2；　　void compress()和void uncompress()是在a.cpp的main函數(shù)中被調(diào)用的，他們的功能分別是壓縮和解壓縮。　　2．函數(shù)結(jié)構(gòu)圖如下：　　3．?dāng)?shù)據(jù)結(jié)構(gòu)設(shè)計　　哈夫曼

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

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

17、t;　　該存儲結(jié)構(gòu)在二叉樹中的結(jié)點(diǎn)結(jié)構(gòu)如下：　　4．功能設(shè)計　　compress函數(shù)：　　該函數(shù)將完成壓縮目標(biāo)文件的功能，首先輸入文件名，讀取目標(biāo)文件ifp=fopen(filename,"rb")，這里”rb”是按二進(jìn)制方式進(jìn)行讀操作，輸入壓縮后的文件名

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

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

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

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

22、關(guān)系。　　else header[i].b=0; 　　header[i].parent=header[i].lch=header[i].rch=-1; //是對結(jié)點(diǎn)進(jìn)行初始化。　　} 　　建立哈夫曼樹：</b&

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

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

25、;/p>　　} 　　} 　　}　　根據(jù)哈夫曼樹的性質(zhì)，n個葉子結(jié)點(diǎn)（權(quán)）需要2n-1個結(jié)點(diǎn)來構(gòu)建一棵哈夫曼樹：　　for(i=n;

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

27、　　header[i].rch=s2;　　header[i].count=header[s1].count+header[s2].count;　　}　　header[i].lch=s1; //計算左分支權(quán)值大??；　　head

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

44、pt1++; 　　strcpy(buf,buf+8); 　　j=strlen(buf); 　　}　　if(f==flength) break; 　　}

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

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

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

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

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

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

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

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

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

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

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

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

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

58、;　　fread(&c,1,1,ifp); 　　f=c; 　　itoa(f,buf,2); //將f轉(zhuǎn)換為二進(jìn)制表示的字符串　　f=strlen(buf); 　　for(l=8;l&g

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載