没有合适的资源?快使用搜索试试~ 我知道了~
数据结构试验哈希表优质资料.doc
0 下载量 60 浏览量
2022-12-02
22:23:41
上传
评论
收藏 748KB DOC 举报
温馨提示
试读
39页
数据结构试验哈希表优质资料.doc
资源推荐
资源详情
资源评论
数据结构试验哈希表优质资料
(可以直接使用,可编辑 优质资料,欢迎下载)
第 10 章实验
实验名称:考试日程安排与成绩统计
实验类型:综合性性实验
班级:20210611
学号:2021061118
姓名:郭鑫
1.问题描述
①问题描述
现要安排考试的考表(即考试日程表),假设共有 10 个班的学生,要安
排 10 门必修课程的考试,必修课程是以班级来确定的,每个班各有 3
门必修课,因此各班的考试科目是不相同的;安排考表的原则是:相同
课程采用统一的试卷,因此同一门课程的考试必须在相同时间进行,同
一个班所修的科目必须安排在不同的时间进行考试,以避免考试时间的
冲突。并要求全部考试的日程尽可能短。
要求对考试结果做统计和排序。假设分别以编号 0,1,2,3,4,5,6,7,8,9 代表
10 门要考试的课程,以 B
1
,B
2
,B
3
,B
4
,B
5
,B
6
,B
7
,B
8
,B
9
,B
10
代
表 10 个班,每个人的信息包括学号、姓名、班级、各门考试课程成绩、
三门课程总成绩,每个班的学生人数自行设定。要求设计一个简单的考
试成绩的查询统计系统实现以下功能:
显示学生考试情况-按考试总分从高到底输出全体学生的信息。-按
照从 B
1
到 B
10
的班级顺序,分班级按照考试总分从高到底的顺序输
出各班学生的信息。-输出指定班的学生考试成绩信息。
统计学生考试成绩-按总成绩统计出 90 分以上、80~89 分、70~79 分、
60~69 分、60 分以下各分数段的人数,并按总分从高到低分段输出。
-根据指定的某们课程的成绩,统计出上述各分数段的人数,并按分
数从高到低分段输出。-统计并输出指定班级中总成绩或某一门课成
绩的各分数段人数和每个人具体的信息。
查找学生成绩-查找总分或某一门课程成绩的指定分数段的人数及
学生的详细信息。-查找指定班级中总分或某一门课程成绩属于某分
数段的学生详细信息。-查找指定学生(例如给定学号)的具体信息,
包括:姓名、班级、各科分数、总分数等。
②求解方法说明
考试日程安排问题。
该问题实际上是对若干元素进行子集划分的问题,要求所划分的每
个子集中的元素没有“考试冲突”关系。
假 设 各 个 班 的 考 试 课 程 分 别 为 :
(1,4,8),(1,3,7),(8,2,4),(1,0,5),(2,6,9),(3,0,8),(4,5,9),(2,9,7),(6,0,3),(5,6,9)。
根据题中考试安排原则,各个班要进行的考试课程可以抽象为“考
试冲突关系”,归纳各个班的考试课程可以整理得到考试冲突关系:
R={(1,4),(1,8),(4,8),(1,3),(1,7),(3,7),(8,2),(2,4),(1,0),(1,5),(0,5),(2,6),(2,
9),(6,9),(3,0),(0,8),(3,8),(4,5),(5,9),(4,5),(2,7),(9,7),(6,0),(6,3),(5,6)}。显
然,“考试冲突”关系 R 的每个有序对中的两门课程不能安排在同
一时间考试,据此可以将 10 门课划分为若干个考试时间没有冲突的
子集,并且使考场的场次尽量少,使得整个考试时间尽可能短。
上述子集划分问题可以用对集合中的元素逐个“筛选”的办法来解
决。首先将集合的第 1 个元素置为第 1 个子集,再逐个检查集合中
的其余元素是否和第 1 个元素有考试冲突,若不存在考试冲突,则
将其加入到第 1 个子集中,继续检查集合中的其余元素,凡是不与
第 1 个子集中的元素冲突的元素都逐个将其加入到其中;接着按同
样的方法“筛选”出若干没有考试冲突的元素构成第 2 个子集,…,
该过程一直到集合中的全部元素都分到某个子集中结束。得到的每
一个子集中的课程就是可以安排在同一时间考试的课程。不同子集
的课程则要安排在不冲突的时间考试。
考试分数的统计与排序
考试成绩输出
✓ 每个学生的信息记录数据项应包括:学号、姓名、班级、课程
1、课程 2、…、课程 10、总成绩。
✓ 按总分高低输出所有学生信息时,应该以总成绩为关键字从高
分到低分对所有的学生记录进行排序,排序方法自行选定,然
后依次输出各个记录。
✓ 按照班级顺序和总分高低输出各班学生信息时,要对学生记录
进行多关键字排序,首先以总成绩为关键字从高分到低分对所
有的学生记录进行排序,然后再以班号为关键字对全部学生记
录排序,再输出结果。
统计成绩统计各分数段的人数,要求由用户输入,具体要求可以有:
✓ 按照总成绩统计各分数段的人数,并输出各分数段的学生记录,
即在统计一个分数段的人数过程中,要输出满足查找条件的学
生记录,再输出统计的结果。
✓ 指定某一门课程,统计各分数段的人数并输出各分数段的学生
记录。
✓ 对指定班级中总成绩或指定课程成绩做各分数段人数的统计,
也要输出各分数段的学生记录。
查找成绩查找要求由用户输入,可以输入以下条件:
✓ 查找指定分数项(总分或某一门课程)的某分数段的学生信息,
输出查找结果。
✓ 查找指定班级、指定分数项的某分数段的学生信息,输出查找
结果。
✓ 查找指定学生(给定学号)的具体信息,输出查找结果。
③算法提示
考试场次的划分——“无考试冲突”子集划分的算法思路。 为了把
10 门课程划分为时间上不冲突的若干场考试,可以利用一个循环队列来
实现求解方法中说明的“筛选”过程。 首先定义一个循环队列,再
把 10 门课程的编号从小到大依次加入到循环队列中,然后重复下列步
骤:
✓ 队头元素出队并作为当前子集的第 1 个元素。
✓ 队头元素继续依次出队,每出队一个队头元素都要检查与当前
子集中的元素是否有“考试冲突”;如果没有冲突,则将其加入
到当前子集中,否则将其重新加入队列中,等待以后加入新子
集的机会。
✓ 比较刚出队元素与前一出队元素编号。因为队列中原有的元素
是以编号从小到大的顺序排列的,重新入队的元素编号一定小
于它的前一元素,所以一旦发现目前出队的元素编号小于前一
个出队的元素,就可以断定当前的“考试冲突”子集已经构建
完,队列中剩余元素应该构建新的子集。为此,在当前的队头
元素出队前,要先记下刚刚出队的元素,以便判断当前出队的
元素是否要开始构建一个新子集。
重复上述步骤一直到队列空,则“无考试冲突”子集划分完成。
由上述算法思路可以知道,“无考试冲突”子集的划分过程是一个
循环的执行过程,循环中的主要操作是元素出队和判断的操作。判断操
作包括出队元素是否可以加入当前子集和是否要开始构建一个新子集
两个方面,对后一个判断如前所述,通过比较出队元素与前一个出队元
素编号大小可以确定。为了判断出队元素与当前子集中的元素是否有
“考试冲突”,可以定义一个二维数组 conf[n][n]来表示课程的考试冲突
关系矩阵,矩阵中各元素的值根据以下规则确定,若编号为 i 的课程和
编号为 j 的课程有考试冲突,则置 conf[i][j]=1,否则置 conf[i][j]=0,考
试冲突关系矩阵如图 1 所示。
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
1
0
1
1
0
0
0
0
0
1
0
1
1
1
1
1
1
0
0
0
0
1
1
1
0
0
1
1
0
0
1
0
0
1
1
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
1
0
0
0
1
0
1
1
1
0
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
1
0
1
1
1
1
0
0
图 1 考试冲突关系矩阵
利用“考试冲突”关系矩阵可以检查出队元素 i 是否与当前子集中
的元素有考试冲突,其方法是:当课程号为 j
1
,j
2
,…,j
k
的元素已经在
当前子集 S 中,要判断目前出队的元素 i 是否可以加入子集 S,只要检
查“考试冲突”关系矩阵中第 i 行的元素 conf[i][ j
1
],conf[i][ j
2
],…
conf[i][ j
k
]的值是否为 0 即可。如果这些元素的值都为 0,表示课程 i 与
子集中的课程没有考试冲突,可以加入其中,否则说明表示课程 i 与子
集中的某些课程有考试冲突,它不能加入该子集中。为了减少在二维数
组 conf 中查找元素的操作,可以定义一个一维数组 clash[n]来方便出队
元素 i 是否要加入当前子集的判断,数组 clash[n]用于记录出队元素 i 与
当前子集中的元素是否存在考试冲突的信息。每当开始构建一个新子集
时,先将数组 clash[n]的各元素初始化为 0,当有编号为 i 的课程加入子
集时,将“考试冲突”关系矩阵中第 i 行的各列的值与数组 clash 的各对
应元素的值相加,因而使得数组 clash 中和编号为 i 的元素有考试冲突的
相应元素的值不再是 0,当下一个队头元素 j 出队时,只要检查数组 clash
中第 j 个元素的值是否为 0,就可以判断其是否与当前子集中的元素有
考试冲突;若数组 clash 中第 j 个元素的值不为 0,则说明元素 j 与当前
子集中元素存在考试冲突,应将其重新加入队列;若数组 clash 中第 j 各
元素的值为 0,则说明它与当前子集中元素不存在考试冲突,应该将它
加入当前子集中,同时要将“考试冲突”关系矩阵中第 j 行的各列的值
与数组 clash 的各对应元素的值相加,这个过程一直到队列空,则划分
无考试冲突子集完成。划分结果可以用一个二维数组来记录各子集中的
元素的方式来表示,也可以用一个一维数组来记录每个元素其所属的子
集号的方式来表示。上述算法的思路可以描述如下:
建立表示课程考试冲突关系矩阵的二维数组 conf[n][n];
定义用于检查当前子集的课程考试冲突信息的数组 clash[n];
定义用于记录子集划分结果的数组 result[n];
pre=n;//pre 用于记录前一个出队元素的编号,初始值置为 n 以
新建第 1 个子集
k=0; //k 用于记录子集序号
0~9(课程编号)依次入队;
while(队列不空)
{
队头元素 i 出队;
if(i<pre)//刚出队元素小于前一个出队元素,生成一个新子集
{
k++;
数组 clash 初始化;
}
if(i 可以加入当前子集)//如果刚出队元素与当前子集中的元素
无考试冲突,将其加入当前子集
{
将 i 加入当前子集,记录 i 所属子集的序号;
将 conf 数组第 i 行各列的值与 clash 数组对应列的值相加并记入
clash 中;
}
else //如果刚出队元素与当前子集中的元素有考试冲突,将其
重新入队
将 i 重新加入队列;
pre=i;
}
考试成绩统计和排序的实现
✓ 按总成绩或按某一门课的成绩统计并输出人数时,应该使各分
剩余38页未读,继续阅读
资源评论
matlab大师
- 粉丝: 2359
- 资源: 9万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功