简单数组 程序设计导论. 2 学习目标 数组的概念、定义和初始化 数组的概念、定义和初始化 二维数组 二维数组 数组的排序问题 数组的排序问题 筛法求素数 筛法求素数.

Presentation on theme: "简单数组 程序设计导论. 2 学习目标 数组的概念、定义和初始化 数组的概念、定义和初始化 二维数组 二维数组 数组的排序问题 数组的排序问题 筛法求素数 筛法求素数."— Presentation transcript:

1 简单数组 程序设计导论

2 2 学习目标 数组的概念、定义和初始化 数组的概念、定义和初始化 二维数组 二维数组 数组的排序问题 数组的排序问题 筛法求素数 筛法求素数

3 3 数组 一组类型相同的数据（变量） 一组类型相同的数据（变量） 方便对一组数据进行命名和访问 方便对一组数据进行命名和访问 数组名 + 下标 唯一确定数组中的一个元素 数组名 + 下标 唯一确定数组中的一个元素 通过数组名 + 下标可以访问数组中的任意元素 通过数组名 + 下标可以访问数组中的任意元素 应用： 应用： 对一组数求最值、平均值 对一组数求最值、平均值 对一组数据排序 对一组数据排序 …… ……

4 4 1.1 一维数组的定义 定义形式： 定义形式： 类型说明符数组名 [ 常量表达式 ] 例： 例： float sheep[10]; int a2001[1000]; 说明 说明 1. 数组名的第一个字符应为英文字母； 2. 用方括号将常量表达式括起； 3. 常量表达式定义了数组元素的个数； 4. 数组的下标从 0 开始，如果定义了 5 个元素，是从第 0 个元素到第 4 个元素 数组的下标从 0 开始，如果定义了 5 个元素，是从第 0 个元素到第 4 个元素 数组的下标从 0 开始，如果定义了 5 个元素，是从第 0 个元素到第 4 个元素 5. 常量表达式中不允许含有变量 常量表达式中不允许含有变量

5 5 例如： int a[5] 定义了 5 个数组元素如下 ： a[0], a[1], a[2], a[3], a[4] 这是 5 个带下标的变量，这 5 个变量的类型是相同的

6 6 例如 int n; n = 5; n = 5; int a[n]; 不合法！ 因为 n 是变量，不是常量 #define N 100 #define M 200 int a[ N ] ; long b[ N + M ] ; double g[ M + 6 ] ; 以上定义是合法的

7 7 1.2 数组初始化 声明的时候初始化 声明的时候初始化 使用 memset 函数 使用 memset 函数

8 8 直接声明时初始化例如 int a[5] = { 3, 5, 4, 1, 2 }; a[0] = 3; a[1] = 5; a[2] = 4; a[3] = 1; a[4] = 2;

9 9 1.2 数组元素的访问 访问一维数组中元素的形式： 访问一维数组中元素的形式： 数组名 [ 下标 ] 例如： 例如： a[0] = a[1] + a[2] ; a[0] = a[1] + a[2] ; 其中： 其中： 下标写在一个方括号中； 下标写在一个方括号中； 下标是整型表达式，如果为浮点型数据， C 截去小数部 分，自动取整。 下标是整型表达式，如果为浮点型数据， C 截去小数部 分，自动取整。 引用时下标不能超界，否则编译程序检查不出错误， 但执行时出现不可知结果。 引用时下标不能超界，否则编译程序检查不出错误， 但执行时出现不可知结果。

10 10 一维数组的访问 // List A of n integer elements has already been set int i; for (i=0;i<n;i++) printf(“%d “, A[i]); printf(“\n”);

11 11 程序举例：哪只羊最重？ 中秋佳节，有贵客来到草原，主人要 从羊群中选一只肥羊宴请宾客，当然要选最 重者。 这样就要记录每只羊的重量，如果有 成千上万只羊，不可能用一般变量来记录。 可以用带有下标的变量，也就是这里要讲的 数组。 我们先看例子：用键盘输入 10 只羊的重量存放到 一个名为 sheep 的数组中

