第 8 章 数组 计算机科学学院 李淮 Tel QQ

/49 本章学习内容本章学习内容  对数组名特殊含义的理解  数组类型，数组的定义和初始化  向函数传递一维数组和二维数组  排序、查找、求最大最小值等常用算法

/49 为什么使用数组 (Array)? 【例 8.1 】读入并保存 10 人的成绩，再计算平均成绩 需定义 10 个不同名整型变量，需要使用多个 scanf() 需定义 10 个不同名整型变量，需要使用多个 scanf() int score1,score2,…score10; int score1,score2,…score10; scanf("%d",&score1); scanf("%d",&score1); scanf("%d",&score2); scanf("%d",&score2); 用数组 用数组 int score[10],i; int score[10],i; for (i=0; i<10; i++) for (i=0; i<10; i++) { scanf("%d",&score[i]); scanf("%d",&score[i]); } 保存大量同 类型的相关 数据

/49 数组概念 1 、数组：一组具有相同数据类型的数据的有序的集合。 2 、数组元素：构成数组的数据。数组中的每一个数组元 素具有相同的名称，不同的下标，可以作为单个变量使 用，所以也称为下标变量。 3 、数组的下标：是数组元素的位置的一个索引或指示。 4 、数组的维数：数组元素下标的个数。根据数组的维数 可以将数组分为一维、二维、三维、多维数组。

/ 一维数组的定义和初始化 一维数组的定义 一维数组的定义 存储类型 数据类型 数组名 [ 整数 1] [ 整数 2] …… [ 整数 n]; 存储类型 数据类型 数组名 [ 整数 1] [ 整数 2] …… [ 整数 n]; a[9] a[8]a[7] a[1] a[0] … 数组首地址 int a[10]; 定义一个有 10 个 int 型元素的数组 定义一个有 10 个 int 型元素的数组 – 系统分配 10 个连续的存储空间给数组 数组名 a 就是此数组的首地址 数组名 a 就是此数组的首地址 基类型 下标从 0 开始

/ 一维数组的定义和初始化 a[9] a[8]a[7] a[1] a[0] … int a[10]; 数组大小必须是值为正的常量，不能为变量 数组大小必须是值为正的常量，不能为变量 – int n=10; – int a[n]; 数组大小可以用宏来定义 数组大小可以用宏来定义 #define SIZE 10 int a[SIZE]; int a[SIZE]; 一维数组的定义 一维数组的定义 存储类型 数据类型 数组名 [ 整数 1] [ 整数 2] …… [ 整数 n]; 存储类型 数据类型 数组名 [ 整数 1] [ 整数 2] …… [ 整数 n]; ×

/ 一维数组的定义和初始化 数组定义后的初值仍然是随机数 数组定义后的初值仍然是随机数 一般需要我们来初始化 一般需要我们来初始化 int a[5] = { 12, 34, 56,78,9 }; int a[5] = { 12, 34, 56,78,9 }; 部分元素初始化，其余元素为零 部分元素初始化，其余元素为零 int a[5] = { 0 }; int a[5] = { 0 }; 如果全部元素均指定初值，定义中可以省略 元素的个数 如果全部元素均指定初值，定义中可以省略 元素的个数 int a[] = { 11, 22, 33, 44, 55 }; int a[] = { 11, 22, 33, 44, 55 };

/ 一维数组的定义和初始化 数组的引用 数组的引用 数组名 [ 下标 ] 数组名 [ 下标 ] 数组下标 (index) 都是从 0 开始 数组下标 (index) 都是从 0 开始 使用 a[0] 、 a[1] 、 a[2] 、 …… 、 a[9] 访问元素 使用 a[0] 、 a[1] 、 a[2] 、 …… 、 a[9] 访问元素 下标既可是常量，也可是整型表达式，如 a[i] 下标既可是常量，也可是整型表达式，如 a[i] – 可以像使用普通变量一样使用它们

/49 如何使两个数组的值相等？ main() { int a[4] = {1,2,3,4}, b[4]; b = a; } 解决方法 方法 1: 逐个元素赋值 b[0]=a[0]; b[1]=a[1]; b[2]=a[2]; b[3]=a[3]; 方法 2: 通过循环赋值 int i; for (i=0;i<4;i++) { b[i] = a[i]; } 原因 : 数组名表示数组的首地址, 其值不可改变 !

/ 一维数组的定义和初始化 【例 8.2 】编程实现显示用户输入的月份（不包括 闰年的月份）拥有的天数 【例 8.2 】编程实现显示用户输入的月份（不包括 闰年的月份）拥有的天数

/ 一维数组的定义和初始化 下标越界是大忌！ 下标越界是大忌！ – 编译程序不检查是否越界 – 下标越界，将访问数组以外的空间 – 越界的数据是未知的

