#include<stdio.h> 
#include<stdlib.h> 
#define KEYN 3 
struct ele{ 
int key; 
struct ele *link; 
}; 
void basesort(struct ele **h) 
{ 
int i,j,factor; 
struct ele *head[10],*tail[10],*p,*u; 
/*依次對鍵值的個位到高位逐位循環*/ 
for(i=0,factor=1,p=*h;i<KEYN;factor*=10,i++) 
{ 
/*按鍵值的當前值將鏈表分拆成十個隊列鏈表*/ 
for(j=0;j<10;j++) /*預置十個空鏈表*/ 
head[j]=NULL; 
while(p) 
{ /*將*p接到某隊列鏈表*/ 
u=p->link; /*保護下一個表元的指針*/ 
j=(p->key/factor)%10; /*求表元鍵值的當前位*/ 
if(head[j]==NULL) /*按當前位值將*p接在對應隊列的末尾*/ 
head[j]=p; 
else 
tail[j]->link=p; 
tail[j]=p; 
p->link=NULL; 
p=u; /*準備訪問下一表元*/ 
} 
/*將十個隊列鏈表鏈接成一個鏈表*/ 
p=NULL; 
for(j=0;j<10;j++) 
{ 
if(head[j]==NULL)continue; /*跳過空鏈表*/ 
if(p==NULL)p=head[j]; 
else u->link=head[j]; /*各鏈表首尾順序鏈接*/ 
u=tail[j]; 
} 
} 
*h=p; 
} 
int a[]={35,298,832,932,38,635,22,15,48}; 
#define N sizeof a/sizeof a[0] 
void main() 
{ 
struct ele *h,*u; 
int i; 
h=NULL; /*先形成一個空鏈表*/ 
for(i=0;i<N;i++) 
{ /*任意形成一個鏈表*/ 
u=(struct ele *)malloc(sizeof(struct ele)); 
u->key=a[i]; 
u->link=h; 
h=u; 
} 
basesort(&h); /*排序*/ 
for(u=h;u;u=u->link) /*順序輸出鏈表各表元的鏈值*/ 
printf("%4d",u->key); 
printf("\n"); 
}