哈夫曼文本压缩C语言实现

/*文件中有些参数定义的比较大，主要是为了适应较大文件的压缩*/#include<stdio.h>#include<stdlib.h>#include<math.h>#include<windows.h>//用以删除多余的中间文件#defineM100000000000//最大字符数intop,co[100];//编码表的扫描指针，简易栈co[]typedefstructHfnode//哈弗曼树结点类型{ intdata;//权值域 charzimu;//存储字母 structHfnode*Lson,*Rson,*next;//儿子链域和森林链域}Hfnode,*Hfptr;typedefstructsnode//静态数组结点类型{ charc;//字符 intf1;//频度}snode;typedefstructLnode//编码表结点类型{ charc; structLnode*next;}Lnode,*Lptr;voidgotoxy(intx,inty){COORDcoord;coord.X=x;coord.Y=y;SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);}voidpaint1(){ inti,j; for(j=0;j<4;j++) {for(i=0;i<70;i++)//简易画线代码，呵呵 putchar(95); putchar(10);putchar(10);putchar(10); } gotoxy(0,4); printf("请输入需打开的文件路径："); gotoxy(0,7); printf("请输入压缩文件的保存路径："); gotoxy(0,10); printf("此次文件压缩率为："); gotoxy(0,13); }voidpaint2(){ inti,j; for(j=0;j<4;j++)//画4行直线 {for(i=0;i<70;i++)//简易画线代码，呵呵 putchar(95); putchar(10);putchar(10);putchar(10); } gotoxy(0,4); printf("请输入解压文件的路径："); gotoxy(0,7); printf("请输入还原文件的保存路径："); gotoxy(0,10); printf("还原结果：");} intputdata(Lptrstrhead)//输入函数{ Lptrp; FILE*fp; inti=0; charinfile[30]; p=strhead; gotoxy(0,5); scanf("%s",infile); if((fp=fopen(infile,"rb"))==NULL) { printf("文件打开错误！\n"); exit(0); }while(!feof(fp)){ p->c=fgetc(fp)&0xFF; p->next=newLnode; p=p->next; /*putchar(ch[i]);*/ i++; }putchar(10);fclose(fp);return(i-1);}intstat(Lptrp,snodech2[],intnum)//统计函数{ inti,j,last=0; for(i=0;i<num;i++) { for(j=0;ch2[j].c!=p->c&&j!=last;) j++; if(j==last) { ch2[j].c=p->c; ch2[j].f1=1; last++; } elsech2[j].f1++; p=p->next; }return(last);}voidorder(snodech2[],intn)//冒泡排序{ inti,j,k,t; chara; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(ch2[j].f1<ch2[k].f1)k=j; if(k!=i) { t=ch2[i].f1; a=ch2[i].c; ch2[i].c=ch2[k].c; ch2[i].f1=ch2[k].f1; ch2[k].c=a; ch2[k].f1=t; } }}Hfptrinition(intn,snodech2[])//初始化函数，造森林链{ inti; Hfptrh,p;h=p=newHfnode;h->data=M;//构造监督原结点for(i=0;i<n;i++) { p->next=newHfnode;//申请结点p=p->next; p->Lson=p->Rson=NULL;//做叶节点 p->zimu=ch2[i].c; p->data=ch2[i].f1;//读入叶之权wi} p->next=h;//构成循环链 returnh;}HfptrcreatHftree(Hfptrhead,intn)//构造树{ inti; Hfptrp,q,r,t1,t2;for(i=1;i<n;i++)//进行n-1编合并 { r=newHfnode;//申请新根 t1=head->next;//t1,t2指向两棵权最小的树根 t2=t1->next; r->data=t1->data+t2->data;//权值相加 r->Lson=t1;//t1,t2做新根r的左右儿子r->Rson=t2; head->next=t2->next;//从森林中删去t1,t2 q=head;//准备进行有序插入 p=head->next;//p是搜索指针，q是p的前驱 while(1)//循环的为r寻找有序位置 if(p->data<r->data) {q=p;p=p->next;}//尚未找到时，继续循环 else {r->next=p;q->next=r;break;}//找到后，插入p }//终止for循环 p=head->next;deletehead;//删去监督元return(p);//返回huffman树之根}//构造完毕Lptrpop(intlast){ inti; Lptrhead,p; head=p=newLnode; for(i=0;i<last;i++) { p->c=co[i]; p->next=newLnode; p=p->next; } p->c=-1; return(head);}voidcodelist(Hfptrp,Lnodelist[],intlast,inta)//造编码表的函数{ if(p->Lson==NULL&&p->Rson==NULL) {list[op].c=p->zimu; list[op].next=pop(last); op++; return;} codelist(p->Lson,list,last+1,co[last]=0); codelist(p->Rson,list,last+1,co[last]=1);}chartrans(inta[])//8位01整数转换为10进制数{ intj=0,y=0; do { y=y+a[j]*(int)pow(2,7-j%8); j++; }while(j%8); return(y);}intrestoretree(snodech2[],intnum2,intnum1,charoutfile[]){ FILE*out1; inti=0,j=0; if((out1=fopen(outfile,"wb"))==NULL) { printf("文件打开错误！\n"); exit(0); } fwrite(&num1,sizeof(int),1,out1); fwrite(&num2,sizeof(int),1,out1); j=j+4; for(i=0;i<num2;i++) {fwrite(&ch2[i].c,sizeof(char),1,out1); fwrite(&ch2[i].f1,sizeof(int),1,out1); j=j+3;} fclose(out1); return(j);}intcompress(Lptrq,Lnodelist[],intnum,charoutfile[])//压缩函数{ inty=0,i=0,j=0,top=0,n=0,a[8]; Lptrp; FILE*out; if((out=fopen(outfile,"ab"))==NULL) { printf("文件打开错误！\n"); exit(0); } while(i<num) { while(q->c!=list[j].c) j++; p=list[j].next; i++; q=q->next; j=0; while(p->c!=-1&&top<8) { a[top]=p->c; p=p->next; top++; if(top==8) {fputc(trans(a),out); top=0; n++;} } } if(top<8) {while(top<8) a[top++]=0; fputc(trans(a),out); n++;}fclose(out);return(n);}intrecover(snodech2[])//还原文件函数{ FILE*in,*out1,*out2; Hfptrp,head,Hfroot;;//p为哈夫曼树搜索指针 charch1[100]; inti=0,z=0,a,m=0,num1,num2; charoutfile1[30]; charoutfile2[30]; gotoxy(0,5); scanf("%s",outfile1); if((in=fopen(outfile1,"rb"))==NULL)//二进制的文件打开，避免意外结束的问题 { printf("文件打开错误！\n"); exit(0); } if((out1=fopen("d:\\change.txt","w"))==NULL)//临时储存01串，避免大容量数组的使用 { printf("文件打开错误！\n"); exit(0); } fread(&num1,sizeof(int),1,in); fread(&num2,sizeof(int),1,in); for(z=0;z<num2;z++) {fread(&ch2[z].c,sizeof(char),1,in); fread(&ch2[z].f1,sizeof(int),1,in);} head=inition(num2,ch2);//调用初始化函数 Hfroot=creatHftree(head,num2);//调用造树函数 p=Hfroot; while(!feof(in)) { a=fgetc(in)&0xFF;//位运算，实现对中文的操作 while(a) {ch1[i++]=a%2; a=a/2;} for(;i!=8;i++) ch1[i]=0; for(;i!=0;i--) fputc(ch1[i-1],out1);//8位01字符倒置输出 } fclose(in);//关闭压缩文件 fclose(out1);//关闭临时文件 if((out1=fopen("d:\\change.txt","rb"))==NULL) { printf("文件打开错误！\n"); exit(0); } gotoxy(0,8); scanf("%s",outfile2); gotoxy(0,11); printf("请稍候..."); gotoxy(0,11); if((out2=fopen(outfile2,"wb"))==NULL) { printf("文件打开错误！\n"); exit(0); } while(!feof(out1)&&m<num1) {if(p->Lson==NULL&&p->Lson==NULL)//非递归遍历哈夫曼树，输出所需叶节点 { fputc(p->zimu,out2),m++; p=Hfroot;} if(fgetc(out1)==0)p=p->Lson; elsep=p->Rson; } if(!feof(out1)&&fgetc(out1)!=0||m<num1) printf("解压失败！\n"),i=-1; fclose(out1); fclose(out2); DeleteFile("D:\\change.txt"); if(i==-1)return0; elsereturn1;}voidmain(){ intnum1,num2,num3,choice,choice2; charoutfile[30]; Lptrstrhead; snodech2[300]; Lnodelist[3000];//编码表 HfptrHfroot,head; do {gotoxy(25,0); printf("小型文本压缩器\n"); printf("请输入需要进行的操作：\n1——压缩；2——解压\n"); strhead=newLnode; op=0; scanf("%d",&choice); gotoxy(0,3); if(choice==1)//压缩部分 { paint1();//优化界面函数 num1=putdata(strhead);//输入函数，num1记录字符总数 num2=stat(strhead,ch2,num1);//统计函数，num2记录叶子数 order(ch2,num2);//排序函数 head=i