/49 b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] b[9] c a 【例 8.3 】 当下标值小于 0 或超过数组长度时 会出现什么情况？ 运行程序或单步执行观察变量变化情况可以看到， 变量 c 和 a 的值因数组越界而被悄悄破坏了 c c c

/49 [ 例 ] 使数组元素 a[0] ～ a[9] 的值为 1 ～ 10 ，然后逆序 输出。 main(){ int i,a[10]; int i,a[10]; for (i=0;i<=9;i++) for (i=0;i<=9;i++) a[i] = i+1; a[i] = i+1; for(i=9;i>=0; i--) for(i=9;i>=0; i--) printf("%d ",a[i]); printf("%d ",a[i]);} 运行输出： 运行输出：

/ 向函数传递一维数组 传递整个数组给另一个函数，可 将数组的首地址作为参数传过去 传递整个数组给另一个函数，可 将数组的首地址作为参数传过去 – 用数组名作函数参数 – 由于首地址相同，故实参数组与形 参数组占用同一段内存 – 在该函数内，形参不仅可以读这个 数组的元素，还可以修改它们

/49 简单变量和数组作函数参数的区别 简单变量和数组作函数参数的区别

/49 【例 8.5 】输入人数，计算平均分 计数控制的循环 计数控制的循环

/49 【例 8.5 】输入人数，计算平均分 计数控制的循环 计数控制的循环

/49 【例 8.6 】输入分数，统计人数，计算平 均分，当输入负值时，表示输入结束 标记控制的循环 —— 负值作为输入结束标记 标记控制的循环 —— 负值作为输入结束标记

/49 【例 8.6 】输入分数 ( 人数？ ) ，计算平均 分，当输入负值时，表示输入结束 标记控制的循环 —— 负值作为输入结束标记 标记控制的循环 —— 负值作为输入结束标记

/49 【例 8.7 】计算最高分 #include #define N 40 int ReadScore(int score[]); int FindMax(int score[], int n); int main() { int score[N], max, n; n = ReadScore(score); printf("Total students are %d\n", n); max = FindMax(score, n); printf("The highest score is %d\n", max); return 0; }

最值算法 算法描述 算法描述 求最大值时，假设第一个数为最大值 求最大值时，假设第一个数为最大值 将每个数逐个与最大值相比较，若比最大值大 则将该数作为新的最大值，直到数组元素比较 完。 将每个数逐个与最大值相比较，若比最大值大 则将该数作为新的最大值，直到数组元素比较 完。

/49 max(i=0) max(i=2)max(i=3) 计算最大值算法计算最大值算法

/49 假设其中的一个学生成绩为最高 假设其中的一个学生成绩为最高 maxScore = score[0]; 对所有学生成绩进行比较，即 对所有学生成绩进行比较，即 for (i=1; i<n; i++) for (i=1; i<n; i++) { 若 score[i] > maxScore 若 score[i] > maxScore 则修改 maxScore 值为 score[i] } 打印最高分 maxScore 打印最高分 maxScore 【例 8.7 】计算最高分

/49 【例 8.7 】计算最高分

/ 排序和查找 排序（ Sorting ）算法 排序（ Sorting ）算法 – 交换法排序 – 选择法排序

比较交换法 基本过程（以降序为例）： 将第一个元素顺序与其后面的元素比较，比第一 个大则进行交换，第一轮完毕后，最大的元素被 挪到了第一个位置 将第一个元素顺序与其后面的元素比较，比第一 个大则进行交换，第一轮完毕后，最大的元素被 挪到了第一个位置 第二轮从第二个元素开始重复上面的过程，结束 后得到第二个最大的元素， 第二轮从第二个元素开始重复上面的过程，结束 后得到第二个最大的元素， 如此下去，经过 N-1 轮的比较，可将 N 个数排好 如此下去，经过 N-1 轮的比较，可将 N 个数排好

第一轮结束，数据 5 已排好 比较交换法 举例 原始数据： 1 ， 2 ， 3 ， 5 ， 4 要求：降序

第 二 轮 比 较 ：第 二 轮 比 较 ： 第二轮结束，找到第二最大值 4 比较交换法

第三轮结果： 第四轮结果： 公式表示： (N 为排序的个数, OP 为操作，降序为 “>”) for( i=0 ; i<n-1 ; i++) 外层循环 N-1 次 for( j=i+1 ; j <n ; j++) 内层依赖外层 if （ S(j) OP S(i) ） { t=S(i):S(i)=S(j):S(j)=t‘ 交换 } 方法：双重循环（循环嵌套） 外循环：控制排序趟数 内循环：排序过程中的数组元素下标取值

