第9章 查找最高分与次高分.docxVIP

第九章实验报告1.基本信息实验项目名称：查找最高分与次高分实验类型：综合性实验班级：090615学号：2009061502姓名：丛远东实验日期：7月72.问题描述有512人参与玩某游戏，从1~512给每个人分配一个编号，每个人的游戏得分在0~999之间，现要用不同方法查找出游戏参与者的最高分和次高分。要求：自行产生512个的随机整数作为所有游戏参与者的得分。输出所有游戏参与者（用编号表示）及其得分。用顺序查找方法查找出其中取得最高分和次高分者及其分数，并输出。锦标赛法查找出其中取得最高分和次高分者及其分数，并输出。通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数，并输出。数据输入：无 随机产生数据输出：所有人的最高分和次高分3.数据结构设计 每个人的结构体为：typedefstruct{int no;//编号int grade;//成绩}node;node Person[520];4.算法设计1）使用rand（）函数为每位学生产生随机成绩void Rand(){//产生随机分数 cout开始产生随机分数……endl;srand(time(NULL));//伪随机 加入种子函数for(inti=1;i=512;i++){ Person[i].no=i; Person[i].grade=rand()%1000;}cout随机分数产生完毕！endl;}2)使用顺序法查找最高分与次高分（我理解的次高分为不与最高分相同）首先设置一个较小值t，然后进行一次遍历，只要大于t，则与t进行交换。然后再进行一次遍历，寻找其中的最大值，且不与刚才的最大值相等。void Order(){//顺序查找法查找最高分和次高分 node high1,high2; high1.grade=-1;high1.no=-1; high2.grade=-1;high2.no=-1; for(inti=0;i=512;i++)//进行第一次循环，查询最高分if(Person[i].gradehigh1.grade){ //high2.no=high1.no; //high2.grade=high1.grade; high1.no=Person[i].no; high1.grade=Person[i].grade; } for(inti=0;i=512;i++)//进行第二次循环，查找次高分if(Person[i].gradehigh2.gradePerson[i].grade!=high1.grade){ high2.no=Person[i].no; high2.grade=Person[i].grade; } HIGH=high1.grade;cout最高分的玩家为Person high1.no 得分:high1.gradeendl;cout次高分的玩家为Person high2.no 得分:high2.gradeendl;}3）使用锦标赛法查找出其中取得最高分和次高分?首先把表中的n个人分为n/2个组，每两个相邻人分为一组，对每个组的两个人的分数进行比较，分数高的为优胜者，通过第一轮比较产生n/2个优胜者。同时对失败者进行比较，找出失败者中的最大值。但考虑到我要找的是不同于最高分的最大值，故还要加入判断，判断是否是最大值（我为了节省时间，用到了上次算法的结果，这样做不太好，可以先存储在计算，但是浪费时间和空间。）然后再将这n/2个数据进行重复运算，知道只剩最后一个，则为最高分，同时失败者产生的最高分为次高分，关键代码如下：intlen=512;//每次比较长度node high2; high2.grade=-1;high2.no=-1; for(inti=1;i=9;i++){//进行9次比较……int k=1; for(int j=1;j=len;j=j+2){//寻找每一段的最高分if(p[j].gradep[j+1].grade){p[k].grade=p[j].grade;p[k].no=p[j].no;if(p[j+1].gradehigh2.grade){ high2.no=p[j+1].no; high2.grade=p[j+1].grade; }