![]() |
#2
榴紫丫2012-03-20 12:54
|

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef struct Node{
char *word;
int count;
int len;
int weight;
struct Node *left,*right;
}Node,*BiTree;
typedef struct node{
char *word;
int weight;
int parent;
int lchild,rchild;
}HuffmanTree[9999];
int *p;
int searchBst(BiTree T,char *keyword,BiTree *p)
{
int cmpres=0;
BiTree ptr;
*p=0;ptr=T;
while(ptr)
{
cmpres=strcmp(ptr->word,keyword);
if(cmpres==0){*p=ptr;return 0;}
else{*p=ptr;ptr=cmpres>0? ptr->left: ptr->right;}
}
return -1;
}
int insertBst(BiTree *t,char *keyword)
{
BiTree s,p;
if(searchBst(*t,keyword,&p)==-1)
{
s=(Node *)malloc(sizeof(Node));
if(!s){printf("存储分配失败!\n");return -1;}
s->word=(char *)malloc(strlen(keyword));
s->len=strlen(keyword);
strcpy(s->word,keyword);
s->left=0;s->right=0;s->count=1;s->weight=s->len;
if(p==0) *t=s;
else if(strcmp(p->word,keyword)<0)
p->right=s;
else p->left=s;
}
else {p->count++; p->weight=p->count*p->len;}
return 0;
}
void FindWords(BiTree *root,char FileName[],char *c1[],int *counts1)
{
char ch,*word,buffer[40],string[2];
FILE *fin;
int i=0;
fin=fopen(FileName,"r");
if(!fin){printf("打开文件%s错误!\n",FileName);return;}
while(!feof(fin))
{
ch=fgetc(fin);
while((!feof(fin))&&(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
{buffer[i++]=ch;ch=fgetc(fin);}
if(i!=0)
{
buffer[i]='\0';
word=(char *)malloc(strlen(buffer));
strcpy(word,buffer);
c1[(*counts1)++]=word;
if(insertBst(root,word)==-1)return;
i=0;
}
if((!feof(fin))&&(ch!=' '))
{
string[0]=ch;
string[1]='\0';
word=(char *)malloc(2);
strcpy(word,string);
c1[(*counts1)++]=word;
if(insertBst(root,word)==-1)return;
}
if(i!=0)
{
buffer[i]='\0';
word=(char *)malloc(strlen(buffer));
strcpy(word,buffer);
c1[(*counts1)++]=word;
if(insertBst(root,word)==-1)return;
i=0;
}
}
fclose(fin);
}
void InOrder(BiTree root,char *c[],int w[],int *counts)
{
if(root)
{
InOrder(root->left,c,w,counts);
c[*counts]=root->word; w[*counts]=root->weight; (*counts)++;
InOrder(root->right,c,w,counts);
}
}
void select(HuffmanTree HT,int *s1,int *s2,int n)
{
for(int i=0;i<n;i++)
if(HT[i].parent==0)
*s1=i;
for(int i=0;i<n;i++)
if((HT[i].parent==0)&&(HT[*s1].weight>HT[i].weight)) *s1=i;
HT[*s1].parent=-1;
for(int j=0;j<n;j++)
if(HT[j].parent==0)
*s2=j;
for(j=0;j<n;j++)
if((HT[j].parent==0)&&(HT[*s2].weight>HT[j].weight)) *s2=j;
}
void createHTree(HuffmanTree HT,char *c[], int w[],int counts)
{
int i,s1,s2;
if(counts<=1) return;
for(i=0;i<counts;i++)
{
HT[i].word=c[i]; HT[i].weight=w[i]; HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
for(;i<2*counts-1;i++)
{
HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;
}
for(i=counts;i<2*counts-1;i++)
{
select(HT,&s1,&s2,i);
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;
}
}
void HuffmanCoding(HuffmanTree HT,char *HC[],char *c[],char *c1[],int counts,int counts1)
{
char *cd;
int i,start,cc,f;
if(counts<=1) return;
cd=(char *)malloc(counts);
cd[counts-1]='\0';
for(i=0;i<counts;i++)
{
start=counts-1;
for(cc=i,f=HT[i].parent;f!=0;cc=f,f=HT[f].parent)
if(HT[f].lchild==cc) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char*)malloc(counts-start);
strcpy(HC[i],&cd[start]);
}
free(cd);
FILE *out;
out=fopen("编码.txt","w");
if(!out){printf("打开文件%s错误!\n","编码.txt");return;}
printf("编码后的结果输出在文件:编码.txt中.\n");
for( i=0;i<counts1;i++)
{
for(int j=0;j<counts;j++)
{
if(strcmp(c1[i],c[j])==0)
fputs(HC[j],out);
}
}
fclose(out);
}
void Decoding(HuffmanTree HT,int counts)
{
int i=0;
char ch,buffer[9999];
FILE *in;
in=fopen("编码.txt","r");
if(!in){printf("打开文件%s错误!\n","编码.txt");return;}
while(!feof(in))
{
ch=fgetc(in);
buffer[i++]=ch;
}
fclose(in);
int j=i;
int p=2*counts-2;
FILE *fout;
char null=' ';
fout=fopen("译码.txt","w");
if(!fout){printf("打开文件%s错误!\n","译码.txt");return;}
printf("译码后的结果输出在文件:译码.txt中.\n");
for(i=0;buffer[i]!='\0'&&i<j;i++)
{
if((buffer[i])=='0') p=HT[p].lchild;
else p=HT[p].rchild;
if(HT[p].lchild==0&&HT[p].rchild==0)
{
fputs(HT[p].word,fout);
fputc(null,fout);
p=2*counts-2;
}
}
fclose(fout);
}
void main()
{
BiTree root=0;
HuffmanTree HT;
char *c[9999];
int w[9999];
char *c1[9999];
int counts=0;
int counts1=0;
char* HC[9999];
char FileName[40];
printf("请输入要进行霍夫曼编码的英文文章的文件名:");
gets(FileName);
FindWords(&root,FileName,c1,&counts1);
InOrder(root,c,w,&counts);
createHTree(HT,c,w,counts);
HuffmanCoding(HT,HC,c,c1,counts,counts1);
Decoding(HT,counts);
}
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef struct Node{
char *word;
int count;
int len;
int weight;
struct Node *left,*right;
}Node,*BiTree;
typedef struct node{
char *word;
int weight;
int parent;
int lchild,rchild;
}HuffmanTree[9999];
int *p;
int searchBst(BiTree T,char *keyword,BiTree *p)
{
int cmpres=0;
BiTree ptr;
*p=0;ptr=T;
while(ptr)
{
cmpres=strcmp(ptr->word,keyword);
if(cmpres==0){*p=ptr;return 0;}
else{*p=ptr;ptr=cmpres>0? ptr->left: ptr->right;}
}
return -1;
}
int insertBst(BiTree *t,char *keyword)
{
BiTree s,p;
if(searchBst(*t,keyword,&p)==-1)
{
s=(Node *)malloc(sizeof(Node));
if(!s){printf("存储分配失败!\n");return -1;}
s->word=(char *)malloc(strlen(keyword));
s->len=strlen(keyword);
strcpy(s->word,keyword);
s->left=0;s->right=0;s->count=1;s->weight=s->len;
if(p==0) *t=s;
else if(strcmp(p->word,keyword)<0)
p->right=s;
else p->left=s;
}
else {p->count++; p->weight=p->count*p->len;}
return 0;
}
void FindWords(BiTree *root,char FileName[],char *c1[],int *counts1)
{
char ch,*word,buffer[40],string[2];
FILE *fin;
int i=0;
fin=fopen(FileName,"r");
if(!fin){printf("打开文件%s错误!\n",FileName);return;}
while(!feof(fin))
{
ch=fgetc(fin);
while((!feof(fin))&&(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
{buffer[i++]=ch;ch=fgetc(fin);}
if(i!=0)
{
buffer[i]='\0';
word=(char *)malloc(strlen(buffer));
strcpy(word,buffer);
c1[(*counts1)++]=word;
if(insertBst(root,word)==-1)return;
i=0;
}
if((!feof(fin))&&(ch!=' '))
{
string[0]=ch;
string[1]='\0';
word=(char *)malloc(2);
strcpy(word,string);
c1[(*counts1)++]=word;
if(insertBst(root,word)==-1)return;
}
if(i!=0)
{
buffer[i]='\0';
word=(char *)malloc(strlen(buffer));
strcpy(word,buffer);
c1[(*counts1)++]=word;
if(insertBst(root,word)==-1)return;
i=0;
}
}
fclose(fin);
}
void InOrder(BiTree root,char *c[],int w[],int *counts)
{
if(root)
{
InOrder(root->left,c,w,counts);
c[*counts]=root->word; w[*counts]=root->weight; (*counts)++;
InOrder(root->right,c,w,counts);
}
}
void select(HuffmanTree HT,int *s1,int *s2,int n)
{
for(int i=0;i<n;i++)
if(HT[i].parent==0)
*s1=i;
for(int i=0;i<n;i++)
if((HT[i].parent==0)&&(HT[*s1].weight>HT[i].weight)) *s1=i;
HT[*s1].parent=-1;
for(int j=0;j<n;j++)
if(HT[j].parent==0)
*s2=j;
for(j=0;j<n;j++)
if((HT[j].parent==0)&&(HT[*s2].weight>HT[j].weight)) *s2=j;
}
void createHTree(HuffmanTree HT,char *c[], int w[],int counts)
{
int i,s1,s2;
if(counts<=1) return;
for(i=0;i<counts;i++)
{
HT[i].word=c[i]; HT[i].weight=w[i]; HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
for(;i<2*counts-1;i++)
{
HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;
}
for(i=counts;i<2*counts-1;i++)
{
select(HT,&s1,&s2,i);
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;
}
}
void HuffmanCoding(HuffmanTree HT,char *HC[],char *c[],char *c1[],int counts,int counts1)
{
char *cd;
int i,start,cc,f;
if(counts<=1) return;
cd=(char *)malloc(counts);
cd[counts-1]='\0';
for(i=0;i<counts;i++)
{
start=counts-1;
for(cc=i,f=HT[i].parent;f!=0;cc=f,f=HT[f].parent)
if(HT[f].lchild==cc) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char*)malloc(counts-start);
strcpy(HC[i],&cd[start]);
}
free(cd);
FILE *out;
out=fopen("编码.txt","w");
if(!out){printf("打开文件%s错误!\n","编码.txt");return;}
printf("编码后的结果输出在文件:编码.txt中.\n");
for( i=0;i<counts1;i++)
{
for(int j=0;j<counts;j++)
{
if(strcmp(c1[i],c[j])==0)
fputs(HC[j],out);
}
}
fclose(out);
}
void Decoding(HuffmanTree HT,int counts)
{
int i=0;
char ch,buffer[9999];
FILE *in;
in=fopen("编码.txt","r");
if(!in){printf("打开文件%s错误!\n","编码.txt");return;}
while(!feof(in))
{
ch=fgetc(in);
buffer[i++]=ch;
}
fclose(in);
int j=i;
int p=2*counts-2;
FILE *fout;
char null=' ';
fout=fopen("译码.txt","w");
if(!fout){printf("打开文件%s错误!\n","译码.txt");return;}
printf("译码后的结果输出在文件:译码.txt中.\n");
for(i=0;buffer[i]!='\0'&&i<j;i++)
{
if((buffer[i])=='0') p=HT[p].lchild;
else p=HT[p].rchild;
if(HT[p].lchild==0&&HT[p].rchild==0)
{
fputs(HT[p].word,fout);
fputc(null,fout);
p=2*counts-2;
}
}
fclose(fout);
}
void main()
{
BiTree root=0;
HuffmanTree HT;
char *c[9999];
int w[9999];
char *c1[9999];
int counts=0;
int counts1=0;
char* HC[9999];
char FileName[40];
printf("请输入要进行霍夫曼编码的英文文章的文件名:");
gets(FileName);
FindWords(&root,FileName,c1,&counts1);
InOrder(root,c,w,&counts);
createHTree(HT,c,w,counts);
HuffmanCoding(HT,HC,c,c1,counts,counts1);
Decoding(HT,counts);
}