#define MAX_KEY_NUM 8 /*关键码项数最大值*/ |
#define RADIX 10 /*关键码基数,此时为十进制整数的基数*/ |
#define MAX_SPACE 1000 /*分配的最大可利用存储空间*/ |
typedef struct |
{ |
KeyType keys[MAX_KEY_NUM]; /*关键码字段*/ |
InfoType otheritems; /*其它字段*/ |
int next; /*指针字段*/ |
} NodeType; /*表结点类型*/ |
typedef struct |
{ |
NodeType r[MAX_SPACE]; /*静态链表,r[0]为头结点*/ |
int keynum; /*关键码个数*/ |
int length; /*当前表中记录数*/ |
} L_TBL; /*链表类型*/ |
typedef int ArrayPtr[radix]; /*数组指针,分别指向各队列*/ |
void Distribute ( NodeType *s, int i,ArrayPtr *f,ArrayPtr *e ) |
{ /*静态链表ltbl 的r 域中记录已按(kye[0],keys[1],…,keys[i-1])有序)*/ |
/*本算法按第i 个关键码keys[i]建立RADIX 个子表,使同一子表中的记录的keys[i]相同*/ |
/*f[0…RADIX-1]和e[0…RADIX-1]分别指向各子表的第一个和最后一个记录*/ |
for ( j=0; j<RADIX; j++ ) 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[j]=p; /* 将p 所指的结点插入到第j 个子表中*/ |
} |
} |
void Collect ( NodeType *r, int i,ArrayPtr f,ArrayPtr e ) |
{ /*本算法按keys[i]自小到大地将f[0…RADIX-1]所指各子表依次链接成一个链表*e[0…RADIX-1]为各子表的尾指针*/ |
for ( j=0; !f[j]; j=succ ( j ) ); /*找第一个非空子表,succ 为求后继函数*/ |
r[0].next=f[j]; |
t=e[j]; /*r[0].next 指向第一个非空子表中第一个结点*/ |
while ( j<RADIX ) |
{ |
for ( j=succ ( j ); j<RADIX-1&&!f[j]; j=succ ( j ) ); /*找下一个非空子表*/ |
if ( f[j] ) {r[t].next=f[j]; t=e[j];} /*链接两个非空子表*/ |
} |
r[t].next=0; /*t 指向最后一个非空子表中的最后一个结点*/ |
} |
void RadixSort ( L_TBL *ltbl ) |
{ /*对ltbl 作基数排序,使其成为按关键码升序的静态链表,ltbl->r[0]为头结点*/ |
for ( i=0; i<ltbl->length; i++ ) ltbl->r[i].next=i+1; |
ltbl->r[ltbl->length].next=0; /*将ltbl 改为静态链表*/ |
for ( i=0; i<ltbl->keynum; i++ ) /*按最低位优先依次对各关键码进行分配和收集*/ |
{ |
Distribute ( ltbl->r,i,f,e ); /*第i 趟分配*/ |
Collect ( ltbl->r,i,f,e ); /*第i 趟收集*/ |
} |
} |