ch8_10.c

一个很好的数据结构（C语言版）讲义。附带全部所需算法源码。

#include <stdio.h>
#define D 3
typedef struct node
{  int key;
/*   float info;*/
   int link;
}JD;

int radixsort(JD r[],int n)
{  int i,j,k,t,p,rd,rg,f[10],e[10];
   for(i=1;i<n;i++)  r[i].link=i+1;
   r[n].link=0;
   p=1; rd=1; rg=10;
   for(i=1;i<=D;i++)
  {  for(j=0;j<10;j++)
     {  f[j]=0;
        e[j]=0;
     }
     do{
          k=(r[p].key%rg)/rd;
          if(f[k]==0)
              f[k]=p;
          else 
              r[e[k]].link=p;
          e[k]=p;
          p=r[p].link;
       }while(p>0);
     j=0;
     while(f[j]==0) j++;
     p=f[j];  t=e[j];
     for(k=j+1;k<10;k++)
        if(f[k]>0)
        {  r[t].link=f[k];
           t=e[k];
        }
     r[t].link=0;
     rg*=10;
     rd*=10;
  }
   return(p);
}

void main()
{
    static JD r[]={{0,0},{278,0},{109,0},{63,0},{930,0},{589,0},
			 {184,0},{505,0},{269,0},{8,0},{83,0}};
    int i,n=10;
    i=radixsort(r,n);
    while(i!=0)
    {  printf("%d  ",r[i].key);
       i=r[i].link;
    }
    printf("\n");
}