數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版課程綜合性實(shí)驗(yàn)報(bào)告

1、.華北科技學(xué)院計(jì)算機(jī)系綜合性實(shí)驗(yàn)實(shí) 驗(yàn) 報(bào) 告 課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） 實(shí)驗(yàn)學(xué)期2009至2010學(xué)年 第2學(xué)期學(xué)生所在系部計(jì)算機(jī)系年級(jí)大二專(zhuān)業(yè)班級(jí)信管B-081學(xué)生XX尹芳學(xué)號(hào)3 任課教師蘭蕓 實(shí)驗(yàn)成績(jī)計(jì)算機(jī)系制實(shí)驗(yàn)報(bào)告須知1、 學(xué)生上交實(shí)驗(yàn)報(bào)告時(shí)，必須為打印稿（A4紙）。頁(yè)面空間不夠，可以順延。2、 學(xué)生應(yīng)該填寫(xiě)的內(nèi)容包括：封面相關(guān)欄目、實(shí)驗(yàn)地點(diǎn)、時(shí)間、目的、設(shè)備環(huán)境、內(nèi)容、結(jié)果及分析等。3、 教師應(yīng)該填寫(xiě)的內(nèi)容包括：實(shí)驗(yàn)成績(jī)、教師評(píng)價(jià)等。4、 教師根據(jù)本課程的綜合性實(shí)驗(yàn)指導(dǎo)單中實(shí)驗(yàn)內(nèi)容的要求，評(píng)定學(xué)生的綜合性實(shí)驗(yàn)成績(jī)；要求在該課程期末考試前將實(shí)驗(yàn)報(bào)告交給任課教師。綜合性實(shí)驗(yàn)中，所涉

2、及的程序，文檔等在交實(shí)驗(yàn)報(bào)告前，拷貝給任課教師。任課教師統(tǒng)一刻錄成光盤(pán)，與該課程的期末考試成績(jī)一同上交到系里存檔。5、 未盡事宜，請(qǐng)參考該課程的實(shí)驗(yàn)大綱和教學(xué)大綱。 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） 課程綜合性實(shí)驗(yàn)報(bào)告開(kāi)課實(shí)驗(yàn)室：基礎(chǔ)一2010年 6月 22 日實(shí)驗(yàn)題目用哈夫曼編碼實(shí)現(xiàn)文件壓縮一、實(shí)驗(yàn)?zāi)康?、了解文件的概念。2、掌握線性鏈表的插入、刪除等算法。3、掌握Huffman樹(shù)的概念及構(gòu)造方法。4、掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及遍歷算法。5、利用Huffman樹(shù)及Huffman編碼，掌握實(shí)現(xiàn)文件壓縮的一般原理。二、設(shè)備與環(huán)境微型計(jì)算機(jī)、Windows 系列操作系統(tǒng) 、Visual C+6.0軟件三、實(shí)驗(yàn)內(nèi)容

3、根據(jù)ascii碼文件中各ascii字符出現(xiàn)的頻率情況創(chuàng)建Haffman樹(shù)，再將各字符對(duì)應(yīng)的哈夫曼編碼寫(xiě)入文件中，實(shí)現(xiàn)文件壓縮。四、功能模塊簡(jiǎn)介和系統(tǒng)結(jié)構(gòu)圖：哈夫曼 壓縮、解壓縮壓縮 解壓縮退出五、實(shí)驗(yàn)結(jié)果及分析（1）系統(tǒng)的主要界面設(shè)計(jì)及運(yùn)行說(shuō)明按屏幕提示進(jìn)行文件壓縮操作。按屏幕提示進(jìn)行文件解壓縮操作。（2）程序的主要代碼*include <stdio.h>*include <string.h>*include <stdlib.h>*include <conio.h>struct headunsigned char b; /記錄字符在數(shù)組中的位置

