hfm 4.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[10];
int n,m,i,j,l,r,start,c,f;
char **hc,*cd;
printf("Input the number:");
scanf("%d",&n);
m=2*n-1;
/* ht=(hufftree)malloc(m*sizeof(huffnode));  */

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);
}

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

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';
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;
}
hc[i]=(char*)malloc((n-start)*sizeof(char));
for(j=0;j<n-start;j++)
hc[i][j]=cd[start+j];
}

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

}

void main()
{
huffmantree();
}