#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define IOsize 256
typedef enum {FALSE,TRUE}bool;
typedef struct
{
int weight; //结点权值
int parent,lchild,rchild; //双亲、左孩子、右孩子
}HTNode,*HuffmanTree;
typedef struct
{
unsigned char cd_len;
unsigned char *data;
}HuffmanCode;
int search(HuffmanTree HT,int n) //找到一个没有双亲的点以初始化select()中min的值
{
for (int i=0;i<=n;i++)
{
if (HT[i].parent == 0)
{
return HT[i].weight;
}
}
}
void select(HuffmanTree HT, int n, int *s1, int *s2) //选择权值最小的两个结点
{
int min = search(HT,n)+1;
for(int i=0;i<=n;i++)
{
if(HT[i].parent==0 && HT[i].weight<min)
{
*s1 = i;
min = HT[i].weight;
}
}
HT[*s1].parent=-1;
min = search(HT,n)+1;
for(int i=0;i<=n;i++)
{
if (HT[i].parent==0 && HT[i].weight<min && i!=*s1)
{
*s2 = i;
min = HT[i].weight;
}
}
}
void CreateHuffmanTree(HuffmanTree HT,int n,int value[]) //创建哈夫曼树
{
int m=2*n-1;
int s1,s2;
//HT=(HuffmanTree*)malloc(sizeof(HuffmanTree)*m);
if(n<1)
{
printf("Error!\n");
return;
}
for(int i=0;i<n;i++)
{
HT[i].weight=value[i];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(int i=n;i<m;i++) //初始化
{
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(int i=n;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].weight=HT[s1].weight+HT[s2].weight;
}
}
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode *HC,int n)
{
int start;
char *cd;
//HC=(HuffmanCode*)malloc(sizeof(HuffmanCode)*n);
cd=(char*)malloc(sizeof(char)*n);
cd[n-1]='\0';
for(int i=0;i<n;i++)
{
start=n-1;
int c=i;
int f=HT[i].parent;
while(f!=0)
{
start--;
cd[start]=HT[f].lchild==c?'1':'0';
c=f;
f=HT[f].parent;
}
HC[i].cd_len=n-start;
HC[i].data=(unsigned char*)malloc(sizeof(unsigned char)*(n-start+1));
strcpy(HC[i].data,&cd[start]);
}
free(cd);
}
char *createfile(char *infp_name,char *outfp_name)
{
char *fp=strrchr(infp_name,'.');
if(fp!=NULL)
{
strncpy(outfp_name,infp_name,fp-infp_name);
outfp_name[fp-infp_name]='\0';
strcat(outfp_name,".zip");
}
else
{
strcpy(outfp_name,infp_name);
strcat(outfp_name,".zip");
}
return outfp_name;
}
unsigned char combine(const unsigned char code[8])
{
unsigned char combine_code = 0;
for(int i=1;i<8;i++)
{
combine_code<<=1;
combine_code|=code[i];
}
return combine_code;
}
void writefile(FILE *infp,FILE *outfp,HuffmanTree HT,HuffmanCode *HC,char *infp_name,int infp_size,int n)
{
unsigned char sum_read=n,sum_write=0,sum_writechar=0,sum_code,sum_copy;
unsigned char read[n],write[n],code[8];
HuffmanCode *huffmancode;
fseek(infp,0,SEEK_SET);
fseek(outfp,0,SEEK_SET);
char head[3]="PBM";
unsigned name_len=strlen(infp_name);
fwrite(head,sizeof(char),3,outfp);
fwrite(&name_len,sizeof(unsigned char),1,outfp);
fwrite(infp_name,sizeof(char),name_len,outfp);
fwrite(&infp_size,sizeof(int),1,outfp);
for(int i=n;i<2*n-1;i++)
{
fwrite(&(HT[i].lchild),sizeof(HT[i].lchild),1,outfp);
fwrite(&(HT[i].rchild),sizeof(HT[i].rchild),1,outfp);
}
while(sum_read==n)
{
sum_read=fread(read,1,n,infp);
for(int i=0;i<sum_read;i++)
{
huffmancode=&HC[read[i]];
sum_code=0;
while(sum_code!=huffmancode->cd_len)
{
if(8-sum_writechar > huffmancode->cd_len-sum_code)
sum_copy=huffmancode->cd_len-sum_code;
else
sum_copy=8-sum_writechar;
memcpy(code+sum_writechar,huffmancode->data+sum_code,sum_copy);
sum_writechar+=sum_copy;
sum_code+=sum_copy;
if(sum_writechar==8)
{
sum_writechar=0;
write[sum_write]=combine(code);
sum_write++;
if(sum_write==n)
{
fwrite(write,1,n,outfp);
sum_write=0;
}
}
}
}
}
if(sum_writechar!=0)
{
write[sum_write]=combine(code);
sum_write++;
}
fwrite(write,1,sum_write,outfp);
}
bool open(FILE **infp,FILE **outfp,char *infp_name,char *outfp_name)
{
outfp_name=(char*)malloc(255*sizeof(char));
outfp_name=createfile(infp_name,outfp_name);
if(strcmp(infp_name,outfp_name)==0)
{
printf("该文件已是压缩文件\n");
return FALSE;
}
printf("待压缩文件为:%s,压缩后文件为:%s\n",infp_name,outfp_name);
if((*outfp=fopen(outfp_name,"wb"))==NULL)
{
printf("文件打开错误，请输入正确的文件路径\n");
return FALSE;
}
if((*infp=fopen(infp_name,"rb"))==NULL)
{
printf("文件打开错误，请输入正确的文件路径\n");
return FALSE;
}
free(outfp_name);
return TRUE;
}
int value_calculate(FILE *infp,int value[])
{
int p=0,read_len=256;
unsigned char read[256];
fseek(infp,0,SEEK_SET);
while(read_len==256)
{
read_len=fread(read,1,256,infp);
for(int i=0;i<read_len;i++)
{
value[(read[i])]++;
}
}
for (int i = 0;i<256;i++)
{
if(value[i]!=0)
{
p++;
}
}
if(p<256)
return p;
else
return 256;
}
int filesize_calculate(int value_final[],int n)
{
int filesize=0;
for(int i=0;i<n;i++)
{
filesize = filesize+value_final[i];
}
return filesize;
}
void value_copy(int value[],int value_final[])
{
int p=0;
for(int i = 0;i<256;i++)
{
if(value[i]!=0)
{
value_final[p]=value[i];
p++;
}
}
}
void compress(char *infp_name,char *outfp_name)
{
FILE *infp,*outfp;
int p=0,l=0,r=0;
bool flag;
float rate;
char judge;
HuffmanCode *HC;
HuffmanTree HT;
int value[256]={0};
int *value_final;
int infp_size,outfp_size=0;
flag=open(&infp,&outfp,infp_name,outfp_name);
int n = value_calculate(infp,value);
int m=2*n-1;
HC= (HuffmanCode*)malloc(sizeof(HuffmanCode)*n);
HT= (HuffmanTree*)malloc(sizeof(HTNode)*m);
value_final=(int*)malloc(sizeof(int)*n);
value_copy(value,value_final);
infp_size=filesize_calculate(value_final,n);
printf("该文件的大小为：%d字节\n",infp_size);
CreateHuffmanTree(HT,n,value_final);
CreateHuffmanCode(HT,HC,n);
writefile(infp,outfp,HT,HC,infp_name,infp_size,n);
for(int i=0;i<n;i++)
{
outfp_size+=value_final[i]*HC[i].cd_len;
}
if(outfp_size%8==0)
outfp_size=outfp_size/8;
else
outfp_size=outfp_size/8+1;
outfp_size+=2*n*sizeof(int)+strlen(infp_name)+1+sizeof(int)+sizeof(char)*3;
rate=(float)outfp_size/infp_size;
printf("压缩完成！压缩文件的长度为:%d字节,且压缩比例:%%%.2lf\n",outfp_size,rate*100);
printf("是否输出哈夫曼树存储终态？\n");
scanf("%c",&judge);
if(judge=='y'||judge=='Y')
{
printf("哈夫曼树存储终态为：\n");
for(int i=0;i<n*2-1;i++)
{
if(i!=m-1)
p=HT[i].parent+1;
else
p=0;
if(i>=n)
{
r=HT[i].rchild+1;
l=HT[i].lchild+1;
}
printf("%d\t%d\t%d\t%d\t%d\n",i+1,HT[i].weight,p,l,r );
}
}
fclose(infp);
fclose(outfp);
for(int i=0;i<n;i++)
{
free(HC[i].data);
}
free(HT);
free(HC);
}
int main()
{
int a;
char infp_name[256];
printf("请选择你需要的项目：\n");
printf("1.压缩\n");
printf("2.解压\n");
printf("0.退出\n");
scanf("%d",&a);
while(a!=0)
{
getchar(); //读取空格
switch(a)
{
case 1:
puts("�
