数据结构试验报告-查找最高分与次高分

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

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

3、)(int)0)1) #defi ne IN_MIN (-IN_MAX-1) con st People MIN=513, IN_MIN; 3. 使用结构体Peoples作为顺序表，存储每个个体 typedef struct People *base; int len gth; Peoples; 三、 算法设计 1. 顺序查找 int search(Peoples *p) People bigger = p-base1; People biggest = p-base1; int n; for(n=1; nbase n.score biggest.score) bigger = biggest

4、; 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-basen.num, biggest .nu m); printf(” 第dA的的分数最大：dn, biggest.num, biggest.score); printf( 第dA的的分数次大：dn, bigger.num, bigg

5、er.score); return 0; 2. 锦标赛查找 (a).每次将最大值选择至树根后调整树 void Adjust(Peoples *p, int x, int n) int l = x * 2; / 左子树 return; if(p-basel. num = p-basex. nu m) 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, le n; Peoples *b;

6、b = (Peoples *)malloc(sizeof(Peoples); len = 1; while(le n n) len base = (People *)malloc(sizeof(People)*le n); b-le ngth = len; for(i=le n/2; ibasei = (i-len/2basei-len/2): (MIN); for(i=le n/2-1; i=1; i-) / 在双亲存放左右最大值 b-basei = max(b-base2 * i, b-base2 * i + 1);int r = l + 1; / if(l = n) /x p-base

7、x = MIN; return; else if(r = n) /x p-basex = p_basel; 右子树 为叶子节点 有左子树，无右子树 for(i=1; ibasei = b-base1; Adjust(b, 1, le n); printf(” 第 dA的的分数最大：dn, a-base1.num, a-base1.score); printf( 第dA的的分数次大：dn, a-base2.num, a-base2.score); free(b); 3 通过无序序列建堆和堆调整得到取得最高分者和次高分者及其分数 (a). 筛选：除p-bases外均满足堆定义，调整 p-bases

8、，将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) 建堆，进行堆调整取得最高分和次高

9、分者，并输出 int i; for(i=(p-length)/2; i0; -i) / HeapAdjust(p, i, p-le ngth); for(i=p-length; i510; -i) / swap(p-base1, p-basei); HeapAdjust(p, 1, i-1); prin tf( 第dA的的分数最大 prin tf( 第dA的的分数次大 从最后一个非叶子节点开始，建立大顶堆 只将最大和次大的得分交换到末尾 :%dn, p-base512.num, p-base512.score); :%dn, p-base511.num, p-base511.score); r

10、eturn 0; 四、运行测试与分析 1.开始运行后，自行产生512个的随机整数作为所有游戏参与者的得分， 并输出所有游戏 参与者（用编号表示）及其得分。 /Yi jPtt .rrrr .nr fTT -/Yr TTJTT -FT rr -frr FT .rr Ar TT -JT ,in TT JTT 人人人人人人人人人人人人人人人人人人人人人人人人 第第第第第第第第第第第 MR 第第第第第第第第第第第 ms習香一 n - -in Hj ,QU .HJ .3J- ,QU .HJ .HJ .Ou ,QU .ITT .TTT1ITT人 人 人 人 人 人 人 人 人 人 人 人 人 人 人 人 人

11、 人 人 人 人 人 0 I u i P I p. Lr I PH Lr ! I ph Lr ! I ! f TrlT*UII B1 0 0 6 0 i 67877659539 靠 沓 暮 蔭習 簷 沓簷 蓮 ;丁 丁 丿 T. . T . _? . T . T . T丁 ；丁 . T. . 丁 丿 丁 丁 .-T. . T ; 丁 . T . 丁. 7 . T. J-J- J_VJ J T T I&M- j * r r - j * r r Jn - /T T JJJ- Jn-irtn Jn I&M n- JFT nff JJ- -n JMj-JTT i 入人人人人人人人人人人

12、人人人人人 79135?9135?91357 112 2 222 3 333 4 44 4 2省略中间部分，余下输出 第第第第第第第第第第第第第第第弟第第第 3输出顺序查找，锦标赛查找，堆排序查找的结果 五、 实验收获与思考 通过本次实验，巩固了关于查找算法的知识， 同时在编程过程中发现了自己的不足， 遇 到了很多语法错误及逻辑错误， 通过不断的调试解决问题，使我对编程有了更加深入的体会 和认识。 顺序查找，锦标赛查找，堆查找的效率及特点： 如果有n个待查找元素，顺序查找每次查找均需进行 n-1次比较，但不需额外存储空间。 锦标赛排序构成的树是满的完全二叉树，深度为 logJ+1，除第一次选择

13、具有最大关键码的 记录需要进行n-1次比较外， 重构树选择具有次小、 再次小关键码记录所需的比较次数均 为O(log2 n)，但这种选择方法虽然减少了许多查找时间， 但是使用了较多的附加存储。 堆查 找的运行时间主要耗费在初始和调整堆时进行的反复筛选上， 堆查找仅需记录一个大小供交 换的辅助存储空间，每个记录仅占有一个存储空间。 六、 源代码 #i nclude #i nclude #in elude #defi ne max(x, y) ( (x.score)(y.score)?(x):(y) #define IN_MAX (int)(unsigned)(int)0)1) #defi ne

14、IN_MIN (-IN_MAX-1) typedef struct int num; int score; People; typedef struct People *base; int len gth; Peoples; con st People MIN=513, IN_MIN; People _; #defi ne swap(x, y) =x; x=y; y=; int ini t_all_people(Peoples *p) int n; sran d(u nsig ned)time(NULL); / 设置每个人的成绩为随机值 for(n=1; nbase n. num = n; p

15、-base n .score = ran d()%1000; p-le ngth = 512; return 0; int copy_people(Peoples *p1. Peoples *p2) int n; for(n=1; nbase n . num = p1-base n . num; p2-base n .score = p1-base n.score; p2-le ngth = p1-le ngth; return 0; int display(Peoples *p) int n; for(n=1; nbasen.num, p-basen.score); if(n%2 = 0)

16、pri ntf(n); return 0; 顺序查找 int search(Peoples *p) People bigger = p-base1; People biggest = p-base1; int n; for(n=1; nbase 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 = big

17、gest.score) int GameSort(Peoples *a, int n) int i, le n; Peoples b; len = 1; while(le n n) len = 1; /le n 为偶数 len = 2 * len; /prin tf(le n:%din,le n); b.base = (People *)malloc(sizeof(People)*le n); b.len gth = len; for(i=le n/2; ile n; i+) / 初始 b.basei = (i-len/2basei-len/2) : (MIN); for(i=le n/2-1

18、; i=1; i-) / 在双亲存放左右最大值 printf(” biggest .nu m); printf( printf( return 0; 第%d人 第dA的的分数最大 第dA的的分数次大 输出后调整 和第%d人的分数一样大n. :%dn, biggest .num, biggest.score); :%dn, bigger.num, bigger.score); /锦标赛排序 int Adjust(Peoples *p, int x, int n) int l = x * 2; / int r = l + 1; / if(l = n) /x p-base x = MIN; retu

19、rn 0; else if(r = n) /x p-basex = p_basel; return 0; if(p-basel. num = p-basex. nu m) Adjust(p, l, n); else Adjust(p, r, n); p-basex = max(p-basel, p-baser); return 0; 左子树 右子树 为叶子节点 有左子树，无右子树 p-base n. num, b.basei = max(b.base2 * i, b.base2 * i + 1); for(i=1; ibasei = b.base1; Adjust(&b, 1, le

20、n); printf( 第 dA的的分数最大：dn, a-base1.num, a-base1.score); printf(” 第dA的的分数次大：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-le ngth)/2; i0; -i) / 从最后一个非叶子节点开始，建立大顶堆 HeapAdjust(p, i, p-le ngth); for(i=p-le ngth; i510; -i) / 只将最大和次大的得分交换到末尾 swap(p-base1, p