表排序算法的C语言实现
基本思想：假定有一待排序序列A1,A1中的元素最大为三位数，我们可以先按照个位对A1排序得到序列A2，然后按照十位对A2排序得到序列A3，最后再按照百位数对A3进行排序，则可以得到一个有序序列B1.
#include
#include
#include
#include
typedef struct LNode
{
int e;
struct LNode *next;
} LNode, *Link;//定义链表结构体
typedef int (*pfn)(int e);//定义指针函数类型
Link CreateList_L2(Link L, int n);//链表生成函数
void ListDisp_L2(Link L);//链表遍历函数
int GeWei(int e);//取个位
int BaiWei(int e);//取百位
int ShiWei(int e);//取十位
Link Insert(Link L,Link p);//链表合成函数
void main()
{
int i=0,j=0;
int k;
time_t t;
Link p=NULL,L=NULL,r=NULL;
Link apstFen[10] ={NULL};
pfn Wei[3] = {GeWei, ShiWei,BaiWei};
srand((long)time(&t));//初始化随机数发生器
p=CreateList_L2(p,10);//生成链表
printf("排序前的链表\n");
ListDisp_L2(p);
L=p;
//依次按个位，十位，百位将链表排序
for( i = 0; i < 3; i++ )
{
//将链表分拆，并放入apstFen[10]中
while(L)
{
L = p;
p=L->next;
L->next = NULL;
j = (*Wei)(L->e);
//将p所指结点插入到相应的分拆数组中
r = apstFen[j];
if ( r == NULL )
{ apstFen[j] = L;
}
else
{
while((r->next) != NULL)
{
r = r->next ;
}
r->next=L;
L->next=NULL;
}
L= p;
}
//组合成新的链表头结点为L
for( k = 0; k < 10; k++ )
{
if( apstFen[k] != NULL )
{
L=Insert(L, apstFen[k]);
apstFen[k] = NULL;
}
}
p=L;
}
printf("排序后的链表 \n");
ListDisp_L2(p);
}
Link CreateList_L2(Link L, int n)/*链表生成函数*/
{
int i;
Link p;
L = (Link)calloc(1,sizeof(LNode));
L->e=rand()%1000;
L->next = NULL;
for(i = n-1; i > 0; --i)
{
p = (Link)calloc(1,sizeof(Link));
p->e=rand()%1000;
p->next = L->next;
L->next = p;
}
return L;
}
void ListDisp_L2(Link L)/*链表的遍历*/
{ Link p=NULL;
int i=0;
p=L;
while(p)
{
printf("%d\n",p->e);
p = p->next;
}
}
int GeWei(int e)//取个位
{
return (e%10);
}
int BaiWei(int e)//取百位
{
return (e/100);
}
int ShiWei(int e)//取十位
{
return ((e%100)/10);
}
Link Insert(Link L,Link p)//组合成新的链表
{
Link head=L;
if(L==NULL)
return p;
while((L->next) != NULL)
L = L->next ;
L->next = p;
return head;
}