資料結構 (Data Structures)

組織、儲存和操作資料的基礎方法

線性資料結構

陣列 (Array):連續記憶體,O(1) 隨機存取,O(n) 插入/刪除。

鏈結串列 (Linked List):非連續記憶體,O(n) 存取,O(1) 插入/刪除。

堆疊 (Stack):後進先出 (LIFO),用於函數呼叫、括號匹配。

佇列 (Queue):先進先出 (FIFO),用於 BFS、工作排程。

樹狀結構

二元樹:每個節點最多兩個子節點。

堆積:完全二元樹實現優先佇列。

二元搜尋樹:左小右大,支援高效查找。

平衡樹:AVL、紅黑樹,保證 O(log n) 操作。

圖結構

鄰接矩陣:V×V 矩陣,適合稠密圖。

鄰接串列:每個頂點維護邊串列,適合稀疏圖。

雜湊結構

雜湊表使用雜湊函數將鍵映射到陣列索引,實現平均 O(1) 的查找。搭配鏈結法或開放定址法處理碰撞。布隆過濾器是空間高效的機率性變體。

本課程範例

相關連結