数据结构试验哈希表.doc

第10章实验
实验名称:考试日程安排与成绩统计
实验类型:综合性性实验
班级：20100611
学号：2010061118
姓名：郭鑫
实验日期：2012。6。28
1. 问题描述
①问题描述
l 现要安排考试的考表(即考试日程表）,假设共有10个班的学生，要安排10门必修课程的考试，必修课程是以班级来确定的,每个班各有3门必修课，因此各班的考试科目是不相同的；安排考表的原则是：相同课程采用统一的试卷，因此同一门课程的考试必须在相同时间进行，同一个班所修的科目必须安排在不同的时间进行考试,以避免考试时间的冲突。并要求全部考试的日程尽可能短。
l 要求对考试结果做统计和排序。假设分别以编号0，1,2,3，4,5，6,7，8，9代表10门要考试的课程，以B1,B2，B3，B4，B5，B6，B7，B8,B9，B10代表10个班，每个人的信息包括学号、姓名、班级、各门考试课程成绩、三门课程总成绩，每个班的学生人数自行设定。要求设计一个简单的考试成绩的查询统计系统实现以下功能：
² 显示学生考试情况-按考试总分从高到底输出全体学生的信息。-按照从B1到B10的班级顺序，分班级按照考试总分从高到底的顺序输出各班学生的信息。-输出指定班的学生考试成绩信息。
² 统计学生考试成绩—按总成绩统计出90分以上、80～89分、70～79分、60～69分、60分以下各分数段的人数，并按总分从高到低分段输出。-根据指定的某们课程的成绩，统计出上述各分数段的人数，并按分数从高到低分段输出。—统计并输出指定班级中总成绩或某一门课成绩的各分数段人数和每个人具体的信息.
² 查找学生成绩—查找总分或某一门课程成绩的指定分数段的人数及学生的详细信息。-查找指定班级中总分或某一门课程成绩属于某分数段的学生详细信息。-查找指定学生(例如给定学号）的具体信息,包括：姓名、班级、各科分数、总分数等。
②求解方法说明
l 考试日程安排问题.
² 该问题实际上是对若干元素进行子集划分的问题，要求所划分的每个子集中的元素没有“考试冲突"关系。
² 假设各个班的考试课程分别为:（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个子集,…,该过程一直到集合中的全部元素都分到某个子集中结束.得到的每一个子集中的课程就是可以安排在同一时间考试的课程。不同子集的课程则要安排在不冲突的时间考试。
l 考试分数的统计与排序
² 考试成绩输出
ü 每个学生的信息记录数据项应包括：学号、姓名、班级、课程1、课程2、…、课程10、总成绩.
ü 按总分高低输出所有学生信息时,应该以总成绩为关键字从高分到低分对所有的学生记录进行排序，排序方法自行选定，然后依次输出各个记录。
ü 按照班级顺序和总分高低输出各班学生信息时，要对学生记录进行多关键字排序，首先以总成绩为关键字从高分到低分对所有的学生记录进行排序，然后再以班号为关键字对全部学生记录排序，再输出结果。
² 统计成绩统计各分数段的人数，要求由用户输入，具体要求可以有：
ü 按照总成绩统计各分数段的人数，并输出各分数段的学生记录，即在统计一个分数段的人数过程中，要输出满足查找条件的学生记录，再输出统计的结果。
ü 指定某一门课程，统计各分数段的人数并输出各分数段的学生记录。
ü 对指定班级中总成绩或指定课程成绩做各分数段人数的统计,也要输出各分数段的学生记录。
² 查找成绩查找要求由用户输入，可以输入以下条件：
ü 查找指定分数项(总分或某一门课程）的某分数段的学生信息，输出查找结果。
ü 查找指定班级、指定分数项的某分数段的学生信息，输出查找结果.
ü 查找指定学生（给定学号）的具体信息，输出查找结果。
③算法提示
l 考试场次的划分—-“无考试冲突”子集划分的算法思路。 为了把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是否与当前子集中的元素有考试冲突，其方法是:当课程号为j1，j2，…,jk的元素已经在当前子集S中，要判断目前出队的元素i是否可以加入子集S，只要检查“考试冲突”关系矩阵中第i行的元素conf［i］[ j1]，conf[i］［ j2］，…conf[i][ jk]的值是否为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；
}
l 考试成绩统计和排序的实现
ü 按总成绩或按某一门课的成绩统计并输出人数时，应该使各分数段的人数和每个学生的信息清晰的分开.
ü 对全体学生或对某一个班的学生的成绩进行排序时，排序方法可以任意选择。就本实验问题而言，因表长不大采用简单的排序方法就可以达到目的，但为了比较各种常用排序方法性能和适用场合，还可以采用不同的排序方法实现排序。
ü 对多关键字的排序要求，要注意排序方法的稳定性问题。例如，在按总成绩从高分到低分对全体学生进行排序后，再按班级从高分到低分进行排序，此时要求分班级排序时采用的排序方法其动态性能必须是稳定的。同样地，如果在按总成绩从高分到低分排序的基础上，再要求按某一门课的成绩从高分到低分排序，也要求第2层排序一定注意选择动态性能稳定的排序方法。
ü 在实现查找或排序功能时，其查找或排序的依据(指定项)和目标(输出结果)通过提示用户输入来确定.
2. 数据结构设计
typedef int KeyType;
typedef char InfoType［10］;
typedef struct /*记录类型＊/
｛
KeyType key； /＊关键字项＊/
InfoType data； /＊其他数据项,类型为InfoType＊/
｝ RecType
3. 算法设计
#include〈iostream〉
using namespace std;
#define MAXE 20/＊线性表中最多元素个数＊/
typedef int KeyType;
typedef char InfoType［10];
typedef struct /*记录类型＊/
｛
KeyType key； /*关键字项＊/
InfoType data; /＊其他数据项,类型为InfoType＊/
｝ RecType；
void SelectSort（RecType R［],int n）/＊直接选择排序算法*/
｛
int i,j，k，l;
RecType temp；
for （i=0；i〈n-1;i++） /*做第i趟排序＊/
｛
k=i;
for (j=i+1；j〈n;j++） /＊在当前无序区R［i。.n-1］中选key最小的R［k］ ＊/
if （R[j］。key〈R[k］。key)
k=j; /＊k记下目前找到的最小关键字所在的位置＊/
if （k！=i） /＊交换R［i]和R［k] ＊/
｛
temp=R［i］；R[i］=R［k];R［k］=temp；
}
printf（" i=%d ”,i)；/*输出每一趟的排序结果*/
for （l=0;l<n；l++）
printf（”％2d”,R［l］。key）;
printf(”\n"）；
｝
｝
int main（）
｛
int i,k，n=10,m=5；
KeyType a[］=｛6，8，7,9，0，1，3，2，4，5｝;
RecType R［MAXE];
for （i=0;i<n；i++）
R[i].key=a[i］;
printf(”\n”）；
printf(" 初始关键字 "）；/*输出初始关键字序列*/
for （k=0；k〈n；k++）
printf（"%2d”，R[k］。key）;
printf(”\n”）；
SelectSort（R，n）；
printf（” 最后结果 ")；/＊输出初始关键字序列＊/
for （k=0；k<n；k++）
printf（”%2d”,R［k］.key）；
printf（”\n\n"）；
system(”pause"）;
｝
4.界面设计
程序包含有多个功能，所以，采用菜单,以方便用户进行功能选择。菜单如下：
1：直接插入排序算法验证
2：快速排序算法验证。
3: 直接选择排序算法验证。
4: 退出

5. 运行、测试与分析
1）直接插入排序算法验证
2） 快速排序算法验证。
3）直接选择排序算法验证.
6. 实验收获及思考
这次实验我对选择拍循序，插入排序，快速排序有了更好的理解，以及时间复杂度的问题分析，通过这次实验，我对排序的内容有了更深入的了解.编程技术有了很大的提高