什么是多維數(shù)組？

在C語言中，多維數(shù)組的存儲實際上是在內(nèi)存中按照一維數(shù)組的方式連續(xù)存儲數(shù)據(jù)的。多維數(shù)組的底層原理可以理解為是一維數(shù)組的擴展。每個維度的大小（元素個數(shù)）決定了存儲空間的布局。

考慮一個二維數(shù)組的例子，例如int arr[3][4]，表示一個3行4列的整數(shù)數(shù)組。底層存儲原理如下：

首先，內(nèi)存中會分配一個連續(xù)的存儲空間，大小為3 * 4 * sizeof(int)字節(jié)，其中sizeof(int)表示一個整數(shù)占用的字節(jié)數(shù)。

數(shù)組的元素在內(nèi)存中按照行優(yōu)先（C語言的約定）方式存儲，也就是說，首先存儲第一行的所有元素，然后是第二行的所有元素，以此類推。

如果我們想訪問數(shù)組的某個元素，例如arr[1][2]，系統(tǒng)會通過內(nèi)存偏移計算來找到對應(yīng)的位置。在這個例子中，偏移計算如下：

偏移 = 行號 * 每行的元素個數(shù) + 列號
偏移 = 1 * 4 + 2 = 6

這意味著arr[1][2]的數(shù)據(jù)存儲在偏移地址6的位置上。

多維數(shù)組的每個維度的大小（行數(shù)和列數(shù)等）會影響內(nèi)存布局和偏移計算。例如，如果有一個三維數(shù)組int arr[2][3][4]，那么在內(nèi)存中會按照一維數(shù)組的形式存儲，同時需要考慮三個維度的大小來計算偏移。

這種按照行優(yōu)先方式存儲多維數(shù)組的原理使得訪問連續(xù)內(nèi)存位置的元素更加高效，因為它充分利用了現(xiàn)代計算機的緩存機制，可以減少內(nèi)存訪問的開銷。同時，它也意味著多維數(shù)組的元素在內(nèi)存中是連續(xù)存儲的，這對于訪問大量數(shù)據(jù)的性能非常重要。

代碼講解使用方式

#include <stdio.h>int main() {// 定義一個二維數(shù)組，表示3行4列的矩陣int matrix[3][4] = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12}};// 使用指針遍歷多維數(shù)組int *ptr = &matrix[0][0]; // 定義一個指向第一個元素的指針printf("遍歷多維數(shù)組的元素：\n");for (int i = 0; i < 3; i++) {for (int j = 0; j < 4; j++) {// 使用指針訪問當(dāng)前元素int element = *(ptr + i * 4 + j); // 計算偏移并解引用指針printf("%d ", element);  //指針遍歷方法printf("%d ", matrix[i][j]); // 數(shù)組下標(biāo)遍歷方法}printf("\n");}return 0;
}

原理解釋：

1. 我們首先定義了一個二維數(shù)組 int matrix[3][4]，表示一個3行4列的矩陣。

2. 然后，我們定義一個指針 int *ptr 并將其初始化為指向數(shù)組的第一個元素，也就是 matrix[0][0]。在C語言中，多維數(shù)組在內(nèi)存中是按照一維數(shù)組的方式連續(xù)存儲的，因此我們可以使用指針來遍歷多維數(shù)組。

3. 接下來，我們使用兩個嵌套的循環(huán)來遍歷多維數(shù)組的元素。外層循環(huán)控制行，內(nèi)層循環(huán)控制列。

4. 在循環(huán)中，我們使用指針 ptr 來訪問當(dāng)前元素。為了計算當(dāng)前元素的偏移，我們使用了 i * 4 + j 的方式，其中 i 表示當(dāng)前行數(shù)，j 表示當(dāng)前列數(shù)。這是因為在二維數(shù)組中，每行有4個元素。

5. 我們通過 *(ptr + i * 4 + j) 來解引用指針，從而獲取當(dāng)前元素的值，并使用 printf 函數(shù)打印出來。

為什么指針遍歷的方式是這樣子的？（助你理解指針的含義）

在Linux64系統(tǒng)下，我們知道一個int類型的大小是4bit。
那么假設(shè)我們的數(shù)組的第一個元素的起始地址為0x00，那么第一個元素應(yīng)該是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); // 計算偏移并解引用指針

