陣列（下）：資料結構中的陣列和程式語言中的陣列的區別

基本類別是什麼意思

在 2。1 節中，我們提到了陣列是儲存相同資料型別的一塊連續的儲存空間。解讀一下：數 組中的資料必須是相同型別的，陣列中的資料必須是連續儲存的。只有這樣，陣列才能實現根 據下標快速地訪問資料。 有些讀者可能會發現，在有些程式語言中，“陣列”這種資料型別並不一定完全符合上面 的定義。例如，在 JavaScript 中，陣列中的資料不一定是連續儲存的，也不一定是相同型別的， 甚至，陣列還可以是變長的。

var arr = new Array（4， ‘hello’， new Date（））；

在大部分關於資料結構和演算法的圖書中，在提到二維陣列或者多維陣列中資料的儲存方式 的時候，一般會這樣介紹：二維陣列中的資料以“先按行，再按列”（或者“先按列，再按行”） 的方式依次儲存在連續的儲存空間中。如果二維陣列定義為 a［n］［m］，那麼 a［i］［ j］ 的定址公式 如式（2-4）所示（以“先按行，再按列”的方式儲存）。

但是，在有些程式語言中，二維陣列並不滿足上面的定義，定址公式也並非如此。例如， Java 中的二維陣列的第二維可以是不同長度的，如下所示，而且第二維的 3 個數組（arr［0］、 arr［1］ 和 arr［2］）在記憶體中也並非連續儲存。

int arr［］［］ = new int［3］［］；arr［0］ = new int［1］；arr［1］ = new int［2］；arr［2］ = new int［3］；

難道有些關於資料結構和演算法的圖書裡的講解脫離實踐？難道程式語言中的陣列沒有完全 按照陣列的定義來設計？哪個對呢？ 實際上，這兩種講法都沒錯。程式語言中的“陣列”並不完全等同於我們在介紹資料結構 和演算法的時候提到的“陣列”。程式語言在實現自己的“陣列”型別的時候，並不是完全遵循 資料結構中“陣列”的定義，而是針對程式語言自身的特點，進行了相應的調整。 在不同的程式語言中，陣列這種資料型別的實現方式不大相同。本節利用幾種比較典型 的程式語言，如 C、C++、Java 和 JavaScript，向讀者介紹一下幾種比較有代表性的陣列實現 方式。

C/C++ 中陣列的實現方式

在 C/C++ 中實現的陣列完全符合資料結構中的陣列的標準定義，利用一塊連續的記憶體空 間儲存相同型別的資料。在 C/C++ 中，無論是基本的型別資料，如 int、long 和 char，還是結 構體、物件，在陣列中都是連續儲存的。我們透過例子來解釋一下。

int arr［3］；arr［0］ = 0；arr［1］ = 1；arr［2］ = 2；

在上面的程式碼中，陣列 arr 中儲存的是 int 型別的資料，對應 的記憶體儲存格式如圖 2-6 所示。從圖 2-6 中可以看出，資料儲存在一 塊連續的記憶體空間中。 在上面的例子中，陣列儲存的是基本型別資料，下面我們看一 下在利用陣列儲存物件（在 C 語言中，物件也稱結構體（struct））時，陣列在記憶體的儲存格式。

struct Dog { char a； char b；}；struct Dog arr［3］；arr［0］。a = ‘0’； arr［0］。b = ‘1’；arr［1］。a = ‘2’； arr［1］。b = ‘3’；arr［2］。a = ‘4’； arr［2］。b = ‘5’；

在上面的程式碼中，陣列 arr 在記憶體中的儲存格式如圖 2-7 所示，資料也是儲存在連續的 記憶體空間中的。 上面介紹的是一維陣列的儲存格式，下面介紹在 C/C++ 語言中多維陣列的儲存格式。注 意，多維陣列與二維陣列類似，我們就用二維陣列進行講解。我們看一下下面這段程式碼。

struct Dog { char a； char b；}；struct Dog arr［3］［2］；

在上面的程式碼中，struct Dog arr［3］［2］ 對應的儲存格式如圖 2-8 所示。從圖 2-8 中 可以發現，C/C++ 語言中的二維陣列與資料結構中的二維陣列是一樣的，資料是以“先按行， 再按列”的方式連續儲存的。

在上文中，我們分析了C/C++的基本資料型別陣列、物件（結構體）陣列，以及二維陣列， 它們的資料儲存格式完全符合資料結構中對陣列的定義。

Java 中陣列的實現方式

在介紹完 C/C++ 中的陣列後，下面看一下 Java 中的陣列。Java 中的陣列的實現並沒有完 全按照資料結構中陣列的定義。我們還是分 3 種情況來分析：基本資料型別陣列、物件陣列和 二維陣列（多維陣列）。 首先，我們先來看一下基本資料型別陣列，也就是說，陣列中儲存的是 int、long 和 char等基本資料型別的資料。我們還是利用一段程式碼來進行講解。

int arr［］ = new int［3］；arr［0］ = 0；arr［1］ = 1；arr［2］ = 2；

