哈弗曼樹的文件壓縮和解壓實驗報告(C語言)

1、lab05 樹結(jié)構(gòu)的應(yīng)用學(xué)號： 姓名： 實驗時間：2011.5.241.問題描述哈弗曼樹的編碼與譯碼 功能：實現(xiàn)對任何類型文件的壓縮與解碼 輸入：源文件，壓縮文件 輸出：解碼正確性判定，統(tǒng)計壓縮率、編碼與解碼速度 要求： 使用邊編碼邊統(tǒng)計符號概率的方法（自適應(yīng)huffman編碼） 和事先統(tǒng)計概率的方法（靜態(tài)huffman編碼） 。2.1程序清單程序書簽：1. main函數(shù)2. 壓縮函數(shù)3. select函數(shù)4. encode函數(shù)5. 解壓函數(shù)#include #include #include #include #include struct nodelong weight; /權(quán)值unsig

2、ned char ch;/字符int parent,lchild,rchild;char code256;/編碼的位數(shù)最多為256位 int codelength;/編碼長度hfmnode512;void compress();void uncompress(); /主函數(shù)void main()int choice; printf(請選擇13：n); printf(1.壓縮文件n); printf(2.解壓文件n); printf(3.退出！n);scanf(%d,&choice);if(choice=1)compress();else if(choice=2)uncompress(); el

3、se if(choice=3)return; else printf(輸入錯誤！);/壓縮函數(shù) void compress()int i,j;char infile20,outfile20;file *ifp,*ofp; unsigned char c;/long filelength,filelength=0;int n,m;/葉子數(shù)和結(jié)點數(shù)int s1,s2; /權(quán)值最小的兩個結(jié)點的標(biāo)號char codes256;long sumlength=0;float rate,speed;int count=0;clock_t start1, start2,finish1,finish2; dou

