/* alg10-11.c 鏈?zhǔn)交鶖?shù)排序 */
 typedef int InfoType; /* 定義其它數(shù)據(jù)項(xiàng)的類型 */
 typedef int KeyType; /* 定義RedType類型的關(guān)鍵字為整型 */
 typedef struct
 {
   KeyType key; /* 關(guān)鍵字項(xiàng) */
   InfoType otherinfo; /* 其它數(shù)據(jù)項(xiàng) */
 }RedType; /* 記錄類型(同c10-1.h) */
 typedef char KeysType; /* 定義關(guān)鍵字類型為字符型 */
 #include"c1.h"
 #include"c10-3.h"
 void InitList(SLList *L,RedType D[],int n)
 { /* 初始化靜態(tài)鏈表L（把數(shù)組D中的數(shù)據(jù)存于L中） */
   char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];
   int i,j,max=D[0].key; /* max為關(guān)鍵字的最大值 */
   for(i=1;i<n;i++)
     if(max<D[i].key)
       max=D[i].key;
   (*L).keynum=(int)(ceil(log10(max)));
   (*L).recnum=n;
   for(i=1;i<=n;i++)
   {
     (*L).r[i].otheritems=D[i-1].otherinfo;
     itoa(D[i-1].key,c,10); /* 將10進(jìn)制整型轉(zhuǎn)化為字符型,存入c */
     for(j=strlen(c);j<(*L).keynum;j++) /* 若c的長(zhǎng)度<max的位數(shù),在c前補(bǔ)'0' */
     {
       strcpy(c1,"0");
       strcat(c1,c);
       strcpy(c,c1);
     }
     for(j=0;j<(*L).keynum;j++)
       (*L).r[i].keys[j]=c[(*L).keynum-1-j];
   }
 }

 int ord(char c)
 { /* 返回k的映射(個(gè)位整數(shù)) */
   return c-'0';
 }

 void Distribute(SLCell r[],int i,ArrType f,ArrType e) /* 算法10.15 */
 { /* 靜態(tài)鍵表L的r域中記錄已按(keys[0],...,keys[i-1])有序。本算法按 */
   /* 第i個(gè)關(guān)鍵字keys[i]建立RADIX個(gè)子表,使同一子表中記錄的keys[i]相同。 */
   /* f[0..RADIX-1]和e[0..RADIX-1]分別指向各子表中第一個(gè)和最后一個(gè)記錄 */
   int j,p;
   for(j=0;j<RADIX;++j)
     f[j]=0; /* 各子表初始化為空表 */
   for(p=r[0].next;p;p=r[p].next)
   {
     j=ord(r[p].keys[i]); /* ord將記錄中第i個(gè)關(guān)鍵字映射到[0..RADIX-1] */
     if(!f[j])
       f[j]=p;
     else
       r[e[j]].next=p;
     e[j]=p; /* 將p所指的結(jié)點(diǎn)插入第j個(gè)子表中 */
   }
 }

 int succ(int i)
 { /* 求后繼函數(shù) */
   return ++i;
 }

 void Collect(SLCell r[],ArrType f,ArrType e)
 { /* 本算法按keys[i]自小至大地將f[0..RADIX-1]所指各子表依次鏈接成 */
   /* 一個(gè)鏈表，e[0..RADIX-1]為各子表的尾指針。算法10.16 */
   int j,t;
   for(j=0;!f[j];j=succ(j)); /* 找第一個(gè)非空子表，succ為求后繼函數(shù) */
   r[0].next=f[j];
   t=e[j]; /* r[0].next指向第一個(gè)非空子表中第一個(gè)結(jié)點(diǎn) */
   while(j<RADIX-1)
   {
     for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j)); /* 找下一個(gè)非空子表 */
     if(f[j])
     { /* 鏈接兩個(gè)非空子表 */
       r[t].next=f[j];
       t=e[j];
     }
   }
   r[t].next=0; /* t指向最后一個(gè)非空子表中的最后一個(gè)結(jié)點(diǎn) */
 }

 void printl(SLList L)
 { /* 按鏈表輸出靜態(tài)鏈表 */
   int i=L.r[0].next,j;
   while(i)
   {
     for(j=L.keynum-1;j>=0;j--)
       printf("%c",L.r[i].keys[j]);
     printf(" ");
     i=L.r[i].next;
   }
 }

 void RadixSort(SLList *L)
 { /* L是采用靜態(tài)鏈表表示的順序表。對(duì)L作基數(shù)排序，使得L成為按關(guān)鍵字 */
   /* 自小到大的有序靜態(tài)鏈表，L.r[0]為頭結(jié)點(diǎn)。算法10.17 */
   int i;
   ArrType f,e;
   for(i=0;i<(*L).recnum;++i)
     (*L).r[i].next=i+1;
   (*L).r[(*L).recnum].next=0; /* 將L改造為靜態(tài)鏈表 */
   for(i=0;i<(*L).keynum;++i)
   { /* 按最低位優(yōu)先依次對(duì)各關(guān)鍵字進(jìn)行分配和收集 */
     Distribute((*L).r,i,f,e); /* 第i趟分配 */
     Collect((*L).r,f,e); /* 第i趟收集 */
     printf("第%d趟收集后:\n",i+1);
     printl(*L);
     printf("\n");
   }
 }

 void print(SLList L)
 { /* 按數(shù)組序號(hào)輸出靜態(tài)鏈表 */
   int i,j;
   printf("keynum=%d recnum=%d\n",L.keynum,L.recnum);
   for(i=1;i<=L.recnum;i++)
   {
     printf("keys=");
     for(j=L.keynum-1;j>=0;j--)
       printf("%c",L.r[i].keys[j]);
     printf(" otheritems=%d next=%d\n",L.r[i].otheritems,L.r[i].next);
   }
 }

 void Sort(SLList L,int adr[]) /* 改此句(類型) */
 { /* 求得adr[1..L.length]，adr[i]為靜態(tài)鏈表L的第i個(gè)最小記錄的序號(hào) */
   int i=1,p=L.r[0].next;
   while(p)
   {
     adr[i++]=p;
     p=L.r[p].next;
   }
 }

 void Rearrange(SLList *L,int adr[]) /* 改此句(類型) */
 { /* adr給出靜態(tài)鏈表L的有序次序，即L.r[adr[i]]是第i小的記錄。 */
   /* 本算法按adr重排L.r，使其有序。算法10.18(L的類型有變) */
   int i,j,k;
   for(i=1;i<(*L).recnum;++i) /* 改此句(類型) */
     if(adr[i]!=i)
     {
       j=i;
       (*L).r[0]=(*L).r[i]; /* 暫存記錄(*L).r[i] */
       while(adr[j]!=i)
       { /* 調(diào)整(*L).r[adr[j]]的記錄到位直到adr[j]=i為止 */
         k=adr[j];
         (*L).r[j]=(*L).r[k];
         adr[j]=j;
         j=k; /* 記錄按序到位 */
       }
       (*L).r[j]=(*L).r[0];
       adr[j]=j;
     }
 }

 #define N 10
 void main()
 {
   RedType d[N]={{278,1},{109,2},{63,3},{930,4},{589,5},{184,6},{505,7},{269,8},{8,9},{83,10}};
   SLList l;
   int *adr;
   InitList(&l,d,N);
   printf("排序前(next域還沒(méi)賦值):\n");
   print(l);
   RadixSort(&l);
   printf("排序后(靜態(tài)鏈表):\n");
   print(l);
   adr=(int*)malloc((l.recnum)*sizeof(int));
   Sort(l,adr);
   Rearrange(&l,adr);
   printf("排序后(重排記錄):\n");
   print(l);
 }