/49 【例 8.8 】交换法从高到低排序 交换法排序 for (i=0; i<n-1; i++) { for (j=i+1; j<n; j++) for (j=i+1; j<n; j++) { if (score[j] > score[i]) if (score[j] > score[i]) " 交换成绩 score[j] 和 score[i]" " 交换成绩 score[j] 和 score[i]" }}

/49 如何实现两数交换？如何实现两数交换？ temp = score[j]; score[j] = score[i]; score[i] = temp; temp score[j] score[i] ？？

/49 【例 8.8 】交换法从高到低排序 void DataSort(int score[], int n) /* 交换法排序 */ { int i, j, temp; for (i=0; i<n-1; i++) { for (j=i+1; j<n; j++) { if (score[j] > score[i]) /* 从高到低 */ { temp = score[j]; score[j] = score[i]; score[i] = temp; }

选择法排序思想方法：按递增排序 对 n 个数排序，先将第一个数与第二个数到第 n 个数逐 一比较，找出最小数的位置 i( 下标 ) ，然后将 a(1) 与 a(i) 进 行 交换，将最小数存放在 a(1) 中 对 n 个数排序，先将第一个数与第二个数到第 n 个数逐 一比较，找出最小数的位置 i( 下标 ) ，然后将 a(1) 与 a(i) 进 行 交换，将最小数存放在 a(1) 中 然后将第二个数依次与第三个到第 n 个数逐一进行比 较，找出第二个到第 n 个数中最小数，然后将 a(2) 与 a(i) 进行交换 然后将第二个数依次与第三个到第 n 个数逐一进行比 较，找出第二个到第 n 个数中最小数，然后将 a(2) 与 a(i) 进行交换 重复上面的步骤，直到排序结束为止 ( 进行 n-1 趟排序 ) 重复上面的步骤，直到排序结束为止 ( 进行 n-1 趟排序 ) 选择法排序

第一趟排序 原始数据 a(1) a(2) a(3) a(4) a(5) a(6) 第一趟排序 第二趟排序 第二趟排序 第三趟排序 第三趟排序 第四趟排序 第四趟排序 第五趟排序 、求数组的最小元素 2 、交换数组中的两个元素 方法：双重循环（循环嵌套） 外循环为 i ：控制排序趟数 内循环为 j ：排序过程中的下标变量 选择法排序

/49 选择法排序选择法排序 选择法排序 for (i=0; i<n-1; i++) { k = i; k = i; for (j=i+1; j<n; j++) for (j=i+1; j<n; j++) { if (score[j] > score[k]) if (score[j] > score[k]) 记录此轮比较中最高分的元素下标 k = j; 记录此轮比较中最高分的元素下标 k = j; } } 若 k 中记录的最大数不在位置 i ，则 若 k 中记录的最大数不在位置 i ，则 " 交换成绩 score[k] 和 score[i]" ， " 交换成绩 score[k] 和 score[i]" ， " 交换学号 num[k] 和 num[i]" ； " 交换学号 num[k] 和 num[i]" ；}

/49 void DataSort(int score[], long num[], int n) /* 选择法 */ { int i, j, k, temp1; long temp2; for (i=0; i<n-1; i++) { k = i; for (j=i+1; j<n; j++) { if (score[j] > score[k]) { k = j; /* 记录最大数下标位置 */ } if (k != i) /* 若最大数不在下标位置 i*/ { temp1 = score[k]; score[k] = score[i]; score[i] = temp1; temp2 = num[k]; num[k] = num[i]; num[i] = temp2; }

/49 【例 8.8 】成绩从高到低顺序

/ 排序和查找 查找（ Searching ）算法 查找（ Searching ）算法 – 顺序查找 – 折半查找

/49 【例 8.10 】顺序查找学号 int LinSearch(long num[], long x, int n) { int i; int i; for (i=0; i<n; i++) for (i=0; i<n; i++) { if (num[i] == x) if (num[i] == x) { return (i); return (i); } } return (-1); return (-1);} 哈，找到了！ 事先不必排序

/49 【例 8.11 】折半查找学号 哈，找到了！ 按升序排序

/49 【例 8.11 】折半查找学号 唉，没找到！

/49 int BinSearch(long num[], long x, int n) { int low, high, mid; low = 0; high = n - 1; while (low <= high) { mid = (high + low) / 2; mid = (high + low) / 2; if (x > num[mid]) { low = mid ; } else if (x < num[mid]) { high = mid ; }else{ return (mid); }} return(-1); } 找到时返回 下标位置 找不到时 返回 -1 若未按学号排序， 则如何修改程序？

/ 二维数组的定义和初始化 一维数组 一维数组 – 用一个下标确定各元素在数组中的顺序 – 可用排列成一行的元素组来表示 如 int a[5]; 如 int a[5]; 二维数组 二维数组 – 用两个下标确定各元素在数组中的顺序 – 可用排列成 i 行， j 列的元素组来表示 如 int b[2][3]; 如 int b[2][3]; n 维数组 n 维数组 – 用 n 个下标来确定各元素在数组中的顺序 如 int c[3][2][4]; 如 int c[3][2][4]; – n≥3 时，维数组无法在平面上表示其各元素的位置 a[0]a[1]a[2]a[3]a[4] b[0][0]b[0][1]b[0][2]b[1][0]b[1][1]b[1][2]

/49 【例】以下程序的运行结果是什么？ int main() { int a[][3]={{1,2,3},{4,5},{6},{0}}; int a[][3]={{1,2,3},{4,5},{6},{0}}; printf("%d,%d,%d\n",a[1][1],a[2][1],a[3][1]); printf("%d,%d,%d\n",a[1][1],a[2][1],a[3][1]); return 0; return 0;} 结果： 5, 0, 0 【例】若 int a[ ][3]={1, 2, 3, 4, 5, 6, 7} ， 则 a 数组的第一维大小是多少？ 二维数组的初始化

/49 数组的数据类型和存储类型 根据数组的数据类型，为每一元素安排相同长度的存储单元 根据数组的数据类型，为每一元素安排相同长度的存储单元 根据数组的存储类型，将其安排在内存的动态存储区、静态 存储区或寄存器区 根据数组的存储类型，将其安排在内存的动态存储区、静态 存储区或寄存器区 用 sizeof(a) 来获得数组 a 所占字节数 用 sizeof(a) 来获得数组 a 所占字节数 short

/49 short int a[2][3]; a[0] a[1] a[1][0] a[1][1] a[1][2] a[0][0] a[0][1] a[0][2] 存放顺序：按行存放 先顺序存放第 0 行元素，再存放第 1 行元 素 a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2] 需知道数组每行列数才能从起始地址开始正确读出数组元素 二维数组的存储结构二维数组的存储结构

/49 二维数组实例二维数组实例 【例 8.4 】从键盘输入 4 个学生的 3 门成绩，并显示。 【例 8.4 】从键盘输入 4 个学生的 3 门成绩，并显示。 #include<stdio.h> void main() { int score[4][3],i,j; int score[4][3],i,j; for(i=0;i<4;i++) { for(i=0;i<4;i++) { for(j=0;j<3;j++) { printf("input score[%d][%d]:",i,j); printf("input score[%d][%d]:",i,j); scanf("%d",&score[i][j]); scanf("%d",&score[i][j]);}}}for(i=0;i<4;i++){ for(j=0;j<3;j++) for(j=0;j<3;j++) { printf("%d\t",score[i][j]); printf("%d\t",score[i][j]); }putchar('\n'); }

/ 向函数传递二维数组 a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2] a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2] 实际传送的是数组第一个元素的地址 short a[2][3];

/ 向函数传递二维数组 在声明二维数组形参时，不能省略数组第二 维的长度（列数），为什么？ 在声明二维数组形参时，不能省略数组第二 维的长度（列数），为什么？ 想想数组在内存中是如何分布的？ 想想数组在内存中是如何分布的？ 元素 a[i][j] 在数组 a 中的位置是： 元素 a[i][j] 在数组 a 中的位置是： i * N + j i * N + j 元素地址： 首地址 + 偏移量 元素地址： 首地址 + 偏移量 a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2] a[0][0] a[0][1] a[0][2] a[1][0] a[1][1] a[1][2] 实际传送的是数组第一个元素的地址 short a[M][N]; 偏移 1*3+2

/49 例 8.12 计算每门课程的总分和平均分 void AverforCourse(int score[][COURSE_N], int sum[], float aver[], int n) float aver[], int n){ int i, j; for (j=0; j<COURSE_N; j++) { sum[j] = 0; sum[j] = 0; for (i=0; i<n; i++) for (i=0; i<n; i++) { sum[j] = sum[j] + score[i][j]; sum[j] = sum[j] + score[i][j]; } aver[j] = (float) sum[j] / n; }} 可省略数组第一维的长度 不能省略第二维的长度

/49 例 8.12 计算每个学生的总分和平均分 void AverforStud(int score[][COURSE_N], int sum[], float aver[], int n) float aver[], int n){ int i, j; for (i=0; i<n; i++) { sum[i] = 0; sum[i] = 0; for (j=0; j<COURSE_N; j++) for (j=0; j<COURSE_N; j++) { sum[i] = sum[i] + score[i][j]; sum[i] = sum[i] + score[i][j]; } aver[i] = (float) sum[i] / COURSE_N; }}

/49 例 8.12 计算每门的总分和平均分

/49 作业 习题