lesson10数据的组织结构一排序.ppt

Lesson10数据的组织结构 学习目标 1 了解数组的排序和查找方法 排序问题将一组无序的数列重新排列成非递减或非递增的顺序是一种经常需要的操作 例如 在管理学生成绩的应用程序中 可以用一个数列表示一个班级的学生成绩 并按照从高到低的顺序重新排列 以便确定获得奖学金的学生 例1 假设用户通过键盘输入一个整型数列 请编写一个程序 将其按照从小到大的顺序重新排列 问题分析首先从n个数据中选择一个最小的数据 并将它交换到第1个位置 然后再从后面n 1个数据中选择一个最小的数据 并将它交换到第2个位置 以此类推 直至最后从两个数据中选择一个最小的数据 并将它交换到第n 1个位置为止 整个排序操作结束 算法描述 include defineNUM10 参与排序的数据个数 intmain intdata NUM 存放参与排序的所有整数 inti j minValue temp 通过键盘输入待排序的整型数列 printf nEnter dintegers NUM for i 0 i NUM i scanf d for i 0 i NUM 1 i minValue i for j i 1 j NUM j if data j data minValue minValue j if minValue i 交换 temp data i data i data minValue data minValue temp 输出排序后的结果 printf nOrderinglistis n for i 0 i NUM i printf 5d data i return0 查找问题所谓查找是指根据某个给定的条件 在一组数据中搜索是否存在满足该条件的数据的过程 如果存在 则表示查找成功 给出成功的标志 否则表示查找不成功 给出失败的标志 在程序中 查找操作的结果经常被用来作为是否执行某项后续操作的决策依据 例2 已知某个班级35名学生的某门课程的考试成绩 请编写一个程序 查看在这个班级中是否存在不及格的学生 问题分析用一维数组记录每位学生的考试成绩 下标表示每个学生的编号 元素内容表示考试成绩 查找可以通过从前往后依次查看每个元素内容的过程实现 算法描述 include include include defineNUM35 学生人数 intmain intscore NUM inti srand time 0 用当前时间设置种子 并生成伪随机序列 随机产生35个考试成绩 for i 0 i NUM i rand函数产生一个随机数范围在 0 4294967295 score i rand 100 随机数限定在 0 99 显示35名学生的考试成绩 for i 0 i NUM i printf nNo d d i 1 score i 顺序查找是否存在不及格的学生 for i 0 i NUM i if score i 60 break 输出查找结果 if i NUM printf nNotallpass elseprintf Allpass return0 例3 已知一个按非递减有序排列的整型数列 12 23 30 45 48 50 67 82 91 103 请编写一个程序 查找其中是否存在与给定key相等的数值 问题分析二分查找是指每次用key与位于查找区间中央位置的元素进行比较 比较结果将会产生下面三种情形之一 如果相等 说明查找成功 如果key小于中央位置的元素 说明如果存在这样的元素 应该位于查找区间的前半部分 并在这一半的区间中继续用相同的方式查找 如果key大于中央位置的元素 说明如果存在这样的元素 应该位于查找区间的后半部分 在这一半的区间中继续用相同的方式查找 可以看出 用key与当前查找区间中央位置的元素比较后 不是找到了 就是将查找区间缩小了一半 直到查找区间不存在了 说明没有要找的key 算法描述 include defineNUM10intmain intvalue NUM 12 23 30 45 48 50 67 82 91 103 非递减整型数列 intlow high mid key printf nEnterakey 输入查找的数值 scanf d P122上机练习1P124编程题1