《清华大学C++课件8》由会员分享，可在线阅读，更多相关《清华大学C++课件8（52页珍藏版）》请在金锄头文库上搜索。
1、,第五章数据组织、筛选与 排序问题的解题思路,内 容 要 点,数组 筛法 排序 结构与结构数组 二维数组,【任务5.1】 哪只羊最重？,图5.1 【任务5.1】程序框图,#include #include using namespace std; int main() float sheep10; / 数组，用于存每只羊的重量memset ( sheep, 0 , sizeof (sheep) ); / 初始化数组元素为0float bigsheep = 0.0; int i = 0, bigsheepNo = 0; for ( i=0; i sheepi; / 输入第i只羊的重量if ( b
2、igsheep sheepi ) / 如果第i只羊比当前最肥羊重 bigsheep = sheepi; / 第i只羊为当前最肥羊bigsheepNo = i; / 纪录第i只羊的编号cout “最肥羊的重量为“bigsheependl;cout “最肥羊的编号为“bigsheepNoendl;return 0; ,数组是具有相同数据类型且按一定次序排列的一组 变量的集合体。,5.1 数组,例： float sheep10;int a8; / 数值型数组,数组定义： 类型说明符 数组名 常量表达式 ,说明： 1. 用方括号 将常量表达式括起，常量表达式定义了数组元素的个数，不允许包含变量。 2.
3、 数组下标从 0 开始。 3. 声明中使用a8 和 执行语句中使用a8 的意义截然不同！,4. 系统不检查数组下标，要注意数组下标是否超出定义范围！,第一种方法：声明时直接初始化例：int a5 = 3, 5, 4, 1, 2 ;第二种方法：使用 memset 函数格式：memset ( 数组名, 初始化值, sizeof (数组名) );例：memset ( sheep, 0, sizeof ( sheep ) );含义：将数组sheep中的全部元素均初始化为 0 ，调用此库函数需加入头文件 。,数组初始化：,2. 其他不变，改变声明项为：int a4 = 0, 1, 2, 3 ;,上机练习
4、：,1. #include using namespace std;int main()int a4; / 声明项cout a0 endl;cout a1 endl;cout a2 endl;cout a3 endl;return 0;,3. 其他不变，改变声明项为：int a4 = 3, 8 ;4. 其他不变，改变声明项为：int a = 3, 8, 9, 22, 27, 36 ;5. 其他不变，改变声明项为：int a4 = 2, 4, 6, 8, 10 ;6. 其他不变，改变声明项为：int a4 = 2, 4, 6, d ;7. 其他不变，改变声明项为：int d;int a4 = 2
5、, 4, 6, d ;8. 其他不变，改变声明项为：int n=4;int an = 0, 1, 2, 3 ;,一维数组示例(1),输入一个含有10个浮点数的一维数组，分别计算数组中所有正数与所有负数的和,数组元素的遍历：使用循环，从头至尾搜索整个数组for (i = 0; i datai;for(i = 0; i 0.0) result1 += datai; else result2 += datai;cout“正数之和为“result1endl;cout“负数之和为“result2endl;,一维数组示例(2),对6个整数按从大到小的顺序排列,int a6 = 1, 8, 3, 2, 4,
6、 9 ;,5.3 冒泡排序法 (bubble sort),i=0 i=1 i=2 i=3 i=4 i=5,a0 a1 a2 a3 a4 a5,初始值 1 8 3 2 4 9,i=0 i=1 i=2 i=3 i=4 i=5,a0 a1 a2 a3 a4 a5,中间结果 8 3 4 9 2 1,扫描遍数： 第一遍扫描：最小的数交换到 a5 中； 第二遍扫描：次小的数交换到 a4 中； 依此类推：有6 个数，前 5 个数到位需 5 遍扫描，第 6 个数自然落在 a0 中。 扫描遍数为 j , j = n-1, n=6,冒泡排序(bubble sort)算法分析：,每遍扫描中相邻元素的比较次数：j =
7、 1，比较 5 次j = 2，比较 4 次j = 5，比较 1 次比较次数为 n - j,int i, j, temp;int a6 = 1, 8, 3, 2, 4, 9;for ( j = 1; j = 5; j+ ) / j为扫描遍数for ( i = 0; i 6 - j; i+ )if ( ai ai+1 ) / 若后面数据比前面大则交换 temp = ai; ai = ai+1; ai+1 = temp;for ( j = 0; j 6; j+ ) cout“a“j“ = “aj ai; for ( j=1; j=5; j+) for ( i=1; i=6-j; i+ ) if (
8、ai ai+1 ) p = ai; ai = ai+1; ai+1 = p; for ( i=1; i=6; i+) cout ai endl; ,关于冒泡排序算法的思考：,for( j = 1; j = 5; j+ ) / j为扫描遍数for( i = 0; i 6 j; i+ )if ( a i a i+1 ) / 若后面数据比前面大则交换 temp = a i ; a i = a i+1 ; a i+1 = temp;,1。for(j = 0; j 5; j+) i 做哪些改动？,2。排序改为 由小到大?,3。如果排序前已整序或接近整序，如何使循环次数减少？,4。还能改进吗? 比如减少交
9、换次数?,shaker sort,排序与搜索：,在计算机科学中，可能没有其它任务比排序和 搜索更为基础而且被分析得更为透彻。,数据库程序 编译程序 解释程序 操作系统 ,排序是为了更方便、更快速地搜索。,对数组排序的方法可分为三类：交换 选择 插入,评价排序算法的一般指标： 平均情况下的速度 最好和最坏情况下的速度 算法是否正态 ,速度：用比较与交换次数来表征指数量级 对数量级,平均情况下速度快的算法往往在最坏情况下表现很差。,选择排序（由小到大）,step1 step2 step3 step4,a0 a1 a2 a3 a4,1和6交换,不用交换,不用交换,5和6交换,已排好序,按最终顺序依次
10、找到每个元素，把它与当前占据这一 位置的元素交换。,快速排序qsort 基于交换排序 nlogn,思路： 1、将待排序的数据放入数组 a 中，下标从 z 到 y ； 2、取 a z 放入变量 k 中，通过分区处理，为 k 选择应该排定的位置。将比 k 大的数放右边，比 k 小的数放左边。当 k 到达最终位置后，由 k 划分左右两个集合。再用同样的思路处理左集合与右集合。,z ykz m-1 m m+1 y,数组a,shell排序 基于插入排序 n1.2,一维数组示例(3),5.2 筛 法,【任务5.2】求 100 以内的所有素数,试商判别法,素数查找的埃拉托色尼(厄拉多塞)筛法 公元前三世纪，
11、希腊天文学家 Eratosthenes 发明了一种算法，用来找出某一范围内的全部素数 算法过程：首先写出从 2 到 n 的整数，假设 n = 20,将第一个数圈起，表明已发现了一个素数，并将数列中所有该素数的倍数打上，因为它们一定不是素数,重复上述步骤，直到所有整数或者被圈起或者打上叉,思路： 把素数看作小石头，把非素数看作沙子，用筛子筛去沙子。 使用数组，下标就是 0 100 的数，数组元素的值作为筛去 与否的标志：0 石头 - 素数 保留1 沙子 - 非素数 筛去,图5.2 【任务5.2】程序框图,关 于 素 数,素数是上帝用来描写宇宙的文字（伽利略语）,求素数的常用方法：试商判别法筛法,
12、1。区间素数求区间 a, b 上的所有素数,2。梅森尼数 ( Mersenne Prime )形如 2n-1 的素数例如：22-1=3, 23-1=7 231 1 = 2147483647,3。孪生素数相差为 2 的两个素数例如：3 与 5 11 与 13 17 与 19 ,4。可逆素数一个素数的逆序仍是素数例如：37 73 可逆素数对1193 1399 1913 1933 3319 ,5。金蝉素数对于素数k，从低位去掉1位,2位,或3位后仍是素数； 从高位去掉1位,2位,或3位后仍是素数；同时去掉最低位 与最高位后仍是素数，则k为金蝉素数。例如：373 3137 3797,关 于 合 数,合
13、数世纪：一个世纪的100个年号全为合数 21, 200000区间中最早出现的合数世纪是16719世纪！,最小的连续n个合数 最小的100个连续合数区间为 370262, 370361 ,有一排 21 盏触摸型灯泡，编号由1至21，全是关灯 状态。第一次摸触开灯，第二次触摸关灯，第三次又开 灯，依此类推。班上有21位同学，座号由1号到21号，1号同学摸触 的灯号是1的倍数，2号同学摸触的灯号是2的倍数，3号 同学摸触的灯号是3的倍数，依此类推。等到大家完成 后，哪些灯是亮着的呢？如果有200盏触摸型灯泡，编号由1至200。有200位 同学，座号由1到200号，依上述规则，最后哪些灯是亮 着的呢？,有趣的例子：开灯？关灯？,【任务5.3】 测量湖泊水深,5.5 二维数组,
