cyuyan.txt

程序运行结果为： 15 22 35 38 48 298 635 832 932

#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"); 
}