hfm 3.cpp

一些数据结构源代码

#include <stdio.h>
#include <malloc.h>
typedef struct{
char data;
int weight,parent,left,right;
}huffnode,* hufftree;

int compare(hufftree ht,int n)
{int i,j,k;
k=32767;
for(i=0;i<n;i++)
if(ht[i].parent==0&&ht[i].weight<k)
{k=ht[i].weight;j=i;}
return(j);
}

void huffmantree()
{huffnode ht[50];
int n,m,i,j,l,r,start,c,f,wpl,k,p,q;
char **hc,*cd,a[100],c1,b[50];
wpl=0;
/*printf("Input the number:");
scanf("%d",&n);

for(i=0;i<n;i++)
{ getchar();
printf("The number %d \ndata:",i+1);
scanf("%c",&ht[i].data);
printf("weight:");
scanf("%d",&ht[i].weight);
} */


printf("Input the string:\n");
i=0;
c1=getchar();
while(c1!='\n')
{a[i++]=c1;
 c1=getchar();
 }
 a[i]='\0';
 k=i;

ht[0].data=a[0];
ht[0].weight=1;
n=1;

for(i=1;i<k;i++)
 { for(j=0;j<n;j++)
   if(a[i]==ht[j].data) {ht[j].weight++;break;}
    if(j==n) {ht[n].data=a[i];ht[n].weight=1;n++;}
  }


m=2*n-1;

for(i=0;i<m;i++)
ht[i].parent=ht[i].left=ht[i].right=0;

printf("data:  ");
for(i=0;i<n;i++)
printf("%c ",ht[i].data);
printf("\n");

printf("weight:");
for(i=0;i<n;i++)
printf("%d ",ht[i].weight);
printf("\n");

for(i=n;i<m;i++)
{l=compare(ht,i);ht[l].parent=i;
r=compare(ht,i);ht[r].parent=i;
ht[i].weight=ht[l].weight+ht[r].weight;
ht[i].left=l;
ht[i].right=r;
}

hc=(char**)malloc(n*sizeof(char*));
cd=(char*)malloc(n*sizeof(char));
cd[n-1]='\0';
printf("wpl=");

for(i=0;i<n;i++)
{ start=n-1;
c=i;
f=ht[i].parent;
while(f!=0)
{if(ht[f].left==c) cd[--start]='0';
else cd[--start]='1';
c=f;f=ht[f].parent;
}

wpl+=ht[i].weight*(n-start-1);

if(i<n-1) printf("%d*%d+",ht[i].weight,n-start-1);
else printf("%d*%d",ht[i].weight,n-start-1);

hc[i]=(char*)malloc((n-start)*sizeof(char));
for(j=0;j<n-start;j++)
hc[i][j]=cd[start+j];
}

printf("=%d\n",wpl); 
for(i=0;i<n;i++)
{printf("%c:",ht[i].data);
printf("%s",hc[i]);
printf("\n");
}

printf("%s\n",a);
for(i=0;i<k;i++)
 for(j=0;j<n;j++)
   if(a[i]==ht[j].data) {printf("%s",hc[j]);break;}
printf("\n");

printf("Input the code:\n");
 scanf("%s",b);
printf("translate:\n");
    p=0;
while(b[p]!='\0')
 {for(i=0;i<n;i++)
 {q=p;
  for(j=0;b[p]!='\0'&&hc[i][j]!='\0';)
 {if(b[p]==hc[i][j]) {p++;j++;}
    else break;
  }
  if(hc[i][j]=='\0') {putchar(ht[i].data);break;}
       else p=q;
  }
}

  printf("\n\n");
}

void main()
{
huffmantree();
}