# include <iostream.h>
# include <stdio.h>
# include <conio.h>
# define MAX_NUM_OF_KEY 8
# define RD 10
# define MAX_SPACE 10000
typedef int KeyType;
typedef int InfoType;
typedef int ArrType[RD];

typedef struct SLCell
{  KeyType keys[MAX_NUM_OF_KEY];
   InfoType otheritems;
   int next;
}SLCell;

typedef struct SLList 
{  SLCell r[MAX_SPACE];
   int keynum;
   int recnum;
}SLList;

int Ord(int KeyBit)                         //Ord() function
{
    int j;
    for(j=0;j<=RD-1&&j!=KeyBit;j++);
    if(j!=KeyBit) return(0);             
       else return(j);
}

void Output(SLList L,int i)             //Output() function
{
     int temp,k;
     printf("\n第 %d 趟收集后队列为:  ",i+1);
     temp=L.r[0].next;
     printf("%d -> ",L.r[temp].otheritems);
     for(k=0;k<L.recnum-2;k++)
     { temp=L.r[temp].next;
       printf("%d -> ",L.r[temp].otheritems);
     }
     printf("%d",L.r[L.r[temp].next].otheritems);
     printf("\n");
}

void Distribute(SLList &L,int i,ArrType &f,ArrType &e)    //Distribute() function
{  int j,p;
   for(j=0;j<RD;j++)              //初始化各子表
      f[j]=0;
   for(p=L.r[0].next;p;p=L.r[p].next)     //运行到L.r[p].next=0为止
   {  j=Ord(L.r[p].keys[i]);              //将记录中第i个关键字映射到[0..RADIX-1]
      if(!f[j])                           //f[j]中未指向任何元素则f[j]头指针指向它
         f[j]=p;
      else
         L.r[e[j]].next=p;                //f[j]已经指向元素时则将e[j]尾指针指向它
      e[j]=p;
   } 
}

void Collect(SLList &L,int i,ArrType f,ArrType e)         //Collect() function
{
    int j,t; 
    for(j=0;!f[j];j++);                              
    L.r[0].next=f[j];              //r[0].next指向第一个非空子表中第一个结点
    t=e[j];
    while(j<RD-1)                                          
    {
        for(j++;j<RD-1&&!f[j];j++);             
        if(f[j])
        {
            L.r[t].next=f[j];
            t=e[j];
        }
    }
/*    int j,t; 
      j=0;                       
      while(j<RD-1)                                          
   {  
      for(j;j<RD-1&&!f[j];j++);             
      if(f[j])
      { 
         L.r[t].next=f[j];
         t=e[j];
         j++;
      }
   }*/
    L.r[t].next=0;                  //t指向最后一个非空子表（最后一个队列）中的最后一个结点
    Output(L,i);                    //输出                     
}

void RadixSort(SLList &L)
{
    int i;
    ArrType f,e;
    for(i=0;i<L.recnum;i++)
    L.r[i].next=i+1;       
    L.r[L.recnum].next=0;  
    for(i=0;i<L.keynum;i++)
    {
        Distribute(L,i,f,e);
        Collect(L,i,f,e);
    }
}

void InitExample(SLList &L)
{
    L.keynum=3;                  //数字的位数
    L.recnum=7;                  //例子中共有7个数字     
    L.r[1].otheritems=930;
    L.r[2].otheritems=063;
    L.r[3].otheritems=023;
    //L.r[3].otheritems=083;
    L.r[4].otheritems=184;
    L.r[5].otheritems=505;
    L.r[6].otheritems=278;
    L.r[7].otheritems=001;
    //L.r[7].otheritems=008;
    printf("初始  无 序  队列为:  930 -> 63 -> 23 -> 184 -> 505 -> 278 -> 1\n");

    L.r[1].keys[0]=0;
    L.r[1].keys[1]=3;
    L.r[1].keys[2]=9;

    L.r[2].keys[0]=3;
    L.r[2].keys[1]=6;
    L.r[2].keys[2]=0;

    L.r[3].keys[0]=3;
    L.r[3].keys[1]=2;
    L.r[3].keys[2]=0;

    L.r[4].keys[0]=4;
    L.r[4].keys[1]=8;
    L.r[4].keys[2]=1;

    L.r[5].keys[0]=5;
    L.r[5].keys[1]=0;
    L.r[5].keys[2]=5;

    L.r[6].keys[0]=8;
    L.r[6].keys[1]=7;
    L.r[6].keys[2]=2;

    L.r[7].keys[0]=1;
    L.r[7].keys[1]=0;
    L.r[7].keys[2]=0;
}

void main()                         
{
    SLList L;
    printf("RadixSort.cpp\n==========================\n\n");
    InitExample(L);              
    RadixSort(L);                
    cout<<endl;
    getch();
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－