??算法：問題求解步驟的描述。
維度 邏輯結構 存儲結構（物理結構） 定義 數據元素之間的邏輯關系 數據結構在計算機中的實現方式 分類 線性/樹形/圖/集合 順序/鏈式 /索引/散列獨立性 獨立于存儲結構 依賴邏輯結構 示例 線性表 、有序表 、數組 （抽象層面）順序表 、鏈表、靜態鏈表ADT描述 描述操作語義 描述具體實現
ADT List { 數據對象：D = { a_i | a_i∈ElemSet, i= 1 , 2 , . . . , n} 數據關系：R = { < a_{ i- 1 } , a_i> | a_{ i- 1 } , a_i∈D} 基本操作：InitList ( & L) , ListInsert ( & L, i, e) . . .
}
術語 本質 所屬層級 與其它概念關系 線性表 邏輯結構 邏輯層 可用順序/鏈式存儲實現 有序表 邏輯結構+約束 邏輯層 元素有序的線性表 順序表 存儲結構 物理層 線性表的順序存儲實現 數組【隨機存取】 邏輯結構+存儲結構 跨層概念 可視為特殊的順序表
特性 線性表（抽象） 順序表（實現） 有序表（特殊） 元素關系 前驅后繼關系 物理相鄰存儲 按關鍵字有序 存儲方式 與實現無關 連續內存空間 通常用順序存儲 查找效率 O(n) 按位O(1)，按值O(n) 順序存儲時可二分O(logn) 插入刪除 依賴實現 移動元素O(n) 需保持有序性O(n)
棧和隊列的ADT相同，即邏輯結構都是線性表。 順序表具有隨機存取是指：查找序號i的元素的時間，與順序表中元素個數n無關 擴容問題 ?順序表插入算法：n個空間滿了時，申請m個，若申請失敗，則說明系統沒有：n+m 個可分配的存儲空間（n也要被復制進新表）對長度為n的、順序存儲的有序表，實現給定的算法中時間復雜度為O(1)的是：獲取第i個值的算法。 線性表是具有n個同類型數據元素的有限序列。除開始元素外，每個元素只有唯一的前驅 元素。 若非空線性表中的元素，既沒有前驅也沒有后繼，則：表中只有1個元素。 線性表的順序存儲結構：是一種隨機存取的存儲結構。 線性表要取前驅后繼則采用什么物理結構：順序表最好。 線性表要取指定序號在最后插入刪除：物理結構用順序表最好。 按值查找一定要比較值，所以與長度有關。
特性 順序存儲 鏈式存儲 物理結構 連續內存空間 離散節點+指針 存儲密度 100% ，所以密度大 <100%（需存儲指針） 訪問方式 隨機存取（直接計算地址） 順序存取（必須遍歷） 插入刪除 O(n)（需移動元素） O(1)（已知位置） 擴容方式 需重新分配+復制 動態增長 緩存友好性 好（空間局部性） 差 代表實現 順序表、靜態數組 單鏈表、雙鏈表 典型應用 頻繁隨機訪問場景 動態數據集合 能表示的邏輯結構 種類少 種類多
不能說某一種存儲結構優于另一種 元素存放順序與存儲空間大小無關 順序和鏈式都能順序存取
視角 解釋 示例 邏輯層 線性結構的推廣（一維數組即線性表） 矩陣是二維線性結構 物理層 順序存儲的典型實現 int a[10]連續存儲 操作特性 通過下標直接訪問元素（本質是基地址+偏移量計算） a[i] ≡ *(a+i)
常見混淆對 區分關鍵 記憶技巧 順序表 vs 數組 順序表強調邏輯關系，數組側重存儲 “數組是順序表的具體實現” 有序表 vs 順序表 有序是邏輯約束，順序是存儲方式 “有序表可以用鏈表實現” 線性表 vs 鏈表 線性表是抽象概念，鏈表是具體實現 “鏈表是實現線性表的方式”
以下是補充棧（Stack）和隊列（Queue）后的完整知識圖譜，嚴格區分邏輯結構與存儲結構，并標注實現方式：