12 12

13 13 //************************************ //* 程序名： 5_1.cpp （数组示例） * //* 作 者： wuwh * //* 编制时间： 2002 年 9 月 20 日 * //* 主要功能：找出最重的羊 * //************************************ #include // 预编译命令 int main()// 主函数 { float sheep[10];// 数组，有 10 个浮点类型元素， // 用于存 10 只羊每一只的重量 float bigsheep=0.0;// 浮点类型变量，存放最肥羊的重量 int i=0, bigsheepNo=0;// 整型变量， i 用于计数循环， // bigsheepNo 用于记录最肥羊的号

14 14 memset ( sheep, 0, sizeof (sheep) );// 初始化数组元素为 0 memset ( sheep, 0, sizeof (sheep) );// 初始化数组元素为 0 for ( i=0; i<10; i=i+1 )// 计数循环 {// 循环，开始 printf(" 请输入羊的重量 sheep[%d]=", i);; // 提示用 scanf("%d", &sheep[i]);// 输入第 i 只羊的重量 if ( bigsheep < sheep[i] )// 如果第 i 只羊比当前最肥羊大 { bigsheep = sheep[i];// 让第 i 只羊为当前最肥羊 bigsheepNo = i;// 纪录第 i 只羊的编号 } } // 循环结束 // 输出最肥羊的重量 printf(" 最肥羊的重量为 %d\n", bigsheep); printf(" 最肥羊的重量为 %d\n", bigsheep); // 输出该羊的编号 printf(" 最肥羊的编号为 %d\n", bigsheepNo); printf(" 最肥羊的编号为 %d\n", bigsheepNo); return 0; return 0;}

15 15 使用 memset 函数 格式为 memset( 数组名, 初始化值, sizeof( 数组名 )) 举例： memset(sheep, 0, sizeof( sheep )); 含义是将名为 sheep 的数组中的全部元素均初 始化为 0 。更深一层是说让系统为 sheep[10] 所 分配的内存单元从 sheep[0] 为标志的地址单元 到该数组的全部地址单元都赋以 0 。调用此库 函数需要加入头文件 。

16 16  1 #include  1 #include int main() { int a[4];// 声明项 int i=0; for(i=0; i<4; i++) printf("%d\n", a[i]); return 0; }  2. 其他不变，改变声明项为 int a[4] = { 0, 1, 2, 3 }; 请自己上机做 7 个实验

17 17  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 d; int d; int a[4] = { 2, 4, 6, d };  7. 其他不变，改变声明项为 int n=4; int a[n] = { 0, 1, 2, 3 };

18 18 练习 1. 给定一组整数，找到其中最小的整数，并 按照输入的逆序输出这组整数 1. 给定一组整数，找到其中最小的整数，并 按照输入的逆序输出这组整数 2. 用数组的方式来处理 Fibonacci 数列问题 2. 用数组的方式来处理 Fibonacci 数列问题

19 19 2 二维数组的概念及其定义 当一维数组的每个元素是一个一维数组时， 就构成了二维数组。二维数组与数学中的 矩阵概念相对应。 当一维数组的每个元素是一个一维数组时， 就构成了二维数组。二维数组与数学中的 矩阵概念相对应。 age[0] age[1] age[2] 17 19 20 18 21 23 16 18 19 22 21 23 20 16 18 17 19 20 18 21 23 16 18 19 22 21 23 20 16 18 一维数组二维数组 矩阵

