利用哈夫曼編碼實(shí)現(xiàn)文件壓縮

1、用哈夫曼壓縮文件(C語言）2007-12-29 21:09利用哈夫曼編碼制作壓縮軟件，內(nèi)容如下：#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>struct headunsigned char b; /記錄字符在數(shù)組中的位置 long count; /字符出現(xiàn)頻率（權(quán)值） long parent,lch,rch; /定義哈夫曼樹指針變量char bits256; /定義存儲(chǔ)哈夫曼編碼的數(shù)組 header512,tmp;/*壓縮*/void comp

2、ress()char filename255,outputfile255,buf512; unsigned char c;long i,j,m,n,f;long min1,pt1,flength,length1,length2;double div;FILE *ifp,*ofp;printf("t請(qǐng)您輸入需要壓縮的文件：");gets(filename);ifp=fopen(filename,"rb");if(ifp=NULL)printf("nt文件打開失敗!nn");return;printf("t請(qǐng)您輸入壓縮后的文件名

3、：");gets(outputfile);ofp=fopen(strcat(outputfile,".hub"),"wb"); if(ofp=NULL)printf("nt壓縮文件失敗!nn");return;flength=0;while(!feof(ifp)fread(&c,1,1,ifp);headerc.count+; /字符重復(fù)出現(xiàn)頻率+1flength+; /字符出現(xiàn)原文件長度+1flength-;length1=flength; /原文件長度用作求壓縮率的分母headerc.count-;for(i=0

4、;i<512;i+)if(headeri.count!=0) headeri.b=(unsigned char)i;/*將每個(gè)哈夫曼碼值及其對(duì)應(yīng)的ASCII碼存放在一維數(shù)組headeri中， 且編碼表中的下標(biāo)和ASCII碼滿足順序存放關(guān)系*/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)樹for(j=i+1;j<256;j+)if(headeri.count<headerj.coun

5、t)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è)哈夫曼樹的需要的結(jié)點(diǎn)數(shù)為2*n-1.m=2*n-1;for(i=n;i<m;i+) /構(gòu)建哈夫曼樹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說明該結(jié)點(diǎn)已存在哈夫曼樹中，跳出循環(huán)重新選擇新結(jié)點(diǎn)*/ if(m

6、in1>headerj.count)pt1=j;min1=headerj.count;continue;headeri.count=headerpt1.count;headerpt1.parent=i; /依據(jù)parent域值（結(jié)點(diǎn)層數(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=headerj.count;continue;headeri.count+=h

7、eaderpt1.count;headeri.rch=pt1; /計(jì)算右分支權(quán)值大小headerpt1.parent=i;for(i=0;i<n;i+) /哈夫曼無重復(fù)前綴編碼f=i;headeri.bits0=0; /根結(jié)點(diǎn)編碼0while(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ǔ)連接“0”“1”編碼headeri.bits0='0'else

8、/置右分支編碼1j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);headeri.bits0='1'fseek(ifp,0,SEEK_SET); /從文件開始位置向前移動(dòng)0字節(jié)，即定位到文件開始位置fwrite(&flength,sizeof(int),1,ofp);/*用來將數(shù)據(jù)寫入文件流中，參數(shù)flength指向欲寫入的數(shù)據(jù)地址，總共寫入的字符數(shù)以參數(shù)size*int來決定，返回實(shí)際寫入的int數(shù)目1*/ fseek(ofp,8,SEEK_SET);buf0=0; /定義緩沖區(qū),它的二進(jìn)制

9、表示00000000f=0;pt1=8;/*假設(shè)原文件第一個(gè)字符是"A"，8位2進(jìn)制為01000001，編碼后為0110識(shí)別編碼第一個(gè)'0'，那么我們就可以將其左移一位，看起來沒什么變化。下一個(gè)是'1'，應(yīng)該|1，結(jié)果00000001同理4位都做完，應(yīng)該是00000110，由于字節(jié)中的8位并沒有全部用完，我們應(yīng)該繼續(xù)讀下一個(gè)字符，根據(jù)編碼表繼續(xù)拼完剩下的4位，如果字符的編碼不足4位，還要繼續(xù)讀一個(gè)字符，如果字符編碼超過4位，那么我們將把剩下的位信息拼接到一個(gè)新的字節(jié)里*/ while(!feof(ifp)c=fgetc(ifp);f+;for

10、(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ì)壓縮后文件的長度strcpy(buf,buf+8); /一個(gè)字節(jié)一個(gè)字節(jié)拼接j=strlen(buf);if(f=flength) break;if(j>0)

11、/對(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(long),1,ofp);for(i=0;i<n;i+)fwrite(&(he

12、aderi.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ǔ)0for(f=j%8;f<8;f+)strcat(headeri.bits,"0");while(headeri.bits0!=0)c=0;for(j=0;j<8;j+) /字符的有效存儲(chǔ)不超過8位，則對(duì)有效位數(shù)左移實(shí)現(xiàn)兩字符編碼的連接if(headeri.bitsj='1') c=(c<<1)|1; /|1不

13、改變原位置上的“0”“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");printf("t壓縮率為 %f%nn",div*100);return;/*解壓縮*/void un

14、compress()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(filename,".hub"),"rb");if(ifp=NULL)printf("nt文件打開失敗!n");return;printf("t請(qǐng)您輸入解壓縮后的

15、文件名：");gets(outputfile);ofp=fopen(outputfile,"wb");if(ofp=NULL)printf("nt解壓縮文件失敗!n");return;fread(&flength,sizeof(long),1,ifp); /讀取原文件長度，對(duì)文件進(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+)fread(&headeri.b

16、,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,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;

17、for(i=0;i<n;i+) /根據(jù)哈夫曼編碼的長短，對(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(headern-1.bits);fseek(ifp,8,SEEK_SET);m=0;bx0=0;while(1) /通過哈夫曼編碼的長短，依次解碼，從原來的位存儲(chǔ)還原到字節(jié)存儲(chǔ)while(strlen(bx)<(unsigned int)p)fread(&c,1,1,ifp);

18、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,headeri.count)=0) break;strcpy(bx,bx+headeri.count); /*從壓縮文件中的按位存儲(chǔ)還原到按字節(jié)存儲(chǔ)字符，字符位置不改變*/c=headeri.b;fwrite(&c,1,1,ofp);m+; /統(tǒng)計(jì)解壓縮后文件的長度if(m=flength) b

19、reak; /flength是原文件長度fclose(ifp);fclose(ofp);printf("nt解壓縮文件成功!n");if(m=flength) /對(duì)解壓縮后文件和原文件相同性比較進(jìn)行判斷（根據(jù)文件大?。﹑rintf("t解壓縮文件與原文件相同!nn");else printf("t解壓縮文件與原文件不同!nn");return;/*主函數(shù)*/int main()int c;while(1) /菜單工具欄printf("t _n"); printf("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&quo