数据结构考研分类复习真题 第十章 答案[44]

手工模拟排序过程略

#define n 待排序记录的个数

typedef struct

{ int key[d]; //关键字由d个分量组成

int next; //静态链域

AnyType other; //记录的其它数据域

} SLRecType;

SLRecType R[n+]; //R[n]存放n个记录

typedef struct

{ int fe; //队列的头尾指针

} SLQueue;

SLQueue B[m] //用队列表示桶共m个

int RadixSort(SLRecType R[] int n)

{ //对R[n]进行基数排序返回收集用的链头指针

for(i=;i<n;i++) R[i]next=i+;//将R[n]链成一个静态链表

R[n]next=; p=; //将初始链表的终端结点指针置空 p指向链表的第一个结点

for(j=d;j>=;j) //进行d趟排序

{for(i=;i<m;i++) { B[i]f=;B[i]e=;}//初始化桶

while(p!=) //按关键字的第j个分量进行分配

{ k=R[p]key[j]; //k为桶的序号

if(B[k]f==) B[k]f=p; //将R[p]链到桶头

else R[B[k]e]next=p; //将R[p]链到桶尾

B[k]e=p; //修改桶的尾指针

p=R[p]next; //扫描下一个记录

}//while

i=;

while(B[i]f==) i++; //找第一个非空的桶

t=B[i]e; p=B[i]f //p为收集链表的头指针t为尾指针

while(i<m)

{i++;

if(B[i]f!=){ R[t]next=B[i]f; t=B[i]e; } //连接非空桶

}//while

R[t]next=; //本趟收集完毕将链表的终端结点指针置空

}//for

return p;

}//RadixSort

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []