#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_NUM_OF_KEY 8
#define RADIX 10
#define MAX_SPACE 1000

typedef int KeysType;
typedef int InfoType;
typedef struct {
	KeysType keys[MAX_NUM_OF_KEY];
	InfoType otheritems;
	int next;
}SLCell;
typedef struct {
	SLCell r[MAX_SPACE];
	int keynum;
	int recnum;
}SLList;
typedef int ArrType[RADIX];

void ListInsert(SLList *L)
{
	int i, n;
	int max;

	printf("Input number of key: ");
	scanf("%d", &(L->keynum));
	if(L->keynum > MAX_NUM_OF_KEY)
		exit(-1);

	L->recnum = 0;
	printf("input key: ");
	scanf("%d", &n);
	max = pow(RADIX, L->keynum);
	while(n>0 && n<max)
	{
		L->recnum++;
		for(i=0; i<L->keynum; i++)
			L->r[L->recnum].keys[i] = (int)(n/pow(RADIX, L->keynum-i-1))%RADIX;
		printf("input key: ");
		scanf("%d", &n);
	}
}

void ListTraverse(SLList L)
{
	int i, k;
	k = L.r[0].next;
	while(k)
	{
		for(i=0; i<L.keynum; i++)
			printf("%d", L.r[k].keys[i]);
		printf(" ");
		k = L.r[k].next;
	}
	printf("\n");
}

void Distribute(SLCell *r, int i, ArrType f, ArrType e)
{
	int j, p;

	for(j=0; j<RADIX; j++)
		f[j] = 0;
	for(p=r[0].next; p; p=r[p].next)
	{
		j = r[p].keys[i];
		if(!f[j])
			f[j] = p;
		else
			r[e[j]].next = p;
		e[j] = p;
	}
}

void Collect(SLCell *r, int i, ArrType f, ArrType e)
{
	int j, t;

	for(j=0; !f[j]; j+=1);
	r[0].next = f[j];
	t = e[j];
	while(j < RADIX)
	{
		for(j+=1; j<RADIX-1 && !f[j]; j+=1);
		if(j<RADIX && f[j])
		{
			r[t].next = f[j];
			t = e[j];
		}
	}
	r[t].next = 0;
}

void RadixSort(SLList *L)
{
	int i;
	ArrType f, e;

	for(i=0; i<L->recnum; i++)
		L->r[i].next = i+1;
	L->r[L->recnum].next = 0;
	for(i=L->keynum-1; i>=0; i--)
	{
		Distribute(L->r, i, f, e);
		Collect(L->r, i, f, e);
	}
}

void main()
{
	SLList L;

	ListInsert(&L);
	RadixSort(&L);
	ListTraverse(L);
}