在上面的程式碼中，arr 陣列中的資料在記憶體中的儲存格式如圖 2-9 所示。注意，new 申請 的空間在堆中，arr 儲存在棧中。arr 儲存的是陣列空間的首地址。 從圖 2-9 可以看出，在 Java 中，基本資料型別陣列符合資料結構中陣列的定義。陣列中 的資料是相同型別的，並且儲存在連續的記憶體空間中。 在介紹完基本資料型別陣列後，我們再來看一下物件陣列，也就是說，陣列中儲存的不是 int、long 和 char 這些基本型別資料，而是物件。我們還是用一個例子來說明。

public class Person { private String name； public Person（String name） { this。name = name； }}Person arr［］ = new Person［3］；arr［0］ = new Person（“Peter”）；arr［1］ = new Person（“Leo”）；arr［2］ = new Person（“Cina”）；

在上面的程式碼中，陣列 arr 中儲存的是 Person 物件。同樣，我們還是把陣列中的資料 在記憶體中的儲存格式用圖表示，如圖 2-10 所示。

從圖 2-10 中可以看出，在 Java 中，物件陣列的儲存格式已經與 C/C++ 中的物件陣列的存 儲格式不一樣了。在 Java 中，物件陣列中儲存的是物件在記憶體中的地址，而非物件本身。對 象本身在記憶體中並不是連續儲存的，而是散落在各個地方。 在瞭解了一維陣列的儲存方式後，我們再來看一下 Java 中的多維陣列。在上文提到過， 多維陣列與二維陣列類似，因此此處還是使用二維陣列進行講解。注意，Java 中的二維陣列與 資料結構中的二維陣列有很大的區別。在 Java 中，二維陣列中的第二維可以是不同長度的。

int arr［］［］ = new int［3］［］；arr［0］ = new int［1］；arr［1］ = new int［2］；arr［2］ = new int［3］；

在上面的程式碼中，arr 是一個二維陣列，第一維長度是 3，第二維的長度各不相同：arr［0］ 的長度是 1，arr［1］ 的長度是 2，arr［2］ 的長度是 3。arr 陣列在記憶體中的儲存格式如圖 2-11 所示。

上面這個二維陣列儲存的是基本型別的資料，我們再來看一下在二維陣列中儲存物件時的 資料儲存格式。我們還是用一個例子來說明。

Person arr［］［］ = new Person［3］［］；arr［0］ = new Person［1］；arr［1］ = new Person［2］；arr［2］ = new Person［3］；arr［0］［0］ = new Person（“Peter”）；arr［1］［1］ = new Person（“Leo”）；

總結一下，在 Java 中，除基本型別一維陣列之外，物件陣列、二維陣列與資料結構中的 陣列的定義有很大區別。

JavaScript 中陣列的實現方式

如果 Java 中的陣列只是根據語言自身的特點，在資料結構中的陣列基礎之上做的改造的 話，那麼 JavaScript 這種動態指令碼語言中的陣列完全被改得“面目全非”了。 在本章開頭，我們提到過，JavaScript 中的陣列可以儲存不同型別的資料，陣列中的數 據也不一定是連續儲存的，並且能支援變長陣列。這完全就是與資料結構中的陣列的定義相 反的。 實際上，JavaScript 中的陣列的底層實現原理已經完全不符合資料結構中的陣列的定義了。也就是說，JavaScript 中的陣列只不過是名字叫陣列而已，與資料結構中的陣列幾乎沒有關係。 接下來，我們就來看一下 JavaScript 中的陣列是如何實現的。實際上，JavaScript 中的數 組會根據儲存資料的不同，選擇不同的實現方式。 如果陣列中儲存的是相同型別的資料，JavaScript 就真的會用資料結構中的陣列來實現。 也就是說，此時會分配一塊連續的記憶體空間來儲存資料。 如果陣列中儲存的是非相同型別的資料，JavaScript 就會用類似雜湊表的結構來儲存資料。 也就是說，此時資料並不是連續儲存在記憶體中的。這是 JavaScript 中的陣列支援儲存不同型別 資料的原因。 如果我們向一個儲存了相同型別資料的陣列中插入一個不同型別的資料，那麼 JavaScript 會將底層的儲存結構從陣列變成雜湊表。 實際上，JavaScript 為了“照顧”一些底層應用的開發者，還提供了 ArrayBuffer 這樣一種 資料型別。ArrayBuffer 完全符合標準的資料結構中的陣列的定義。ArrayBuffer 分配一塊連續 的記憶體空間，僅僅用來儲存相同型別的資料。

本文摘自《資料結構與演算法之美》

20個經典資料結構與演算法，100個真實專案場景案例，300多幅演算法手繪圖解，一本在手，演算法全有，面試大廠不愁！

豆瓣評分9。5，極客時間暢銷專欄集結成書，內容更新30%

下一篇

連結串列（上）：如何基於連結串列實現 LRU 快取淘汰演算法

喜歡請關注+評論+轉發哦