根據(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) 字節(jié)，因此每次移動一個 int 的大小（通常是4字節(jié)）。這正是為什么我們在計算偏移時只需要考慮 i 和 j，而不需要考慮元素的物理大小。

所以，偏移是按照指針的增量來計算的，而不是根據(jù)元素的物理大小。這種方式使得多維數(shù)組的遍歷更加通用，不受元素大小的影響。

使用場景

多維數(shù)組是一種在程序中組織和存儲數(shù)據(jù)的重要數(shù)據(jù)結(jié)構(gòu)，它可以用于解決各種問題，具有廣泛的應(yīng)用場景。以下是多維數(shù)組的一些常見作用和使用場景，以及一些例子：

• 矩陣和二維數(shù)據(jù)的表示： 多維數(shù)組通常用于表示矩陣、表格和類似的二維數(shù)據(jù)結(jié)構(gòu)。例如，圖像處理中的像素矩陣、棋盤游戲的棋盤狀態(tài)、二維地圖等。

• 多維數(shù)據(jù)的存儲和處理： 多維數(shù)組可以用于存儲和處理具有多個維度的數(shù)據(jù)。例如，科學(xué)和工程領(lǐng)域中的多維數(shù)據(jù)集，如立體圖像數(shù)據(jù)、聲音信號、氣象數(shù)據(jù)等（當(dāng)然，考研你肯定處理不到這玩意，我寫代碼可能用得到）。

• 矩陣運算： 線性代數(shù)中的矩陣運算和矩陣乘法通常需要使用多維數(shù)組表示。例如，計算機圖形學(xué)中的矩陣變換和投影（算法題經(jīng)常需要用到矩陣變換）。

嵌套結(jié)構(gòu)： 多維數(shù)組可以用于表示嵌套結(jié)構(gòu)的數(shù)據(jù)，例如多層的樹形結(jié)構(gòu)或多層的地理數(shù)據(jù)。

圖和網(wǎng)絡(luò)算法： 圖和網(wǎng)絡(luò)算法通常使用多維數(shù)組來表示節(jié)點和邊的關(guān)系。例如，圖的鄰接矩陣或鄰接列表（圖是最經(jīng)典的用多維數(shù)組的方法了）。

游戲開發(fā)： 多維數(shù)組常用于游戲開發(fā)中的地圖、迷宮、游戲棋盤、角色位置等（迷宮算法以及路徑算法也都會用到）。

動態(tài)規(guī)劃： 動態(tài)規(guī)劃算法中，多維數(shù)組常用于存儲中間計算結(jié)果，以解決優(yōu)化問題，如最短路徑、最長公共子序列等（最常見的還是在動態(tài)規(guī)劃中）。

空間和時間復(fù)雜度優(yōu)化： 多維數(shù)組可以用于優(yōu)化數(shù)據(jù)訪問和算法性能。例如，在一些計算密集型任務(wù)中，多維數(shù)組的合理使用可以降低時間復(fù)雜度。

408考研各數(shù)據(jù)結(jié)構(gòu)C/C++代碼（Continually updating）

408考研各數(shù)據(jù)結(jié)構(gòu)C/C++代碼（Continually updating）
這個模塊是我應(yīng)一些朋友的需求，希望我能開一個專欄，專門提供考研408中各種常用的數(shù)據(jù)結(jié)構(gòu)的代碼，并且希望我附上比較完整的注釋以及提供用戶輸入功能，ok，fine，這個專欄會一直更新，直到我認(rèn)為沒有新的數(shù)據(jù)結(jié)構(gòu)可以講解了。
目前我比較熟悉的數(shù)據(jù)結(jié)構(gòu)如下：
數(shù)組、鏈表、隊列、棧、樹、B/B+樹、紅黑樹、Hash、圖。
所以我會先有空更新出如下幾個數(shù)據(jù)結(jié)構(gòu)的代碼，歡迎關(guān)注。 當(dāng)然，在我前兩年的博客中，對于鏈表、哈夫曼樹等常用數(shù)據(jù)結(jié)構(gòu)，我都提供了比較完整的詳細(xì)的實現(xiàn)以及思路講解，有興趣可以去考古。