Loading... # 对 C++ 二维数组的理解 ## 二维数组的定义 二维数组在数学上对应的概念是矩阵,我们可以这样定义三阶单位矩阵。 ```cpp int matrix0[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; int matrix1[][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; int matrix2[3][3] = {1, 0, 0, 0, 1, 0, 0, 0, 1}; ``` 二维数组在逻辑上相当于一个二级指针,但和一维数组不同,二维数组不能直接当作二级指针,以下定义 `p0` 和 `p1` 均是错误的,而方式三是正确的。 ```cpp int** p0 = matrix0; int** p1 = &matrix0; int* p2 = *matrix0; ``` ## 二维数组的存储 二维数组是一个非线性的数据结构,而内存的空间的线性的,一种解决方案就是保持元素的顺序不变,把二维数组中所有的元素按顺序存储在一块连续的空间里,就像一维数组这样。事实上 C++ 也正是这样做的。 我们首先需要说明元素的顺序,在 C++ 中,这里我不想介绍“高维优先”的存储规则,我们只需要一个例子就可以明白数组的存储方式: ```cpp int matrix[2][3] = {{0,1,2},{3,4,5}}; // 等价于 {0,1,2,3,4,5} ``` 其中 `012345` 在内存中占据一块连续的空间。 ## 二维数组的访问 ### 下标访问 - 访问元素 下标访问很简单,对于上面定义的数组,只需要 `matrix0[i][j]` 即可,其中 `i`、`j` 分别是矩阵的行和列。 根据上面提到的二维数组的存储,我们知道 `matrix0[i][j]` 实际上等价于 `*(*matrix0 + i + j * 3)`,这样我们也很可以理解为什么数组定义中最高维的大小是可以省略的。因为我们在访问数组中的元素的时候,其实我们不需要最高维的大小来计算元素位置的偏移量。 - 访问子数组 例如我们获取矩阵的第二行 `matrix0[1]`,结果是一个长度为三的一维数组。 根据二维数组的存储原理,如果我们把允许用 `int*` 代表一维数组的话,上述语句等价为 `*matrix0 + 1*3`,这里我们也可以从另一个方面列举为什么二维数组除了最高维的大小外,其他不能省略。 ### 指针访问 以指针方式访问二维数组的方式是多样的,例如下面语句都是 `matrix0[i][j]` 的等价表达。 ```cpp *(matrix0[0] * i + j * 3); *(*matrix0 * i + j * 3); *(&matrix0[0][0] * i + j * 3); ``` 当二维数组大小不定时,以用指针方式访问很有用处。 ## 动态创建二维数组 所有动态创建二维数组,指的是二维数组的大小在编译时时未确定的。 C++ 不允许以一维数组的方式直接创建动态数组,例如 `int** matrix = new int[n][n]` 是不合法的,我们需要采用间接的方式。 ### 指针数组 <div class="tip inlineBlock info"> 数组指针和指针数组的区别:https://blog.csdn.net/mick_hu/article/details/100931034 </div> 例如我们需要创建 `matrix[n][m]` 这样一个二维数组,我们可以先创建一个长度为 `n` 的指针数组,把数组指针作为元素放入指针数组中。 ```cpp // 创建 int** matrix = new int*[n]; for(int i=0;i<n;i++) { matrix[i] = new int[m]; } // 访问 matrix[i][j] int r = *(*matrix + j * m + i); // 删除 for(int i=0;i<n;i++) { delete []matrix[i]; } delete[] matrix; ``` ### 用一维数组模拟二维数组 如果我们能理解动态数组申请的本质——申请一块内存空间,事实上我们完全可以用一个一维数组模拟一个二维数组。 ```cpp // 创建 int* matrix = new int[n*m]; // 访问 matrix[i][j] int r = *(matrix + j * m + i); // 删除 delete[] matrix; ``` ### 两种方式的区别 从内存空间分配方式上,第一种方式不保证所有元素存储在一片连续的内存区域中,而是最多可能存储在 `m` 块区域中,第二种方式保证所有元素连续存储;从效率上看,第二种方式效率会更高,因为创建、访问、删除所需要的操作数更少,而且数据存储在一块连续的区域中;从代码的角度上看,第二种方式更简洁。所以在大多数情况下,我更倾向于第二种方式。 ### 一个例子 <div class="tip inlineBlock info"> 其实是博主的C++ 作业 </div> (程序设计) 编写以下函数: (1)在一个二维数组中形成以下形式的n阶矩阵: $$ \left( \begin{matrix} 1&1&1&1&1 \\ 2&1&1&1&1 \\ 3&2&1&1&1 \\ 4&3&2&1&1 \\ 5&4&3&2&1 \end{matrix} \right) $$ (2)去掉靠边的元素,生成新的n-2阶矩阵; (3)求矩阵主对角线下元素之和; (4)以方阵形式输出数组。 ```cpp #include <iostream> #include <iomanip> /** 创建矩阵 */ void create(int *&array, int n); /** 输出矩阵 */ void println(int *&array, int n); /** (n-2)阶子矩阵 */ void sub(int *&array, int n); /** 求主对角线的元素和并输出 */ void sum(int *&array, int n); /** 访问矩阵i行j列位置的元素,ij从0开始 */ inline int* access(int *&array, int n, int i, int j); using namespace std; int main(int argc, char** argv) { int* p; // matrix int n; cout << "请输入矩阵的阶数: "; cin >> n; create(p, n); cout << endl << "成功创建矩阵: " << endl; println(p, n); sum(p, n); cout << endl << endl; sub(p, n); cout << "(n-2)阶新矩阵为: " << endl; println(p, n-2); sum(p, n-2); return 0; } int* access(int *&array, int n, int i, int j) { return array + i * n + j; } void create(int *&array, int n) { array = new int[n * n]; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { int* p = access(array, n, i, j); if (i <= j) { *p = 1; } else { *p = i - j + 1; } } } } void println(int *&array, int n) { cout << endl; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cout << setw(5) << *access(array, n, i, j); } cout << endl << endl; } } void sub(int *&array, int n) { int *p = new int[(n-2)*(n-2)]; for(int i=1;i<n-1;i++) { for(int j=1;j<n-1;j++) { *access(p, n-2, i-1, j-1) = *access(array, n, i, j); } } delete[] array; // prevent memory leaks array = p; } void sum(int *&array, int n) { int total = 0; for(int i=0;i<n;i++) { for(int j=0;j<i;j++) { total += *access(array, n, i, j); } } cout << "矩阵主对角线下方的元素和为: " << total << endl; } ``` 最后修改:2020 年 05 月 11 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用,请随意赞赏