11-8.c

这些是数据结构结构的经典实现算法

#include "stdio.h"
#define	MAX_NUM_OF_KEY		8	/*关键字的最大值*/
#define	RADIX				10	/*关键字基数，此时是十进制整数的基数*/
#define	MAX_SPACE			10000
typedef int KeysType;
typedef char InfoType;
typedef int * Arrtype;
typedef	struct{
	KeysType	keys[MAX_NUM_OF_KEY]; /*关键字*/
	InfoType		otheritems;				/*其他数据项*/
	int 			next;
}RSCell;
typedef	struct{
	RSCell	r[MAX_SPACE];		/*静态链表的可利用空间，r[0]为头结点*/
	int		keynum;				/*记录的当前关键字个数*/
	int		recnum;				/*静态链表的当前长度*/
}RSList;

void distribute(RSCell r,int I,Arrtype	f,Arrtype e)
{/*数组f[0..RADIX-1]和e[0..RADIX-1]分别指向各子表中的第一个和最后一个记录。*/
	int j;
	for(j=0;j<RADIX;++)
		f[j]=0;
	for(p=r[0].next;p;p=r[p].next)
	{
		j=ord[r[p].keys[i]];/*ord将记录中第i个关键字映射到[0..RADIX-1]*/
		if(!f[j])
			f[j]=p;
		else	
			r[e[j]].next=p;
		e[i]=p;
	}
}
void	collect(RSCell  r,int I,ArrType f,ArrType e)
{
	int j;
	for(j=0;!f[j];j=succ(j))
		;     /*找第一个非空子表，succ为求后继函数*/
	r[0].next=f[j];
	t=e[j];
	while(j<RADIX)
	{
		for(j=succ(j);j<RADIX_!&&!f[j];j=succ(j))
			;	/*找下一个非空子表*/
		if(f[j])
		{/*链接两个非空子表*/
			r[t].next=f[j];
			t=e[j];
		}
	}
	r[t].next=0;
}
void RADIX_Sort(RCList L)
{
	int i;
   	for (i=1;i<L.recnum;i++)
			L.r[i].next=i+1;
	L.r[L.recnum].next=0;
	for(i=0;i<L.keynum;i++)
	{
		distribute(L.r,i,f,e);
		collect(L.r,i,f,e);
	}
}

void main()
{
	RCList L;
	RADIX_Sort(L);
}