數據結構與算法

研究數據結構的核心

研究數據結構的目標是設計高效的算法。核心內容包括：

• 邏輯結構：描述數據之間的邏輯關係。
• 存儲結構：在計算機中實現邏輯結構的方式。
• 基本操作：在數據結構上的操作，如插入、刪除、查找等。

邏輯結構

線性結構

元素之間有一對一的線性關係。

例子：

• 線性表：數據按順序排列（如數組、鍊表）。
• 棧：後進先出（LIFO）。
• 隊列：先進先出（FIFO）。
• 串：字符序列（字符串）。
• 數組：固定大小的連續存儲單元。
• 廣義表：允許元素為另一個線性表的特殊結構。

非線性結構

元素之間關係複雜，可能有層次或網絡關係。

例子：

• 樹：節點間有一對多的層次關係。
• 圖：節點間有任意多對多的關係。

數據存儲結構

順序存儲結構

用連續的內存單元存儲數據。

特點：

• 易於通過索引訪問。
• 插入和刪除操作相對複雜，需要移動大量元素。

鏈式存儲結構

用指針將不連續的內存單元連結在一起。

特點：

• 靈活，支持動態擴展。
• 插入和刪除效率高，但隨機訪問速度慢。

算法的定義與五個特性

算法定義

解決特定問題的一系列明確的指令。

五個特性

• 有窮性：算法必須在有限步驟內完成。
• 確定性：每一步有明確的含義。
• 可行性：每一步都能在有限時間內完成。
• 輸入：算法接受零個或多個輸入。
• 輸出：算法產生一個或多個輸出。

數據結構中的關係

線性結構

元素之間一對一的關係，形成直線結構。

例子：鍊表、數組。

樹形結構

元素之間一對多的關係，形成分支結構。

例子：二叉樹、B樹。

圖形結構

元素之間多對多的關係，形成網絡結構。

例子：社交網絡中的好友關係圖。

抽象數據類型(ADT)

定義了數據和操作，但與具體實現無關。

如棧，ADT 定義了 push 和 pop 操作，而不涉及具體實現。