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

。数据结构与程序设计实验实 验 报 告课程名称数据结构与程序设计实验课程编号0906550实验项目名称查找最高分与次高分学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学实验报告六实验课名称：数据结构与程序设计实验实验名称：查找最高分与次高分 班级：学号：姓名：时间：2016.05.05一、问题描述有 512 人参与玩某游戏，从 1512 给每个人分配一个编号，每个人的游戏得分在 0999 之间，现要用不同方法查找出游戏参与者的最高分和次高分。要求：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 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-basen; if(p-basen.num != biggest.num & p-basen.score = biggest.score) 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;2锦标赛查找(a). 每次将最大值选择至树根后调整树void Adjust(Peoples *p, int x, int 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); else Adjust(p, r, n); p-basex = max(p-basel, p-baser); (b). 初始树并依次查找最大值与最大值void GameSort(Peoples *a, int n) int i, len; Peoples *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); for(i=1; ibasei = b-base1; Adjust(b, 1, len); 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 basej+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(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;四、运行测试与分析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; 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-length = 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 bigger.score) bigger = p-basen; if(p-basen.num != biggest.num & p-basen.score = biggest.score) 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, 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); else Adjust(p, r, n); p-basex = max(p-basel, p-baser); 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:%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-) /在双亲存放左右最大值 b.basei = max(b.base2 * i, b.base2 * i + 1); for(i=1; ibasei = 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 basej+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); p