0.问题引入
定义一个整型变量
int a；
如果要你来定义100个整型变量
int a0,a1,a2,a3,...,a100
很显然，上面的方法不是很聪明的样子
有没有一种办法，让我们一次定义一组相同类型的变量呢？
=>数组
1.什么是数组？
一组具有相同类型的数据元素的有序集合
有序：一段有序的存储空间
在c语言中，数组：
一维数组
二维数组
三维数组
....
其实，C语言中只有一维数组
2.一维数组
2.1定义格式
如：
int a[10];
//a[0] a[1] ...a[9]
类型说明符 数组名[整型表达式]；
or
类型说明符 数组名[整型表达式] = {初始化列表}；
“类型说明符”：指定数组中每一个元素的类型，不是数组的类型！！！
可以是c语言中任意合法的类型（基本类型，构造类型，指针类型）
typeof(a[0]) => int:数组中元素的类型
typeof (a) => int[10] :整个数组的类型
”数组名“ ：
对象的名字，“标识符”
给数组取名字的时候，要符合C语言标识符的规定
整型表达式：
指定数组中数据元素的个数。
C语言规定在定义数组时，需要指定（隐含指定-编译器可以推断出）数组元素的个数
“常量表达式”
int a = 5;
int b[a];//以前不能够通过编译的，现在ubuntu优化了。
建议大家在定义数组的时候，还是使用常量表达式。
例子：
int a[5];//定义一个数组，数组名为a，里面有5个int类型的元素
int是数组元素的类型，并不是数组a的类型
2.2一维数组的引用
int a[10];//定义了一个数组，数组名为a，里面含有10个int类型的元素
如何来访问（引用）这些元素呢？
引用数组元素：
数组名[下标]
“下标” ：C语言规定数组元素的下标是从0开始
0，1，2，3，4，...，n-1（n是表示，数组有n个元素）
引用数组元素和引用普通变量是一模一样的。
数组元素也是有左值和右值。
int a[10];
int b;
a[0] = 1024; //把数值1024赋值给元素a[0]
//a[0]代表元素a[0]的地址，把数值1024
存放到a[0]的地址中去。
b = a[0];//把a[0]的值赋值给b，a[0]代表元素a[0]的值（右值）
2.3一维数组在内存中的存放
在C语言中，用一组连续的存储空间，从低地址到高地址
依次存放数组中的每一个元素。
如;
int a[10];
a[0]-------0x3000
a[1]-------0x3004
练习;
1.请大家写一个程序，验证一下，数组的存储方式
int a[5];
&a[0] ==>取元素a[0]的地址；
printf("%p\n",&a[0]);
printf("%p\n",&a[1]);
.....
完整的C语言代码;
#include
int main()
{
int a[5];
for(int i =0;i<5;i++)
{
printf("%p\n",&a[i]);
}
}
2.定义一个一维数组，通过键盘来给每一个元素赋值
再依次输出数组中元素的值。
#include
int main()
{
int a[5];
for(int i = 0;i<5;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<5;i++)
{
printf("%d\n",a[i]);
}
}
2.4 一维数组的初始化
类型说明符 数组名 [整型表达式] = {初始化列表}；
初始化： 是指定义对象时，就指定对象的值。
数组的初始化使用{}
例子;
int a[5];
printf("%d\n",a[0]);//undefine 未知的
（1）在定义一个数组时，给每一个元素进行初始化
int a[10] = {0,1,2,3,4,5,6,7,8,9};
（2）可以只对前面的元素进行初始化，后面的元素会自动初始化为0
int a[10] = {1,2,3};
a[0] =1;
a[1] = 2;
..
a[3] = 0;
....
a[9] = 0;
int a[10] = {0};//将数组中的每一个元素都初始化为0
（3）如果对全部元素都赋初始值，在定义数组的时候，可以不指定数组的长度（元素个数）
编译器可以自己推断出你有多少个元素
int a[] = {1,2,3,4,5};
===>
int a[5] = {1,2,3,4,5};
int a[]={0};
===>
int a[1] ={0};
NOTE:只有在定义数组时，指定数组全部元素的值
只能在初始化时，给数组整体赋值
int a[5] = {1,2,3,4,5};//OBJK
int a[5];
a[5] = {1,2,3,4,5};//ERROR
a = {1,2,3,4,5};//ERROR
练习：
1.定义一个一维数组，并从键盘随机输入每一个元素的值，
求该一维数组的元素之和，最大值，最小值。
#include
int main()
{
int a[10];
int i;
int sum =0;
for(i=0;i<10;i++)
{
scanf("%d",&a[i]);
}
int max =a[0];
int min = a[0];
for(i=0;i<10;i++)
{
sum += a[i];
if(a[i]>max)
{
max = a[i];
}
if(a[i] { min = a[i]; } } printf("sum = %d,max=%d,min=%d\n",sum,max,min); } 2.判断一个一维数组是否递增 思路： a[0]<=a[1]<=a[2]<=....a[n-1] 只要找到一个》符号，那么就能证明这个数组就不是递增。 a[i] PK a[i+1] #include int main() { int a[10]; int i; for(i=0;i<10;i++) { scanf("%d",&a[i]); } int flag =0;// 0 -递增；1- 不是递增 for(i=0;i<9;i++) { if(a[i]>a[i+1]) { flag = 1; break; } } if(flag==1) { printf("NO"); } if(flag==0) { printf("YES"); } } 把数组中的每一个元素按一定的规律（升序或降序）放置到合适的位置上面去。 冒泡排序 <----- 希尔排序 快速排序 选择排序 <----- 插入排序 堆排序 ..... 相邻的两个元素，两两比较，把较大者往后移（升序） “两两比较” 假设有N个元素： 第0趟排序： if(a[0]>a[1]) a[0]<->a[1] if(a[1]>a[2]) a[1]<->a[2] if(a[N-2]>a[N-1]) a[N-2]<->a[N-1] 序列中，最大值已经保存到a[N-1] => i来表示数组元素的下标 所以：要比较的式子可以用i来替代 if(a[i]>a[i+1]) a[i]<->a[i+1] for(i=0;i { if(a[i]>a[i+1]) { int temp; temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; } } 第一趟排序： if(a[0]>a[1]) a[0]<->a[1] if(a[1]>a[2]) a[1]<->a[2] if(a[N-3]>a[N-2]) a[N-3]<->a[N-2] 此时，序列中，第二大的值已经保存在a[N-2] => i来表示数组元素的下标 所以：要比较的式子可以用i来替代 if(a[i]>a[i+1]) a[i]<->a[i+1] for(i=0;i { if(a[i]>a[i+1]) { int temp; temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; } } 只需要将上面的冒泡，进行N-1趟，就可以把所有的元素都放置在合适的位置上面 每一趟冒泡的代码形式都一样的，所以说，只要将上面的代码，想办法让他循环N-1， 那么整个序列就有序了嘛！！！ for(m=0;m { for(i=0;i { if(a[i]>a[i+1]) { int temp; temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; } } } printf(); m 用来标记第m趟冒泡 第m趟冒泡要比较多少次 m = 0 N-1(i m = 1 N-2(i m = 2 N-3(i m = x N-1-x(i （1）选择一个最大的元素（遍历数组） （2）把最大的元素与最后面一个位置的元素进行交换 times =1：表示第一次选择排序 int max = a[0]; int max_i = 0; for(i=0;i { if(a[i]>max) { max = a[i]; max_i = i; } } if(max_i ！=N-1) { a[max_i]<->a[N-1]; } times = 2:表示第二次选择排序 int max = a[0]; int max_i = 0; for(i = 0;i { if(a[i]>max) { max = a[i]; max_i = i; } } if(max_i !=N-2) { a[max_i]<-->a[N-2]; } times = t:表示第t次交换 int max = a[0]; int max_i = 0; for(i = 0;i { if(a[i]>max) { max = a[i]; max_i = i; } } if(max_i != N-t) { a[max_i]<-->a[N-t]; } 第几次选择交换 数组下标的范围 交换位置 times = 1 i times = 2 i ..... times = t i 最多需要选择交换N-1次 for(t=1;t { int max = a[0]; int max_i = 0; for(i = 0;i { if(a[i]>max) { max = a[i]; max_i = i; } } if(max_i != N-t) { a[max_i]<-->a[N-t]; } } 在数组a[N]查找一个元素x，如果找到了就返回下标，没有找到就返回-1 （1）查找可以用“遍历” for(i=0;i { if(a[i]==x) { return i; } } return -1; （2）在一个有序数组中查找，用遍历，就显得有点LOW。 “二分查找法”/“折半查找法” 练习： 在一个有序的数组中，去查找一个值为x的元素 找到了就打印其下标，没有找到，那么打印：没有此元素 4 int L,R; int a[N]; int i,x; for(i=0;i { scanf("%d",&a[i]); } scanf("%d",&x); L = 0; R = N-1; while(L<=R) { mid =(L+R)/2; if(a[mid] { L = mid +1; } else if (a[mid]>x)//x比中间元素小，所以舍弃mid以及它右边的 { R = mid -1; } else { printf("x=>%d\n",mid);//mid表示下标 } } //没有找到值为x的那一个元素 总结： 1.数组概念问题 2.一维数组 2.1 定义 2.2 数组元素的引用 2.3 数组元素的存储问题 2.4 数组的初始化 3.排序 冒泡 选择 时间复杂度：o（n^2） 4.二分查找法 练习： 1.求斐波拉契数列的前20项之和 斐波拉契数列 1 1 2 3 5 8 13 21 a[i] = a[i-1]+a[i-2] S1: 先求第i项 =>ai S2: 累加sum +=ai int a[20] = {0}; a[0] = a[1] = 1; sum = a[0]+a[1]; for(i=2;i<20;i++) { a[i] = a[i-1] + a[i-2]; sum +=a[i]; } 2.不用排序，把一个数组中的负数放置数组的前面 如; 2 4 -3 5 -4 8 -2 -2 -3 -1 1 2 3 4 i 思路： 用一个i来记录负数存放的下标 用j来遍历数组，遇到负数，那么就交换 a[i]<--->a[j] i++, 继续从下标为j的地方遍历数组 int a[N]; i = 0; //存放负数的下标 for(j=0;j<20;j++) { if(a[j]<0) //交换位置，并且i+1 { a[i]<->a[j]; i++; } } 3.不用排序，求数组中第二大的那一个元素的值（只能遍历一次） 思路; int max; int max_2； max = a[0]>a[1]?a[0]:a[1]; max_2 = a[0]>a[1]?a[1]:a[0]; for(i=2;i { if(a[i]>max) { max_2 = max; max = a[i]; } else { if(a[i]>max_2) { max_2 = a[i]; } } } 回顾一下，一维数组 定义格式： 元素类型 数组名[数组元素的个数]； 例子： int a[4];//定义了一个数组，数组名为a，里面有4个int类型的元素。 //在定义数组a的时候，也声明了一个新类型 “像a这样的类型” typeof(a) =》int [4] a[0] int a[1] int 问题： 定义3个像a这样类型的变量，该如何定义 元素类型 数组名 [数组元素个数] typeof(a) b [3]; ==> int [4] b[3]; ==> int b[3][4]; //二维数组 b的含义：b是一个数组，里面含有3个int[4]类型的元素 由上面的推导过程可以得出 c语言中，二维数组实际上就是一个一维数组，只不过该一维数组中的每一个元素 又是一个一维数组 例子： int b[3][4] <=>int[4] b[3]; 数组名为b，里面有三个元素 b[0] _ _ _ _》里面含有4个int类型的元素,b[0]又是一个数组，数组名b[0] b[1] _ _ _ _》里面含有4个int类型的元素,b[1]又是一个数组，数组名b[1] b[2] _ _ _ _》里面含有4个int类型的元素,b[2]又是一个数组，数组名b[2] 矩阵角度来看; 三行四列
从矩阵角度来说 类型说明符 数组名[行数][列数] 连续的存储空间，从低地址到高地址 按行存放，先顺序存放第0行的元素，然后再存放第一行的元素 练习： 1.请大家，来验证一下，二维数组的元素存储方式 #include int main() { int a[3][4]; i = 0; a[0] _ _ _ _ printf("%p\n",&a[0][0]) printf("%p\n",&a[0][1]) printf("%p\n",&a[0][2]) printf("%p\n",&a[0][3]) for(j=0;j<4;j++) { printf("%p\n",&a[0][j]) } i = 1; a[1] _ _ _ _ printf("%p\n",&a[1][0]) printf("%p\n",&a[1][1]) printf("%p\n",&a[1][2]) printf("%p\n",&a[1][3]) for(j=0;j<4;j++) { printf("%p\n",&a[1][j]) } .... for(i=0;i<3;i++) { for(j=0;j<4;j++) { printf("%p\n",&a[i][j]); } } } 2.从键盘按行来给二维数组的每一个元素赋值，然后按列打印输出每个数组元素的值 1 2 3 4 5 6 7 8 9 10 11 12 #include #define M 3 #define N 4 int main() { for(i=0;i<3;i++) { for(j=0;j<4;j++) { scanf("%d",&a[i][j]); } } for(j=0;j<4;j++) { for(i=0;i<3;i++) { printf("%d\n",a[i][j]); } } }
数组元素的引用： 数组名[下标] 例子: int a[3][4]; //int[4] a[3] a[0] _ _ X _ //a[0]是一个数组名，里面含有4个int类型的元素 a[1] _ _ _ _ 要访问上面的元素X，该如何访问？ 数组名[下标] a[0][2] <==>X 以矩阵的角度： 数组名[行号][列号] a[0][2] 引用二维数组的元素和引用普通变量是一模一样， 它也有左值和右值之分 例子： a[0][2] = 1024; //把数值1024，写到a[0][2]的存储空间中去（变量的地址） int b = a[0][2];//把a[0][2]的值，赋值给b（变量的值） scanf("%d",&a[0][2]) printf("%d\n",a[0][2]);//右值 printf("%p\n",&a[0][2]);//左值 连续的存储空间，连续的存储空间，从低地址到高地址 按行存放，先顺序存放第0行的元素，然后再存放第一行的元素 在定义二维数组时，可以指定每个元素或部分元素的初始值。 (1)分行给二维数组赋初值 int a[3][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12} } (2)将所有二维数组的初始值写在一个{}内， 按数组的排列顺序一一对应各个元素 int a[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12}; a[0][0] = 1; a[1][0] = 5; a[2][3] = 12; a[2][0] = 9; #define M 3 #define N 4 int a[M][N] ===>int a[3][4] a[3][4],很显然越界了！！！（段错误） (3)对部分元素赋初始值，其余的元素自动置0 int a[3][4]={{1,2},{5},{9,10,11}}; <=> {{1,2,0,0},{5,0,0,0},{9,10,11,0}}; (4)如果对全部元素都赋初始值，则定义二维数组时，对一维数组的长度可以省略 但是第二维的长度不能省略 int [][4] = {1,2,3,4,5,6,7,8,9,10,11}; NOTE: 只有在数组定义时，才能对数组整体赋值。 练习; 1.定义一个二维数组，将数组中的元素随机进行初始化，然后要求该二维数组 的所有元素之和，最大值，最小值。 2.把一个二维数组，行列互换 1 2 3 4 1 5 9 5 6 7 8 2 6 10 9 10 11 12 ===> 3 7 11 4 8 12 #include #define M 3 #define N 4 int a[M][N] = {1,2,3,4,5,6,7,8,9,10,11,12}; int b[N][M]; for(int i =0;i { for(int j = 0;j { b[i][j] = a[j][i]; } } //按行输出b for(int i =0;i { for(int j = 0;j { printf("%d ",b[i][j]); } printf("\n"); } 3.实现矩阵乘法 A[M][K] * B[K][N] = C[M][N] {1 2 4 { 1 2 7（1*1 +2*3 +4*0） 26 （1*2+2*2+4*5） 2 0 3} * 3 2 = 2 （2*1+0*3+3*0） 19（2*2+0*2+3*5） 0 5 } 第一个的列数必须要等于第二个的行数 #include #define M 3 #define N 4 #define K 2 int main() { int A[M][K]; int B[K][N]; int C[M][N] = {0}; int i, j, k; printf("给数组A[3][2]赋值:\n"); for(i = 0; i < M; i++) { for(j = 0; j < K; j++) { scanf("%d", &A[i][j]); } } printf("给数组B[2][4]赋值:\n"); for(i = 0; i < K; i++) { for(j = 0; j < N ; j++) { scanf("%d", &B[i][j]); } } //-------矩阵乘法--------------- for(i = 0; i < M; i++) { for(j = 0; j < N; j++) { /* C[i][j] : i = 0, j = 0 : A[i][0] * B[0][j] + A[i][1] * B[1][j] + ...... A[i][K-1]* B[K-1][j] */ C[i][j] = 0; for(k = 0; k < K; k++) { C[i][j] += A[i][k] * B[k][j]; } } } for(i = 0; i < M; i++) { for(j = 0; j < N; j++) { printf("%d ", C[i][j]); } printf("\n"); } } 关于xxx的类型，给它定性 它是个什么东西。 int a[4] //a是一个含有4个int类型元素的数组 typeof(a) =》int [4] float b[10] //b是一个含有10个float类型的数组 typeof(b) => float [10] int a[3][4] //a是一个含有3个元素并且每个元素又含有4个int类型元素的数组 typeof(a) ==>int[4] [3] 关于数组定义： 数组元素的类型 数组名[元素个数]； 二维数组： 可以从矩阵的角度来看： 几行几列 元素的类型 数组名[行号][列号] 二维数组的元素引用： 数组名[行下标][列下标] 二维数组的存储; 连续的存储空间，从低地址到高地址 从第0行开始，按顺序存储每一个元素。 二维数组的初始化： 只能省略行号不能省略列号 将一个整数m，插入到一个升序的数组（一维数组）中去，使得插入后，数组a仍然有序。 把一个m，插入到有序数组中去，使得插入后仍然有序 （1）找到插入的位置 a,遍历数组 从头开始，一个一个去找，找到数组中第一个比m大的那一个元素，那么，那个元素的 位置，就是我要插入m的位置 for(i=0;i { if(a[i]>m) { //找到了 //待插入的位置，下标为i break； } } b,折半查找法 通过分析: 当循环结束后，那么得到待插入的位置pos if(a[mid] > m) //往中间插入，或往数组最前面插入一个元素 { pos = mid ; } else if(a[mid] == m) { pos = mid; //找到了元素的值为m，那么这个元素的位置就是m要插入的位置 } else //a[mid] < m 往数组最后面去插入一个元素 { pos = mid+1; } （2）插入操作 假设待插入元素的位置是 pos 将pos及其以后的元素，统统往后移(给待插入元素腾出位置) 再将m赋值给 a[pos] int L, R, mid, pos; //L 记录数组左边的下标 //R 记录数组右边的下标 //mid 记录 L,R的中间的下标 //pos 记录待插入的位置的下标 L = 0; R = n-1; while(L <= R) { mid = (L + R)/2; if(a[mid] > m) { R = mid - 1; } else if(a[mid] < m) { L = mid + 1; } else //a[mid] == m { //pos = mid; break; } } if( a[mid] == m ) { pos = mid; } else if(a[mid] > m) { pos = mid; } else //a[mid] < m { pos = mid+1; } //(2) 插入m for(i = N-2; i >= pos; i--) { a[i+1] = a[i]; } a[pos] = m; } 练习 1.求一个二维数组中山顶元素的个数 山顶：此处比周围（上下左右）高，就是山顶。 思路： 遍历整个数组，如果此元素比周围的元素值都要大 此处就是一个山顶，count++ int a[M][N]; int count = 0; for(i=0;i { for(j=0;j { if(a[i][j]比上下左右的元素值要大) { count++； } } } a[i][j]比上下左右的元素值要大 它比上面大&&比下面大&&比左边大&&比右边大 它比上面大： 上面不存在元素 || 真比上面大 (i==0) || a[i][j]>a[i-1][j] 它比下面大： 下面不存在元素 ||真比下面大 (i == M-1) || a[i][j]>a[i+1][j] .... 2.求一个二维数组中的鞍点 鞍点：行最大，列最小 思路; 遍历二维数组，看数组是不是一个鞍点 for(i=0;i { for(j=0;j { if(a[i][j]是鞍点) { printf("a[%d][%d]==%d\n",i,j,a[i][j]); } } } a[i][j]是鞍点 a[i][j] 是第i行最大值 &&是第j列的最小值 定义两个辅助数组： int b[M];//保存每一行的最大值 int c[N]；//保存每一列的最小值 a[i][j] 是第i行的最大值 ==>a[i][j] == b[i] && a[i][j] 是第j列的最小值 ==>a[i][j] == c[j] b[0] = a[0][0] for(j = 0;j { if(a[0][j]>b[0]) { b[0] = a[0][j]; } } .... for(i=0;i { b[i] = a[i][0]; for(j = 0;j { if(a[i][j]>b[i]) { b[i] = a[i][j]; } } } c[N].... c[j] = a[i][j] if(a[i][j]==b[i] && a[i][j]==c[j]) 3.最长上升子序列的长度（选做） 1 4 -3 -9 5 9 0 思路： int a[N]; 定义辅助数组L[N] L[i]表示以a[i]结尾的最长上升子序列的长度 4,以下叙述中错误的是？（C） A,对于double类型数组，不可以直接用数组名对数组进行整体输入或输出 B,数组名代表的是数组所占存储区的首地址，其值不可改变 C,当程序执行中，数组元素的下标超出所定义的下标范围时，系统将给出“下标越界”的出错信息 D,可以通过赋初值的办法确定数组元素的个数 5,以下程序的输出结果是？(45) main() { int p[8]={11,12,13,14,15,16,17,18}; int i=0,j=0; while(i++<7) if(p[i]%2) j+=p[i]; printf("%d\n",j)); } 6,有以下程序，程序输出的结果是？(25) main() { int i,s=0,t[]={1,2,3,4,5,6,7,8,9}; for(i=0;i<9;i+=2) s+=*(t+i); printf("%d\n",s); } 7,有以下程序，如果运行时输入:2 4 6 <回车>，则输出结果为？ (2,0,4) main() { int x[3][2]={0},i; for(i=0;i<3;i++) scanf("%d",x[i]); printf("%3d%3d%3d",x[0][0],x[0][1],x[1][0]); } 8,有以下程序，以下叙述中正确的是(B) #include { char p[]={'a','b','c'},q[10]={'a','b','c'}; printf("%d %d\n",strlen(p),strlen(q)); } A,在给p，q数组置初值时，系统会自动添加字符串结束符，故输出的长度为3 B,由于p数组中没有字符串结束符，长度不能确定，但q数组中字符串长度为3 C,由于q数组中没有字符串结束符，长度不能确定，但p数组中字符串长度为3 D,由于p,q数组中都没有字符串结束符，故长度不能确定 9,以下能正确定义一维数组的一项是？(B) A, int a[5]={0,1,2,3,4,5}; B,char a[]={0,1,2,3,4,5}; C,char a={'A','B','C'}; D,int a[5]="0123" 10,设有如下定义，则正确的叙述为(C) char x[]={"abcdefg"}; char y[]={'a','b','c','d','e','f','g'}; A,数组x和数组y等价 B,数组x和数组y长度相同 C,数组x的长度大于数组y的长度 D,数组x的长度小于数组y的长度3.排序的问题
冒泡排序：
选择排序
4.查找一个元素
5.二维数组
5.1二维数组的定义格式
1.2二维数组的引用
1.3二维数组元素的存放
1.4二维数组的初始化
6.关于数组的类型
7.回顾
![[工业自动化-1]：PLC架构与工作原理](https://img-blog.csdnimg.cn/ce10a1471ed14382bc58364cf8bd5209.png)
还没有评论，来说两句吧...