04 数组.ppt

第1页：第四讲数组封面

本页为第四讲 数组章节封面，本讲讲解数组的定义与使用，并以挑肥羊、筛法求素数、冒泡排序为例展开。

第2页：挑肥羊问题引入

中秋佳节有贵客来到草原，主人要从羊群中选一只肥羊宴请宾客，当然要选最重者。这样就要记录每只羊的重量，如果有成千上万只羊，不可能用一般变量来记录。

可以用带有下标的变量，也就是这里要讲的数组。问题：哪只羊最重？

第3页：挑肥羊程序示例

#include <stdio.h> void main() { float sheep[10]; float max; int i,k; max = 0.0; for ( i=0; i<10; i=i+1 ) { printf("请输入羊的重量...", i); ... } }

第4页：挑肥羊程序框图

本页以程序框图形式给出挑肥羊算法：依次输入每只羊的重量，与当前最大重量比较，较大者更新最大值并记录其编号。源文件未给出更多文字说明。

第5页：数组的定义

数组的定义形式为 类型说明符 数组名[常量表达式]，例：float sheep[10];、int a2001[1000];

1. 数组名的第一个字符应为英文字母
2. 用方括号将常量表达式括起
3. 常量表达式定义了数组元素的个数

第6页：数组下标与注意事项

4. 数组下标从 0 开始，若定义 5 个元素则为第 0 至第 4 个元素，如 int a[5] 得到 a[0]~a[4] 五个同类型带下标变量
5. 常量表达式中不允许包含变量，例如 int n; n=5; int a[n]; 不合法

第7页：数组的初始化

数组初始化是在定义数组的同时完成赋初值，例如：

int a[5] = { 3, 5, 4, 1, 2 };

等价于 a[0]=3、a[1]=5、a[2]=4、a[3]=1、a[4]=2。

第8页：数组上机实验（一）

//1. #include <stdio.h> void main() { int a[4]; printf("a[0]=%d; a[1]=%d; a[2]=%d; a[3]=%d\n", a[0], a[1], a[2], a[3]); }int a[4] = { 0, 1, 2, 3 };

请自己上机做 6 个实验，观察数组元素的初值情况。

第9页：数组上机实验（二）

• 3. 改变声明项为 int a[4] = { 3, 8 };——初值个数少于元素个数
• 4. 改变声明项为 int a[4] = { 2, 4, 6, 8, 10 };——初值个数多于元素个数
• 5. 改变声明项为 int a[4] = { 2, 4, 6, d };——初值中出现未定义变量
• 6. 改变声明项为 int n=4; int a[n] = { 0, 1, 2, 3 };——用变量定义长度

请上机观察编译与运行结果并分析原因。

第10页：筛法求素数的思路

讨论问题：使用筛法求 100 以内的所有素数。

1. 把 100 个数看作沙子和小石头子，小石头子权称素数，沙子当作非素数，用筛子筛走沙子剩下的就是素数
2. 非素数一定是 2、3、4…… 的倍数
3. 使用数组，让下标就是 100 以内的数，元素值作为筛去与否的标志，筛去后让元素值为 1

第11页：筛法的数学依据

• 单位数：仅有一个数 1
• 素数：大于 1 且只有 1 和它自身两个正因数
• 合数：除 1 和自身外还有其他正因数

1 不是素数，除 1 以外的自然数只有素数与合数。筛法实际上是筛去合数、留下素数。为提高效率，注意：令 n 为合数（这里是 100），c 为 n 的最小正因数，则可据初等数论缩小筛选范围。

第12页：筛法程序框图

本页以程序框图形式给出筛法求素数的流程：prime 数组清零、正因数 d 初始化、循环筛去合数。源文件未给出更多文字说明。

第13页：筛法框图说明与do while

1. 第一块是计数型循环，将 prime 数组清零：prime[c]=0; c=2,3,…,100
2. 第二块把正因数 d 初始化为 d=2
3. 第三块是循环筛数，使用 do while 语句，属于直到型循环

do { 循环体语句块 } while (表达式);

第14页：直到型循环框图

本页给出直到型循环的框图：先执行循环体，再判断表达式，直到表达式为假时才退出循环。

第15页：求π的近似值

例：求 π 的近似值。用变量 pi 表示 π 的值，令括号中的每个项逐项累加，当最后一项的绝对值小于等于给定精度（如 1e-6）时，忽略掉以后的项。

第16页：求π的程序代码

