课题.cpp

对一篇文章编码和解码

//各种类型的定义
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100000
typedef struct
{int weight;
int parent,lchild,rchild;
char name;
}htnode,*huffmantree;
typedef char ** huffmancode;



//从文件中读入要译码的文件，把它放在一维数组中
void input(char a[])
{FILE *fp;
char ch;
int i=0;
if((fp=fopen("file.txt","r+"))==NULL)
{printf("can not open the file\n");
exit(0);
}
ch=fgetc(fp);
while(ch!=EOF) 
{a[i++]=ch;
ch=fgetc(fp);
}
a[i]='\0';
}



//输出要编码的文件
void output(char a[])
{int i=0;
while(a[i]!='\0')
putchar(a[i++]);
printf("\n\n");
}




//统计一维数组中有多少种不同的字符，各有多少个
void tongji2(char a[],char c[],int bb[])
{int i=0,j,k,sum=0;
j=1;
int b[100]={0};
float d[100];
c[j]=a[i];b[j]++;j++;
sum++;
for(i=1;a[i]!='\0';i++)
{sum++;
	for(k=1;k<j;k++)
if(a[i]==c[k]){b[k]++;break;}
 if(k==j&&a[i]!=c[--k])
 {c[j]=a[i];b[j]++;j++;}
}
c[j]='\0';
for(i=1;c[i]!='\0';i++)
{
d[i]=(b[i]*1.0/sum)*1000.;
bb[i]=(int)d[i];
}
}



//从树中选取没有父亲的节点的权值最小的两个序号
void select(huffmantree ht, int n,int &s1,int &s2)
{int a[100];
int b[100];
int j=0,k=0;
int n1,n2;
int i;
int t,t1;
	huffmantree p=ht+1;
for(i=1;i<=n;i++,p++)
if(p->parent==0)
{a[j]=p->weight;
b[k]=i; k++;
j++;}
n1=j;
n2=k;
for(k=0;k<n2;k++)
for(j=k+1;j<n2;j++)
if(a[k]>a[j])
{t=a[k]; t1=b[k];a[k]=a[j];b[k]=b[j];b[j]=t1;a[j]=t;}
s1=b[0];
s2=b[1];
}



//进行编码
void huffmancoding(huffmantree &ht,huffmancode &hc,int *w,char *s,int n)
{int m;
huffmantree p;
char *cd;
int i;
int s1,s2;
int start;
int c,f;
w++;s++;

	if(n<=1)return ;
	m=2*n-1;
	ht=(huffmantree)malloc((m+1)*sizeof(htnode));

for(p=ht+1,i=1;i<=n;++i,++p,++s,++w)
{p->weight=*w; p->parent=0;
p->lchild=p->rchild=0;
p->name=*s;
}

for(i=n+1;i<=m;i++,p++)
{p->weight=p->parent=p->lchild=p->rchild=0;
p->name='\0';
}
//树的初始化


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].weight=ht[s1].weight+ht[s2].weight;
ht[i].name='\0';
}
//形成一颗完整的二叉树


//把字符对应的编码纪录到一个数组里
hc=(huffmancode)malloc((n+1)*sizeof(char *));

cd=(char*)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{start=n-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]);
}
}



//译码
void huffmanyima2(huffmantree ht,char *e,char p[],int m)
{int i,t,j=0;
t=m;
for(i=0;*(e+i)!='\0';i++)
{if(*(e+i)=='0')
t=ht[t].lchild;
else 
	t=ht[t].rchild;

if(ht[t].lchild==0 && ht[t].rchild==0)
{	p[j++]=ht[t].name;
t=m;
}
}
p[j]='\0';
printf("\n");
}



//生成译码文件
void save2(char a[])
{FILE *fp;
int k=0;
if((fp=fopen("file2.txt","w+"))==NULL)
{printf("can't open the file\n");
exit(0);
}
while(a[k]!='\0')
{fputc(a[k],fp);
k++;}
fclose(fp);
}



//生成编码文件
void save(char a[],char c[],huffmancode hc,char aa[],int n)
{FILE *fp;
	int i,j,k,t=0;
k=0;
char r[300000];
for(i=0;a[i]!='\0';i++)
{for(j=1;j<=n;j++)
if(a[i]==c[j])
{strcpy(&aa[t],hc[j]);
strcpy(&r[k],hc[j]);
k=strlen(r);
t=strlen(aa);
r[k]=' ';
k++;
}
}
r[k]=aa[t]='\0';
k=0;
//printf("%s\n",aa);
if((fp=fopen("file1.txt","w+"))==NULL)
{printf("can't open the file\n");
exit(0);
}
while(r[k]!='\0')
{fputc(r[k],fp);
k++;}
fclose(fp);
}



void main()
{char a[MAXSIZE];
char c[100];
int i,j,k,t,n;
char p[MAXSIZE];
t=0;
int b[100]={0};
	
input(a);
   output(a);
	tongji2(a,c,b);


n=strlen(c)-1;
huffmantree ht;
huffmancode hc;
char aa[300000];

huffmancoding (ht,hc,b,c,n);

for(i=1;i<=n;i++)
printf("%3c  %s\n",ht[i].name,hc[i]);
printf("\n\n");

save(a,c,hc,aa,n);

huffmanyima2(ht,aa,p,2*n-1);

save2(p);

}