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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Tip

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