哈夫曼樹與文件解壓壓縮C言代碼

1、1.問題描述哈弗曼樹的編碼與譯碼 功能：實(shí)現(xiàn)對(duì)任何類型文件的壓縮與解碼 輸入：源文件，壓縮文件 輸出：解碼正確性判定，統(tǒng)計(jì)壓縮率、編碼與解碼速度 要求： 使用邊編碼邊統(tǒng)計(jì)符號(hào)概率的方法（自適應(yīng)Huffman編碼） 和事先統(tǒng)計(jì)概率的方法（靜態(tài)Huffman編碼）2.1程序清單程序書簽：1. main函數(shù)2. 壓縮函數(shù)3. select函數(shù)4. encode函數(shù)5. 解壓函數(shù)#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#include <ti

2、me.h>struct nodelong weight; /權(quán)值unsigned char ch;/字符int parent,lchild,rchild;char code256;/編碼的位數(shù)最多為256位 int CodeLength;/編碼長(zhǎng)度hfmnode512;void compress();void uncompress(); /主函數(shù)void main()int choice; printf("請(qǐng)選擇13：n"); printf("1.壓縮文件n"); printf("2.解壓文件n"); printf("

3、3.退出！n");scanf("%d",&choice);if(choice=1)compress();else if(choice=2)uncompress(); else if(choice=3)return; else printf("輸入錯(cuò)誤！");/壓縮函數(shù) void compress()int i,j;char infile20,outfile20;FILE *ifp,*ofp; unsigned char c;/long FileLength,filelength=0;int n,m;/葉子數(shù)和結(jié)點(diǎn)數(shù)int s1,s2;

4、/權(quán)值最小的兩個(gè)結(jié)點(diǎn)的標(biāo)號(hào)char codes256;long sumlength=0;float rate,speed;int count=0;clock_t start1, start2,finish1,finish2; double duration1,duration2;void encode(struct node *nodep,int n);/編碼函數(shù)int select(struct node *nodep,int pose);/用于建哈弗曼樹中選擇權(quán)值最小的結(jié)點(diǎn)的函數(shù) printf("請(qǐng)輸入要壓縮的文件名:"); scanf("%s",i

5、nfile); ifp=fopen(infile,"rb");if(ifp=NULL) printf("文件名輸入錯(cuò)誤，文件不存在!n"); return; printf("請(qǐng)輸入目標(biāo)文件名:"); scanf("%s",outfile); ofp=fopen(outfile,"wb");if(ofp=NULL) printf("文件名輸入錯(cuò)誤，文件不存在!n"); return;start1=clock() ;/開始計(jì)時(shí)1/統(tǒng)計(jì)文件中字符的種類以及各類字符的個(gè)數(shù)/先用字符的

6、ASCII碼值代替結(jié)點(diǎn)下標(biāo)FileLength=0; while(!feof(ifp) fread(&c,1,1,ifp); hfmnodec.weight+; FileLength+;FileLength-; /文件中最后一個(gè)字符的個(gè)數(shù)會(huì)多統(tǒng)計(jì)一次，所以要減一hfmnodec.weight-;/再將ASCII轉(zhuǎn)換為字符存入到結(jié)點(diǎn)的ch成員里，同時(shí)給雙親、孩子賦初值-1 n=0; for(i=0;i<256;i+)if(hfmnodei.weight!=0)hfmnodei.ch=(unsigned char)i; n+;/葉子數(shù) hfmnodei.lchild=hfmnodei

7、.rchild=hfmnodei.parent=-1; m=2*n-1;/哈弗曼樹結(jié)點(diǎn)總數(shù) j=0; for(i=0;i<256;i+)/去掉權(quán)值為0的結(jié)點(diǎn) if(hfmnodei.weight!=0) hfmnodej=hfmnodei; j+; for(i=n;i<m;i+)/初始化根結(jié)點(diǎn)hfmnodei.lchild=hfmnodei.rchild=-1;hfmnodei.parent=-1;/建立哈弗曼樹 for(i=n;i<m;i+) s1=select(hfmnode,i-1); hfmnodei.lchild=s1; hfmnodes1.parent=i; s2

8、=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( "哈弗曼樹編碼用時(shí)為：%f secondsn", duration1 );*/ printf("編碼完成，是否查看編碼信息: y or n?

9、n"); c=getch(); if(c='y')printf("n"); printf("葉子數(shù)為%d,結(jié)點(diǎn)數(shù)為%dn",n,m); for(i=0;i<n;i+)printf("%d號(hào)葉子結(jié)點(diǎn)的權(quán)值為：%ld,雙親為：%d,左右孩子：%d,編碼為：%sn",i,hfmnodei.weight,hfmnodei.parent,hfmnodei.lchild,hfmnodei.code);start2=clock() ;/開始計(jì)時(shí)2 fseek(ifp,0,SEEK_SET);/將ifp指針移到文件開頭

10、位置 fwrite(&FileLength,4,1,ofp);/將FileLength寫入目標(biāo)文件的前4個(gè)字節(jié)的位置 fseek(ofp,8,SEEK_SET);/再將目標(biāo)文件指針ofp移到距文件開頭8個(gè)字節(jié)位置 codes0=0;/將編碼信息寫入目標(biāo)文件 while(!feof(ifp) fread(&c,1,1,ifp); filelength+; for(i=0;i<n;i+) if(c=hfmnodei.ch) break;/ch必須也為unsigned 型 strcat(codes,hfmnodei.code); while(strlen(codes)>=

11、8) for(i=0;i<8;i+)/將codes的前8位01代碼表示的字符存入c if(codesi='1') c=(c<<1)|1; else c=c<<1; fwrite(&c,1,1,ofp); /將新的字符寫入目標(biāo)文件sumlength+; strcpy(codes,codes+8);/更新codes的值 if(filelength=FileLength) break; /再將剩余的不足8位的01代碼補(bǔ)全8位，繼續(xù)寫入 if(strlen(codes)>0) strcat(codes,"00000000"

12、); for(i=0;i<8;i+) if(codesi='1') c=(c<<1)|1; else c=c<<1; fwrite(&c,1,1,ofp); sumlength+; sumlength+=8;printf("編碼區(qū)總長(zhǎng)為：%ld個(gè)字節(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個(gè)字節(jié)里 fseek(ofp,

13、sumlength,SEEK_SET); fwrite(&n,4,1,ofp);/把葉子數(shù)n寫進(jìn)編碼段后面的4個(gè)字節(jié)的位置/為方便解壓，把編碼信息存入n后面的位置/存儲(chǔ)方式為：n*（字符值（1個(gè)字節(jié)）+該字符的01編碼的位數(shù)（1個(gè)字節(jié)）+編碼（字節(jié)數(shù)不確定，用count來計(jì)算總值） for(i=0;i<n;i+) fwrite(&(hfmnodei.ch),1,1,ofp); c=hfmnodei.CodeLength;/編碼最長(zhǎng)為256位，因此只需用一個(gè)字節(jié)存儲(chǔ) fwrite(&c,1,1,ofp); /寫入字符的編碼 if(hfmnodei.CodeLengt

14、h%8!=0) for(j=hfmnodei.CodeLength%8;j<8;j+)/把編碼不足8位的在低位補(bǔ)0,賦值給C，再把C寫入 strcat(hfmnodei.code,"0"); while(hfmnodei.code0!=0)/開始存入編碼，每8位二進(jìn)制數(shù)存入一個(gè)字節(jié) c=0; for(j=0;j<8;j+) if(hfmnodei.codej='1') c=(c<<1)|1; else c=c<<1; strcpy(hfmnodei.code,hfmnodei.code+8);/編碼前移8位，繼續(xù)存入編碼

15、count+; /編碼占的字節(jié)數(shù)的總值 fwrite(&c,1,1,ofp); printf("n"); finish2=clock(); duration2=(double)(finish2- start2) / CLOCKS_PER_SEC; /*printf( "寫入目標(biāo)文件用時(shí)為：%f secondsn", duration2);*/ printf( "壓縮用時(shí)為：%f secondsn", duration1+duration2); speed=(float)FileLength/(duration1+duratio

16、n2)/1000; printf("n壓縮速率為：%5.2f KB/Sn",speed);printf("n"); printf("源文件長(zhǎng)度為：%ld個(gè)字節(jié)n",FileLength);sumlength=sumlength+4+n*2+count; /計(jì)算壓縮后文件的長(zhǎng)度printf("壓縮后文件長(zhǎng)度為：%ld個(gè)字節(jié)n",sumlength);rate=(float)sumlength/(float)FileLength;printf("壓縮率(百分比)為：%4.2f%n",rate*100

17、); fclose(ifp); fclose(ofp); return;/返回書簽/建立哈弗曼樹中用于選擇最小權(quán)值結(jié)點(diǎn)的函數(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.weight<min)min=nodepi.weight; s1=i;return s1;/返回書簽/哈弗曼編碼函數(shù)void encode(struct node *nod

18、ep,int n) /從葉子向根求每個(gè)字符的哈弗曼編碼int start;int i,f,c;char codes256;codesn-1='0' /編碼結(jié)束符for(i=0;i<n;i+) /逐個(gè)字符求哈弗曼編碼 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.code,&codesstart); nod

19、epi.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("請(qǐng)輸入要解壓的文件名:"

20、;); scanf("%s",infile); ifp=fopen(infile,"rb");if(ifp=NULL) printf("文件名輸入錯(cuò)誤，文件不存在!n"); return; printf("請(qǐng)輸入目標(biāo)文件名:"); scanf("%s",outfile); ofp=fopen(outfile,"wb");if(ofp=NULL) printf("文件名輸入錯(cuò)誤，文件不存在!n"); return;start=clock() ;/開始計(jì)時(shí) f

21、read(&FileLength,4,1,ifp);/從壓縮文件讀出FileLength、sumlength fread(&sumlength,4,1,ifp); fseek(ifp,sumlength,SEEK_SET); /利用sumlength讀出n的值 fread(&n,4,1,ifp); printf("n解碼信息:源文件長(zhǎng)度為%d個(gè)字節(jié),字符種類n=%dn",FileLength,n); for(i=0;i<n;i+)/讀結(jié)點(diǎn)信息 fread(&hfmnodei.ch,1,1,ifp);/字符 fread(&c,1,

22、1,ifp);/編碼長(zhǎng)度 hfmnodei.CodeLength=c; hfmnodei.code0=0; if(hfmnodei.CodeLength%8>0) m=hfmnodei.CodeLength/8+1;/m為編碼占的字節(jié)數(shù) else m=hfmnodei.CodeLength/8; for(j=0;j<m;j+)/根據(jù)字節(jié)長(zhǎng)度m讀出編碼 fread(&c,1,1,ifp);/此處c為01編碼轉(zhuǎn)換成的字符 itoa(c,buf,2);/字符型編碼轉(zhuǎn)換成二進(jìn)制型（首位為1） /如果編碼不夠8位，則說明缺少了8-k位0，因此應(yīng)先在前面空缺位寫0 for(k=8;k&

23、gt;strlen(buf);k-) strcat(hfmnodei.code,"0"); /再把二進(jìn)制編碼存進(jìn)hfmnode.code中 strcat(hfmnodei.code,buf); hfmnodei.codehfmnodei.CodeLength=0;/去掉編碼中多余的0 /找出編碼長(zhǎng)度的最大值 maxlength=0; for(i=0;i<n;i+) if(hfmnodei.CodeLength>maxlength) maxlength=hfmnodei.CodeLength;/開始寫入目標(biāo)文件 fseek(ifp,8,SEEK_SET); /指針

24、指向編碼區(qū)，開始解碼 filelength=0; codes0=0; buf0=0; while(1) while(strlen(codes)<maxlength)/codes小于編碼長(zhǎng)度的最大值時(shí)，繼續(xù)讀碼 fread(&c,1,1,ifp); itoa(c,buf,2);/還原編碼 for(k=8;k>strlen(buf);k-) strcat(codes,"0");/把缺掉的0補(bǔ)上 strcat(codes,buf);/codes中此時(shí)存的為一串01編碼 for(i=0;i<n;i+) /在codes中查找能使其前weight位和hfmno

25、de.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é)束 finish = clock(); duration = (double)(finish - start

26、) / CLOCKS_PER_SEC; printf( "n解壓完成，解壓用時(shí)為：%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("此文件長(zhǎng)度為：%ld個(gè)字節(jié)n",FileLength);*/printf("n解壓速度為：%5.2fKB/Sn",speed); fclose(ifp); fclose(ofp); return;2.2程序運(yùn)行結(jié)果：1.對(duì)文件”測(cè)試.txt”進(jìn)行壓縮，壓縮后存儲(chǔ)在文件”目標(biāo).doc”中，壓縮速率為：2055.00KB/S，壓縮率為64.92%。程序運(yùn)行結(jié)果截圖如下：2.再對(duì)”測(cè)試.txt“文件進(jìn)行解壓，目標(biāo)文件為“目標(biāo)1.doc “。程序運(yùn)行結(jié)果如下：2.3算法描述（1） 壓縮文件壓縮文件時(shí)要先對(duì)源文件進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)字符的種類及出現(xiàn)的次數(shù)（即權(quán)值）。統(tǒng)計(jì)完成之后，建立哈弗曼樹：每次選取權(quán)值最小且無p