#include <stdio.h> #include <math.h> void main() { int sum; float pi, a, b, c; pi = 0; sum = 0; a = 1.0; b = 1.0; c = 1.0; do { pi = pi + c; sum = sum + 1; a = a + 2.0; b = -b; ... } while (...); }

第17页：求π的运行结果与思考

运行结果：pi = 3.141594，sum = 500001

提问

这种循环当表达式的值永远为真时会如何？答：会构成死循环，即无休止地执行循环体。

请实验：1. 将 b 定义为 int 型看执行结果并分析原因；2. 将 1e-6 变为 1e-7 或 1e-4 看结果。

第18页：while当循环

另一种循环是“当循环”，一般形式为：

while (表达式) { 语句块；(循环体) }

先判断表达式，为真才执行循环体。

第19页：最小公倍数的算法分析

举例：求两个整数的最小公倍数。分析：假定有 x、y 且 x>y，设最小公倍数为 z：

1. z 一定会 >= x
2. z = kx，k = 1,2,…
3. z 一定会被 y 整除

用两个最简单的数试一下即可找到算法，比如 x=5、y=3。

第20页：最小公倍数的求解步骤

1. 第一步 z=x，z % y != 0 不能整除：5，5 % 3 != 0
2. 第二步 z = z + x 不能整除：10，10 % 3 != 0
3. 第三步 z = z + x：15，15 % 3 == 0 能整除，找到了 z，15 就是 5 和 3 的最小公倍数

第21页：最小公倍数参考程序

#include <stdio.h> #include <math.h> void main() { int x, y, z, w; scanf("%d%d", &x, &y); if ( x < y ) { w = x; x = y; y = w; } z = x; while ( z % y != 0 ) { z = z + x; } printf("%d\n", z); }

第22页：三种循环的比较

• 1. for 循环（计数型循环）
• 2. 当型循环（while 循环）
• 3. 直到型循环（do while 循环）

请同学们比较三种循环的异同之处，并上机完成挑肥羊与筛素数的程序，自学与比较。

第23页：冒泡排序问题提出

问题：将几个数从大到小排序并输出，本页介绍冒泡排序法。

第24页：冒泡排序扫描过程

本页以图示方式展示冒泡排序的逐遍扫描与相邻元素交换过程，源文件未给出更多文字说明。

第25页：冒泡排序的扫描规律

从表中可以看出最小的一个数第一遍扫描就交换到 a[6] 中。若将 a[1] 视为水底、a[6] 视为水面：

• 最轻的（最小的）数 1 最先浮到水面，交换到 a[6]
• 次轻的 2 第二遍扫描交换到 a[5]；再轻的 3 第三遍扫描交换到 a[4]
• 6 个数前 5 个数到位需 5 遍扫描，第 6 个最重的数自然落在 a[1] 中，即 j=n-1，n=6

第26页：每遍扫描的比较次数

• 当 j=1 时，i=1,2,…,n-j；n=6 时比较 5 次后 a[6] 得到最小数，之后 a[6] 不必再参与比较
• 第二遍搜索 j=2，i=1,2,3,4，比较 4 次后次小的数到达 a[5]
• 因此 j=3 时 i=1,2,3；j=4 时 i=1,2；j=5 时 i=1

理出上述规律后，程序就不难编了。

第27页：冒泡排序的变量定义

• n——待排序的数的个数，这里 n=6
• j——扫描遍数，j=1,2,…,n-1
• i——第 j 遍扫描待比较元素的下标，i=1,2,…,n-j

第28页：冒泡排序的算法步骤

1. 将待排序的数据放入数组中
2. 置 j 为 1
3. 让 i 从 1 到 n-j，比较 a[i] 与 a[i+1]，若 a[i] >= a[i+1] 位置不动；若 a[i] < a[i+1] 则交换：p=a[i]; a[i]=a[i+1]; a[i+1]=p;，步骤3结束后 a[n-j+1] 中为最小的数
4. 让 j=j+1；只要 j!=n 就返回步骤3，将 a[n-j+1] 的值排好；当 j==n 时执行步骤5
5. 输出排序结果

第29页：冒泡排序参考程序

#include <stdio.h> void main() { int i, j, p, a[7]; for (i=1; i<=6; i=i+1) { printf("请输入待排序的数a[%d]=", i); scanf ("%d", &a[i]); } for ( j=1; j<=5; j=j+1) for ( i=1; i<=6-j; i=i+1 ) { ... } }

采用两重计数型循环完成冒泡排序。

第30页：第四讲结束页

本页为第四讲 数组的结束页，本讲内容至此结束。