没有合适的资源?快使用搜索试试~ 我知道了~
首页数据结构课程设计——多关键字排序.docx
数据结构——多关键字排序 问题描述:多关键字的排序有其一定的实用范围。例如:在进行高考分数处理时,除了需对总分进行排序外,不同的专业对单科分数的要求不同,因此尚需在总分相同的情况下,按用户提出的单科分数的次序要求排出考生录取的次序。 要求:(1)假设待排序的记录数不超过10000,表中记录的关键字数不超过5,各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系,输出排序结果。(2)约定按LSD法(.最低位优先)进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法,其二是利用"分配"和"收集"的方法。并综合比较这两种策略。 测试数据:由随机数产生器生成。
资源详情
资源评论
资源推荐
一、问题描述与任务定义
多关键字排序
问题描述:多关键字的排序有其一定的实用范围。例如 :在进行高考分数处
理时,除了需对总分进行排序外,不同的专业对单科分数的要求不同,因此尚
需在总分相同的情况下,按用户提出的单科分数的次序要求排出考生录取的次
序。
要求:(1)假设待排序的记录数不超过 10000,表中记录的关键字数不超过
5,各个关键字的范围均为 0 至 100。按用户给定的进行排序的关键字的优先
关系,输出排序结果。(2)约定按 LSD 法(.最低位优先)进行多关键字的排序。
在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法,其二
是利用"分配"和"收集"的方法。并综合比较这两种策略。
测试数据:由随机数产生器生成。
实现提示:
用 5 至 8 组数据比较不同排序策略所需时间。由于是按 LSD 方法进行排序,
1
则对每个关键字均可进行整个序列的排序,但在利用通常的内部排序方法进行
排序时,必须选用稳定的排序方法。借助"分配"和"收集"策略进行的排序,如
同一趟"基数排序",由于关键字的取值范围为 0 至 100,则分配时将得到 104
个链表。
二、设计思路
三、设计内容
3.1 详细设计
本程序是对语文,数学,英语,计算机,其他以及总分进行的按照用户给
定的科目优先级顺序进行优先排序。各科分数为 0~100。总分分数为 0~
500。
由于本实验约定按 LSD 进行多关键字的排序。在对个关键字进行排序时采
用两种策略:其一是利用稳定的内部排序法,其二是利用“分配”和“收集”的方法 。
所以在一个程序里实现了这两种排序方法,并且可进行算法时间的比较。
2
第一种排序方法由于要使用稳定的排序方法,故参考书上的几种排序方法
后,选用了冒泡排序和静态链表存储方式,每一趟排序后,找出最高分 。第二
种排序方法利用“分配”与“收集”的基数排序算法,用静态链表存储分数,在一趟
排序中,将结点分配到相应的链队列中去,再按从高到低链接起来。
通过设置获取用户输入的科目关键字顺序,判断进行排序科目序列的顺序。
对各科目及总分进行排序完成后,调用函数进行数据输出至屏幕。
3.1.1 数据结构设计
(1)稳定的内部排序法
结构体定义
typedef struct node //定义结构体
{
int key[6]; //数据域
struct node *next; //指针域
}*Score,Lnode;
基本操作
Score RandData(Score &L,int n)
初始条件:L 为创建的静态链表,代表了一个学生成绩的记录,n 为生成的随机
3
数个数。
操作结果:随机生成 n 个数据并保存到链表 L 中,返回链表头指针。
Score BubbleSort(Score &L,int n)
初始条件:L 为创建的静态链表
操作结果:对链表进行冒泡降序排序,返回指针 L。
void PrintScore(Score &L)
初始条件:L 为创建的静态链表。
操作结果:在屏幕上显示链表。
(2)“分配”与“收集”的基数排序
结构体定义
typedef struct node //定义结构体
{
int key[6]; //数据域
struct node *next; //指针域
}*Score,Lnode;
基本操作
Score RandData(Score &L,int n)
初始条件:L 为创建的静态链表,代表了一个学生成绩的记录,n 为生成的随机
数个数。
4
操作结果:随机生成 n 个数据并保存到链表 L 中,返回链表头指针。
Score RadixSort(Score &L, int n)
初始条件:L 为创建的静态链表,代表了一条学生成绩的记录。
操作结果:对链表 L 的第 n 个关键字进行基数排序。
void PrintScore(Score &L)
初始条件:L 为创建的静态链表。
操作结果:在屏幕上显示链表。
3.1.2 主要算法设计
(1)稳定的内部排序
Score BubbleSort(Score &L,int n ) //对链表进行冒泡降序排序,返回指针
L
{
Score p,q,s,t,N;
t=(Score)malloc(sizeof(node));
N=(Score)malloc(sizeof(node));
N->next=L->next; //把 N 指向链表 L
L->next=NULL; //L 重新指向空
s=L; //创建新的链表 L
while(N->next->next)
{
p=N->next;
5
剩余25页未读,继续阅读
计算机瞎鼓捣能手
- 粉丝: 23
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- stc12c5a60s2 例程
- Android通过全局变量传递数据
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论5