程序填空题：基数排序
基数排序。
```c++
#include
#define MAXNUM_KEY 8 //关键字项数的最大值
#define RADIX 10 //关键字基数，此时是十进制整数的基数
#define MAX_SPACE 10000
using namespace std;
typedef struct
{
char keys[MAXNUM_KEY]; //关键字
int next;
}SLCell;
typedef struct
{
SLCell r[MAX_SPACE]; //静态链表的可利用空间，r[0]为头结点
int keynum; //记录的当前关键字个数
int recnum; //静态链表的当前长度
}SLList; //静态链表类型
void InitList(SLList *L)
{
int i,n,keynum;
cin>>n>>keynum;
(*L).keynum=keynum;
(*L).recnum=n;
for(i=1;i<=n;i++)
cin>>(*L).r[i].keys;
}
void Distribute(SLCell *r,int i,int *f,int *e)
{
int j,p;
for(j=0;j for(p=r[0].next;p;p=r[p].next)
{
j=r[p].keys[i]-'0';
if(!f[j])
@@[f[j]](2)=p;
else
r[e[j]].next=p;
@@[e[j]](2)=p;
}
}
void Collect (SLCell *r,int i,int *f,int *e)
{
int j,t;
for(j=0;!f[j];j++);
r[0].next=@@[f[j]](2);
t=@@[e[j]](2);
while(j {
for(j++;j if(f[j])
{
@@[r[t].next](2)=f[j];
@@[t](2)=e[j];
}
}
r[t].next=0;
}
void RadixSort(SLList &L)
{
int i;
int f[RADIX],e[RADIX];
for(i=0;i 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 print(SLList L)
{
int p,flag=1;
for(p=L.r[0].next;p;p=L.r[p].next)
{if(flag)
{cout< else
cout<<" "< }
}
int main()
{
SLList l;
InitList(&l);
RadixSort(l);
print(l);
return 0;
}
```
### 输入样例：
第一行输入待排序个数n和关键字个数keynum，接下来输入n个数（字符串）。
```in
10 3
278 109 063 930 589 184 505 269 008 083
```
### 输出样例：
输出排序结果。
```out
008 063 083 109 184 269 278 505 589 930
```
答案：
第1空：f[j]
第2空：e[j]
第3空：f[j]
第4空：e[j]
第5空：r[t].next
第6空：t
```c++
#include
#define MAXNUM_KEY 8 //关键字项数的最大值
#define RADIX 10 //关键字基数，此时是十进制整数的基数
#define MAX_SPACE 10000
using namespace std;
typedef struct
{
char keys[MAXNUM_KEY]; //关键字
int next;
}SLCell;
typedef struct
{
SLCell r[MAX_SPACE]; //静态链表的可利用空间，r[0]为头结点
int keynum; //记录的当前关键字个数
int recnum; //静态链表的当前长度
}SLList; //静态链表类型
void InitList(SLList *L)
{
int i,n,keynum;
cin>>n>>keynum;
(*L).keynum=keynum;
(*L).recnum=n;
for(i=1;i<=n;i++)
cin>>(*L).r[i].keys;
}
void Distribute(SLCell *r,int i,int *f,int *e)
{
int j,p;
for(j=0;j
{
j=r[p].keys[i]-'0';
if(!f[j])
@@[f[j]](2)=p;
else
r[e[j]].next=p;
@@[e[j]](2)=p;
}
}
void Collect (SLCell *r,int i,int *f,int *e)
{
int j,t;
for(j=0;!f[j];j++);
r[0].next=@@[f[j]](2);
t=@@[e[j]](2);
while(j
for(j++;j
{
@@[r[t].next](2)=f[j];
@@[t](2)=e[j];
}
}
r[t].next=0;
}
void RadixSort(SLList &L)
{
int i;
int f[RADIX],e[RADIX];
for(i=0;i
for(i=L.keynum-1;i>=0;i--)
{
Distribute(L.r,i,f,e);
Collect(L.r,i,f,e);
}
}
void print(SLList L)
{
int p,flag=1;
for(p=L.r[0].next;p;p=L.r[p].next)
{if(flag)
{cout<
cout<<" "<
}
int main()
{
SLList l;
InitList(&l);
RadixSort(l);
print(l);
return 0;
}
```
### 输入样例：
第一行输入待排序个数n和关键字个数keynum，接下来输入n个数（字符串）。
```in
10 3
278 109 063 930 589 184 505 269 008 083
```
### 输出样例：
输出排序结果。
```out
008 063 083 109 184 269 278 505 589 930
```
答案：
第1空：f[j]
第2空：e[j]
第3空：f[j]
第4空：e[j]
第5空：r[t].next
第6空：t
