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

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

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

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

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

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

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

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

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

這種按照行優(yōu)先方式存儲(chǔ)多維數(shù)組的原理使得訪問連續(xù)內(nèi)存位置的元素更加高效，因?yàn)樗浞掷昧爽F(xiàn)代計(jì)算機(jī)的緩存機(jī)制，可以減少內(nèi)存訪問的開銷。同時(shí)，它也意味著多維數(shù)組的元素在內(nèi)存中是連續(xù)存儲(chǔ)的，這對(duì)于訪問大量數(shù)據(jù)的性能非常重要。

代碼講解使用方式

#include <stdio.h>int main() {// 定義一個(gè)二維數(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]; // 定義一個(gè)指向第一個(gè)元素的指針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); // 計(jì)算偏移并解引用指針printf("%d ", element);  //指針遍歷方法printf("%d ", matrix[i][j]); // 數(shù)組下標(biāo)遍歷方法}printf("\n");}return 0;
}

原理解釋：

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

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

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

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

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

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

在Linux64系統(tǒng)下，我們知道一個(gè)int類型的大小是4bit。
那么假設(shè)我們的數(shù)組的第一個(gè)元素的起始地址為0x00，那么第一個(gè)元素應(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)

但是為什么我們?cè)谑褂弥羔槺闅v的時(shí)候，寫法是：

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

根據(jù)這個(gè)計(jì)算方式，我們?cè)诘谝恍兄械玫揭韵缕?#xff1a;

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不太一樣，為什么呢？

這是因?yàn)?ptr 是一個(gè)指向 int 類型的指針，它的增量是 sizeof(int) 字節(jié)，因此每次移動(dòng)一個(gè) int 的大小（通常是4字節(jié)）。這正是為什么我們?cè)谟?jì)算偏移時(shí)只需要考慮 i 和 j，而不需要考慮元素的物理大小。

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

使用場(chǎng)景

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

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

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

• 矩陣運(yùn)算： 線性代數(shù)中的矩陣運(yùn)算和矩陣乘法通常需要使用多維數(shù)組表示。例如，計(jì)算機(jī)圖形學(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é)點(diǎn)和邊的關(guān)系。例如，圖的鄰接矩陣或鄰接列表（圖是最經(jīng)典的用多維數(shù)組的方法了）。

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

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

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

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

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