20 20 2.1 二维数组的定义 二维数组的一般定义形式： 二维数组的一般定义形式： 类型标识符 数组名 [ 常量表达式 1 ] [ 常量表达式 2] 其中： 其中： 类型标识符：数组中每个元素的数据类型。可以 是 C 语言中所有的数据类型。 类型标识符：数组中每个元素的数据类型。可以 是 C 语言中所有的数据类型。 数组名：合法的标识符，数组名就是变量名。 数组名：合法的标识符，数组名就是变量名。 常量表达式 1 ：又称行下标，指出二维数组中一 维数组元素的个数。 常量表达式 1 ：又称行下标，指出二维数组中一 维数组元素的个数。 常量表达式 2 ：又称行列标，表明每个一维数组 中的元素个数。 常量表达式 2 ：又称行列标，表明每个一维数组 中的元素个数。

21 21 多维数组的定义 二维数组的每一个元素又是相同的类型的 一维数，就构成了三维数组， …… 依此类 推，就可构成四维或更多维的数组。 二维数组的每一个元素又是相同的类型的 一维数，就构成了三维数组， …… 依此类 推，就可构成四维或更多维的数组。 n 维数组的一般定义形式： n 维数组的一般定义形式： 类型标识符 数组名 [ 常量表达式 1] [ 常量表达式 2] …… [ 常量表达式 n] 其中：各参数的说明与二维数组相同。 其中：各参数的说明与二维数组相同。

22 22 三维数组的排列顺序 说明一个三维数组： 说明一个三维数组： int a[2][3][2]; 12 个元素在内存中排列顺 序如右图： 12 个元素在内存中排列顺 序如右图： a[0][0][0] a[0][0][1] a[0][1][0] a[0][1][1] a[0][2][0] a[0][2][1] a[1][0][0] a[1][0][1] a[1][1][0] a[1][1][1] a[1][2][0] a[1][2][1]

23 23 计算多维数组中元素位置的公式 一个 m×n 的二维数组 a ，其中 a[i][j] 在数组中 的位置为： 一个 m×n 的二维数组 a ，其中 a[i][j] 在数组中 的位置为： i ×n ＋ j ＋ 1 一个 m×n×u 的三维数组 a ，其中 a[i][j][k] 在数 组中的位置为： 一个 m×n×u 的三维数组 a ，其中 a[i][j][k] 在数 组中的位置为： i×n×u ＋ j×n ＋ k ＋ 1

24 24 2.2 访问二维数组和多维数组 访问二维数组中元素的形式： 访问二维数组中元素的形式： 数组名 [ 下标 ][ 下标 ] 其中： 其中： 每一个下标写在一个方括号中； 每一个下标写在一个方括号中； 下标是整型表达式，如果为浮点型数据， C 截 去小数部分，自动取整。 下标是整型表达式，如果为浮点型数据， C 截 去小数部分，自动取整。 引用时下标不能超界，否则编译程序检查不出 错误，但执行时出现不可知结果。 引用时下标不能超界，否则编译程序检查不出 错误，但执行时出现不可知结果。

25 25 多维数组的遍历 遍历多维数组元素的最好算法就是利用嵌 套循环 遍历多维数组元素的最好算法就是利用嵌 套循环 一般的结构是： 一般的结构是： for( i = 0; i <  ; i++ ) for( j = 0; j <  ; j++ ) for( j = 0; j <  ; j++ ) for( k = 0; k <  ; k++ ) for( k = 0; k <  ; k++ )

26 26 二维数组和多维数组的初始化 二维数组和多维数组都可以初始化，与一 维数组初始化的差别是由于维数增多，初 始化时特别注意元素的排列顺序。 二维数组和多维数组都可以初始化，与一 维数组初始化的差别是由于维数增多，初 始化时特别注意元素的排列顺序。 例二维数组的初始化 例二维数组的初始化 int i[2][3]={{1,2,3},{4,5,6}}; 或写成 int i={ {1,2,3}, {4,5,6}}; {4,5,6}};或写成 int i[2][3]={1,2,3,4,5,6};

27 27 省略部分内容的二维数组初始化 初始化从第一个元素起连续的部分元素： 初始化从第一个元素起连续的部分元素： int i[2][3]={1,2,3,4}; 省略第一个维数（不能省略第二下标）： 省略第一个维数（不能省略第二下标）： int i[ ][3]={1,2,3,4,5,6};

