利用哈夫曼編碼制作壓縮軟件，內容如下：
#include?<stdio.h>?
#include?<string.h>?
#include?<stdlib.h>?
#include?<conio.h>
struct?head?
{
unsigned?char?b;//記錄字符在數組中的位置
long?count;?//字符出現頻率（權值）?
long?parent,lch,rch;//定義哈夫曼樹指針變量
char?bits[256];?//定義存儲哈夫曼編碼的數組
}?
header[512],tmp;
/*壓縮*/
void?compress()?
{
char?filename[255],outputfile[255],buf[512];?
unsigned?char?c;?
long?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("\n\t文件打開失敗!\n\n");?
return;?
}
printf("\t請您輸入壓縮後的文件名：");?
gets(outputfile);?
ofp=fopen(strcat(outputfile,".hub"),"wb");?
if(ofp==NULL)?
{
printf("\n\t壓縮文件失敗!\n\n");?
return;?
}
flength=0;?
while(!feof(ifp))?
{
fread(&c,1,1,ifp);?
header[c].count++;//字符重復出現頻率+1
flength++;//字符出現原文件長度+1
}
flength--;?
length1=flength;?//原文件長度用作求壓縮率的分母
header[c].count--;?
for(i=0;i<512;i++)?
{
if(header[i].count!=0)?header[i].b=(unsigned?char)i;?
/*將每個哈夫曼碼值及其對應的ASCII碼存放在壹維數組header[i]中，
且編碼表中的下標和ASCII碼滿足順序存放關系*/
else?header[i].b=0;?
header[i].parent=-1;header[i].lch=header[i].rch=-1;//對結點進行初始化
}?
for(i=0;i<256;i++)//根據頻率（權值）大小，對結點進行排序，選擇較小的結點進樹
{
for(j=i+1;j<256;j++)
{
if(header[i].count<header[j].count)
{
tmp=header[i]; header[i]=header[j];? header[j]=tmp;?}?
}?
}
for(i=0;i<256;i++)?if(header[i].count==0)?break;?
n=i;//外部葉子結點數為n個時，內部結點數為n-1，整個哈夫曼樹的需要的結點數為2*n-1.
m=2*n-1;
for(i=n;i<m;i++)//構建哈夫曼樹
{
min1=999999999;//預設的最大權值，即結點出現的最大次數
for(j=0;j<i;j++)?
{
if(header[j].parent!=-1)?continue;
//parent!=-1說明該結點已存在哈夫曼樹中，跳出循環重新選擇新結點*/
if(min1>header[j].count)?
{
pt1=j;? min1=header[j].count;? continue;?}?
}
header[i].count=header[pt1].count;?
header[pt1].parent=i;//依據parent域值（結點層數）確定樹中結點之間的關系
header[i].lch=pt1;//計算左分支權值大小
min1=999999999;
for(j=0;j<i;j++)?
{
if(header[j].parent!=-1)?continue;?
if(min1>header[j].count)?
{
pt1=j;? min1=header[j].count;? continue;?}?
}
header[i].count+=header[pt1].count;?
header[i].rch=pt1;//計算右分支權值大小
header[pt1].parent=i;?
}
for(i=0;i<n;i++)//哈夫曼無重復前綴編碼
{
f=i;?
header[i].bits[0]=0;//根結點編碼0
while(header[f].parent!=-1)?
{
j=f;?
f=header[f].parent;?
if(header[f].lch==j)//置左分支編碼0
{
j=strlen(header[i].bits);? memmove(header[i].bits+1,header[i].bits,j+1); //依次存儲連接“0”“1”編碼 header[i].bits[0]='0';?}
else//置右分支編碼1
{
j=strlen(header[i].bits);? memmove(header[i].bits+1,header[i].bits,j+1);? header[i].bits[0]='1';?}?
}?
}
fseek(ifp,0,SEEK_SET);//從文件開始位置向前移動0字節，即定位到文件開始位置
fwrite(&flength,sizeof(int),1,ofp);
/*用來將數據寫入文件流中，參數flength指向欲寫入的數據地址，
總***寫入的字符數以參數size*int來決定，返回實際寫入的int數目1*/?
fseek(ofp,8,SEEK_SET);?
buf[0]=0;//定義緩沖區,它的二進制表示00000000
f=0;?
pt1=8;?
/*假設原文件第壹個字符是"A"，8位2進制為01000001，編碼後為0110識別編碼第壹個'0'，
那麽我們就可以將其左移壹位，看起來沒什麽變化。下壹個是'1'，應該|1，結果00000001?
同理4位都做完，應該是00000110，由於字節中的8位並沒有全部用完，我們應該繼續讀下壹個字符，
根據編碼表繼續拼完剩下的4位，如果字符的編碼不足4位，還要繼續讀壹個字符，
如果字符編碼超過4位，那麽我們將把剩下的位信息拼接到壹個新的字節裏*/
while(!feof(ifp))?
{
c=fgetc(ifp);?
f++;?
for(i=0;i<n;i++)?
{
if(c==header[i].b)?break;?
}
strcat(buf,header[i].bits);?
j=strlen(buf);
c=0;?
while(j>=8)//對哈夫曼編碼位操作進行壓縮存儲
{
for(i=0;i<8;i++)?
{
if(buf[i]=='1')?c=(c<<1)|1;? else?c=c<<1;?}
fwrite(&c,1,1,ofp);?
pt1++;//統計壓縮後文件的長度
strcpy(buf,buf+8);//壹個字節壹個字節拼接
j=strlen(buf);?
}
if(f==flength)?break;?
}
if(j>0)//對哈夫曼編碼位操作進行壓縮存儲
{
strcat(buf,"00000000");?
for(i=0;i<8;i++)?
{
if(buf[i]=='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(&(header[i].b),1,1,ofp);?
c=strlen(header[i].bits);?
fwrite(&c,1,1,ofp);?
j=strlen(header[i].bits);?
if(j%8!=0)//若存儲的位數不是8的倍數，則補0
{
for(f=j%8;f<8;f++)?
strcat(header[i].bits,"0");?}
while(header[i].bits[0]!=0)?
{
c=0;?
for(j=0;j<8;j++)//字符的有效存儲不超過8位，則對有效位數左移實現兩字符編碼的連接
{
if(header[i].bits[j]=='1')?c=(c<<1)|1;//|1不改變原位置上的“0”“1”值 else?c=c<<1;?}
strcpy(header[i].bits,header[i].bits+8);//把字符的編碼按原先存儲順序連接
fwrite(&c,1,1,ofp);?
}?
}?
length2=pt1--;
div=((double)length1-(double)length2)/(double)length1;//計算文件的壓縮率
fclose(ifp);?
fclose(ofp);?
printf("\n\t壓縮文件成功!\n");?
printf("\t壓縮率為?%f%%\n\n",div*100);?
return;?
}
/*解壓縮*/
void?uncompress()?
{
char?filename[255],outputfile[255],buf[255],bx[255];?
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("\n\t文件打開失敗!\n");?
return;?
}
printf("\t請您輸入解壓縮後的文件名：");?
gets(outputfile);?
ofp=fopen(outputfile,"wb");?
if(ofp==NULL)?
{
printf("\n\t解壓縮文件失敗!\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(&header[i].b,1,1,ifp);?
fread(&c,1,1,ifp);?
p=(long)c;//讀取原文件字符的權值
header[i].count=p;?
header[i].bits[0]=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(header[i].bits,"0");?}
strcat(header[i].bits,buf);?
}?
header[i].bits[p]=0;?
}?
for(i=0;i<n;i++)//根據哈夫曼編碼的長短，對結點進行排序
{
for(j=i+1;j<n;j++)?
{
if(strlen(header[i].bits)>strlen(header[j].bits))?
{
tmp=header[i];? header[i]=header[j];? header[j]=tmp;?}?
}?
}?
p=strlen(header[n-1].bits);?
fseek(ifp,8,SEEK_SET);?
m=0;?
bx[0]=0;?
while(1)//通過哈夫曼編碼的長短，依次解碼，從原來的位存儲還原到字節存儲
{
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--)?//在單字節內對相應位置補0
{
strcat(bx,"0");?}
strcat(bx,buf);?
}
for(i=0;i<n;i++)?
{
if(memcmp(header[i].bits,bx,header[i].count)==0)?break;?
}
strcpy(bx,bx+header[i].count);/*從壓縮文件中的按位存儲還原到按字節存儲字符，
字符位置不改變*/
c=header[i].b;?
fwrite(&c,1,1,ofp);?
m++;//統計解壓縮後文件的長度
if(m==flength)?break;//flength是原文件長度
}?
fclose(ifp);?
fclose(ofp);?
printf("\n\t解壓縮文件成功!\n");?
if(m==flength)//對解壓縮後文件和原文件相同性比較進行判斷（根據文件大小）
printf("\t解壓縮文件與原文件相同!\n\n");?
else?printf("\t解壓縮文件與原文件不同!\n\n");
return;?
}
/*主函數*/
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");
printf("\n");
printf("\t?說明：（1）采用哈夫曼編碼\n");
printf("\t（2）適用於文本文件\n");?
printf("\n");
do//對用戶輸入進行容錯處理
{
printf("\n\t*請選擇相應功能(0-2):");?
c=getch();?
printf("%c\n",c);?
if(c!='0'?&&?c!='1'?&&?c!='2')
{?
printf("\t@_@請檢查您的輸入在0~2之間！\n"); printf("\t請再輸入壹遍！\n");}
}while(c!='0'?&&?c!='1'?&&?c!='2');?
if(c=='1')?compress();?//調用壓縮子函數
else?if(c=='2')?uncompress();//調用解壓縮子函數
else?
{
printf("\t歡迎您再次使用該工具^_^\n");?
exit(0);//退出該工具
}
system("pause");//任意鍵繼續
system("cls");?//清屏
}
return?0;
}