1、#include <string.h>#include <stdlib.h>#include <conio.h>struct headunsigned char b; /記錄字符在數(shù)組中的位置 long count; /字符出現(xiàn)頻率（權值）long parent,lchild,rchild; /定義哈夫曼樹指針變量 char bits256; /定義存儲哈夫曼編碼的數(shù)組 header512,tmp;/*壓縮*/void compress()char filename255,outputfile255,buf512; unsigned char c;long

2、i,j,m,n,f;long min1,pt1,flength,length1,length2;double div;FILE *ifp,*ofp;printf("t請您輸入需要壓縮的文件："); gets(filename);ifp=fopen(filename,"rb");if(ifp=NULL)printf("nt文件打開失敗!nn");return;printf("t請您輸入壓縮后的文件名："); gets(outputfile);ofp=fopen(strcat(outputfile,".hub

3、"),"wb"); if(ofp=NULL)printf("nt壓縮文件失敗!nn");return;flength=0;while(!feof(ifp)fread(&c,1,1,ifp);headerc.count+; /字符重復出現(xiàn)頻率+1flength+; /字符出現(xiàn)原文件長度+1flength-;length1=flength; /原文件長度用作求壓縮率的分母headerc.count-;for(i=0;i<512;i+)if(headeri.count!=0) headeri.b=(unsigned char)i;/*將

4、每個哈夫曼碼值及其對應的ASCII碼存放在一維數(shù)組headeri中，且編碼表中的下標和ASCII碼滿足順序存放關系*/else headeri.b=0;headeri.parent=-1;headeri.lchild=headeri.rchild=-1; /對結點進行初始化for(i=0;i<256;i+) /根據(jù)頻率（權值）大小，對結點進行排序，選擇較小的結點進樹 for(j=i+1;j<256;j+)if(headeri.count<headerj.count)tmp=headeri;headeri=headerj;headerj=tmp;for(i=0;i<256

5、;i+) if(headeri.count=0) break;n=i; /外部葉子結點數(shù)為n個時，內部結點數(shù)為n-1，整個哈夫曼樹的需要的結點數(shù)為2*n-1. m=2*n-1;for(i=n;i<m;i+) /構建哈夫曼樹min1=999999999; /預設的最大權值，即結點出現(xiàn)的最大次數(shù)for(j=0;j<i;j+)if(headerj.parent!=-1) continue;/parent!=-1說明該結點已存在哈夫曼樹中，跳出循環(huán)重新選擇新結點*/if(min1>headerj.count)pt1=j;min1=headerj.count;continue;head

6、eri.count=headerpt1.count;headerpt1.parent=i; /依據(jù)parent域值（結點層數(shù)）確定樹中結點之間的關系headeri.lchild=pt1; /計算左分支權值大小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+=headerpt1.count;headeri.rchild=pt1; /計算右分支權值大小headerpt1.p

7、arent=i;for(i=0;i<n;i+) /哈夫曼無重復前綴編碼f=i;headeri.bits0=0; /根結點編碼0while(headerf.parent!=-1)j=f;f=headerf.parent;if(headerf.lchild=j) /置左分支編碼0j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);/依次存儲連接“0”“1”編碼headeri.bits0='0'else /置右分支編碼1j=strlen(headeri.bits);memmove(headeri.bit

8、s+1,headeri.bits,j+1);headeri.bits0='1'fseek(ifp,0,SEEK_SET); /從文件開始位置向前移動0字節(jié)，即定位到文件開始位置 fwrite(&flength,sizeof(int),1,ofp);/*用來將數(shù)據(jù)寫入文件流中，參數(shù)flength指向欲寫入的數(shù)據(jù)地址，總共寫入的字符數(shù)以參數(shù)size*int來決定，返回實際寫入的int數(shù)目1*/fseek(ofp,8,SEEK_SET);buf0=0; /定義緩沖區(qū),它的二進制表示00000000f=0;pt1=8;/*假設原文件第一個字符是"A"，8位2

9、進制為01000001，編碼后為0110識別編碼第一個'0'， 那么我們就可以將其左移一位，看起來沒什么變化。下一個是'1'，應該|1，結果00000001同理4位都做完，應該是00000110，由于字節(jié)中的8位并沒有全部用完，我們應該繼續(xù)讀下一個字符， 根據(jù)編碼表繼續(xù)拼完剩下的4位，如果字符的編碼不足4位，還要繼續(xù)讀一個字符，如果字符編碼超過4位，那么我們將把剩下的位信息拼接到一個新的字節(jié)里*/while(!feof(ifp)c=fgetc(ifp);f+;for(i=0;i<n;i+)if(c=headeri.b) break;strcat(buf,h

10、eaderi.bits);j=strlen(buf);c=0;while(j>=8) /對哈夫曼編碼位操作進行壓縮存儲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)計壓縮后文件的長度strcpy(buf,buf+8); /一個字節(jié)一個字節(jié)拼接j=strlen(buf);if(f=flength) break;if(j>0) /對哈夫曼編碼位操作進行壓縮存儲strcat(buf,"00000000");

11、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(&(headeri.b),1,1,ofp);c=strlen(headeri.bits);fwrite(&

12、amp;c,1,1,ofp);j=strlen(headeri.bits);if(j%8!=0) /若存儲的位數(shù)不是8的倍數(shù)，則補0for(f=j%8;f<8;f+)strcat(headeri.bits,"0");while(headeri.bits0!=0)c=0;for(j=0;j<8;j+) /字符的有效存儲不超過8位，則對有效位數(shù)左移實現(xiàn)兩字符編碼的連接 if(headeri.bitsj='1') c=(c<<1)|1; /|1不改變原位置上的“0”“1”值else c=c<<1;strcpy(headeri.b

13、its,headeri.bits+8); /把字符的編碼按原先存儲順序連接fwrite(&c,1,1,ofp);length2=pt1-;div=(double)length1-(double)length2)/(double)length1; /計算文件的壓縮率fclose(ifp);fclose(ofp);printf("nt壓縮文件成功!n");printf("t壓縮率為 %f%nn",div*100);return;/*解壓縮*/void uncompress()char filename255,outputfile255,buf255,

14、bx255;unsigned char c;long i,j,m,n,f,p,l;long flength;FILE *ifp,*ofp;printf("t請您輸入需要解壓縮的文件：");gets(filename);ifp=fopen(strcat(filename,".hub"),"rb");if(ifp=NULL)printf("nt文件打開失敗!n");return;printf("t請您輸入解壓縮后的文件名：");gets(outputfile);ofp=fopen(outputfil

15、e,"wb");if(ofp=NULL)printf("nt解壓縮文件失敗!n");return;fread(&flength,sizeof(long),1,ifp); /讀取原文件長度，對文件進行定位 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,1,1,ifp);fread(&c,1,1,ifp);p=(long)c; /讀取原文

16、件字符的權值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轉換為二進制表示的字符串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ù)哈夫曼編碼的長短，對結點進行排序 for(j=i+1

17、;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) /通過哈夫曼編碼的長短，依次解碼，從原來的位存儲還原到字節(jié)存儲 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

18、;l-) /在單字節(jié)內對相應位置補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); /*從壓縮文件中的按位存儲還原到按字節(jié)存儲字符， 字符位置不改變*/c=headeri.b;fwrite(&c,1,1,ofp);m+; /統(tǒng)計解壓縮后文件的長度if(m=flength) break; /flength是原文件長度fclose(ifp);fclose(ofp);p

19、rintf("nt解壓縮文件成功!n");if(m=flength) /對解壓縮后文件和原文件相同性比較進行判斷（根據(jù)文件大小） printf("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");printf("t|_|n&qu