数据结构实验报告

1、。数据结构与程序设计实验实验报告课程名称数据结构与程序设计实验课程编号0906550实验项目名称查找最高分与次高分学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学。1。实验报告六实验课名称：数据结构与程序设计实验实验名称：查找最高分与次高分班级： 学号： 姓名： 时间：一、问题描述有 512 人参与玩某游戏，从 1512 给每个人分配一个编号，每个人的游戏得分在 0999 之间，现要用不同方法查找出游戏参与者的最高分和次高分。要求：a.自行产生512个的随机整数作为所有游戏参与者的得分。b. 输出所有游戏参与者（用编号表示）及其得分。c

2、. 用顺序查找方法查找出其中取得最高分和次高分者及其分数，并输出。d. 锦标赛法查找出其中取得最高分和次高分者及其分数，并输出。e. 通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数，并输出。f. 比较不同方法的查找效率和各自的特点。二、数据结构设计1使用结构体People 存储序号和得分，表示个体typedef structint num;int score;People;2设置 MIN表示 People 数据类型的最小值，用于竞标赛查找#define IN_MAX (int)(unsigned)(int)0)1)#define IN_MIN (-IN_MAX-1)const Pe

3、ople MIN=513, IN_MIN;3使用结构体Peoples 作为顺序表，存储每个个体typedef structPeople *base;int length;Peoples;三、算法设计1顺序查找int search(Peoples *p)People bigger = p-base1;People biggest = p-base1;int n;for(n=1; nbasen.score biggest.score)bigger = biggest;biggest = p-basen;else if(p-basen.score bigger.score)bigger = p-ba

4、sen;if(p-basen.num != biggest.num & p-basen.score = biggest.score)printf(第 %d 人 和 第 %d 人 的 分 数 一 样 大 n,p-basen.num,biggest.num);。2。printf(第 %d人的的分数最大:%dn, biggest.num, biggest.score);printf(第 %d人的的分数次大:%dn, bigger.num, bigger.score);return 0;2锦标赛查找(a).每次将最大值选择至树根后调整树void Adjust(Peoples *p, int x, in

5、t n) int l = x * 2; /左子树int r = l + 1; /右子树if(l = n) /x为叶子节点p-basex = MIN;return;else if(r = n) /x有左子树，无右子树p-basex = p-basel;return;if(p-basel.num = p-basex.num)Adjust(p, l, n);elseAdjust(p, r, n);p-basex = max(p-basel, p-baser);(b).初始树并依次查找最大值与最大值void GameSort(Peoples *a, int n) int i, len;Peoples

