數(shù)據(jù)結(jié)構(gòu)分類

常見的數(shù)據(jù)結(jié)構(gòu)包括數(shù)組、鏈表、棧、隊列、哈希表、樹、堆、圖，它們可以從“邏輯結(jié)構(gòu)”和“物理結(jié)構(gòu)”兩個維度進行分類。

3.1.1   邏輯結(jié)構(gòu)：線性與非線性

邏輯結(jié)構(gòu)揭示了數(shù)據(jù)元素之間的邏輯關(guān)系。在數(shù)組和鏈表中，數(shù)據(jù)按照順序依次排列，體現(xiàn)了數(shù)據(jù)之間的線性關(guān)系；而在樹中，數(shù)據(jù)從頂部向下按層次排列，表現(xiàn)出祖先與后代之間的派生關(guān)系；圖則由節(jié)點和邊構(gòu)成，反映了復(fù)雜的網(wǎng)絡(luò)關(guān)系。

如圖 3-1 所示，邏輯結(jié)構(gòu)可被分為“線性”和“非線性”兩大類。線性結(jié)構(gòu)比較直觀，指數(shù)據(jù)在邏輯關(guān)系上呈線性排列；非線性結(jié)構(gòu)則相反，呈非線性排列。

• 線性數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、棧、隊列、哈希表。
• 非線性數(shù)據(jù)結(jié)構(gòu)：樹、堆、圖、哈希表。

圖 3-1   線性與非線性數(shù)據(jù)結(jié)構(gòu)

非線性數(shù)據(jù)結(jié)構(gòu)可以進一步被劃分為樹形結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)。

• 線性結(jié)構(gòu)：數(shù)組、鏈表、隊列、棧、哈希表，元素之間是一對一的順序關(guān)系。
• 樹形結(jié)構(gòu)：樹、堆、哈希表，元素之間是一對多的關(guān)系。
• 網(wǎng)狀結(jié)構(gòu)：圖，元素之間是多對多的關(guān)系。

3.1.2   物理結(jié)構(gòu)：連續(xù)與離散

在計算機中，內(nèi)存和硬盤是兩種主要的存儲硬件設(shè)備。硬盤主要用于長期存儲數(shù)據(jù)，容量較大（通?？蛇_到 TB 級別）、速度較慢。內(nèi)存用于運行程序時暫存數(shù)據(jù)，速度較快，但容量較?。ㄍǔ?GB 級別）。

在算法運行過程中，相關(guān)數(shù)據(jù)都存儲在內(nèi)存中。圖 3-2 展示了一個計算機內(nèi)存條，其中每個黑色方塊都包含一塊內(nèi)存空間。我們可以將內(nèi)存想象成一個巨大的 Excel 表格，其中每個單元格都可以存儲一定大小的數(shù)據(jù)，在算法運行時，所有數(shù)據(jù)都被存儲在這些單元格中。

系統(tǒng)通過內(nèi)存地址來訪問目標位置的數(shù)據(jù)。如圖 3-2 所示，計算機根據(jù)特定規(guī)則為表格中的每個單元格分配編號，確保每個內(nèi)存空間都有唯一的內(nèi)存地址。有了這些地址，程序便可以訪問內(nèi)存中的數(shù)據(jù)。

圖 3-2   內(nèi)存條、內(nèi)存空間、內(nèi)存地址

內(nèi)存是所有程序的共享資源，當某塊內(nèi)存被某個程序占用時，則無法被其他程序同時使用了。因此在數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計中，內(nèi)存資源是一個重要的考慮因素。比如，算法所占用的內(nèi)存峰值不應(yīng)超過系統(tǒng)剩余空閑內(nèi)存；如果缺少連續(xù)大塊的內(nèi)存空間，那么所選用的數(shù)據(jù)結(jié)構(gòu)必須能夠存儲在離散的內(nèi)存空間內(nèi)。

如圖 3-3 所示，物理結(jié)構(gòu)反映了數(shù)據(jù)在計算機內(nèi)存中的存儲方式，可分為連續(xù)空間存儲（數(shù)組）和離散空間存儲（鏈表）。物理結(jié)構(gòu)從底層決定了數(shù)據(jù)的訪問、更新、增刪等操作方法，同時在時間效率和空間效率方面呈現(xiàn)出互補的特點。

圖 3-3   連續(xù)空間存儲與離散空間存儲

值得說明的是，所有數(shù)據(jù)結(jié)構(gòu)都是基于數(shù)組、鏈表或二者的組合實現(xiàn)的。例如，棧和隊列既可以使用數(shù)組實現(xiàn)，也可以使用鏈表實現(xiàn)；而哈希表的實現(xiàn)可能同時包含數(shù)組和鏈表。

• 基于數(shù)組可實現(xiàn)：棧、隊列、哈希表、樹、堆、圖、矩陣、張量（維度 ≥3 的數(shù)組）等。
• 基于鏈表可實現(xiàn)：棧、隊列、哈希表、樹、堆、圖等。

基于數(shù)組實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)也被稱為“靜態(tài)數(shù)據(jù)結(jié)構(gòu)”，這意味著此類數(shù)據(jù)結(jié)構(gòu)在初始化后長度不可變。相對應(yīng)地，基于鏈表實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)被稱為“動態(tài)數(shù)據(jù)結(jié)構(gòu)”，這類數(shù)據(jù)結(jié)構(gòu)在初始化后，仍可以在程序運行過程中對其長度進行調(diào)整。

Tip

如果你感覺物理結(jié)構(gòu)理解起來有困難，建議先閱讀下一章“數(shù)組與鏈表”，然后再回顧本節(jié)內(nèi)容。