數(shù)據(jù)結(jié)構(gòu)詳解：從數(shù)組到樹(shù)，再到哈希表

本文深入探討幾種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，包括數(shù)組、鍊錶、二叉搜索樹(shù)（BST）和哈希表，並闡述其在內(nèi)存中的組織方式及優(yōu)缺點(diǎn)。

信息結(jié)構(gòu)與抽像數(shù)據(jù)結(jié)構(gòu)

信息結(jié)構(gòu)指的是內(nèi)存中組織信息的方式，而抽像數(shù)據(jù)結(jié)構(gòu)則是我們概念上對(duì)這些結(jié)構(gòu)的理解。 理解抽像數(shù)據(jù)結(jié)構(gòu)有助於我們更好地在實(shí)踐中實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)。

堆棧和隊(duì)列

隊(duì)列是一種遵循FIFO（先進(jìn)先出）原則的抽像數(shù)據(jù)結(jié)構(gòu)，類似於排隊(duì)等候。其主要操作包括入隊(duì)（添加元素到隊(duì)列尾部）和出隊(duì)（移除隊(duì)列頭部元素）。

堆棧則遵循LIFO（後進(jìn)先出）原則，如同疊盤(pán)子。其操作包括壓入（添加元素到堆棧頂部）和彈出（移除堆棧頂部元素）。

數(shù)組

數(shù)組是一種在內(nèi)存中連續(xù)存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)。 如下圖所示，數(shù)組在內(nèi)存中佔(zhàn)據(jù)連續(xù)的存儲(chǔ)空間。

內(nèi)存中可能存在其他程序、函數(shù)和變量，以及之前使用過(guò)的冗餘數(shù)據(jù)。 如果需要向數(shù)組添加新元素，則需要重新分配內(nèi)存並複制整個(gè)數(shù)組，這會(huì)造成效率低下。

預(yù)先分配過(guò)多的內(nèi)存雖然可以減少複製操作，但卻會(huì)浪費(fèi)系統(tǒng)資源。因此，根據(jù)實(shí)際需求分配內(nèi)存至關(guān)重要。

鍊錶

鍊錶是一種強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，它允許將位於不同內(nèi)存區(qū)域的值連接成一個(gè)列表，並支持動(dòng)態(tài)擴(kuò)展或縮小。

每個(gè)節(jié)點(diǎn)包含兩個(gè)值：數(shù)據(jù)值和指向下一個(gè)節(jié)點(diǎn)的指針。最後一個(gè)節(jié)點(diǎn)的指針值為NULL，表示鍊錶的結(jié)尾。

C語(yǔ)言中，節(jié)點(diǎn)可以定義如下：

 <code class="c">typedef struct CS-第 5 週 { int number; struct CS-第 5 週 *next; } CS-第 5 週;</code>

以下示例展示了鍊錶的創(chuàng)建過(guò)程：

鍊錶的缺點(diǎn)包括：需要額外內(nèi)存存儲(chǔ)指針，以及無(wú)法通過(guò)索引直接訪問(wèn)元素。

二叉搜索樹(shù)(BST)

二叉搜索樹(shù)是一種高效存儲(chǔ)、搜索和檢索數(shù)據(jù)的樹(shù)形結(jié)構(gòu)。

BST 的優(yōu)點(diǎn)在於動(dòng)態(tài)性和搜索效率（O(log n)），缺點(diǎn)在於樹(shù)不平衡時(shí)搜索效率會(huì)下降到O(n)，並且需要額外的內(nèi)存存儲(chǔ)指針。

哈希表

哈希表類似於字典，包含鍵值對(duì)。 它利用哈希函數(shù)將鍵映射到數(shù)組索引，從而實(shí)現(xiàn)O(1) 的平均查找時(shí)間。

哈希衝突（多個(gè)鍵映射到同一個(gè)索引）可以通過(guò)鍊錶或其他方法解決。 哈希函數(shù)的設(shè)計(jì)對(duì)哈希表的性能至關(guān)重要。 一個(gè)簡(jiǎn)單的哈希函數(shù)示例如下：

 <code class="c">#include <ctype.h> unsigned int hash(const char *word) { return toupper(word[0]) - 'A'; }</ctype.h></code>

本文基於cs50x 2024源碼整理。

以上是CS-第 5 週的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！