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

/*文件中有些参数定义的比较大，主要是为了适应较大文件的压缩*/ #include #include #include

#include//用以删除多余的中间文件 #define M 100000000000//最大字符数

int op,co[100];//编码表的扫描指针，简易栈co[] typedef struct Hfnode //哈弗曼树结点类型 {

int data;//权值域 char zimu;//存储字母

struct Hfnode *Lson,*Rson,*next;//儿子链域和森林链域

}Hfnode,*Hfptr;

typedef struct snode//静态数组结点类型 {

char c;//字符 int f1;//频度 }snode;

typedef struct Lnode//编码表结点类型 { char c; struct Lnode *next; }Lnode,*Lptr;

void gotoxy(int x,int y){ COORD coord; coord.X=x; coord.Y=y;

SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HANDLE ), coord ); }

void paint1() {

int i,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);

void paint2() {

int i,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(\还原结果：\

}

int putdata(Lptr strhead)//输入函数 {

Lptr p; FILE*fp; int i=0;

char infile[30]; p=strhead; gotoxy(0,5);

scanf(\

if((fp=fopen(infile,\{ }

printf(\文件打开错误！\\n\exit(0);

while(!feof(fp)) {

p->c=fgetc(fp)&0xFF; p->next=new Lnode; p=p->next;

/*putchar(ch[i]);*/ i++;

}

putchar(10); fclose(fp); return(i-1); }

int stat(Lptr p,snode ch2[],int num)//统计函数 {

int i,j,last=0; for(i=0;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++;

else ch2[j].f1++; p=p->next; }

return(last); }

void order(snode ch2[],int n)//冒泡排序 { int i,j,k,t;

char a;

for(i=0;i

k=i;

for(j=i+1;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;

}

}

}

Hfptr inition(int n,snode ch2[])//初始化函数，造森林链 {

int i;

Hfptr h,p;

h=p=new Hfnode;

h->data=M;//构造监督原结点 for(i=0;i

{ p->next=new Hfnode;//申请结点

p=p->next; p->Lson=p->Rson=NULL;//做叶节点 }

p->zimu=ch2[i].c;

p->data=ch2[i].f1;//读入叶之权wi

p->next=h;//构成循环链 return h;

}

Hfptr creatHftree(Hfptr head,int n)//构造树 {

int i;

Hfptr p,q,r,t1,t2;

for(i=1;i

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->datadata)

{q=p;p=p->next;}//尚未找到时，继续循环

else {r->next=p;q->next=r;break;}//找到后，插入p }//终止for循环

p=head->next;

delete head;//删去监督元

return (p);//返回huffman树之根 }

//构造完毕

Lptr pop(int last) { }

void codelist(Hfptr p,Lnode list[],int last,int a)//造编码表的函数 { if(p->Lson==NULL&&p->Rson==NULL) {list[op].c=p->zimu; }

char trans(int a[])//8位01整数转换为10进制数 {

int j=0,y=0; do

{

y=y+a[j]*(int)pow(2,7-j%8); j++;

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); int i; Lptr head,p; head=p=new Lnode; for(i=0;i

p->c=co[i];

p->next=new Lnode; p=p->next;

}

p->c=-1;

return(head);

}while(j%8); return(y);

}

int restoretree(snode ch2[],int num2,int num1,char outfile[])

{ }

FILE*out1; int i=0,j=0;

if((out1=fopen(outfile,\{

printf(\文件打开错误！\\n\exit(0);

}

fwrite(&num1,sizeof(int),1,out1); fwrite(&num2,sizeof(int),1,out1); j=j+4;

for(i=0;i

{fwrite(&ch2[i].c,sizeof(char),1,out1); fwrite(&ch2[i].f1,sizeof(int),1,out1); j=j+3;}

fclose(out1); return(j);

int compress(Lptr q,Lnode list[],int num,char outfile[])//压缩函数 {

int y=0,i=0,j=0,top=0,n=0,a[8]; Lptr p; FILE*out;

if((out=fopen(outfile,\

{

printf(\文件打开错误！\\n\

exit(0); }

while(i

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); }

int recover(snode ch2[])//还原文件函数 {

FILE*in,*out1,*out2;

Hfptr p,head,Hfroot;;//p为哈夫曼树搜索指针 char ch1[100];

int i=0,z=0,a,m=0,num1,num2; char outfile1[30];

char outfile2[30]; gotoxy(0,5);

scanf(\

if((in=fopen(outfile1,\二进制的文件打开，避免意外结束的问题 {

printf(\文件打开错误！\\n\

exit(0); }

if((out1=fopen(\临时储存01串，避免大容量数组的使用 }

{

printf(\文件打开错误！\\n\exit(0);

fread(&num1,sizeof(int),1,in); fread(&num2,sizeof(int),1,in); for(z=0;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(\{ }

printf(\文件打开错误！\\n\exit(0);

gotoxy(0,8);

scanf(\gotoxy(0,11); printf(\请稍候...\gotoxy(0,11);

if((out2=fopen(outfile2,\{ printf(\文件打开错误！\\n\ exit(0); }

while(!feof(out1)&&m

{if(p->Lson==NULL&&p->Lson==NULL)//非递归遍历哈夫曼树，输出所需叶节点 {

fputc(p->zimu,out2),m++; p=Hfroot;}

if(fgetc(out1)==0)p=p->Lson; else p=p->Rson;

}

if(!feof(out1)&&fgetc(out1)!=0||m

DeleteFile(\if(i==-1)return 0; else return 1;

void main() {

int num1,num2,num3,choice,choice2; char outfile[30]; Lptr strhead;

snode ch2[300];

Lnode list[3000];//编码表 Hfptr Hfroot,head; do

{gotoxy(25,0);

printf(\小型文本压缩器\\n\

printf(\请输入需要进行的操作：\\n1——压缩； 2——解压\\n\strhead=new Lnode; op=0;

scanf(\gotoxy(0,3);

if(choice==1)//压缩部分 { paint1();//优化界面函数

num1=putdata(strhead);//输入函数，num1记录字符总数 num2=stat(strhead,ch2,num1);//统计函数，num2记录叶子数 order(ch2,num2);//排序函数

head=inition(num2,ch2);//调用初始化函数

Hfroot=creatHftree(head,num2);//调用造树函数 codelist(Hfroot,list,0,0);//造编码表 gotoxy(0,8);

scanf(\

gotoxy(0,11);

printf(\请稍后...\

num3=restoretree(ch2,num2,num1,outfile);//存储哈夫曼树

num3=num3+compress(strhead,list,num1,outfile);//压缩函数，num3记录压缩后的字gotoxy(0,11);

printf(\计算压缩率 gotoxy(0,13);

符数

} {

else if(choice==2)//还原部分

paint2();//优化界面函数 if(recover(ch2))

printf(\操作成功！\

gotoxy(0,13);//还原函数 }

else printf(\输入错误！\\n\

printf(\是否继续？1——继续；2——结束\\n\scanf(\

if(choice2==1)system(\}while(choice2==1);

printf(\谢谢使用，再见！\\n\

}

//本程序由何劼、唐宇珠、任相泉、王枫皓设计编写

本文来源：https://www.bwwdw.com/article/ic4r.html