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

struct Node
{
	int data;
	Node *prior;
	Node *next;
};


template <class type>
type * del_entry( type *L)
{
	type *p;
	p=L->next;
	if (p!=L)
	{
		p->prior->next=p->next;
		p->next->prior=p->prior;
	}
	else p=NULL;
	return p;
}

template <class type>
void add_entry(type *L, type *p)
{
	p->prior=L->prior;
	p->next=L;
	L->prior->next=p;
	L->prior=p;
}

template <class type>
int get_digital(type *p, int i)
{
	int key;
	key=p->data;
	if (i!=0)
		key=key/pow(10,i);
	return key%10;
}

template <class type>
void append(type *L, type *L1)
{
	if (L1->next!=L1)
	{
		L->prior->next=L1->next;
		L1->next->prior=L->prior;
		L1->prior->next=L;
		L->prior=L1->prior;
	}
}

template <class type>
void radix_sort(type *L, int k)
{
	type *Lhead[10], *p;
	int i,j;
	for (i=0;i<10;i++)
		Lhead[i]=new type;
	for (i=0;i<k;i++)
	{
		for (j=0;j<10;j++)
			Lhead[j]->prior=Lhead[j]->next=Lhead[j];
		while (L->next!=L)
		{
			p=del_entry(L);
			j=get_digital(p,i);
			add_entry(Lhead[j],p);
		}
		for (j=0;j<10;j++)
			append(L,Lhead[j]);
	}
	for (i=0;i<10;i++)
		delete (Lhead[i]); 
}

Node  * Create_L (int n)
{
	Node *h,*p,*s; //h:頭結(jié)點，p:下一結(jié)點，s:當前結(jié)點 
	int i; 
	if((h=new Node)==NULL) 
	{ 
		cout<<"分配內(nèi)存失敗..."<<endl; 
	} 
    h->data=0;
	h->prior=NULL; 
	h->next=NULL; 
	p=h; 
	for (i=0;i<n;i++) 
	{ 
		if((s=new Node)==NULL) 
		{ 
			cout<<"分配內(nèi)存失敗..."<<endl; 
		} 
		p->next=s; 
	//	cout<<"請輸入第"<<i+1<<"個數(shù)據(jù)"; 
		cin>>s->data; 
		s->prior=p; 
		s->next=NULL; 
		p=s; 
	} 
	s->next=h; 
	h->prior=s; 
	return h; 
} 

template <class type>
void Print_L(type *L)
{
	type *p;
	p=L->next;
	while(p!=L)
	{
		cout<<p->data<<" ";
		p=p->next;
		}
	cout<<endl;
}


	

int main()
{
	Node *L;
	int n=10;
	L=Create_L(10);
	Print_L(L);
	radix_sort(L,4);
	Print_L(L);
	return 0;
}