数据结构与程序
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
实验
实 验 报 告
课程名称
数据结构与程序设计实验
课程编号
0906550
实验项目名称
查找最高分与次高分
学号
年级
姓名
专业
计算机科学与技术
学生所在学院
计算机学院
指导教师
杨静
实验室名称地点
21B276
哈尔滨工程大学
实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
六
实验课名称:数据结构与程序设计实验
实验名称:查找最高分与次高分
班级:
学号:
姓名:
时间:2016.05.05
一、问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
描述
有 512 人参与玩某游戏,从 1~512 给每个人分配一个编号,每个人的游戏得
分在 0~999 之间,现要用不同方法查找出游戏参与者的最高分和次高分。要求:
a. 自行产生 512 个的随机整数作为所有游戏参与者的得分。
b. 输出所有游戏参与者(用编号表示)及其得分。
c. 用顺序查找方法查找出其中取得最高分和次高分者及其分数,并输出。
d. 锦标赛法查找出其中取得最高分和次高分者及其分数,并输出。
e. 通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数,并输出。
f. 比较不同方法的查找效率和各自的特点。
二、数据结构设计
1.使用结构体People存储序号和得分,表示个体
typedef struct{
int num;
int 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作为顺序表,存储每个个体
typedef struct{
People *base;
int length;
}Peoples;
三、算法设计
1.顺序查找
int search(Peoples *p){
People bigger = p->base[1];
People biggest = p->base[1];
int n;
for(n=1; n<=512; n++){
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){
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);
return 0;
}
2.锦标赛查找
(a). 每次将最大值选择至树根后调整树
void Adjust(Peoples *p, int x, int n) {
int l = x * 2; //左子树
int r = l + 1; //右子树
if(l >= n){ //x为叶子节点
p->base[x] = MIN;
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]);
}
(b). 初始树并依次查找最大值与最大值
void GameSort(Peoples *a, int n) {
int i, len;
Peoples *b;
b = (Peoples *)malloc(sizeof(Peoples));
len = 1;
while(len < n){
len <<= 1; //len为偶数
//printf("len:%d ",len);
}
len = 2 * len;
//printf("len:%d\n",len);
b->base = (People *)malloc(sizeof(People)*len);
b->length = len;
for(i=len/2; i
base[i] = (i-len/2base[i-len/2]) : (MIN);
}
for(i=len/2-1; i>=1; i--){ //在双亲存放左右最大值
b->base[i] = max(b->base[2 * i], b->base[2 * i + 1]);
}
for(i=1; i<=2; i++){ //只调整前两个顺序,依次将树根前置
a->base[i] = b->base[1];
Adjust(b, 1, len);
}
printf("第%d人的的分数最大:%d\n", a->base[1].num, a->base[1].score);
printf("第%d人的的分数次大:%d\n", a->base[2].num, a->base[2].score);
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];
int j;
for(j=2*s; j<=m; j*=2){
if(jbase[j].score < p->base[j+1].score)){
++j; //j指向较大的孩子节点
}
if(!(rc.score < p->base[j].score)){
break;
}
p->base[s] = p->base[j];
s=j;
}
p->base[s] = rc;
return 0;
}
(b). 对p->base[1..512]建堆,进行堆调整取得最高分和次高分者,并输出
int HeapSort(Peoples *p){
int i;
for(i=(p->length)/2; i>0; --i){ //从最后一个非叶子节点开始,建立大顶堆
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);
printf("第%d人的的分数次大:%d\n", p->base[511].num, p->base[511].score);
return 0;
}
四、运行测试与
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
1.开始运行后,自行产生 512 个的随机整数作为所有游戏参与者的得分,并输出所有游戏参与者(用编号表示)及其得分。
2.省略中间部分,余下输出
3.输出顺序查找,锦标赛查找,堆排序查找的结果
五、实验收获与思考
通过本次实验,巩固了关于查找算法的知识,同时在编程过程中发现了自己的不足,遇到了很多语法错误及逻辑错误,通过不断的调试解决问题,使我对编程有了更加深入的体会和认识。
顺序查找,锦标赛查找,堆查找的效率及特点:
如果有n个待查找元素,顺序查找每次查找均需进行n-1次比较,但不需额外存储空间。锦标赛排序构成的树是满的完全二叉树,深度为log2n+1,除第一次选择具有最大关键码的
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
需要进行 n-1 次比较外, 重构树选择具有次小、再次小关键码记录所需的比较次数均为O(log2n),但这种选择方法虽然减少了许多查找时间,但是使用了较多的附加存储。堆查找的运行时间主要耗费在初始和调整堆时进行的反复筛选上,堆查找仅需记录一个大小供交换的辅助存储空间,每个记录仅占有一个存储空间。
六、源代码
#include
#include
#include
#define max(x, y) ( ((x.score)>(y.score)?(x):(y)))
#define IN_MAX (int)(((unsigned)(~((int)0)))>>1)
#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 _;
#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;
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);
if(n%2 == 0) printf("\n");
}
return 0;
}
//顺序查找
int search(Peoples *p){
People bigger = p->base[1];
People biggest = p->base[1];
int n;
for(n=1; n<=512; n++){
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){
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);
return 0;
}
//锦标赛排序 -- 输出后调整
int Adjust(Peoples *p, int x, int n) {
int l = x * 2; //左子树
int r = l + 1; //右子树
if(l >= n){ //x为叶子节点
p->base[x] = MIN;
return 0;
}else if(r >= n){ //x有左子树,无右子树
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);
}
p->base[x] = max(p->base[l], p->base[r]);
return 0;
}
int GameSort(Peoples *a, int n) {
int i, len;
Peoples b;
len = 1;
while(len < n){
len <<= 1; //len为偶数
}
len = 2 * len;
//printf("len:%d\n",len);
b.base = (People *)malloc(sizeof(People)*len);
b.length = len;
for(i=len/2; ibase[i-len/2]) : (MIN);
}
for(i=len/2-1; i>=1; i--){ //在双亲存放左右最大值
b.base[i] = max(b.base[2 * i], b.base[2 * i + 1]);
}
for(i=1; i<=2; i++){ //只调整前两个顺序,依次将树根前置
a->base[i] = b.base[1];
Adjust(&b, 1, len);
}
printf("第%d人的的分数最大:%d\n", a->base[1].num, a->base[1].score);
printf("第%d人的的分数次大:%d\n", a->base[2].num, a->base[2].score);
return 0;
}
/*
* 堆排序--筛选
* 只有p->base[s]不符合规定, 将p->base[s,m]建立为大顶堆
*/
int HeapAdjust(Peoples *p, int s, int m){
People rc = p->base[s];
int j;
for(j=2*s; j<=m; j*=2){
if(jbase[j].score < p->base[j+1].score)){
++j; //j指向较大的孩子节点
}
if(!(rc.score < p->base[j].score)){
break;
}
p->base[s] = p->base[j];
s=j;
}
p->base[s] = rc;
return 0;
}
/*
* 对p->base[1..512]进行堆排序,只将最大和次大交换到末尾
*/
int HeapSort(Peoples *p){
int i;
for(i=(p->length)/2; i>0; --i){ //从最后一个非叶子节点开始,建立大顶堆
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);
printf("第%d人的的分数次大:%d\n", p->base[511].num, p->base[511].score);
return 0;
}
int main(){
Peoples p1;
p1.base = (People *)malloc(sizeof(People)*513);
Peoples p2;
p2.base = (People *)malloc(sizeof(People)*513);
Peoples p3;
p3.base = (People *)malloc(sizeof(People)*513);
init_all_people(&p1);
copy_people(&p1, &p2);
copy_people(&p1, &p3);
display(&p1);
printf("\n顺序查找:\n");
search(&p1);
printf("\n锦标赛查找:\n");
GameSort(&p2, 513);
printf("\n堆排序查找:\n");
HeapSort(&p3);
free(p1.base);
free(p2.base);
free(p3.base);
return 0;
}
教师评分:
教师签字: