free(b);
}
3．通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数
(a).筛选:除p->base[s]外均满足堆定义，调整p->base[s]，将p->base[s,m]建立为大顶堆
int HeapAdjust(Peoples *p, int s, int m){
People rc = p->base[s];
HeapAdjust(p, i, p->length);
}
for(i=p->length; i>510; --i){ //只将最大和次大的得分交换到末尾
swap(p->base[1], p->base[i]);
HeapAdjust(p, 1, i-1);
}
printf("第%d人的的分数最大:%d\n", p->base[512].num, p->base[512].score);
p->base[n].score = rand()%1000;
}
p->length = 512;
return 0;
}
int copy_people(Peoples *p1, Peoples *p2){
int n;
for(n=1; n<=512; n++){
p2->base[n].num = p1->base[n].num;
p2->base[n].score = p1->base[n].score;
}
p2->length = p1->length;
return 0;
}
int display(Peoples *p){
int n;
for(n=1; n<=512; n++){
printf("第%3d个人的分数是%3d ", p->base[n].num, p->base[n].score);
}People;
2．设置MIN表示People数据类型的最小值，用于竞标赛查找
#define IN_MAX (int)(((unsigned)(~((int)0)))>>1)
#define IN_MIN (-IN_MAX-1)
const People MIN={513, IN_MIN};
3．使用结构体Peoples作为顺序表，存储每个个体
printf("第%d人和第%d人的分数一样大\n", p->base[n].num, biggest.num);
}
}
printf("第%d人的的分数最大:%d\n", biggest.num, biggest.score);
printf("第%d人的的分数次大:%d\n", bigger.num, bigger.score);
int j;
for(j=2*s; j<=m; j*=2){
if(j<m && (p->base[j].score < p->base[j+1].score)){
++j; //j指向较大的孩子节点
}
if(!(rc.score < p->base[j].score)){
break;
}
p->base[s] = p->base[j];
#define swap(x, y) { _=x; x=y; y=_; }
int init_all_people(Peoples *p){
int n;
srand((unsigned)time(NULL)); //设置每个人的成绩为随机值
for(n=1; n<=512; n++){
p->base[n].num = n;
return;
}else if(r >= n){ //x有左子树，无右子树
p->base[x] = p->base[l];
return;
}
if(p->base[l].num == p->base[x].num){
Adjust(p, l, n);
}else{
Adjust(p, r, n);
}
p->base[x] = max(p->base[l], p->base[r]);
3．输出顺序查找，锦标赛查找，堆排序查找的结果
五、实验收获与思考
通过本次实验，巩固了关于查找算法的知识，同时在编程过程中发现了自己的不足，遇到了很多语法错误及逻辑错误，通过不断的调试解决问题，使我对编程有了更加深入的体会和认识。
顺序查找，锦标赛查找，堆查找的效率及特点：
如果有n个待查找元素，顺序查找每次查找均需进行n-1次比较，但不需额外存储空间。锦标赛排序构成的树是满的完全二叉树，深度为log2n+1，除第一次选择具有最大关键码的记录需要进行n-1次比较外，重构树选择具有次小、再次小关键码记录所需的比较次数均为O(log2n)，但这种选择方法虽然减少了许多查找时间，但是使用了较多的附加存储。堆查找的运行时间主要耗费在初始和调整堆时进行的反复筛选上，堆查找仅需记录一个大小供交换的辅助存储空间，每个记录仅占有一个存储空间。
return 0;
}
2．锦标赛查找
(a).每次将最大值选择至树根后调整树
void Adjust(Peoples *p, int x, int n) {
int l = x * 2; //左子树
int r = n){ //x为叶子节点
p->base[x] = MIN;
printf("第%d人的的分数次大:%d\n", p->base[511].num, p->base[511].score);
return 0;
}
四、运行测试与分析
1．开始运行后，自行产生512个的随机整数作为所有游戏参与者的得分，并输出所有游戏参与者（用编号表示）及其得分。
2．省略中间部分，余下输出
姓名：
时间：2016.05.05
一、问题描述
有512人参与玩某游戏，从1~512给每个人分配一个编号，每个人的游戏得
分在0~999之间，现要用不同方法查找出游戏参与者的最高分和次高分。要求：
a.自行产生512个的随机整数作为所有游戏参与者的得分。
b.输出所有游戏参与者（用编号表示）及其得分。
c.用顺序查找方法查找出其中取得最高分和次高分者及其分数，并输出。
p->base[x] = p->base[l];
return 0;
}
if(p->base[l].num == p->base[x].num){
Adjust(p, l, n);
}else{
Adjust(p, r, n);
d.锦标赛法查找出其中取得最高分和次高分者及其分数，并输出。
e.通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数，并输出。
f.比较不同方法的查找效率和各自的特点。
二、数据结构设计
1．使用结构体People存储序号和得分，表示个体
typedef struct{
int num;
int score;
if(p->base[n].score > biggest.score){
bigger = biggest;
biggest = p->base[n];
}else if(p->base[n].score > bigger.score){
bigger = p->base[n];
}
if(p->base[n].num != biggest.num && p->base[n].score == biggest.score){
数据结构与程序设计实验
实验报告
课程名称
数据结构与程序设计实验
课程编号
0906550
实验项目名称
查找最高分与次高分
学号
年级
姓名
专业
计算机科学与技术
学生所在学院
计算机学院
指导教师
杨静
实验室名称地点
21B276
哈尔滨工程大学
实验报告六
实验课名称：数据结构与程序设计实验
实验名称：查找最高分与次高分
班级：
学号：
#define IN_MIN (-IN_MAX-1)
typedef struct{
int num;
int score;
}People;
typedef struct{
People *base;
int length;
}Peoples;
const People MIN={513, IN_MIN};
People _;
bigger = biggest;
biggest = p->base[n];
}else if(p->base[n].score > bigger.score){
bigger = p->base[n];
}
if(p->base[n].num != biggest.num && p->base[n].score == biggest.score){
s=j;
}
p->base[s] = rc;
return 0;
}
(b).对p->base[1..512]建堆，进行堆调整取得最高分和次高分者，并输出
int HeapSort(Peoples *p){