数据结构实验报告-查找最高分与次高分 - 图文

数据结构与程序设计实验

实 验 报 告

课程名称 实验项目名称学号姓名数据结构与程序设计实验 课程编号 0906550 计算机学院查找最高分与次高分 年级专业 计算机科学与技术 学生所在学院 指导教师21B276 杨静 实验室名称地点

哈尔滨工程大学

实验报告六

实验课名称：数据结构与程序设计实验 实验名称：查找最高分与次高分 班级： 学号： 姓名： 时间：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\ } } printf(\第%d人的的分数最大:%d\\n\ printf(\第%d人的的分数次大:%d\\n\ 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 = 2 * len; //printf(\ b->base = (People *)malloc(sizeof(People)*len); b->length = len; for(i=len/2; ibase[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\ printf(\第%d人的的分数次大:%d\\n\ 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\ printf(\第%d人的的分数次大:%d\\n\ return 0; } 四、运行测试与分析 1．开始运行后，自行产生 512 个的随机整数作为所有游戏参与者的得分，并输出所有游戏参与者（用编号表示）及其得分。 2．省略中间部分，余下输出 3．输出顺序查找，锦标赛查找，堆排序查找的结果