数据结构哈夫曼编码实现.doc

#include<>
#include<>
typedef struct haha{
int weight;
int parent,lchild,rchild,flag;
char data;
}haha,*friday;
typedef struct hehe{
char m;
int n;
struct hehe *next;
}hehe,*zhouwu;
typedef char * *gege;
void begin(zhouwu &l)
{
zhouwu p,q,r;
int flag;
l=(zhouwu)malloc(sizeof(hehe));
l->next=NULL;
l->n=0;
r=p=q=l;
printf("请输入要编码的字符串: ");
for(int i=0; ; )
{
p=(zhouwu)malloc(sizeof(hehe));
p->n=0;
p->m=getchar();
if(p->m=='\n')
break;
flag=0;
while(r->next!=NULL)
{
if(r->next->m==p->m)
{
r->next->n++;
flag=1;
free(p);
break;
}
else
r=r->next;
}
if(flag==0)
{
p->next=q->next;
p->n++;
q->next=p;
q=p;
l->n++;
}
r=l;
}
}
void select(friday &ht,int k,int &x,int &y)
{
int first,j[2],m=0,i;
for(int h=1;h<=2;h++)
{
for(first=32767,i=1;i<=k;i++)
{
if(ht[i].flag==0)
{
if(first>ht[i].weight)
{
first=ht[i].weight;
j[m]=i;
}
}
}
x=j[0];
y=j[1];
m++;
ht[x].flag=1;
if(m==2)
ht[y].flag=1;
}
}
void huffmancoding(friday &ht,zhouwu &l)
{
int m;
m=2*l->n-1;
ht=(friday)malloc((m+1)*sizeof(haha));
friday p;
zhouwu q=l;
int i;
for(p=ht+1,i=1;i<=l->n;++i,++p)
{
p->weight=q->next->n;
p->flag=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
p->data=q->next->m;
q=q->next;
}
for( ;i<=m;++i,++p)
{
p->flag=0;
p->weight=0;
p->parent