4、ble duration1,duration2;void encode(struct node *nodep,int n);/編碼函數(shù)int select(struct node *nodep,int pose);/用于建哈弗曼樹中選擇權(quán)值最小的結(jié)點的函數(shù) printf(請輸入要壓縮的文件名:); scanf(%s,infile); ifp=fopen(infile,rb);if(ifp=null) printf(文件名輸入錯誤，文件不存在!n); return; printf(請輸入目標(biāo)文件名:); scanf(%s,outfile); ofp=fopen(outfile,wb);if(of

5、p=null) printf(文件名輸入錯誤，文件不存在!n); return;start1=clock() ;/開始計時1/統(tǒng)計文件中字符的種類以及各類字符的個數(shù)/先用字符的ascii碼值代替結(jié)點下標(biāo)filelength=0; while(!feof(ifp) fread(&c,1,1,ifp); hfmnodec.weight+; filelength+;filelength-; /文件中最后一個字符的個數(shù)會多統(tǒng)計一次，所以要減一hfmnodec.weight-;/再將ascii轉(zhuǎn)換為字符存入到結(jié)點的ch成員里，同時給雙親、孩子賦初值-1 n=0; for(i=0;i256;i+)if(h

6、fmnodei.weight!=0)hfmnodei.ch=(unsigned char)i; n+;/葉子數(shù) hfmnodei.lchild=hfmnodei.rchild=hfmnodei.parent=-1; m=2*n-1;/哈弗曼樹結(jié)點總數(shù) j=0; for(i=0;i256;i+)/去掉權(quán)值為0的結(jié)點 if(hfmnodei.weight!=0) hfmnodej=hfmnodei; j+; for(i=n;im;i+)/初始化根結(jié)點hfmnodei.lchild=hfmnodei.rchild=-1;hfmnodei.parent=-1;/建立哈弗曼樹 for(i=n;im;i+

7、) s1=select(hfmnode,i-1); hfmnodei.lchild=s1; hfmnodes1.parent=i; s2=select(hfmnode,i-1); hfmnodei.rchild=s2; hfmnodes2.parent=i; hfmnodei.weight=hfmnodes1.weight+hfmnodes2.weight; /編碼encode(hfmnode,n); finish1=clock();duration1=(double)(finish1- start1) / clocks_per_sec; /*printf( 哈弗曼樹編碼用時為：%f seco

8、ndsn, duration1 );*/ printf(編碼完成，是否查看編碼信息: y or n?n); c=getch(); if(c=y)printf(n); printf(葉子數(shù)為%d,結(jié)點數(shù)為%dn,n,m); for(i=0;in;i+)printf(%d號葉子結(jié)點的權(quán)值為：%ld,雙親為：%d,左右孩子：%d,編碼為：%sn,i,hfmnodei.weight,hfmnodei.parent,hfmnodei.lchild,hfmnodei.code);start2=clock() ;/開始計時2 fseek(ifp,0,seek_set);/將ifp指針移到文件開頭位置 fwr

9、ite(&filelength,4,1,ofp);/將filelength寫入目標(biāo)文件的前4個字節(jié)的位置 fseek(ofp,8,seek_set);/再將目標(biāo)文件指針ofp移到距文件開頭8個字節(jié)位置 codes0=0;/將編碼信息寫入目標(biāo)文件 while(!feof(ifp) fread(&c,1,1,ifp); filelength+; for(i=0;i=8) for(i=0;i8;i+)/將codes的前8位01代碼表示的字符存入c if(codesi=1) c=(c1)|1; else c=c0) strcat(codes,00000000); for(i=0;i8;i+) if(c

10、odesi=1) c=(c1)|1; else c=c1; fwrite(&c,1,1,ofp); sumlength+; sumlength+=8;printf(編碼區(qū)總長為：%ld個字節(jié)n,sumlength-8); /將sumlength和n的值寫入目標(biāo)文件，為的是方便解壓 fseek(ofp,4,seek_set); fwrite(&sumlength,4,1,ofp);/把sumlength寫進(jìn)目標(biāo)文件的第5-8個字節(jié)里 fseek(ofp,sumlength,seek_set); fwrite(&n,4,1,ofp);/把葉子數(shù)n寫進(jìn)編碼段后面的4個字節(jié)的位置/為方便解壓，把編碼信

11、息存入n后面的位置/存儲方式為：n*（字符值（1個字節(jié)）+該字符的01編碼的位數(shù)（1個字節(jié)）+編碼（字節(jié)數(shù)不確定，用count來計算總值） for(i=0;in;i+) fwrite(&(hfmnodei.ch),1,1,ofp); c=hfmnodei.codelength;/編碼最長為256位，因此只需用一個字節(jié)存儲 fwrite(&c,1,1,ofp); /寫入字符的編碼 if(hfmnodei.codelength%8!=0) for(j=hfmnodei.codelength%8;j8;j+)/把編碼不足8位的在低位補0,賦值給c，再把c寫入 strcat(hfmnodei.code

12、,0); while(hfmnodei.code0!=0)/開始存入編碼，每8位二進(jìn)制數(shù)存入一個字節(jié) c=0; for(j=0;j8;j+) if(hfmnodei.codej=1) c=(c1)|1; else c=c1; strcpy(hfmnodei.code,hfmnodei.code+8);/編碼前移8位，繼續(xù)存入編碼 count+; /編碼占的字節(jié)數(shù)的總值 fwrite(&c,1,1,ofp); printf(n); finish2=clock(); duration2=(double)(finish2- start2) / clocks_per_sec; /*printf( 寫入

13、目標(biāo)文件用時為：%f secondsn, duration2);*/ printf( 壓縮用時為：%f secondsn, duration1+duration2); speed=(float)filelength/(duration1+duration2)/1000; printf(n壓縮速率為：%5.2f kb/sn,speed);printf(n); printf(源文件長度為：%ld個字節(jié)n,filelength);sumlength=sumlength+4+n*2+count; /計算壓縮后文件的長度printf(壓縮后文件長度為：%ld個字節(jié)n,sumlength);rate=(f

14、loat)sumlength/(float)filelength;printf(壓縮率(百分比)為：%4.2f%n,rate*100); fclose(ifp); fclose(ofp); return;/返回書簽/建立哈弗曼樹中用于選擇最小權(quán)值結(jié)點的函數(shù)int select(struct node *nodep,int pose) int i;int s1;long min=2147483647;/s初值為long型的最大值for(i=0;i=pose;i+)if(nodepi.parent!=-1)continue;if(nodepi.weightmin)min=nodepi.weight

15、; s1=i;return s1;/返回書簽/哈弗曼編碼函數(shù)void encode(struct node *nodep,int n) /從葉子向根求每個字符的哈弗曼編碼int start;int i,f,c;char codes256;codesn-1=0; /編碼結(jié)束符for(i=0;in;i+) /逐個字符求哈弗曼編碼 start=n-1; for(c=i,f=nodepi.parent;f!=-1;c=f,f=nodepf.parent) start-; if(nodepf.lchild=c) codesstart=0; else codesstart=1; strcpy(nodepi

16、.code,&codesstart); nodepi.codelength=strlen(nodepi.code); /返回書簽/解壓函數(shù)void uncompress() /解壓文件 clock_t start, finish; double duration;file *ifp,*ofp; char infile20,outfile20; long filelength,sumlength,filelength;int n,m; int i,j,k;char buf256,codes256; unsigned char c;int maxlength;float speed; printf

17、(請輸入要解壓的文件名:); scanf(%s,infile); ifp=fopen(infile,rb);if(ifp=null) printf(文件名輸入錯誤，文件不存在!n); return; printf(請輸入目標(biāo)文件名:); scanf(%s,outfile); ofp=fopen(outfile,wb);if(ofp=null) printf(文件名輸入錯誤，文件不存在!n); return;start=clock() ;/開始計時 fread(&filelength,4,1,ifp);/從壓縮文件讀出filelength、sumlength fread(&sumlength,4

18、,1,ifp); fseek(ifp,sumlength,seek_set); /利用sumlength讀出n的值 fread(&n,4,1,ifp); printf(n解碼信息:源文件長度為%d個字節(jié),字符種類n=%dn,filelength,n); for(i=0;i0) m=hfmnodei.codelength/8+1;/m為編碼占的字節(jié)數(shù) else m=hfmnodei.codelength/8; for(j=0;jstrlen(buf);k-) strcat(hfmnodei.code,0); /再把二進(jìn)制編碼存進(jìn)hfmnode.code中 strcat(hfmnodei.code

19、,buf); hfmnodei.codehfmnodei.codelength=0;/去掉編碼中多余的0 /找出編碼長度的最大值 maxlength=0; for(i=0;imaxlength) maxlength=hfmnodei.codelength;/開始寫入目標(biāo)文件 fseek(ifp,8,seek_set); /指針指向編碼區(qū)，開始解碼 filelength=0; codes0=0; buf0=0; while(1) while(strlen(codes)strlen(buf);k-) strcat(codes,0);/把缺掉的0補上 strcat(codes,buf);/codes

20、中此時存的為一串01編碼 for(i=0;in;i+) /在codes中查找能使其前weight位和hfmnode.code相同的i值，weight即為codelength if(memcmp(hfmnodei.code,codes,(unsigned int)hfmnodei.codelength)=0) break; strcpy(codes,codes+hfmnodei.codelength);/更新codes的值 c=hfmnodei.ch; fwrite(&c,1,1,ofp); filelength+; if(filelength=filelength) break;/寫入結(jié)束 f

21、inish = clock(); duration = (double)(finish - start) / clocks_per_sec; printf( n解壓完成，解壓用時為：%f secondsn, duration ); fseek(ifp,0,seek_set); filelength=0; while(!feof(ifp) fread(&c,1,1,ifp); filelength+;filelength-; speed=(float)filelength/duration/1000;/*printf(此文件長度為：%ld個字節(jié)n,filelength);*/printf(n解壓

22、速度為：%5.2fkb/sn,speed); fclose(ifp); fclose(ofp); return;2.2程序運行結(jié)果：1.對文件xue.doc（45，056字節(jié)）進(jìn)行壓縮，壓縮后存儲在文件b.txt中，壓縮速率為：3003.73kb/s，壓縮率為75.50%。程序運行結(jié)果截圖如下：2.再對b.txt文件進(jìn)行解壓，目標(biāo)文件為pp.doc,解壓后的文件pp.doc與源文件xue.doc完全相同，解壓速度為180.94 kb/s。程序運行結(jié)果如下：2.3算法描述（1） 壓縮文件壓縮文件時要先對源文件進(jìn)行統(tǒng)計，統(tǒng)計字符的種類及出現(xiàn)的次數(shù)（即權(quán)值）。統(tǒng)計完成之后，建立哈弗曼樹：每次選取權(quán)值最小且無parent的結(jié)點作為左右孩子，建成一棵二叉樹，且設(shè)置新的二叉樹的根結(jié)點的權(quán)值為其左右孩子的權(quán)值之和。直至建成含有2*n-1個結(jié)點的哈弗曼樹。給每種字符進(jìn)行編碼。按照從葉子到根的順序求其編碼。算法和圖示如下：for(i=0;in;i+) sta