?? huf.c
字號:
//包含的頭文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <fcntl.h>
#include <io.h>
struct HTNode
{ //壓縮用Huffman樹結點
unsigned long weight; //字符頻度（權值）
unsigned int parent,lchild,rchild;
};
typedef char ElemType;
typedef struct
{
ElemType elem;
unsigned int m_weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //Huffman樹對應結點
typedef char ** HuffmanCode;
typedef int Status;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight; //符號及其出現次數
int bits; //記錄實際比特數，清空緩沖區
char chl; //字節
int lbits;
void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int); //Huffman編碼算法
void Select(HuffmanTree,int,int *,int *); //選擇結點
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int); //Huffman編碼輸出
void Write(unsigned int bit); //向outfp中寫入一個比特
void Writek(unsigned int num,unsigned int h);//向outfp中寫入k個比特
void WriteToOutfp(); //強行寫入outfp
unsigned int Read(); //從infp中讀出一個比特
unsigned int Readk(unsigned int k);//從infp中讀出k個比特
int NToBits(unsigned int num); //0~num之間的整數用二進位表示所需的最少位數
FILE *infp,*outfp; //輸入/出文件
Status main(void)
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c; //符號
unsigned int i; //用于循環
int x;
char y;
unsigned int n; //符號數
int wei; //符號對應的個數
int total=0;
int num;
x=0;
while(x!=3)
{
printf("請選擇是從文件中讀取還是自己輸入要操作的數:\n(1:自己輸入,2:從文件中讀取,3:退出):");
scanf("%d",&x);
//gets(x);
switch(x)
{
case 1:
{
float tnum;
printf("自己輸入只能進行壓縮!\n");
printf("請輸入Huffman樹的符號數:" );
scanf("%d",&n);
w=(Weight *)malloc(n*sizeof(Weight));//為w分配連續的內存空間
printf("請輸入符號及其個數：");
for(i=0;i<n;i++)
{
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
total+=w[i].m_weight;
}
total=total;//計算輸入的字符的總長度
printf("壓縮前,總字節數為:%d\n",total);
HuffmanCoding(&HT,&HC,w,n);//進行Huffman編碼
OutputHuffmanCode(HT,HC,n);//輸出Huffman編碼
num=0;
for (i=0;i<n;i++)
{
num +=strlen(HC[i+1])*w[i].m_weight;//計算編碼后的長度
}
tnum = num;
num=ceil(tnum/8);
printf("壓縮后總字節數為:%d\n",num);
break;
}
case 2:
{
//Huffman();
//char y;
printf("請選擇是進行壓縮還是解壓縮：(1:壓縮，2:解壓縮)");
scanf("%s",&y);
//gets(x);
switch(y)
{
case '1':
{
unsigned int size,l;
//stat buf;
char infName[256],outfName[256];
int ch;
unsigned int k=0; ////頻度大于零的字符數
unsigned int char_index[256]; //字符對應在樹結點表的下標(char_index[0]到char_index[n-1])
bits=0; //清空緩沖區
chl=0;
printf("請輸入源文件名:(大小小于4GB):"); //被壓縮文件最多4GB
scanf("%s",&infName);
if((infp=fopen(infName,"rb"))==NULL)
{
printf("不能打開文件:%s\n",infName);
exit(1);
}
if(feof(infp)!=0)
{
printf("空的源文件:%s\n",infName);
exit(1);
}
printf("請輸入解碼后要保存的文件名:");
scanf("%s",&outfName);
if((outfp=fopen(outfName,"wb"))==NULL)
{
printf("不能打開文件:%s\n",outfName);
exit(1);
}
printf("處理中...\n");
fseek(infp,0,SEEK_END);
size=ftell(infp); //計算打開的文件的大小
printf("壓縮前文件的總字節數為:%d\n",size);
rewind(infp); //將文件指針重新指向開頭
w=(Weight *)malloc(256*sizeof(Weight)); //為w分配空間
ch=fgetc(infp); //從文件中獲取一個字符
w[0].elem=ch;
w[0].m_weight=0;
char_index[ch]=1;
//ch=fgetc(infp);
while(ch!=EOF) //保存符合和出現次數
{
unsigned int i;
for(i=0;i<=k;i++)
{
if(ch == w[i].elem)
{
w[i].m_weight=w[i].m_weight+1;
break;
}
}
if(i>k)
{
k=k+1;
w[k].elem=ch;
w[k].m_weight=1;
char_index[ch] = k+1;
}
ch=fgetc(infp);
}
k=k+1;
HuffmanCoding(&HT,&HC,w,k);//進行Huffman編碼
num=0;
rewind(outfp); //將文件指針重新指向輸出文件的開頭
fwrite(&size,sizeof(unsigned int),1,outfp); //寫入文件的長度
Writek(k-1,8); //寫入符合的個數
for(i=0;i<k;i++)
fwrite(&(w[i].elem),sizeof(char),1,outfp); //寫入各個符合
l=NToBits(2*k-1); //k用二進位表示所需的最少位數
for(i=k+1;i<=2*k-1;i++)
{
Writek(HT[i].lchild,l);
Writek(HT[i].rchild,l);
}
rewind(infp); //將文件指針重新指向輸入文件的開頭
ch=fgetc(infp); //讀取一個字符
while(feof(infp)==0) //將編碼寫入文件
{
unsigned int c;
c=char_index[ch];
for(i=0;i<strlen(HC[c]);i++)
{
if(HC[c][i]=='0')Write(0);
else Write(1);
}
ch=fgetc(infp);
}
WriteToOutfp(); //最后一個字節沒有則強行寫入
fseek(outfp,0,SEEK_END);
num=ftell(outfp); //計算壓縮后文件的大小
printf("壓縮后文件的總字節數為:%d\n",num);
fclose(infp);fclose(outfp);
break;
}
case '2': //選擇解壓縮
{
unsigned int size;
unsigned int l;
unsigned int bit,c,i;
char infName[256],outfName[256];
char Leaf[256]; //葉結點對應字符(leaf[1]到leaf[n])
unsigned int k; ////頻度大于零的字符數
// unsigned int char_index[256]; //字符對應在樹結點表的下標(char_index[0]到char_index[n-1])
bits=0; //清空緩沖區
chl=0;
printf("請輸入編碼文件名::");
scanf("%s",&infName);
if((infp=fopen(infName,"rb"))==NULL)
{
printf("不能打開文件:%s\n",infName);
exit(1);
}
if(feof(infp)!=0)
{
printf("空的編碼文件:%s\n",infName);
exit(1);
}
printf("請輸入目標文件文件名:");
scanf("%s",&outfName);
if((outfp=fopen(outfName,"wb"))==NULL)
{
printf("不能打開文件:%s\n",outfName);
exit(1);
}
printf("處理中...\n");
fseek(infp,0,SEEK_END);
size=ftell(infp); //計算文件大小
printf("解壓縮前文件的總字節數為:%d\n",size);
bits=0; //清空緩沖區
chl=0;
rewind(infp); //將文件指針重新指向輸入文件的開頭
fread(&size,sizeof(unsigned int),1,infp);
k=Readk(8); //讀取字符數目
k=k+1;
w=(Weight *)malloc(256*sizeof(Weight)); //分配空間
for(i=1;i<=k;i++)
fread(&Leaf[i],sizeof(char),1,infp);
l=NToBits(2*k-1);
HT=(HuffmanTree)malloc((l+1)*sizeof(HTNode)); //分配空間
for(i=1;i<=k;i++) //讀出葉結點
{
HT[i].lchild=HT[i].rchild=0;
}
for(i=k+1;i<=2*k-1;i++)
{
HT[i].lchild=Readk(l);
HT[i].rchild=Readk(l);
}
bit=Read(); //讀一個bit
for(i=0;i<size;i++)
{
c=2*k-1; //2*k-1為根結點的下標
while((HT[c].lchild!=0||HT[c].rchild!=0)&&(feof(infp)==0))
{
if(bit==0)
c=HT[c].lchild;
else
c=HT[c].rchild;
bit=Read();
}
fputc(Leaf[c],outfp); //將字符寫入outfp中
}
fseek(outfp,0,SEEK_END);
size=ftell(outfp);
printf("解壓縮后文件的總字節數為:%d\n",size);
fclose(infp);fclose(outfp);
break;
//結束
}
}
}
}
}
return 1;
}
void Write(unsigned int bit) //向outfp中寫入一個比特
{
bits++;
chl=(chl<<1)+bit;
if(bits==8)
{ //緩沖區已滿,寫入outfp
fputc(chl,outfp);
bits=0;
chl=0;
}
}
void Writek(unsigned int num,unsigned int h) //向outfp中寫入k個比特
{
int *s;
unsigned int i,bit;
bit =0;
s=(int *)malloc((h+2)*sizeof(int));
for(i=1;i<=h;i++)
{
s[i]=0;
s[i]=num & 1;
num=num>>1;
}
for(i=h;i>0;)
{
bit=s[i];
Write(bit);
i--;
}
}
void WriteToOutfp() //強行寫入outfp
{
int i;
int l;
l=bits;
if(l>0)
for(i=0;i<8-l;i++)
Write(0);
}
int NToBits(unsigned int num) //0~num之間的整數用二進位表示所需的位數
{
unsigned int l=0,power=1;
while(power<=num){
l++;power=power*2;
}
return l;
}
unsigned int Read() //從infp中讀出一個比特
{
unsigned int bit;
if(bits==0)
{
chl=fgetc(infp);
bits=8;
}
bit=(chl & 128)>>7;
chl=chl<<1;
bits--;
return bit;
}
unsigned int Readk(unsigned int k) //從infp中讀出k個比特
{
unsigned int bit;
unsigned int i;
int num=0;
for(i=0;i<k;)
{
bit=Read();
num=(num<<1)+bit;
i++;
}
return num;
}
/*
*/
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n) //Huffman編碼算法
{
int i,m,s1,s2,start,c,f;
char *cd;
// HuffmanTree p;
if(n<=1)
return;
m=2*n-1;
//在內存為*HT分配長度為m+1個HTNode結構體大小的連續空間
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
//初始化HuffmanTree前n個節點
for(i=1;i<=n;++i)
{
(*HT)[i].elem=w[i-1].elem;
(*HT)[i].m_weight=w[i-1].m_weight;
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
//初始化HuffmanTree前n+1到m節點
for(;i<=m;++i)
{
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
//構造Huffman
for(i=n+1;i<=m;++i)
{
Select(*HT,i-1,&s1,&s2);
(*HT)[s1].parent=i;
(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;
(*HT)[i].rchild=s2;
(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
}
//在內存為*HT分配長度為n個char大小的連續空間
(*HC)=(HuffmanCode)malloc(n*sizeof(char*));
cd=(char *)malloc(n*sizeof(char)); //為cd分配n個char占的空間大小
cd[n-1]='\0';
//為每個葉子結點進行編碼
for(i=1;i<=n;++i)
{
start=n-1;
//從葉子結點開始向上搜索，如果它是其父結點的左孩子，則其編碼為0，否則為1，直到根結點
for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)
{
if((*HT)[f].lchild ==c)
cd[--start]='0';
else
cd[--start]='1';
}
(*HC)[i]=(char *)malloc((n-start)*sizeof(char)); //為每個結點的編碼分配存儲空間
strcpy((*HC)[i],&cd[start]);//將結點的編碼首地址保存到HC中
}
}
//選擇出權值最小并且父親結點的權值為0的2個結點
void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
int i;
(*s1)=(*s2)=0;//初始化s1和s2
for(i=1;i<=n;i++)
{
if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)//將權值最小的結點地址保存在s1中
{
(*s2)=(*s1);
(*s1)=i;
}
else
(*s2)=i;
}
if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)//為s1和s2初始植入結點
{
if((*s1)==0)
(*s1)=i;
else if((*s2)==0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
}
}
}
if((*s1)>(*s2))
{
i=(*s1);
(*s1)=(*s2);
(*s2)=i;
}
return;
}
//Huffman編碼輸出
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\n序號 符號 權重 huffman編碼\n");
for(i=1;i<=n;i++)
{
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -