#include
#include
#include
int count=0;//用来计算叶子结点
int NUM=0;//用来计算短文字母总数
int min[2];
typedef struct Essays
{
char ch;
int num;
struct Essays *next;
}Essay;
typedef struct Huff_Trees
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}Huff_Tree;
void write(char ch[])
{
int i=0;
FILE *fp;
if((fp=fopen("F:\数据结构\实验\a.txt","w"))==NULL)
{
printf("can't open file a!\n");
exit(0);
}
while(ch[i]!='\0')
{
fputc(ch[i],fp);
putchar(ch[i]);
i++;
}
putchar(10);
rewind(fp);
fclose(fp);
}
void count1(char cha[],Essay *head)
{
Essay *essay,*p,*end;
int i=0;
p=head;
end=head;
printf("正在计算短文的长度和各个字母出现的次数！\n");
while(cha[i]!='\0')
{
for(p=head;p!=NULL;p=p->next)
{
if(p->ch==cha[i])
{
(p->num)++;
break;
}
}
if(p==NULL)
{
essay=(Essay *)malloc(1*sizeof( Essay));
essay->ch=cha[i];
essay->num=1;
essay->next=NULL;
end->next=essay;
end=end->next;
NUM++;
}
count++;
i++;
}
printf("计算结果如下：共有%d个字母,%d个不同的字母\n",count,NUM);
printf("字母 出现次数\n");
for(p=head->next;p!=NULL;p=p->next)
{
printf("%c %d",p->ch,p->num);
printf("\n");
}
printf("计算结果显示完毕！\n");
// free(essay);
}
void Select(Huff_Tree ht[],int n)
{
int i,j,tep=1;
for(i=1;i<=n;i++)
{
if(ht[i].parent==0)
{
if(tep==1)
min[0]=i;
else
min[1]=i;
tep++;
}
if(tep>2)
break;
}
if(min[0]>min[1])
{
tep=min[0];
min[0]=min[1];
min[1]=tep;
}
for(j=i+1;j<=n&&ht[j].parent==0;j++)
if(ht[j].weight<ht[min[1]].weight)
{
if(ht[j].weight<ht[min[0]].weight)
{
min[1]=min[0];
min[0]=j;
}
else
min[1]=j;
}
}
void HuffmanCoding(Essay head,char **HC,Huff_Tree HT[])
{
char *cd;
Essay *ess;
int m=2*NUM-1,term;
int i,s1,s2,start,c,f;
ess=head->next;
if(NUM<=1)
printf("该树只有一个结点！\n");
cd=(char *)malloc(NUM*sizeof(char));
for(i=1;i<=NUM;i++,ess=ess->next)
{
HT[i].weight=ess->num;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=NUM+1;i<=m;i++)
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=NUM+1;i<=m;i++)//建立赫夫曼树
{
Select(HT,i-1);
s2=min[0];
s1=min[1];
if((HT[s1].lchild!=0||HT[s1].rchild!=0)&&(HT[s2].lchild==0||HT[s2].rchild==0))
{
term=s2;
s2=s1;
s1=term;
}
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;
}
printf("得出的赫夫曼树如下：\nweight parent lchild rchild\n");
for(i=1;i<=m;i++)
printf("%d %d %d %d\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
//求赫夫曼编码
printf("现在进行赫夫曼编码的求解：\n");
cd[NUM-1]='\0';
for(i=1;i<=NUM;i++)
{
start=NUM-1;
for(c=i,f=HT[i].parent;HT[c].parent!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=(char *)malloc((NUM-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
//printf("%s\n",cd);
}
printf("赫夫曼编码如下：\n");
for(i=1;i
puts(HC[i]);
//for(ess=head->next;ess!=NULL;ess=ess->next)
// printf("%c",ess->ch);
}
void coding(char ch1[],char **Hc,Essay *head)
{
int i,j,t=0;
char **code;
Essay *p;
FILE *fp;
code=(char *)malloc((count)*sizeof(char ));
for(i=0;i
{
for(p=head->next,j=1;p!=NULL;p=p->next,j++)
if(ch1[i]==(p->ch))
{
code[t]=(char *)malloc((strlen(Hc[j]))*sizeof(char ));
strcpy(code[t],Hc[j]);
t++;
break;
}
}
if((fp=fopen("F:\数据结构\实验\b.txt","w+"))==NULL)
{
printf("can't open file b!\n");
exit(0);
}
for(i=0;i<count;i++)
fputs(code[i],fp);
rewind(fp);
fclose(fp);
/ FILE fp1,*fp2;
if((fp1=fopen("F:\数据结构\实验\a.txt","r+"))==NULL)
{
printf("can't open file a!\n");
exit(0);
}
if((fp2=fopen("F:\数据结构\实验\b.txt","w+"))==NULL)
{
printf("can't open file b!\n");
exit(0);
}
while(!feof(fp1))
fputc(fgetc(fp1),fp2);
//printf("b文件：\n");
/*while(!feof(fp2))
putchar(fgetc(fp2));
putchar(10);
rewind(fp1);
rewind(fp2);
fclose(fp1);
fclose(fp2);/
}
void decoding(char **Hc,Essay head)
{
FILE *fp;
char *word;//用来存储译码后的字母
char *temp;
int i,j,t=0;
Essay *p;
if((fp=fopen("F:\数据结构\实验\c.txt","w+"))==NULL)
{
printf("can't open file c!\n");
exit(0);
}
word=(char *)malloc(count*sizeof(char));
temp=(char *)malloc(NUM*sizeof(char));
while(!feof(fp))
{
i=0;
while(fgetc(fp)!='\0')
{
temp[i]=fgetc(fp);
i++;
}
temp[i]='\0';
for(j=1,p=head->next;j<=NUM;j++,p=p->next)
if(strcmp(Hc[j],temp)==0)
{
word[t]=p->ch;
t++;
}
}
for(i=0;i<count;i++)
fputc(word[i],fp);
rewind(fp);
fclose(fp);
}
void equal()
{
FILE *fp1,*fp2;
int flag=1;
if((fp1=fopen("F:\数据结构\实验\a.txt","w+"))==NULL)
{
printf("can't open file a!\n");
exit(0);
}
if((fp2=fopen("F:\数据结构\实验\c.txt","w+"))==NULL)
{
printf("can't open file c!\n");
exit(0);
}
while(!feof(fp1)&&!feof(fp2))
{
if(fgetc(fp1)!=fgetc(fp2))
{
printf("赫夫曼编码错误！！！\n");
flag=0;
break;
}
}
if(flag==1)
printf("赫夫曼编码正确！！！\n");
}
void main()
{
Essay *head,*p;
char ch2[]="dasda";
char **Hc;
Huff_Tree *HT;
HT=(Huff_Tree *)malloc((2*NUM)*sizeof(Huff_Tree));
head=(Essay *)malloc(sizeof(Essay));
Hc=(char *)malloc((NUM+1)*sizeof(char *));
head->next=NULL;
head->ch='0';
head->num=0;
write(ch2);
count1(ch2,head);
printf("head里面的数据：\n");
for(p=head->next;p!=NULL;p=p->next)
printf("%c %d\n",p->ch,p->num);
HuffmanCoding(head,Hc,HT);
printf("head里面的数据：\n");
for(p=head->next;p!=NULL;p=p->next)
printf("%c %d\n",p->ch,p->num);
coding(ch2,Hc,head);
decoding(Hc,head);
equal();
}
