#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 20
typedef struct
{
char data;
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;//结点类型
void Select(HuffmanTree *H,int n,int *p,int *q)//求前n个结点中父结点不存在，并且权值最小的两个结点
{
HuffmanTree HT,HT2;
int i;
HT=NULL;
HT2=NULL;
for(i=1;i<=n;i++)//求权值最小的结点
if(H[i]->parent==0 && HT==NULL)
{
HT=H[i];
*p=i;
}
else if(H[i]->parent==0 && H[i]->weight < HT->weight)
{
HT=H[i];
*p=i;
}
for(i=1;i<=n;i++)//求权值次小的结点
if(H[i]->parent==0 && HT2==NULL && H[i]!=HT)
{
HT2=H[i];
*q=i;
}
else if(H[i]->parent==0 && H[i]!=HT && H[i]->weight < HT2->weight)
{
HT2=H[i];
*q=i;
}
}//Select
void Read(int geshu)//读出bianma1.txt即所得编码文件中的内容
{
FILE *fp;
int i=1;
char *ch;
if((fp=fopen("D:\\bianma1.txt","r"))==NULL) exit(-1);
printf("所得电文编码如下：\n");
for(i=1;i<geshu;i++)
{
ch=(char *)malloc(sizeof(char));
fread(&ch,sizeof(char *),1,fp);
printf("%s ",ch);
}
putchar('\n');
fclose(fp);
}
HuffmanTree * Bian_ma(int *a)//给出电文文件，对该电文进行编码并保存在文件中
{
HuffmanTree *HT,*H;
FILE *fp,*fp1;
int w[28]={0};
int num=0,m=0,i=1,start=0,geshu=0,j=1;
int cout[27]={0},n=1;
int p1=0,p2=0;
char d[50]={'\0'},*cd,**HC;
if((fp=fopen("D:\\dianwen.txt","r"))==NULL)//dianwen.txt为电文文件
{
printf("cannot open the file1\n"); exit(-1);
}
while(!feof(fp))
{
d[i++]=fgetc(fp);
}//while
geshu=i-1;//电文中含有的总字母个数
i=1;
while(d[i]>='a' && d[i]<='z')
{
w[d[i++]-96]++;//求电文中各个字母的权值，如w[1]为A的权值
}
i=1;
while(i <= 26)//求含有几个非同字母
{
if(w[i++]) num++;
}
for(i=1;i<=26;i++)//cout[i]表示电文中字母X的编码为HC[cout[X-96]]
{
if(w[i]) cout[i]=n++; //n开始为1
}
m=2*num-1;//需要的总结点数目
*a=m;//返回树的结点个数，用于译码函数
HT=(HuffmanTree * ) malloc ((m+1)*sizeof(HuffmanTree));
for(i=1;i<=m;i++)
HT[i]=(HuffmanTree ) malloc (sizeof(HTNode));
H=&HT[1];
for(i=1;i<28;i++)//初始化HT[]
{
if(w[i])
{
(*H)->data=96+i;
(*H)->weight=w[i];
(*H)->parent=0;
(*H)->lchild=0;
(*H)->rchild=0;
H++;
}
}
for(i=num+1;i<=m;i++)//初始化
{
(*H)->data='\0';
(*H)->weight=0;
(*H)->parent=0;
(*H)->lchild=0;
(*H)->rchild=0;
H++;
}
for(i=num+1;i<=m;i++)//构造哈夫曼树
{
Select(HT,i-1,&p1,&p2);//在前i-1个节点中选择parent为0的两个权值最小的结点位置赋给p1，p2
HT[p1]->parent=i;
HT[p2]->parent=i;
HT[i]->lchild=p1;
HT[i]->rchild=p2;
HT[i]->weight=HT[p1]->weight+HT[p2]->weight;
}
HC=(char **) malloc ((num+1)*sizeof(char *));//HC为字符串数组，0号单元未用
cd=(char *) malloc (num*sizeof(char));
cd[num-1]='\0';//使cd为字符串
for(i=1;i<=num;i++)//对每个字母求编码
{
start=num-1;
for(p1=i,p2=HT[i]->parent;p2!=0;p1=p2,p2=HT[p2]->parent)//从叶子结点逆向求编码
{
if(HT[p2]->lchild==p1)//p1为左子树
cd[--start]='0';
else cd[--start]='1';
}
HC[i]=(char *) malloc ((num-start)*sizeof(char));
strcpy(HC[i],&cd[start]);//字符串复制HC[i]为第i个非同字母的编码
}//for i
free(cd);
if((fp1=fopen("D:\\bianma1.txt","w"))==NULL) exit(-1);
while(d[j]>= 'a' && d[j]<='z')//将编码存入到文件2中
{
if(fwrite(&HC[cout[d[j]-96]],sizeof(char *),1,fp1)!=1)
printf("存储编码时出错\n");
j++;
}
fclose(fp);
fclose(fp1);
Read(geshu);//输出电文编码
return HT;
}//GouHuff
void Du_yima()//输出译码后的文件的内容
{
FILE *fp1;
char ch;
if((fp1=fopen("D:\\yima2.txt","r"))==NULL)
{
printf("can not open yima2.txt\n");
exit(-1);
}
printf("所得译码为:\n");
while(!feof(fp1))
{
ch=fgetc(fp1);
if(ch>='a' && ch<='z')
putchar(ch);
}
putchar('\n');
fclose(fp1);
return;
}
void Yi_ma(HuffmanTree *HT,int m)//给出编码要求译码
{
HuffmanTree H;
FILE *fp,*fp2;
char ch=' ',ma[MAX];
int i=0,j=0;
if((fp=fopen("D:\\yima1.txt","r"))==NULL) exit(-1);//yima1.txt是所给的编码文件
while(!feof(fp))//译码过程
{
H=HT[m];
while(H->lchild||H->rchild)//从根开始直到找到叶子结点
{
ch=fgetc(fp);
if(ch==EOF) break;
if(ch=='0')
H=HT[H->lchild];
else if(ch=='1') H=HT[H->rchild];
}
if(ch==EOF) break;//文件结束则，跳出循环
else
ma[i++]=H->data;//H为叶子结点，将其包含的字母赋给ma[]
}
ma[i]='\0';
fp2=fopen("D:\\yima2.txt","w");//yima2.txt为所得电文
for(j=0;j<i;j++)//将所得译码存入文件
{
fputc(ma[j],fp2);
}
fclose(fp);
fclose(fp2);
Du_yima();//读取yima2.txt中的内容
return;
}
void main()//说明：电文为小写字母
{
HuffmanTree *HT;
int m=1;//m返回所求哈夫曼树的结点个数，对译码过程有用处
HT=Bian_ma(&m);//给出电文求编码
Yi_ma(HT,m);//给编码译为电文
}//main
评论0