28 28 三维数组的初始化 例： 例： int a[2][3][4]={ {{ 1, 2, 3, 4},{ 5, 6, 7, 8},{ 9, 10,11,12}} {{13,14,15,16},{17,18,19,20},{21,22,23,24}} }; };或 int a[2][3][4]={1,2,3,4,5,6,7,8,9,10,11,12,13, 14,15,16,17,18,19,20,21,22,23,24};

29 29 程序举例 有 n 个学生，每个学生学 m 门课，已知所 有学生的各门课的成绩，分别求每门课 的平均成绩和每个学生的平均成绩。设 各学生成绩如下： 有 n 个学生，每个学生学 m 门课，已知所 有学生的各门课的成绩，分别求每门课 的平均成绩和每个学生的平均成绩。设 各学生成绩如下：

30 30 解题思路 学生成绩是一张二维表，可按每一行为一 个学生的成绩，每一列是一门的成绩，存 储成绩表在二维数组中。 学生成绩是一张二维表，可按每一行为一 个学生的成绩，每一列是一门的成绩，存 储成绩表在二维数组中。 求每门课的平均成绩 求每门课的平均成绩 二维数组每列数据之和 / 学生人数 二维数组每列数据之和 / 学生人数 求每个学生的平均成时： 求每个学生的平均成时： 二维数组每行数据之和 / 课程数 二维数组每行数据之和 / 课程数

31 31 排序问题 将数组元素按照一定的顺序重新排列 将数组元素按照一定的顺序重新排列 例如：将几个数从大到小排序并输出 例如：将几个数从大到小排序并输出 a 1 8 3 2 4 9 a 1 8 3 2 4 9 下标 1 2 3 4 5 6 下标 1 2 3 4 5 6 希望从大到小排成： a 9 8 4 3 2 1 a 9 8 4 3 2 1 下标 1 2 3 4 5 6 下标 1 2 3 4 5 6

32 32 排序方法 选择排序 选择排序 插入排序 插入排序 冒泡排序 冒泡排序 …… ……

33 33 选择排序 从所有元素中选择一个最小元素放在 a[0] （即让最小元素 a[p] 与 a[0] 交换），作为第一 轮；第二轮是从 a[1] 开始到最后的各元素中 选择一个最小元素，放在 a[1] 中 … ；以下依 此类推。 n 个数要进行 (n-1) 轮。在第一轮中 要比较 (n-1) 次，第二轮中比较 (n-2) 次， … ， 第 i 轮中比较 (n-i) 次。但在每一轮中只进行一 次数据交换 从所有元素中选择一个最小元素放在 a[0] （即让最小元素 a[p] 与 a[0] 交换），作为第一 轮；第二轮是从 a[1] 开始到最后的各元素中 选择一个最小元素，放在 a[1] 中 … ；以下依 此类推。 n 个数要进行 (n-1) 轮。在第一轮中 要比较 (n-1) 次，第二轮中比较 (n-2) 次， … ， 第 i 轮中比较 (n-i) 次。但在每一轮中只进行一 次数据交换

34 冒泡算法图示

35 35

36 36

37 37 冒泡算法分析 从表中可以看出最小的一个数第一遍扫描就交换到 a[6] 中。 如果将 a[1] 视为水底， a[6] 视为水面：  最轻的 ( 最小的 ) 一个数 1 最先浮到水面，交换到 a[6];  次轻的 2 第二遍扫描交换到 a[5] ；  再轻的 3 第三遍扫描交换到 a[4] ； … 依此类推，有 6 个数，前 5 个数到位需 5 遍扫描，第 6 个最 重的数自然落在 a[1] 中。因此， 6 个数只需 5 遍扫描，即 j=n-1, n=6 。

