線性表

線性結構的特點

• 線性結構中的元素具有嚴格的一對一關係，表現為一個前驅和一個後繼。
• 通常存儲為順序表（數組）或鍊表。

順序表中第 $i$ 個數據元素存儲位置的計算

公式： $\text{LOC}(a_i)=\text{LOC}(a_1)+(i-1)\times L$

• $\text{LOC}(a_i)$：第 $i$ 個數據元素的存儲地址。
• $i$：數據元素在表中的位置。
• $L$：每個元素所佔存儲單元大小。

該公式體現了順序存儲結構中地址的連續性，計算時間複雜度為 $O(1)$。

順序表的基本操作

• 取值：根據位置直接通過公式計算地址，時間複雜度為 $O(1)$。
• 查找：按值查找時，需要逐個比較，時間複雜度為 $O(n)$。
• 插入與刪除：為保持數據的連續性，需要移動元素，時間複雜度為 $O(n)$。

順序存儲結構的特點

• 邏輯相鄰即物理相鄰：數據存儲為一段連續的內存空間。
• 隨機存取：通過公式快速計算元素地址，支持直接訪問任意位置。
• 存儲密度大：所有存儲空間都存儲有效數據，密度為 1。

鏈式存儲結構的特點

• 物理位置不一定相鄰：數據元素之間通過指針連結，內存分配靈活。
• 順序存取：必須從頭節點開始，逐一訪問每個元素。
• 存儲密度小於 1：每個節點需要額外存儲指針信息。
• 鍊表：單鍊表中每個節點包含數據域和指針域。

單鍊表的操作

單鍊表的插入操作

在位置 p 之後插入新節點 s：

s->next = p->next;

p->next = s;

1. 將 s 的指針指向 p 的後繼。
2. 將 p 的指針指向 s。

單鍊表的刪除操作

刪除位置 p 之後的節點 q：

q = p->next;

p->next = q->next;

1. 將 q 定位為 p 的後繼節點。
2. 修改 p 的指針，使其跳過 q。

效率

插入和刪除只需修改指針，時間複雜度為 $O(1)$，不需要移動數據。