链式基数排序.txt

数据结构用C语言实现的各种排序方法

#define D 3 //数的最高位数是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;//链的link域指向下一个结点
   r[n].link=0; //尾结点指针域为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;
     }//每一次分配前初值置为0
     do{
          k=(r[p].key%rg)/rd;//截取位值
          if(f[k]==0)
              f[k]=p;  //若对应的队列为空则链在对头指针f上
          else 
              r[e[k]].link=p; //若对应的队列非空则链在对尾指针e上
          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);
}