写在开头二维指针数组和普通二维数组的区别只是行之间不连续存放按照相同的方式访问就行对于一维数组模拟的二维数组需要人工计算索引转换去访问二维数组的元素能不用就不用1. 矩阵连通读取一个 ×N×N 矩阵3≤≤203≤N≤20和一个坐标 (,)(x,y)行列索引均从1开始计算该坐标对应值的连接数。连接规则如下从 (,)(x,y) 出发与其值相同且四方向相邻上下左右的元素视为连接递归遍历所有连接元素的相邻位置统计总连接数含自身。原题为从txt文件读入输入格式首行为整数 N表示矩阵维度后续 N 行为矩阵元素每行包含 N 个整数以空格分隔最后一行包含两个整数 x 和 y以空格分隔代码实现自己写的:与常规周围位置的方向数组的区别题目要求从左上开始按顺时针螺旋即右下左上4个方向一循环定义direct[4][2]分别为这个方向的方向数组然后和常规题目一样先填充再根据方向数组计算下一个位置是否合法不合法则说明此方向上已经到边界了需要改变到下一个方向按顺时针即d(d1)%4法一#include stdio.h #include stdlib.h int isconnect(int N,int* arr, int i, int j,int* visited); void main() { int N; scanf(%d, N); int* arr (int*)malloc(sizeof(int) * N * N); //int型可以用一维数组指针模拟二维数组 int* visited (int*)malloc(sizeof(int) * N * N); for (int i 0; i N; i) { for (int j 0; j N; j) { scanf(%d, arr[i*Nj]); visited[i * N j] 0; } } int x, y; scanf(%d %d, x, y); int i x - 1; //注意这里的处理传入从0开始的索引方便计算 int j y - 1; int count isconnect(N, arr, i, j, visited); printf(%d\n, count); free(arr); free(visited); } int isconnect(int N, int* arr, int i, int j, int* visited) { if (visited[i * N j]) { return 0; } visited[i * N j] 1; //先标记已访问后面递归到该元素时就不会重复统计 int temp arr[i * N j]; int a 0; //int a; 只有作为「全局变量」或「静态局部变量static int a;」时才会自动 // 初始化为 0作为「局部自动变量」函数内直接 int a;时是内存随机垃圾值 int b 0; int c 0; int d 0; if (i - 1 0 ) { //边界不满足不存在则跳过存在才比较值是否相同 if (arr[(i - 1) * N j] temp) { a isconnect(N, arr, i - 1, j, visited); } } if (i 1 N) { if (arr[(i 1) * N j] temp) { b isconnect(N, arr, i 1, j, visited); } } if (j - 1 0 ) { if (arr[i * N j - 1] temp) { c isconnect(N, arr, i, j - 1, visited); } } if (j 1 N) { if (arr[i * N j 1] temp) { d isconnect(N, arr, i, j 1, visited); } } return 1abcd; //这里的1是传入的这个元素本身也算上 // 再加上周围4个位置上的连通数量这4个位置再递归统计它们各自的周围4个位置 }法二推荐int dir[4][2] { // 左、上、右、下 {0,-1}, {-1,0}, {0,1}, {1,0} }; int islt(int** arr, int** visited, int x, int y,int m,int n) { if (visited[x][y]) return 0; if (!arr[x][y]) { visited[x][y] 1; return 0; } // 当前位置是1了 int sum 1; visited[x][y] 1; for (int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; if (nx 0 nx m !visited[nx][ny]) { sumislt(arr, visited, nx, ny, m, n); } } return sum; } void main() { int m, n; scanf(%d %d, m, n); int** arr (int**)malloc(sizeof(int*) * m); for (int i 0; i m; i) { arr[i] (int*)malloc(sizeof(int) * n); for (int j 0; j n; j) { scanf(%d, arr[i][j]); } } // 初始化visited数组 int** visited (int**)malloc(sizeof(int*) * m); for (int i 0; i m; i) { visited[i] (int*)malloc(sizeof(int) * n); for (int j 0; j n; j) { visited[i][j] 0; } } int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (islt(arr, visited, i, j, m, n) ! 0) { count; } } } printf(%d\n, count); }2.核心 二维数组在内存里就是连续存放的一维块“跨行” 本质上就是指针偏移一行的元素总数列数 个位置这正是理解数组指针遍历的核心。// 定义3行4列的二维数组 int arr[3][4] { {1, 2, 3, 4}, {2, 4, 6, 8}, {3, 6, 9, 12} };// 正确声明数组指针p指向arr的第一行int[4]类型 int (*p)[4] arr;通过双循环用指针访问数组的每一个元素 有3种方式理解for (int i 0; i 3; i) { // 内层循环遍历列j从0到3对应4列 for (int j 0; j 4; j) { // 核心访问方式通过指针p访问arr[i][j] // 方式1最贴合指针本质的写法推荐理解 int value *(*(p i) j); // 方式2简化写法等价于方式1推荐实际使用 // int value (p i)[j]; // 方式3和普通数组写法一致完全等价 // int value p[i][j]; printf(arr[%d][%d] %d\t, i, j, value); } printf(\n); // 每行结束换行 }int (*p)[4]是指向包含 4 个 int 元素的一维数组的指针正好匹配二维数组arr的每一行核心逻辑拆解p指向arr的第 0 行首行p i指针偏移i行指向arr的第i行*(p i)解引用得到第i行的首地址等价于arr[i]*(p i) j在第i行的基础上偏移j列指向arr[i][j]的地址*(*(p i) j)最终解引用得到arr[i][j]的值。补充p[i][j]是 C 语言的语法糖完全等价于*(*(p i) j)写法更简洁实际开发中更常用相当于直接把指针p当二维数组名称arr用数组名是一个 “指向数组首元素的常量指针可以通过数组名偏移再解引用来遍历数组元素3.卷积操作data.txt:1 2 3 4 5 6 7 8 9 1 0 0 1原始特征矩阵为3*3卷积核为2*2步长为1没有padding时步长从0到1和卷积核规模一致发现最后输出与卷积核尺寸一致tips: 一般是4个for循环解决两两一组一组遍历输出结果每个位置一组遍历卷积核元素、特征图中对应元素相乘相加得到的结果存入结果位置 !void main() { int arr[3][3]; int core[2][2]; FILE* in fopen(data.txt, r); for (int i 0; i 3; i) { for (int j 0; j 3; j) { fscanf(in, %d, arr[i][j]); } } for (int i 0; i 2; i) { for (int j 0; j 2; j) { fscanf(in, %d, core[i][j]); } } // 求卷积 int res[2][2]{0}; for (int i 0; i 2; i) { for (int j 0; j 2; j) { for (int a 0; a 2; a) { for (int b 0; b 2; b) { // 固定套路卷积核的每个元素跟步长一样 res[i][j] core[a][b] * arr[i a][j b]; } } } } for (int i 0; i 2; i) { for (int j 0; j 2; j) { printf(%d , res[i][j]); } printf(\n); } fclose(in); }4.复习PAT 1050题 螺旋顺时针按降序填充矩阵关键点越界或已经填充过时通过方向数组d(d1)%4取模因为右下左上4个方向来改变转向实现顺时针向内旋转从而从00位置出发填充完整个矩阵5.复习PAT 1068题 邻近点像素差且唯一通过8行2列即不包含自身的方向数组去遍历周围8个邻近位置关于函数接收二维数组时注意区分该二维数组是否是连续存储还是二维指针数组如果是二维指针数组可以用int**类型去接收然后arr[i][j]就能访问了6.矩阵乘法注意不是卷积如矩阵A为m*n型、矩阵B为n*k型A*B得到矩阵C为m*k型核心逻辑通过三层嵌套循环实现外层循环遍历 C的行对应也为矩阵A 的行 // i中层循环遍历 C 的列对应也为矩阵B 的列// j内层循环遍历 A 的列也是B 的行二者一定要相等才能作乘法累加计算 C 中每个元素的值 // kfor (int i 0; i m; i) { for (int j 0; j k; j) { int sum 0; for (int k 0; k n; k) { sum A[i][k] * B[k][j]; } C[i][j] sum; } }7.对于一个二维字符数组构成的汉字/图形要想倒过来福倒了把遍历方式换成从最后一行最后一列向前遍历即可8.hot100合并区间思路1.以区间的起始值start为关键字对所有区间升序排序(防止漏掉、重复)2.定义创建一个结果数组先将排序后的第一个区间加入结果作为初始合并区间3.定义一个变量last_end记录最近一次的区间的右端点4.从第二个区间开始遍历排序后的区间如果当前区间的左端点 last_end则结果数组的len不用1,只需要取res[len][1]max(last_end,arr[i][1])修改结果中区间的右端点如果当前区间的左端点 last_end则结果数组memcpy(res[len], arr[i], sizeof(int) * 2);加入新区间到结果中9.洛谷模拟实现矩阵的顺时针、逆时针旋转90度// 反转一维数组用于反转列时提取列元素 void reverse(int* arr, int len) { int l 0, r len - 1; while (l r) { int temp arr[l]; arr[l] arr[r]; arr[r] temp; l; r--; } } void xz(int** arr, int n,int z) { // 先转置 for (int i 0; i n; i) { 注意只需要遍历上三角矩阵对角线以外的元素作交换就完成转置了 如果遍历全部元素相当于交换两次又还原了没有交换 for (int j i1; j n; j) { int temp arr[i][j]; arr[i][j] arr[j][i]; arr[j][i] temp; } } if (z) { // 逆时针旋转90度 //再反转每列 int* temp (int*)malloc(sizeof(int) * n); for (int i 0; i n; i) { int count 0; for (int j 0; j n; j) { temp[count] arr[j][i]; } reverse(temp, n); for (int j 0; j n; j) { arr[j][i] temp[j]; } } } else { // 顺时针旋转90度 //再反转每行 for (int i 0; i n; i) { reverse(arr[i], n); } } } void main() { int n, m;// n是方阵规模、m是操作次数 scanf(%d %d, n, m); int** arr (int**)malloc(sizeof(int*) * n); int tc 0; for (int i 0; i n; i) { arr[i] (int*)malloc(sizeof(int) * n); for (int j 0; j n; j) { arr[i][j] tc; } } //int x, y, r, z; int z; for (int i 0; i m; i) { //scanf(%d %d %d %d, x, y, r, z); scanf(%d, z); xz(arr, n,z); for (int j 0; j n; j) { for (int k 0; k n; k) { printf(%d , arr[j][k]); } printf(\n); } } }10.复习pgcode 川大 单词方阵对周围8个方向每个方向连续深入4次进行比较的思路直接用for a控制次数并把a当作数组索引参与比较for (int k 0; k 8; k) { // 8个方向每个方向最多匹配4次 int x i; int y j; int flag 1; for (int a 0; a 4; a) { x dir[k][0]; y dir[k][1]; if (s[x][y] ! hx[a]) { flag 0; // 不匹配 break; } } if (flag) { // 匹配 x i; y j; for (int a 0; a 4; a) { x dir[k][0]; y dir[k][1]; visited[x][y] 1; // 需要保留 visited[i][j] 1; } } }另外注意细节可以把visited数组写成全局变量这样就不用在函数参数里面传来传去!
二、矩阵，整型二维数组操作
写在开头二维指针数组和普通二维数组的区别只是行之间不连续存放按照相同的方式访问就行对于一维数组模拟的二维数组需要人工计算索引转换去访问二维数组的元素能不用就不用1. 矩阵连通读取一个 ×N×N 矩阵3≤≤203≤N≤20和一个坐标 (,)(x,y)行列索引均从1开始计算该坐标对应值的连接数。连接规则如下从 (,)(x,y) 出发与其值相同且四方向相邻上下左右的元素视为连接递归遍历所有连接元素的相邻位置统计总连接数含自身。原题为从txt文件读入输入格式首行为整数 N表示矩阵维度后续 N 行为矩阵元素每行包含 N 个整数以空格分隔最后一行包含两个整数 x 和 y以空格分隔代码实现自己写的:与常规周围位置的方向数组的区别题目要求从左上开始按顺时针螺旋即右下左上4个方向一循环定义direct[4][2]分别为这个方向的方向数组然后和常规题目一样先填充再根据方向数组计算下一个位置是否合法不合法则说明此方向上已经到边界了需要改变到下一个方向按顺时针即d(d1)%4法一#include stdio.h #include stdlib.h int isconnect(int N,int* arr, int i, int j,int* visited); void main() { int N; scanf(%d, N); int* arr (int*)malloc(sizeof(int) * N * N); //int型可以用一维数组指针模拟二维数组 int* visited (int*)malloc(sizeof(int) * N * N); for (int i 0; i N; i) { for (int j 0; j N; j) { scanf(%d, arr[i*Nj]); visited[i * N j] 0; } } int x, y; scanf(%d %d, x, y); int i x - 1; //注意这里的处理传入从0开始的索引方便计算 int j y - 1; int count isconnect(N, arr, i, j, visited); printf(%d\n, count); free(arr); free(visited); } int isconnect(int N, int* arr, int i, int j, int* visited) { if (visited[i * N j]) { return 0; } visited[i * N j] 1; //先标记已访问后面递归到该元素时就不会重复统计 int temp arr[i * N j]; int a 0; //int a; 只有作为「全局变量」或「静态局部变量static int a;」时才会自动 // 初始化为 0作为「局部自动变量」函数内直接 int a;时是内存随机垃圾值 int b 0; int c 0; int d 0; if (i - 1 0 ) { //边界不满足不存在则跳过存在才比较值是否相同 if (arr[(i - 1) * N j] temp) { a isconnect(N, arr, i - 1, j, visited); } } if (i 1 N) { if (arr[(i 1) * N j] temp) { b isconnect(N, arr, i 1, j, visited); } } if (j - 1 0 ) { if (arr[i * N j - 1] temp) { c isconnect(N, arr, i, j - 1, visited); } } if (j 1 N) { if (arr[i * N j 1] temp) { d isconnect(N, arr, i, j 1, visited); } } return 1abcd; //这里的1是传入的这个元素本身也算上 // 再加上周围4个位置上的连通数量这4个位置再递归统计它们各自的周围4个位置 }法二推荐int dir[4][2] { // 左、上、右、下 {0,-1}, {-1,0}, {0,1}, {1,0} }; int islt(int** arr, int** visited, int x, int y,int m,int n) { if (visited[x][y]) return 0; if (!arr[x][y]) { visited[x][y] 1; return 0; } // 当前位置是1了 int sum 1; visited[x][y] 1; for (int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; if (nx 0 nx m !visited[nx][ny]) { sumislt(arr, visited, nx, ny, m, n); } } return sum; } void main() { int m, n; scanf(%d %d, m, n); int** arr (int**)malloc(sizeof(int*) * m); for (int i 0; i m; i) { arr[i] (int*)malloc(sizeof(int) * n); for (int j 0; j n; j) { scanf(%d, arr[i][j]); } } // 初始化visited数组 int** visited (int**)malloc(sizeof(int*) * m); for (int i 0; i m; i) { visited[i] (int*)malloc(sizeof(int) * n); for (int j 0; j n; j) { visited[i][j] 0; } } int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (islt(arr, visited, i, j, m, n) ! 0) { count; } } } printf(%d\n, count); }2.核心 二维数组在内存里就是连续存放的一维块“跨行” 本质上就是指针偏移一行的元素总数列数 个位置这正是理解数组指针遍历的核心。// 定义3行4列的二维数组 int arr[3][4] { {1, 2, 3, 4}, {2, 4, 6, 8}, {3, 6, 9, 12} };// 正确声明数组指针p指向arr的第一行int[4]类型 int (*p)[4] arr;通过双循环用指针访问数组的每一个元素 有3种方式理解for (int i 0; i 3; i) { // 内层循环遍历列j从0到3对应4列 for (int j 0; j 4; j) { // 核心访问方式通过指针p访问arr[i][j] // 方式1最贴合指针本质的写法推荐理解 int value *(*(p i) j); // 方式2简化写法等价于方式1推荐实际使用 // int value (p i)[j]; // 方式3和普通数组写法一致完全等价 // int value p[i][j]; printf(arr[%d][%d] %d\t, i, j, value); } printf(\n); // 每行结束换行 }int (*p)[4]是指向包含 4 个 int 元素的一维数组的指针正好匹配二维数组arr的每一行核心逻辑拆解p指向arr的第 0 行首行p i指针偏移i行指向arr的第i行*(p i)解引用得到第i行的首地址等价于arr[i]*(p i) j在第i行的基础上偏移j列指向arr[i][j]的地址*(*(p i) j)最终解引用得到arr[i][j]的值。补充p[i][j]是 C 语言的语法糖完全等价于*(*(p i) j)写法更简洁实际开发中更常用相当于直接把指针p当二维数组名称arr用数组名是一个 “指向数组首元素的常量指针可以通过数组名偏移再解引用来遍历数组元素3.卷积操作data.txt:1 2 3 4 5 6 7 8 9 1 0 0 1原始特征矩阵为3*3卷积核为2*2步长为1没有padding时步长从0到1和卷积核规模一致发现最后输出与卷积核尺寸一致tips: 一般是4个for循环解决两两一组一组遍历输出结果每个位置一组遍历卷积核元素、特征图中对应元素相乘相加得到的结果存入结果位置 !void main() { int arr[3][3]; int core[2][2]; FILE* in fopen(data.txt, r); for (int i 0; i 3; i) { for (int j 0; j 3; j) { fscanf(in, %d, arr[i][j]); } } for (int i 0; i 2; i) { for (int j 0; j 2; j) { fscanf(in, %d, core[i][j]); } } // 求卷积 int res[2][2]{0}; for (int i 0; i 2; i) { for (int j 0; j 2; j) { for (int a 0; a 2; a) { for (int b 0; b 2; b) { // 固定套路卷积核的每个元素跟步长一样 res[i][j] core[a][b] * arr[i a][j b]; } } } } for (int i 0; i 2; i) { for (int j 0; j 2; j) { printf(%d , res[i][j]); } printf(\n); } fclose(in); }4.复习PAT 1050题 螺旋顺时针按降序填充矩阵关键点越界或已经填充过时通过方向数组d(d1)%4取模因为右下左上4个方向来改变转向实现顺时针向内旋转从而从00位置出发填充完整个矩阵5.复习PAT 1068题 邻近点像素差且唯一通过8行2列即不包含自身的方向数组去遍历周围8个邻近位置关于函数接收二维数组时注意区分该二维数组是否是连续存储还是二维指针数组如果是二维指针数组可以用int**类型去接收然后arr[i][j]就能访问了6.矩阵乘法注意不是卷积如矩阵A为m*n型、矩阵B为n*k型A*B得到矩阵C为m*k型核心逻辑通过三层嵌套循环实现外层循环遍历 C的行对应也为矩阵A 的行 // i中层循环遍历 C 的列对应也为矩阵B 的列// j内层循环遍历 A 的列也是B 的行二者一定要相等才能作乘法累加计算 C 中每个元素的值 // kfor (int i 0; i m; i) { for (int j 0; j k; j) { int sum 0; for (int k 0; k n; k) { sum A[i][k] * B[k][j]; } C[i][j] sum; } }7.对于一个二维字符数组构成的汉字/图形要想倒过来福倒了把遍历方式换成从最后一行最后一列向前遍历即可8.hot100合并区间思路1.以区间的起始值start为关键字对所有区间升序排序(防止漏掉、重复)2.定义创建一个结果数组先将排序后的第一个区间加入结果作为初始合并区间3.定义一个变量last_end记录最近一次的区间的右端点4.从第二个区间开始遍历排序后的区间如果当前区间的左端点 last_end则结果数组的len不用1,只需要取res[len][1]max(last_end,arr[i][1])修改结果中区间的右端点如果当前区间的左端点 last_end则结果数组memcpy(res[len], arr[i], sizeof(int) * 2);加入新区间到结果中9.洛谷模拟实现矩阵的顺时针、逆时针旋转90度// 反转一维数组用于反转列时提取列元素 void reverse(int* arr, int len) { int l 0, r len - 1; while (l r) { int temp arr[l]; arr[l] arr[r]; arr[r] temp; l; r--; } } void xz(int** arr, int n,int z) { // 先转置 for (int i 0; i n; i) { 注意只需要遍历上三角矩阵对角线以外的元素作交换就完成转置了 如果遍历全部元素相当于交换两次又还原了没有交换 for (int j i1; j n; j) { int temp arr[i][j]; arr[i][j] arr[j][i]; arr[j][i] temp; } } if (z) { // 逆时针旋转90度 //再反转每列 int* temp (int*)malloc(sizeof(int) * n); for (int i 0; i n; i) { int count 0; for (int j 0; j n; j) { temp[count] arr[j][i]; } reverse(temp, n); for (int j 0; j n; j) { arr[j][i] temp[j]; } } } else { // 顺时针旋转90度 //再反转每行 for (int i 0; i n; i) { reverse(arr[i], n); } } } void main() { int n, m;// n是方阵规模、m是操作次数 scanf(%d %d, n, m); int** arr (int**)malloc(sizeof(int*) * n); int tc 0; for (int i 0; i n; i) { arr[i] (int*)malloc(sizeof(int) * n); for (int j 0; j n; j) { arr[i][j] tc; } } //int x, y, r, z; int z; for (int i 0; i m; i) { //scanf(%d %d %d %d, x, y, r, z); scanf(%d, z); xz(arr, n,z); for (int j 0; j n; j) { for (int k 0; k n; k) { printf(%d , arr[j][k]); } printf(\n); } } }10.复习pgcode 川大 单词方阵对周围8个方向每个方向连续深入4次进行比较的思路直接用for a控制次数并把a当作数组索引参与比较for (int k 0; k 8; k) { // 8个方向每个方向最多匹配4次 int x i; int y j; int flag 1; for (int a 0; a 4; a) { x dir[k][0]; y dir[k][1]; if (s[x][y] ! hx[a]) { flag 0; // 不匹配 break; } } if (flag) { // 匹配 x i; y j; for (int a 0; a 4; a) { x dir[k][0]; y dir[k][1]; visited[x][y] 1; // 需要保留 visited[i][j] 1; } } }另外注意细节可以把visited数组写成全局变量这样就不用在函数参数里面传来传去!
