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

[题目分析]本题是基数排序的特殊情况关键字只含一位数字的整数

typedef struct

{ int key;

int next;

} SLRecType;

SLRecType R[N+];

typedef struct

{ intfe;

} SLQueue;

SLQueue B[];

int Radixsort(SLRecType R[]int n) //设各关键字已输入到R数组中

{for (i=;i<n;i++ ) R[i]next=i+;

R[n]next=; p=; //表示静态链表结束

for (i=;i<=;i++);{ B[i]f=; B[i]e=;} //设置队头队尾指针初值

while (p!=) //一趟分配

{k=R[p]key; //取关键字

if(B[k]f==)B[k]f=p; //修改队头指针

else R[B[k]e]next=p;

B[k]e=p;

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

}

i=; //一趟收集

while (B[i]f==) i++;

t=B[i]e; p=B[i]f;

while (i<)

{i++;

if (B[i]f!=)

{ R[t]next=B[i]f;t=B[i]e;} }

R[t]next=;

return p; //返回第一个记录指针

}

[算法讨论]若关键字含d位则要进行d趟分配和d趟收集关键字最好放入字符数组以便取关键字的某位

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