数据结构试验哈希表.doc
《数据结构试验哈希表.doc》由会员分享,可在线阅读,更多相关《数据结构试验哈希表.doc(7页珍藏版)》请在咨信网上搜索。
1、第10章实验实验名称:考试日程安排与成绩统计实验类型:综合性性实验班级:20100611学号:2010061118姓名:郭鑫实验日期:2012。6。281. 问题描述问题描述l 现要安排考试的考表(即考试日程表),假设共有10个班的学生,要安排10门必修课程的考试,必修课程是以班级来确定的,每个班各有3门必修课,因此各班的考试科目是不相同的;安排考表的原则是:相同课程采用统一的试卷,因此同一门课程的考试必须在相同时间进行,同一个班所修的科目必须安排在不同的时间进行考试,以避免考试时间的冲突。并要求全部考试的日程尽可能短。l 要求对考试结果做统计和排序。假设分别以编号0,1,2,3,4,5,6,
2、7,8,9代表10门要考试的课程,以B1,B2,B3,B4,B5,B6,B7,B8,B9,B10代表10个班,每个人的信息包括学号、姓名、班级、各门考试课程成绩、三门课程总成绩,每个班的学生人数自行设定。要求设计一个简单的考试成绩的查询统计系统实现以下功能: 显示学生考试情况-按考试总分从高到底输出全体学生的信息。-按照从B1到B10的班级顺序,分班级按照考试总分从高到底的顺序输出各班学生的信息。-输出指定班的学生考试成绩信息。 统计学生考试成绩按总成绩统计出90分以上、8089分、7079分、6069分、60分以下各分数段的人数,并按总分从高到低分段输出。-根据指定的某们课程的成绩,统计出上
3、述各分数段的人数,并按分数从高到低分段输出。统计并输出指定班级中总成绩或某一门课成绩的各分数段人数和每个人具体的信息. 查找学生成绩查找总分或某一门课程成绩的指定分数段的人数及学生的详细信息。-查找指定班级中总分或某一门课程成绩属于某分数段的学生详细信息。-查找指定学生(例如给定学号)的具体信息,包括:姓名、班级、各科分数、总分数等。求解方法说明l 考试日程安排问题. 该问题实际上是对若干元素进行子集划分的问题,要求所划分的每个子集中的元素没有“考试冲突关系。 假设各个班的考试课程分别为:(1,4,8),(1,3,7),(8,2,4),(1,0,5),(2,6,9),(3,0,8),(4,5,
4、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门课划分为若干个考试时间没有冲突的子集,
5、并且使考场的场次尽量少,使得整个考试时间尽可能短。 上述子集划分问题可以用对集合中的元素逐个“筛选的办法来解决。首先将集合的第1个元素置为第1个子集,再逐个检查集合中的其余元素是否和第1个元素有考试冲突,若不存在考试冲突,则将其加入到第1个子集中,继续检查集合中的其余元素,凡是不与第1个子集中的元素冲突的元素都逐个将其加入到其中;接着按同样的方法“筛选”出若干没有考试冲突的元素构成第2个子集,该过程一直到集合中的全部元素都分到某个子集中结束.得到的每一个子集中的课程就是可以安排在同一时间考试的课程。不同子集的课程则要安排在不冲突的时间考试。l 考试分数的统计与排序 考试成绩输出 每个学生的信息
6、记录数据项应包括:学号、姓名、班级、课程1、课程2、课程10、总成绩. 按总分高低输出所有学生信息时,应该以总成绩为关键字从高分到低分对所有的学生记录进行排序,排序方法自行选定,然后依次输出各个记录。 按照班级顺序和总分高低输出各班学生信息时,要对学生记录进行多关键字排序,首先以总成绩为关键字从高分到低分对所有的学生记录进行排序,然后再以班号为关键字对全部学生记录排序,再输出结果。 统计成绩统计各分数段的人数,要求由用户输入,具体要求可以有: 按照总成绩统计各分数段的人数,并输出各分数段的学生记录,即在统计一个分数段的人数过程中,要输出满足查找条件的学生记录,再输出统计的结果。 指定某一门课程
7、,统计各分数段的人数并输出各分数段的学生记录。 对指定班级中总成绩或指定课程成绩做各分数段人数的统计,也要输出各分数段的学生记录。 查找成绩查找要求由用户输入,可以输入以下条件: 查找指定分数项(总分或某一门课程)的某分数段的学生信息,输出查找结果。 查找指定班级、指定分数项的某分数段的学生信息,输出查找结果. 查找指定学生(给定学号)的具体信息,输出查找结果。算法提示l 考试场次的划分-“无考试冲突”子集划分的算法思路。 为了把10门课程划分为时间上不冲突的若干场考试,可以利用一个循环队列来实现求解方法中说明的“筛选”过程。 首先定义一个循环队列,再把10门课程的编号从小到大依次加入到循环队
8、列中,然后重复下列步骤: 队头元素出队并作为当前子集的第1个元素. 队头元素继续依次出队,每出队一个队头元素都要检查与当前子集中的元素是否有“考试冲突”;如果没有冲突,则将其加入到当前子集中,否则将其重新加入队列中,等待以后加入新子集的机会。 比较刚出队元素与前一出队元素编号。因为队列中原有的元素是以编号从小到大的顺序排列的,重新入队的元素编号一定小于它的前一元素,所以一旦发现目前出队的元素编号小于前一个出队的元素,就可以断定当前的“考试冲突”子集已经构建完,队列中剩余元素应该构建新的子集.为此,在当前的队头元素出队前,要先记下刚刚出队的元素,以便判断当前出队的元素是否要开始构建一个新子集。重
9、复上述步骤一直到队列空,则“无考试冲突”子集划分完成。由上述算法思路可以知道,“无考试冲突”子集的划分过程是一个循环的执行过程,循环中的主要操作是元素出队和判断的操作.判断操作包括出队元素是否可以加入当前子集和是否要开始构建一个新子集两个方面,对后一个判断如前所述,通过比较出队元素与前一个出队元素编号大小可以确定.为了判断出队元素与当前子集中的元素是否有“考试冲突”,可以定义一个二维数组confnn来表示课程的考试冲突关系矩阵,矩阵中各元素的值根据以下规则确定,若编号为i的课程和编号为j的课程有考试冲突,则置confij=1,否则置confij=0,考试冲突关系矩阵如图1所示.01010110
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 试验 哈希表
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。