4、long count; /字符出現(xiàn)頻率（權(quán)值） long parent,lch,rch; /定義哈夫曼樹(shù)指針變量 char bits256; /定義存儲(chǔ)哈夫曼編碼的數(shù)組header512,tmp;void unpress() /文字解壓函數(shù)char filename255,outputfile255,buf255,bx255; unsigned char c; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp; printf("t請(qǐng)輸入您要解壓縮的文件名："); gets(filename); ifp=fopen(strcat

5、(filename,".txt"),"rb"); if(ifp=NULL)printf("nt文件打開(kāi)失敗!n"); return;printf("t請(qǐng)輸入您解壓縮后的文件名："); gets(outputfile); ofp=fopen(outputfile,"wb"); if(ofp=NULL)printf("nt操作失敗!n"); return;fread(&flength,sizeof(long),1,ifp); /讀取原文件長(zhǎng)度，對(duì)文件進(jìn)行定位 fread(

6、&f,sizeof(long),1,ifp); fseek(ifp,f,SEEK_SET); fread(&n,sizeof(long),1,ifp); for(i=0;i<n;i+)fread(&headeri.b,1,1,ifp); fread(&c,1,1,ifp); p=(long)c; /讀取原文件字符的權(quán)值 headeri.count=p; headeri.bits0=0; if(p%8>0) m=p/8+1; else m=p/8; for(j=0;j<m;j+)fread(&c,1,1,ifp); f=c; itoa(f

7、,buf,2); /將f轉(zhuǎn)換為二進(jìn)制表示的字符串 f=strlen(buf); for(l=8;l>f;l-)strcat(headeri.bits,"0");strcat(headeri.bits,buf); headeri.bitsp=0; for(i=0;i<n;i+) /根據(jù)哈夫曼編碼的長(zhǎng)短，對(duì)結(jié)點(diǎn)進(jìn)行排序for(j=i+1;j<n;j+)if(strlen(headeri.bits)>strlen(headerj.bits);tmp=headeri; headeri=headerj; headerj=tmp; p=strlen(header

8、n-1.bits); fseek(ifp,8,SEEK_SET); m=0; bx0=0;while(1) /通過(guò)哈夫曼編碼的長(zhǎng)短，依次解碼，從原來(lái)的位存儲(chǔ)還原到字節(jié)存儲(chǔ)while(strlen(bx)<(unsigned int)p)fread(&c,1,1,ifp); f=c; itoa(f,buf,2); f=strlen(buf); for(l=8;l>f;l-) /在單字節(jié)內(nèi)對(duì)相應(yīng)位置補(bǔ)0strcat(bx,"0");strcat(bx,buf);for(i=0;i<n;i+)if(memcmp(headeri.bits,bx,heade

9、ri.count)=0) break;strcpy(bx,bx+headeri.count); c=headeri.b; fwrite(&c,1,1,ofp); m+; /統(tǒng)計(jì)解壓縮后文件的長(zhǎng)度 if(m=flength) break; /flength是原文件長(zhǎng)度 fclose(ifp); fclose(ofp); printf("nt解壓縮文件成功!n"); if(m=flength) /對(duì)解壓縮后文件和原文件相同性比較進(jìn)行判斷（根據(jù)文件大小）printf("t解壓縮文件與原文件相同!nn");else printf("t解壓縮文件

10、與原文件不同!nn"); return;void press() /文件壓縮函數(shù)long i,j,m,n,f; unsigned char c; long min1,pt1,flength,length1,length2;double div;char filename255,outputfile255,buf512; FILE *ifp,*ofp; printf("t請(qǐng)您輸入需要壓縮的文件名(格式如:*.txt)："); gets(filename); ifp=fopen(filename,"r"); if(ifp=NULL)printf(&

11、quot;nt文件打開(kāi)失敗!nn"); return;printf("t請(qǐng)您輸入壓縮后的文件名(格式如:'*')："); gets(outputfile); ofp=fopen(strcat(outputfile,".txt"),"w"); if(ofp=NULL)printf("nt壓縮文件失敗!nn"); return;flength=0; while(!feof(ifp)fread(&c,1,1,ifp); headerc.count+; /字符重復(fù)出現(xiàn)頻率+1 flengt

12、h+; /字符出現(xiàn)原文件長(zhǎng)度+1 flength-; length1=flength; /原文件長(zhǎng)度用作求壓縮率的分母 headerc.count-; for(i=0;i<512;i+)if(headeri.count!=0) headeri.b=(unsigned char)i; else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1; /對(duì)結(jié)點(diǎn)進(jìn)行初始化 for(i=0;i<256;i+) /根據(jù)頻率（權(quán)值）大小，對(duì)結(jié)點(diǎn)進(jìn)行排序，選擇較小的結(jié)點(diǎn)進(jìn)樹(shù)for(j=i+1;j<256;j+)if(header

13、i.count<headerj.count)tmp=headeri;headeri=headerj;headerj=tmp;for(i=0;i<256;i+) if(headeri.count=0) break; n=i; /外部葉子結(jié)點(diǎn)數(shù)為n個(gè)時(shí)，內(nèi)部結(jié)點(diǎn)數(shù)為n-1，整個(gè)哈夫曼樹(shù)的需要的結(jié)點(diǎn)數(shù)為2*n-1. m=2*n-1; for(i=n;i<m;i+) /構(gòu)建哈夫曼樹(shù)min1=999999999; /預(yù)設(shè)的最大權(quán)值，即結(jié)點(diǎn)出現(xiàn)的最大次數(shù) for(j=0;j<i;j+)if(headerj.parent!=-1) continue; /parent!=-1說(shuō)明該結(jié)點(diǎn)

14、已存在哈夫曼樹(shù)中，跳出循環(huán)重新選擇新結(jié)點(diǎn)*/ if(min1>headerj.count)pt1=j; min1=headerj.count; continue;headeri.count=headerpt1.count; headerpt1.parent=i; /依據(jù)parent域值（結(jié)點(diǎn)層數(shù)）確定樹(shù)中結(jié)點(diǎn)之間的關(guān)系 headeri.lch=pt1; /計(jì)算左分支權(quán)值大小 min1=999999999; for(j=0;j<i;j+)if(headerj.parent!=-1) continue;if(min1>headerj.count)pt1=j;min1=header

15、j.count;continue;headeri.count+=headerpt1.count; headeri.rch=pt1; /計(jì)算右分支權(quán)值大小 headerpt1.parent=i;for(i=0;i<n;i+) /哈夫曼無(wú)重復(fù)前綴編碼f=i; headeri.bits0=0; /根結(jié)點(diǎn)編碼0 while(headerf.parent!=-1)j=f; f=headerf.parent; if(headerf.lch=j) /置左分支編碼0j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1);/依次存儲(chǔ)

16、連接“0”“1”編碼 headeri.bits0='0'else /置右分支編碼1j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0='1'fseek(ifp,0,SEEK_SET); /從文件開(kāi)始位置向前移動(dòng)0字節(jié)，即定位到文件開(kāi)始位置 fwrite(&flength,sizeof(int),1,ofp); fseek(ofp,8,SEEK_SET); buf0=0; /定義緩沖區(qū),它的二進(jìn)制表示00000000 f=0; pt1=8; whil

17、e(!feof(ifp)c=fgetc(ifp); f+; for(i=0;i<n;i+)if(c=headeri.b) break;strcat(buf,headeri.bits); j=strlen(buf); c=0;while(j>=8) /對(duì)哈夫曼編碼位操作進(jìn)行壓縮存儲(chǔ)for(i=0;i<8;i+)if(bufi='1') c=(c<<1)|1; else c=c<<1;fwrite(&c,1,1,ofp); pt1+; /統(tǒng)計(jì)壓縮后文件的長(zhǎng)度 strcpy(buf,buf+8); /一個(gè)字節(jié)一個(gè)字節(jié)拼接 j=strl

18、en(buf);if(f=flength) break;if(j>0) /對(duì)哈夫曼編碼位操作進(jìn)行壓縮存儲(chǔ)strcat(buf,"00000000"); for(i=0;i<8;i+)if(bufi='1') c=(c<<1)|1;else c=c<<1;fwrite(&c,1,1,ofp); pt1+;fseek(ofp,4,SEEK_SET); fwrite(&pt1,sizeof(long),1,ofp); fseek(ofp,pt1,SEEK_SET); fwrite(&n,sizeof(lo

19、ng),1,ofp); for(i=0;i<n;i+)fwrite(&(headeri.b),1,1,ofp); c=strlen(headeri.bits); fwrite(&c,1,1,ofp); j=strlen(headeri.bits); if(j%8!=0) /若存儲(chǔ)的位數(shù)不是8的倍數(shù)，則補(bǔ)0 for(f=j%8;f<8;f+) strcat(headeri.bits,"0");while(headeri.bits0!=0)c=0; for(j=0;j<8;j+) /字符的有效存儲(chǔ)不超過(guò)8位，則對(duì)有效位數(shù)左移實(shí)現(xiàn)兩字符編碼的連接

20、if(headeri.bitsj='1') c=(c<<1)|1; /|1不改變?cè)恢蒙系摹?”“1”值 else c=c<<1;strcpy(headeri.bits,headeri.bits+8); /把字符的編碼按原先存儲(chǔ)順序連接 fwrite(&c,1,1,ofp);length2=pt1-;div=(double)length1-(double)length2)/(double)length1; /計(jì)算文件的壓縮率 fclose(ifp); fclose(ofp); printf("nt壓縮文件成功!n"); pri

21、ntf("t壓縮率為 %f%nn",div*100); return;int main()int c; while(1) /菜單工具欄printf("t n"); printf("t * 哈夫曼 壓縮、解壓縮 * n"); printf("t n"); printf("t _n"); printf("t| |n"); printf("t| 1.壓縮 |n"); printf("t| 2.解壓縮 |n"); printf("t| 0.退出 |n"); printf("t|_|n");printf("n");printf("t 說(shuō)明：（1）采用哈夫曼編碼n");printf("t （2）適用于字符型文本文件n");printf("n"); do /對(duì)用戶輸入進(jìn)行容錯(cuò)處理printf("nt*請(qǐng)選擇相應(yīng)功能(0-2):"); c=getch();printf("%cn",c); if(