20081102
可压缩任意类型的文件,但压缩率远比不上RAR,测试一张BMP图片3次赫夫曼最高压缩率27%,RAR可达3%。这说明数据结构还是很有用的,但我觉得如果能运用于实践会更好。
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<stdlib.h>
#include<conio.h>
typedef struct htn
{
unsigned long weight;
struct htn *father;
struct htn *lchild;
struct htn *rchild;
}HTN;
{
unsigned long weight;
struct htn *father;
struct htn *lchild;
struct htn *rchild;
}HTN;
void error();
HTN *mi(HTN *head,HTN *end);
void compress(char *iname);
HTN *btree(HTN p[511]);
void scopy(char *de,char *so);
void coding(char code[256][18],HTN ht[511],HTN *p);
void outtree(FILE *out,HTN p[511]);
FILE *outbehind(char *q);
void outinfo(FILE *in,FILE *out,char code[256][18]);
HTN *mi(HTN *head,HTN *end);
void compress(char *iname);
HTN *btree(HTN p[511]);
void scopy(char *de,char *so);
void coding(char code[256][18],HTN ht[511],HTN *p);
void outtree(FILE *out,HTN p[511]);
FILE *outbehind(char *q);
void outinfo(FILE *in,FILE *out,char code[256][18]);
void main()
{
char iname[20];
{
char iname[20];
printf("inname:");
scanf("%s",iname);/*未处理溢出*/
compress(iname);
getch();/*getchar报警告?*/
}
scanf("%s",iname);/*未处理溢出*/
compress(iname);
getch();/*getchar报警告?*/
}
void error()
{
printf("\n\nError!");
getch();
exit(0);
}
{
printf("\n\nError!");
getch();
exit(0);
}
HTN *mi(HTN *head,HTN *end)
{
HTN *min=0;
for(;head<=end;head++)
if(head->weight&&!head->father&&(min==0||head->weight<min->weight))
min=head;
if(!min->weight||min->father){printf("!!%d",min);getch();return 0;}
min->father=min;
return min;
}
{
HTN *min=0;
for(;head<=end;head++)
if(head->weight&&!head->father&&(min==0||head->weight<min->weight))
min=head;
if(!min->weight||min->father){printf("!!%d",min);getch();return 0;}
min->father=min;
return min;
}
void compress(char *iname)
{
FILE *in,*out;
HTN ht[511]={0},*base;/*指针可置0?*/
char code[256][18]={0};
int i;
/*堆管理会更好*//*位段?*//*不超过16位?*/
if(!(in=fopen(iname,"rb")))error();
while(!feof(in))ht[fgetc(in)].weight++;
base=btree(ht);
printf("btree finish");getch();
coding(code,ht,base);
printf("coding finish");getch();
{
FILE *in,*out;
HTN ht[511]={0},*base;/*指针可置0?*/
char code[256][18]={0};
int i;
/*堆管理会更好*//*位段?*//*不超过16位?*/
if(!(in=fopen(iname,"rb")))error();
while(!feof(in))ht[fgetc(in)].weight++;
base=btree(ht);
printf("btree finish");getch();
coding(code,ht,base);
printf("coding finish");getch();
out=outbehind(iname);
outtree(out,ht);
printf("outtree finish");getch();
fseek(in,0l,0);
for(i=0;i<18;i++)printf("!%d",code[255][i]);
getch();
outinfo(in,out,code);
printf("\n\nFinish!");
}
outtree(out,ht);
printf("outtree finish");getch();
fseek(in,0l,0);
for(i=0;i<18;i++)printf("!%d",code[255][i]);
getch();
outinfo(in,out,code);
printf("\n\nFinish!");
}
HTN *btree(HTN p[511])
{
HTN *head=p,*end=p+510,*min1,*min2;
int i;
for(i=0;i<=510;i++)printf("%lu ",head[i].weight);getch();
for(p+=256;p<=end;p++)
{
min1=mi(head,p-1);/*指针的指针?*/
min2=mi(head,p-1);
if(!min1||!min2){p=min1?min1:min2;p++;break;}/*当出现权为0时运行出错*/
min1->father=min2->father=p;
p->weight=min1->weight+min2->weight;/*文件最大2G*/
p->lchild=min1;
p->rchild=min2;
}
printf("p-end=%d",p-end);getch();
for(i=0;i<=510;i++)printf("%lu ",head[i].weight);getch();
p--;
p->father=0;
if(!min1&&!min2)error();
if(p==head+255)p=min1?min1:min2;
printf("\n%lu",p->weight);getch();
return p;
}
{
HTN *head=p,*end=p+510,*min1,*min2;
int i;
for(i=0;i<=510;i++)printf("%lu ",head[i].weight);getch();
for(p+=256;p<=end;p++)
{
min1=mi(head,p-1);/*指针的指针?*/
min2=mi(head,p-1);
if(!min1||!min2){p=min1?min1:min2;p++;break;}/*当出现权为0时运行出错*/
min1->father=min2->father=p;
p->weight=min1->weight+min2->weight;/*文件最大2G*/
p->lchild=min1;
p->rchild=min2;
}
printf("p-end=%d",p-end);getch();
for(i=0;i<=510;i++)printf("%lu ",head[i].weight);getch();
p--;
p->father=0;
if(!min1&&!min2)error();
if(p==head+255)p=min1?min1:min2;
printf("\n%lu",p->weight);getch();
return p;
}
void scopy(char *de,char *so)
{
while((*de++=*so++)!=-1);
}
{
while((*de++=*so++)!=-1);
}
void coding(char code[256][18],HTN ht[511],HTN *p)
{
HTN *head=ht,*end=ht+510;
char temp[18],deep=1;
{
HTN *head=ht,*end=ht+510;
char temp[18],deep=1;
for(;ht<=end;ht++)ht->weight=0;
while(p)
{
if(p->weight==0)
{
p->weight=1;
if(p->lchild)
{
p=p->lchild;
temp[deep++]=0;
}
else
{
temp[deep]=-1;
temp[0]=deep-1;
scopy(code[p-head],temp);/*256次调用过多,可改进*/
}
}
else if(p->weight==1)
{
p->weight=-1;
if(p->rchild)
{
p=p->rchild;
temp[deep++]=1;
}
}
else
{
p=p->father;
deep--;
}
}
}
while(p)
{
if(p->weight==0)
{
p->weight=1;
if(p->lchild)
{
p=p->lchild;
temp[deep++]=0;
}
else
{
temp[deep]=-1;
temp[0]=deep-1;
scopy(code[p-head],temp);/*256次调用过多,可改进*/
}
}
else if(p->weight==1)
{
p->weight=-1;
if(p->rchild)
{
p=p->rchild;
temp[deep++]=1;
}
}
else
{
p=p->father;
deep--;
}
}
}
void outtree(FILE *out,HTN p[511])
{
HTN *head=p,*end=p+510;
{
HTN *head=p,*end=p+510;
for(p+=256;p<=end;p++)
{
fputc(p->lchild?p->lchild-head:255,out);
fputc(p->rchild?p->rchild-head:255,out);
}
}
{
fputc(p->lchild?p->lchild-head:255,out);
fputc(p->rchild?p->rchild-head:255,out);
}
}
FILE *outbehind(char *q)
{
char oname[20],*p=oname;
FILE *out;
{
char oname[20],*p=oname;
FILE *out;
while((*p++=*q++)!='.');/*未处理没有后缀的情况*/
*p++='r';
*p++='s';
*p=0;
if(!(out=fopen(oname,"wb")))error();
while(*q)fputc(*q++,out);/*可改进?*/
fputc(0,out);
return(out);
}
*p++='r';
*p++='s';
*p=0;
if(!(out=fopen(oname,"wb")))error();
while(*q)fputc(*q++,out);/*可改进?*/
fputc(0,out);
return(out);
}
void outinfo(FILE *in,FILE *out,char code[256][18])
{
char t[25]={0},*p,*q;/*位运算更快?*/
unsigned char we[9]={128,64,32,16,8,4,2,1,0},m,*w;
{
char t[25]={0},*p,*q;/*位运算更快?*/
unsigned char we[9]={128,64,32,16,8,4,2,1,0},m,*w;
while(!feof(in))
{
if(*t>=8)/*取一个字节*/
{
for(p=t+1,m=0,w=we,*t-=8;*w;w++,p++)
if(*p)m+=*w;
fputc(m,out);
q=t+1;
while((*q++=*p++)!=-1);
}
else/*连接*/
{
q=t+*t+1;
p=code[fgetc(in)];
*t+=*p;
p++;
while((*q++=*p++)!=-1);
}
}
}
{
if(*t>=8)/*取一个字节*/
{
for(p=t+1,m=0,w=we,*t-=8;*w;w++,p++)
if(*p)m+=*w;
fputc(m,out);
q=t+1;
while((*q++=*p++)!=-1);
}
else/*连接*/
{
q=t+*t+1;
p=code[fgetc(in)];
*t+=*p;
p++;
while((*q++=*p++)!=-1);
}
}
}