#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXNUM 128
#define RADIX 10

typedef struct NoElem
{
	int data;
	struct NoElem *next;
}NoElem;
typedef struct 
{
	NoElem *front;
	NoElem *rear;
}NoList;
NoList *(nolist[RADIX]);

int InitList(NoList *list)
{
	list->front=(NoElem *)malloc(sizeof(NoElem));
	if(!list->front)
	{
		printf("malloc failed\n");
		return 0;
	}
	list->rear=list->front;
    list->front->next=NULL;
	return 1;
}
int InsertNoList(NoList *list,int no)
{
	NoElem *p;
	p=(NoElem *)malloc(sizeof(NoElem));
	if(!p)
	{
		printf("malloc failed\n");
		return 0;
	}
	p->data=no;
	p->next=NULL;
	list->rear->next=p;
	list->rear=p;
	return 1;
}
int Distribute(NoList *list[],int a[],int n)
{
	int i,k,weigt;
	weigt=(int)pow(RADIX,n);
	for(i=0;a[i]!=0;i++)
	{   
		if(!a[i]) return 1;
		k=((int)a[i]/weigt)%RADIX;
//		printf("the times is:%d\n",k);
		if(!InsertNoList(nolist[k],a[i]))
		{
			printf("Insert failed\n");
			return 0;
		}
	}
	return 1;
}
int ListEmpty(NoList *list)
{
	if(list->front==list->rear)
		return 1;
	return 0;
}
void ClearList(NoList *list)
{
	NoElem *p;
	p=list->front->next;
	while(p->next)
	{
		list->front->next=p->next;
		free(p);
		p=list->front->next;
	}
	list->rear=list->front;
	list->front->next=NULL;
	free(p);
	return ;
}

void Collect(NoList *nolist[],int a[])
{
	int i,k=0;
	NoElem *p;
//	printf("go to collect\n");
	for(i=0;i<RADIX;i++)
	{
		if(ListEmpty(nolist[i]))
			continue;
		for(p=nolist[i]->front->next;p!=NULL;p=p->next)
		 a[k++]=p->data;           //printf("%4d",a[k-1]);}
		ClearList(nolist[i]);
	}
	a[k]=0;
//	for(k=0;a[k]!=0;k++)
//		printf("%4d ",a[k]);
	return ;
}
void Iniarray(int a[],int *plen)
{   
	int i,len;
	printf("Enter the numbers end with 0 :\n");
	for(i=0;i<MAXNUM;i++)
	{
		scanf("%d",&a[i]);
        len=(int)log10(a[i])+1;
		if(*plen<len)
			*plen=len;
		if(!a[i])
		   return;
	}
}
void main(void)
{
	
	int i,times,array[MAXNUM],maxlen=0;
	for(times=0;times<RADIX;times++)
	{
		nolist[times]=(NoList *)malloc(sizeof(NoList));
		if(!nolist) 
		{
			printf("mallic space for list failed\n");
			return;
		}
		if(!InitList(nolist[times])) return;
	}
	Iniarray(array,&maxlen);
	printf("select %d times.\n",maxlen);
    for(times=0;times<maxlen;times++)
	{
		if(!Distribute(nolist,array,times)) return;
		Collect(nolist,array);
	}
	printf("the numbers in order:\n");
	for(i=0;array[i]!=0;i++)
	{
		printf("%6d",array[i]);
		if(!((i+1)%6))
			printf("\n");
	}
	printf("\n");
	return;
}