【数据结构C/C++】多维数组的原理、访问方式以及作用

什么是多维数组？

在C语言中，多维数组的存储实际上是在内存中按照一维数组的方式连续存储数据的。多维数组的底层原理可以理解为是一维数组的扩展。每个维度的大小（元素个数）决定了存储空间的布局。

考虑一个二维数组的例子，例如int arr[3][4]，表示一个3行4列的整数数组。底层存储原理如下：

首先，内存中会分配一个连续的存储空间，大小为3 * 4 * sizeof(int)字节，其中sizeof(int)表示一个整数占用的字节数。

数组的元素在内存中按照行优先（C语言的约定）方式存储，也就是说，首先存储第一行的所有元素，然后是第二行的所有元素，以此类推。

如果我们想访问数组的某个元素，例如arr[1][2]，系统会通过内存偏移计算来找到对应的位置。在这个例子中，偏移计算如下：

偏移 = 行号 * 每行的元素个数 + 列号
偏移 = 1 * 4 + 2 = 6

这意味着arr[1][2]的数据存储在偏移地址6的位置上。

多维数组的每个维度的大小（行数和列数等）会影响内存布局和偏移计算。例如，如果有一个三维数组int arr[2][3][4]，那么在内存中会按照一维数组的形式存储，同时需要考虑三个维度的大小来计算偏移。

这种按照行优先方式存储多维数组的原理使得访问连续内存位置的元素更加高效，因为它充分利用了现代计算机的缓存机制，可以减少内存访问的开销。同时，它也意味着多维数组的元素在内存中是连续存储的，这对于访问大量数据的性能非常重要。

代码讲解使用方式

#include <stdio.h>int main() {// 定义一个二维数组，表示3行4列的矩阵int matrix[3][4] = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12}};// 使用指针遍历多维数组int *ptr = &matrix[0][0]; // 定义一个指向第一个元素的指针printf("遍历多维数组的元素：\n");for (int i = 0; i < 3; i++) {for (int j = 0; j < 4; j++) {// 使用指针访问当前元素int element = *(ptr + i * 4 + j); // 计算偏移并解引用指针printf("%d ", element);  //指针遍历方法printf("%d ", matrix[i][j]); // 数组下标遍历方法}printf("\n");}return 0;
}

原理解释：

1. 我们首先定义了一个二维数组 int matrix[3][4]，表示一个3行4列的矩阵。

2. 然后，我们定义一个指针 int *ptr 并将其初始化为指向数组的第一个元素，也就是 matrix[0][0]。在C语言中，多维数组在内存中是按照一维数组的方式连续存储的，因此我们可以使用指针来遍历多维数组。

3. 接下来，我们使用两个嵌套的循环来遍历多维数组的元素。外层循环控制行，内层循环控制列。

4. 在循环中，我们使用指针 ptr 来访问当前元素。为了计算当前元素的偏移，我们使用了 i * 4 + j 的方式，其中 i 表示当前行数，j 表示当前列数。这是因为在二维数组中，每行有4个元素。

5. 我们通过 *(ptr + i * 4 + j) 来解引用指针，从而获取当前元素的值，并使用 printf 函数打印出来。

为什么指针遍历的方式是这样子的？（助你理解指针的含义）

在Linux64系统下，我们知道一个int类型的大小是4bit。
那么假设我们的数组的第一个元素的起始地址为0x00，那么第一个元素应该是0x04。也就是如下：

matrix[0][0] (地址0) matrix[0][1] (地址4) matrix[0][2] (地址8) matrix[0][3] (地址12)
matrix[1][0] (地址16) matrix[1][1] (地址20) matrix[1][2] (地址24) matrix[1][3] (地址28)
matrix[2][0] (地址32) matrix[2][1] (地址36) matrix[2][2] (地址40) matrix[2][3] (地址44)

但是为什么我们在使用指针遍历的时候，写法是：

 int element = *(ptr + i * 4 + j); // 计算偏移并解引用指针

根据这个计算方式，我们在第一行中得到以下偏移：

matrix[0][0] 的偏移是 i * 4 + j = 0 * 4 + 0 = 0。
matrix[0][1] 的偏移是 i * 4 + j = 0 * 4 + 1 = 1。
matrix[0][2] 的偏移是 i * 4 + j = 0 * 4 + 2 = 2。
matrix[0][3] 的偏移是 i * 4 + j = 0 * 4 + 3 = 3。

这看上去与我们上面写的地址是0，4，8不太一样，为什么呢？

这是因为 ptr 是一个指向 int 类型的指针，它的增量是 sizeof(int) 字节，因此每次移动一个 int 的大小（通常是4字节）。这正是为什么我们在计算偏移时只需要考虑 i 和 j，而不需要考虑元素的物理大小。

所以，偏移是按照指针的增量来计算的，而不是根据元素的物理大小。这种方式使得多维数组的遍历更加通用，不受元素大小的影响。

使用场景

多维数组是一种在程序中组织和存储数据的重要数据结构，它可以用于解决各种问题，具有广泛的应用场景。以下是多维数组的一些常见作用和使用场景，以及一些例子：

• 矩阵和二维数据的表示： 多维数组通常用于表示矩阵、表格和类似的二维数据结构。例如，图像处理中的像素矩阵、棋盘游戏的棋盘状态、二维地图等。

• 多维数据的存储和处理： 多维数组可以用于存储和处理具有多个维度的数据。例如，科学和工程领域中的多维数据集，如立体图像数据、声音信号、气象数据等（当然，考研你肯定处理不到这玩意，我写代码可能用得到）。

• 矩阵运算： 线性代数中的矩阵运算和矩阵乘法通常需要使用多维数组表示。例如，计算机图形学中的矩阵变换和投影（算法题经常需要用到矩阵变换）。

嵌套结构： 多维数组可以用于表示嵌套结构的数据，例如多层的树形结构或多层的地理数据。

图和网络算法： 图和网络算法通常使用多维数组来表示节点和边的关系。例如，图的邻接矩阵或邻接列表（图是最经典的用多维数组的方法了）。

游戏开发： 多维数组常用于游戏开发中的地图、迷宫、游戏棋盘、角色位置等（迷宫算法以及路径算法也都会用到）。

动态规划： 动态规划算法中，多维数组常用于存储中间计算结果，以解决优化问题，如最短路径、最长公共子序列等（最常见的还是在动态规划中）。

空间和时间复杂度优化： 多维数组可以用于优化数据访问和算法性能。例如，在一些计算密集型任务中，多维数组的合理使用可以降低时间复杂度。

408考研各数据结构C/C++代码（Continually updating）

408考研各数据结构C/C++代码（Continually updating）
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下：
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。