6、*b;b = (Peoples *)malloc(sizeof(Peoples);len = 1;while(len n)len base = (People *)malloc(sizeof(People)*len);b-length = len;for(i=len/2; ibasei = (i-len/2basei-len/2) : (MIN);for(i=len/2-1; i=1; i-) /在双亲存放左右最大值b-basei = max(b-base2 * i, b-base2 * i + 1);。3。for(i=1; ibasei = b-base1;Adjust(b, 1, len)

7、;printf(第 %d人的的分数最大:%dn, a-base1.num, a-base1.score);printf(第 %d人的的分数次大:%dn, a-base2.num, a-base2.score);free(b);3通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数(a).筛选 :除 p-bases外均满足堆定义，调整p-bases，将 p-bases,m建立为大顶堆int HeapAdjust(Peoples *p, int s, int m)People rc = p-bases;int j;for(j=2*s; j=m; j*=2)if(jbasej.score ba

8、sej+1.score)+j; /j指向较大的孩子节点if(!(rc.score basej.score)break;p-bases = p-basej;s=j;p-bases = rc;return 0;(b). 对 p-base1.512 建堆，进行堆调整取得最高分和次高分者，并输出 int HeapSort(Peoples *p)int i;for(i=(p-length)/2; i0; -i) / 从最后一个非叶子节点开始，建立大顶堆 HeapAdjust(p, i, p-length);for(i=p-length; i510; -i) / 只将最大和次大的得分交换到末尾 swap(

9、p-base1, p-basei);HeapAdjust(p, 1, i-1);printf(第 %d人的的分数最大:%dn, p-base512.num, p-base512.score);printf(第 %d人的的分数次大:%dn, p-base511.num, p-base511.score);return 0;四、运行测试与分析。4。1开始运行后， 自行产生 512个的随机整数作为所有游戏参与者的得分，并输出所有游戏参与者（用编号表示）及其得分。2省略中间部分，余下输出3输出顺序查找，锦标赛查找，堆排序查找的结果。5。五、实验收获与思考通过本次实验， 巩固了关于查找算法的知识，同时在

10、编程过程中发现了自己的不足，遇到了很多语法错误及逻辑错误，通过不断的调试解决问题，使我对编程有了更加深入的体会和认识。顺序查找，锦标赛查找，堆查找的效率及特点：如果有 n 个待查找元素， 顺序查找每次查找均需进行n-1 次比较，但不需额外存储空间。锦标赛排序构成的树是满的完全二叉树，深度为logn2 +1，除第一次选择具有最大关键码的记录需要进行 n-1 次比较外，重构树选择具有次小、再次小关键码记录所需的比较次数均为 O(log2 n) ，但这种选择方法虽然减少了许多查找时间，但是使用了较多的附加存储。堆查找的运行时间主要耗费在初始和调整堆时进行的反复筛选上，堆查找仅需记录一个大小供交换的辅

11、助存储空间，每个记录仅占有一个存储空间。六、源代码#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 structint num;int score;People;typedef structPeople *base;int length;Peoples;const People MIN=513, IN_MIN;People _;#define swap(x

12、, y) _=x; x=y; y=_; 。6。int init_all_people(Peoples *p)int n;srand(unsigned)time(NULL); / 设置每个人的成绩为随机值 for(n=1; nbasen.num = n;p-basen.score = rand()%1000;p-length = 512;return 0;int copy_people(Peoples *p1, Peoples *p2)int n;for(n=1; nbasen.num = p1-basen.num;p2-basen.score = p1-basen.score;p2-lengt

13、h = p1-length;return 0;int display(Peoples *p)int n;for(n=1; nbasen.num, p-basen.score); if(n%2 = 0) printf(n);return 0;/ 顺序查找int search(Peoples *p)People bigger = p-base1;People biggest = p-base1;int n;for(n=1; nbasen.score biggest.score)bigger = biggest;biggest = p-basen;else if(p-basen.score bigg

14、er.score)bigger = p-basen;if(p-basen.num != biggest.num & p-basen.score = biggest.score)。7。printf(第 %d 人 和 第 %d 人 的 分 数 一 样 大 n,p-basen.num,biggest.num);printf(第 %d人的的分数最大:%dn, biggest.num, biggest.score);printf(第 %d人的的分数次大:%dn, bigger.num, bigger.score);return 0;/ 锦标赛排序 - 输出后调整int Adjust(Peoples *p

15、, int x, int n) int l = x * 2; /左子树int r = l + 1; /右子树if(l = n) /x为叶子节点p-basex = MIN;return 0;else if(r = n) /x有左子树，无右子树p-basex = p-basel;return 0;if(p-basel.num = p-basex.num)Adjust(p, l, n);elseAdjust(p, r, n);p-basex = max(p-basel, p-baser);return 0;int GameSort(Peoples *a, int n) int i, len;Peop

16、les b;len = 1;while(len n)len = 1; /len为偶数len = 2 * len;/printf(len:%dn,len);b.base = (People *)malloc(sizeof(People)*len);b.length = len;for(i=len/2; ilen; i+) /初始b.basei = (i-len/2basei-len/2) : (MIN);for(i=len/2-1; i=1; i-) /在双亲存放左右最大值。8。b.basei = max(b.base2 * i, b.base2 * i + 1);for(i=1; ibasei

17、 = b.base1;Adjust(&b, 1, len);printf(第 %d人的的分数最大:%dn, a-base1.num, a-base1.score);printf(第 %d人的的分数次大:%dn, a-base2.num, a-base2.score);return 0;/* 堆排序 - 筛选* 只有 p-bases 不符合规定 , 将 p-bases,m 建立为大顶堆*/int HeapAdjust(Peoples *p, int s, int m)People rc = p-bases;int j;for(j=2*s; j=m; j*=2)if(jbasej.score ba

18、sej+1.score)+j; /j指向较大的孩子节点if(!(rc.score basej.score)break;p-bases = p-basej;s=j;p-bases = rc;return 0;/* 对 p-base1.512 进行堆排序 , 只将最大和次大交换到末尾*/int HeapSort(Peoples *p)int i;for(i=(p-length)/2; i0; -i) / 从最后一个非叶子节点开始，建立大顶堆 HeapAdjust(p, i, p-length);for(i=p-length; i510; -i) / 只将最大和次大的得分交换到末尾 swap(p-base1, p-basei);HeapAdjust(p, 1, i-1);