38 38 再看在每遍扫描中，相邻两数组元素的比较次数。  当 j=1 时， i=1,2, …,n-j 。 n=6 时，比较 5 次之后 a[6] 中有一 个最小数到达，这时 a[6] 不必再参与比较了。  因此在第二遍搜索时， j=2, i=1,2, …,n-j ，即 i=1,2,3,4 。 比较 4 次之后次小的一个数到达了 a[5] 。这时 a[5] 不必再 参与比较了。  因此， j=3 时， i=1,2,3 ； j=4 时， i=1,2 ； j=5 时， i=1 。 理出上述规律后，程序就不难编了

39 39 冒泡排序算法设计 为了表述方便，定义以下 3 个变量： 为了表述方便，定义以下 3 个变量： n —— 待排序的数的个数，这里 n=6 n —— 待排序的数的个数，这里 n=6 j —— 扫描遍数， j=1,2, …,n-1 j —— 扫描遍数， j=1,2, …,n-1 i —— 第 j 遍扫描待比较元素的下标， i=1,2, …,n-j i —— 第 j 遍扫描待比较元素的下标， i=1,2, …,n-j

40 40 采用两重计数型循环，步骤如下 ：  步骤 1 ：将待排序的数据放入数组中；  步骤 2 ：置 j 为 1 ；  步骤 3 ： 让 i 从 1 到 n-j ，比较 a[i] 与 a[i+1] ， 如果 a[i] >= a[i+1] ，位置不动； 如果 a[i] >= a[i+1] ，位置不动； 如果 a[i] < a[i+1] ，位置交换。 如果 a[i] < a[i+1] ，位置交换。  步骤 4 ： 让 j = j+1 ；只要 j != n 返回步骤 3 ，当 j==n 时执行步骤 5  步骤 5 ：输出排序结果

41 41 //************************************ //* 程 序 名： 5_4.cpp * //* 作 者： wuwh * //* 编制时间： 2002 年 9 月 22 日 * //* 主要功能：冒泡排序 * //************************************ #include // 预编译命令 int main()// 主函数 { int i=0, j=0, p=0, a[7];// 整型变量 memset( a, 0, sizeof(a) );// 整型数组初始化 for (i=1; i<=6; i++)// 键入 6 个数，放入 a 数组中 { printf( " 请输入待排序的数 a[%d]=", i);// 提示 scanf( "%d", &a[i]);// 用键盘输入整数赋给 a[i] } for ( j=1; j<=5; j++)// 冒泡排序，外层循环 for ( i=1; i<=6-j; i++ )// 内层循环 if ( a[i] < a[i+1] )// 如果 a[i] < a[i+1] { p = a[i];// 让 a[i] 与 a[i+1] 交换 p = a[i];// 让 a[i] 与 a[i+1] 交换 a[i] = a[i+1]; a[i] = a[i+1]; a[i+1] = p; a[i+1] = p;} for ( i=1; i<=6; i++)// 输出排序结果 printf( "%d\n", a[i]);// 输出 a[i] return 0; }

42 42 //************************************ //* 程 序 名： 5_4.cpp * //* 作 者： wuwh * //* 编制时间： 2002 年 9 月 22 日 * //* 主要功能：冒泡排序 * //************************************ #include // 预编译命令

