CS-第 5 週

數據結構詳解：從數組到樹，再到哈希表

本文深入探討幾種常見的數據結構，包括數組、鍊錶、二叉搜索樹（BST）和哈希表，並闡述其在內存中的組織方式及優缺點。

信息結構與抽像數據結構

信息結構指的是內存中組織信息的方式，而抽像數據結構則是我們概念上對這些結構的理解。 理解抽像數據結構有助於我們更好地在實踐中實現各種數據結構。

---

堆棧和隊列

隊列是一種遵循FIFO（先進先出）原則的抽像數據結構，類似於排隊等候。其主要操作包括入隊（添加元素到隊列尾部）和出隊（移除隊列頭部元素）。

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

---

數組

數組是一種在內存中連續存儲數據的結構。 如下圖所示，數組在內存中佔據連續的存儲空間。

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

預先分配過多的內存雖然可以減少複製操作，但卻會浪費系統資源。因此，根據實際需求分配內存至關重要。

---

鍊錶

鍊錶是一種強大的數據結構，它允許將位於不同內存區域的值連接成一個列表，並支持動態擴展或縮小。

每個節點包含兩個值：數據值和指向下一個節點的指針。最後一個節點的指針值為NULL，表示鍊錶的結尾。

C語言中，節點可以定義如下：

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

以下示例展示了鍊錶的創建過程：

鍊錶的缺點包括：需要額外內存存儲指針，以及無法通過索引直接訪問元素。

---

二叉搜索樹(BST)

二叉搜索樹是一種高效存儲、搜索和檢索數據的樹形結構。

BST 的優點在於動態性和搜索效率（O(log n)），缺點在於樹不平衡時搜索效率會下降到O(n)，並且需要額外的內存存儲指針。

---

哈希表

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

哈希衝突（多個鍵映射到同一個索引）可以通過鍊錶或其他方法解決。 哈希函數的設計對哈希表的性能至關重要。 一個簡單的哈希函數示例如下：

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

本文基於cs50x 2024源碼整理。

以上是CS-第 5 週的詳細內容。更多資訊請關注PHP中文網其他相關文章！