#include
#include
#define maxbit 10
#define maxvalue 1000
#define maxsize 26
typedef struct HNode
{
int weight;
int parent,lchild,rchild;
}HNode,*HTree;
typedef char **HCode;
int Count(char *s,int cnt[],char str[])
{
char *p;
int i,j,k;
int temp[26];
for(i=0;i<26;i++)
temp[i]=0;
for(p=s;*p!='\0';p++)
if(*p>='A'&&*p<='z')
{
k=(*p)-65;
temp[k]++;
}
for(i=0,j=0;i<26;i++)
if(temp[i]!=0)
{
str[j]=i+65;
cnt[j]=temp[i];
j++;
}
str[j]='\0';
return j;
}
void HuffmanCoding(HTree *HT,HCode *HC,int *w,int n)
{
int m;
int m1,m2,x1,x2;
int i,j,start;
char *cd;
int c,f;
HNode *p;
if(n<=1)return;
m=2*n-1;
* HT=(HNode *)malloc(m *sizeof(HNode));
for(p=*HT,i=0;i
p->weight=*w;
p->lchild=-1;
p->rchild=-1;
p->parent=-1;
}
for(;i
p->weight=0;
p->lchild=-1;
p->rchild=-1;
p->parent=-1;
}
for(i=n;i
m1=m2=maxvalue;
x1=x2=0;
for(j=0;j {
if((*HT)[j].parent==-1&&(*HT)[j].weight
m2=m1;x2=x1;
m1=(*HT)[j].weight;
x1=j;
}
else
if((*HT)[j].parent==-1&&(*HT)[j].weight
m2=(*HT)[j].weight;
x2=j;
}
}
(*HT)[x1].parent=i;(*HT)[x2].parent=i;
(*HT)[i].lchild=x1;(*HT)[i].rchild=x2;
(*HT)[i].weight=m1+m2;
}
*HC=(HCode)malloc(n * sizeof(HCode));
cd=(char *)malloc(n *sizeof(char));
cd[n-1]='\0';
for(i=0;i
start=n-1;
for(c=i,f=(*HT)[i].parent;f!=-1;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]);
}
free(cd);
}
void Coding(HCode *HC,char *s,char str[])
{
int i,j;
char *cp;
FILE *fp;
fp=fopen("\\codefile.txt","w");
while(*s)
{
for(i=0;i
{
for(j=0,cp=(*HC)[i];j
break;
}
s++;
}
fclose(fp);
}
void Print(HCode *HC,char str[],int cn[],int n)
{
int i;
for(i=0;i
printf("%c出现%d次,编码是:",str[i],cn[i]);
puts((*HC)[i]);
putchar('\n');
}
return;
}
char *Decode(HCode *HC,char str[],int num)
{
FILE *fp;
char s[254];
char *p;
static char cd[maxbit+1];
int i,j,k=0,cjs;
fp=fopen("\\codefile.txt","r");
while(!feof(fp))
{
cjs=0;
for(i=0;i
cd[i]=' ';cd[i+1]='\0';
cd[i]=fgetc(fp);
for(j=0;j
{
s[k]=str[j];
k++;
cjs=1;
break;
}
}
}
s[k]='\0';
p=s;
return p;
}
/*主函数*/
void main()
{
char st[254],*s,str[26];
int cn[26];
int num;
HNode *HT;
HCode HC;
printf("输入需要编码的字符串(假设均为大写英文字母):\n");
gets(st);
num=Count(st,cn,str);
HuffmanCoding(&HT,&HC,cn,num);
Print(&HC,str,cn,num);
Coding(&HC,st,str);
printf("\n");
s=Decode(&HC,str,num);
printf("%s\n",s);
getchar();
}
这是程序源代码。。应该没问题。