43 43 int main() { int i = 0, j = 0, p = 0, a[ 7 ]; memset( a, 0, sizeof( a ) ); for ( i =1; i <=6; i++ ) { printf( " 请输入待排序的数 a[%d]=", i); printf( " 请输入待排序的数 a[%d]=", i); scanf( "%d", &a[i]); scanf( "%d", &a[i]);}

44 44 for ( j=1; j<=5; j++) // 外层循环 for ( i=1; i<=6-j; i++ ) // 内层循环 T if ( a[i] < a[i+1] ) F T if ( a[i] < a[i+1] ) F{ p = a[i]; p = a[i]; a[i] = a[i+1]; a[i] = a[i+1]; a[i+1] = p; a[i+1] = p;}

45 45 for ( j = 1; j <= 5; j++ )// 外层循 环 for ( i = 1; i <= 6-j; i++ )// 内层循环 for ( i = 1; i <= 6-j; i++ )// 内层循环 if ( a[ i ] < a[ i+1 ] ) // 让 a[i] 与 a[i+1] 交换 // 让 a[i] 与 a[i+1] 交换{ p = a[ i ]; p = a[ i ]; a[ i ] = a[ i+1 ]; a[ i ] = a[ i+1 ]; a[ i+1] = p; a[ i+1] = p;}

46 46 for ( i = 1; i <=6 ; i++) for ( i = 1; i <=6 ; i++) // 输出排序结果 printf( "%d\n", a[i]); }

47 47 筛法 例：使用筛法求 100 以内的所有素数。 思路  想象将 100 个数看作沙子和小石头子，让小石头子权 称素数；让沙子当作非素数。弄一个筛子，只要将 沙子筛走，剩下的就是素数了。  非素数一定是 2 、 3 、 4 …… 的倍数。  使用数组，让下标就是 100 以内的数，让数组元素的 值作为筛去与否的标志。比如筛去以后让元素值为 1 。

48 48 思路  想象将 100 个数看作沙子和小石头子，让小石头子权 称素数；让沙子当作非素数。弄一个筛子，只要将 沙子筛走，剩下的就是素数了。  非素数一定是 2 、 3 、 4 …… 的倍数。  使用数组，让下标就是 100 以内的数，让数组元素的 值作为筛去与否的标志。比如筛去以后让元素值为 1 。

49 49 方法的依据 1 至 100 这些自然数可以分为三类： 1 至 100 这些自然数可以分为三类： 单位数：仅有一个数 1 。 单位数：仅有一个数 1 。 素数：是这样一个数，它大于 1 ，且只有 1 和它自身这样两个正因数。 素数：是这样一个数，它大于 1 ，且只有 1 和它自身这样两个正因数。 合数：除了 1 和自身以外，还有其他正因数。 合数：除了 1 和自身以外，还有其他正因数。 1 不是素数，除 1 以外的自然数，当然只有素数与 合数。筛法实际上是筛去合数，留下素数。

50 50 效率的考虑 令 n 为合数（这里是 100 ）， c 为 n 的最小正因数 令 n 为合数（这里是 100 ）， c 为 n 的最小正因数 只要找到 c 就可以确认 n 为合数，将其筛去 只要找到 c 就可以确认 n 为合数，将其筛去 注意：要进行 “ 筛 ” 的 1 — 100 的数字是与数组 prime[101] 的下标相对应的，而每个数组元素的取 值只有 2 个：是 0 或 1 ，分别代表（标志）与下标相 对应的数字是素数或不是素数 注意：要进行 “ 筛 ” 的 1 — 100 的数字是与数组 prime[101] 的下标相对应的，而每个数组元素的取 值只有 2 个：是 0 或 1 ，分别代表（标志）与下标相 对应的数字是素数或不是素数

51 51 程序框图如下： 请同学来 分析左边 程序的结 构 从而了解 算法的设 计思路 为程序代 码的实现 创造条件 C 是合数， d 是正因数

52 52 该题目的筛法思路 第一块是一个计数型的循环语句，功能是将 prime 数组清零。 第一块是一个计数型的循环语句，功能是将 prime 数组清零。 prime[c] = 0;c = 2, 3, …,100 第二块是正因数 d 初始化为 d = 2 第二块是正因数 d 初始化为 d = 2 所有 d 的倍数将会被筛掉 所有 d 的倍数将会被筛掉 第三块是循环筛数。这里用了一个 do while 语句， 属于一种直到型循环，其一般形式为： 第三块是循环筛数。这里用了一个 do while 语句， 属于一种直到型循环，其一般形式为：do{循环体语句块} while ( 表达式 )