数据结构课程设计
学 院： 信息科学与工程学院
专 业： 计算机科学与技术
班 级： 计 0902
学 号： 20091221067
学生姓名： 付乐颖
指导教师： 王永燕
201 1 年 3 月 9 日
一、实验内容
【设计题目】
多关键字排序的程序设计
【问题描述】
多关键字的排序有一定的使用范围。例如：在进行高考分数处理时，除了需要
对总分进行排序外。不同的专业单科分数的要求不同，因此尚需在总分相同的
情况下，按用户提出的单科分数的次序要求排除考生录取的次序。
【基本要求】
(1) 假设待排序的记录数不超过10000，表中记录的关键字数不超过5，各个关
键字的范围均为0至100。按用户给定的进行排序的关键词优先关系，输出排序
结果。
(2) 约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策
略：其一是利用稳定的内部排序法，其二是利用“分配”和“收集”的方法；并综合
比较这两种策略。
【测试数据】
测试用例自己设计。
二、数据结构设计
1.静态链表的结点类型
typedef struct{
int keys[MAX_NUM_OF_KEY]; //关键字
int next; //下一个的数组下标
}SLCell;
2.静态链表类型
typedef struct{
SLCell r[MAX_SPACE]; //静态链表的可利用空间，r[0]为头结点
int keynum; //记录的当前关键字个数
int recnum; //记录的个数
}SLList;
3.功能模块设计
SLList Creat()
操作结果：用 SLList 接收考生的各科成绩。
void Distribute(SLCell *r,int i,int *f,int *e)
初始条件：存在以 i 为下标的关键字。
操作结果：以下标为 i 的关键字为准做一趟分配。
void Collect(SLCell *r,int i,int *f,int *e)
初始条件：存在以 i 为下标的关键字。
操作结果：以下标为 i 的关键字为准做一趟收集。
void RadixSort(SLList *l)
操作结果：对*l 中的成绩做链式基数排序。
void ShowRank(SLList *l)
操作结果：按名次顺序输出考生的名次和分数。
void BubbleSort(SLList &l,int key[])
操作结果：对 l 中的成绩进行冒泡排序
三、算法设计
1.稳定的内部排序法：
void BubbleSort(SLList &l,int key[]) //LSD 冒泡法排序
{
int y,i,j,k;
SLCell R;
for(k=3;k>=0;k--) //根据给出的关键字顺序按LSD法对各科成绩进行排序
{
i=key[k];
for(y=0;y<l.recnum-1;y++)
for(j=1;j<l.recnum-y;j++)
{
if(l.r[j].keys[i]<l.r[j+1].keys[i])
{
R=l.r[j];
l.r[j]=l.r[j+1];
l.r[j+1]=R;
}
}
}
- 1
- 2
前往页