第二章 線性表

2.1線性表的定義和基本操作

線性表：一種邏輯結構，表示數據元素之間的一對一線性關系（如數組、鏈表、棧、隊列等）。

2.1.1線性表的定義

線性表是具有相同數據類型的n(n>0)個數據元素的有限序列。
(其中n為表長，當n=0時線性表是一個空表。若用L命名線性表，則其一般表示為)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

• 幾個概念:
  1.?aiai是線性表中的“第i個”元素線性表中的位序。
  2.?a1a1是表頭元素;anan是表尾元素。
  3.?除第一個元素外，每個元素有且僅有一個直接前驅:除最后一個元素外，每個元素有且僅有一個直接后繼。

• 存儲結構：
  1. 順序存儲結構：順序表
  2. 鏈式存儲結構：鏈表

2.2順序表

順序表：線性表的一種物理實現方式，通過連續內存空間存儲元素（即數組實現的線性表）。

2.2.1順序表的概念

• 順序表：用順序存儲的方式實現線性表順序存儲。把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關系由存儲單元的鄰接關系來體現。
• 順序表的特點

1. 隨機訪問，即可以在O(1)時間內找到第i個元素。
2. 存儲密度高，每個節點只存儲數據元素。
3. 擴展容量不方便。
4. 插入刪除操作不方便，需移動大量元素：O(n)。

2.2.2順序表的實現

2.2.3順序表的基本操作?

操作	移動方向	起始位置	目的
插入	從表尾開始向后移動	最后一個元素	防止覆蓋未處理的元素
刪除	從刪除位置開始向前移動	刪除位置的下一個	直接覆蓋，無需額外緩存

2.3線性表的鏈式表示

2.3.1單鏈表

• 特點：
  優點：不要求大片連續空間，改變容量方便。
  缺點：不可隨機存取，要耗費一定空間存放指針。

• 基礎操作總結?

操作	核心思想	時間復雜度	邊界條件
頭部插入	新節點指向原頭節點，更新頭指針	O(1)	空鏈表
尾部插入	遍歷到末尾，鏈接新節點	O(n)	空鏈表
指定位置插入	找到前驅節點，調整指針	O(n)	前驅節點不存在
刪除頭節點	頭指針后移，釋放原頭節點	O(1)	空鏈表
刪除指定節點	找到前驅節點，跳過目標節點并釋放	O(n)	目標節點不存在或為頭節點
修改節點	遍歷找到目標節點，更新數據	O(n)	目標節點不存在
按值查找	遍歷鏈表，匹配數據	O(n)	無匹配
按位置查找	遍歷到指定索引	O(n)	索引越界

• ?單鏈表的建立

1. Step 1:初始化一個單鏈表
2. Step 2:每次取一個數據元素，插入到表尾/表頭

• 尾插法建立單鏈表
  平均時間復雜度O(n)
  思路：每次將新節點插入到當前鏈表的表尾，所以必須增加一個尾指針r,使其始終指向當前鏈表的尾結點。好處：生成的鏈表中結點的次序和輸入數據的順序會一致。
• 頭插法建立單鏈表
  平均時間復雜度O(n) 思路：新節點始終插入鏈表頭部，最終鏈表順序與輸入順序相反。
• ?鏈表的逆置：

  LNode *Inverse(LNode *L)
  {LNode *p, *q;p = L->next;     //p指針指向第一個結點L->next = NULL;  //頭結點指向NULLwhile (p != NULL){q = p;p = p->next;q->next = L->next;  L->next = q;}return L;

  2.3.2雙鏈表

雙鏈表是一種比單鏈表更復雜的鏈式數據結構，每個節點包含兩個指針，分別指向前驅節點（prev）和后繼節點（next），從而支持雙向遍歷。

2.3.3循環鏈表?

循環鏈表是鏈表的變種，其特點是?尾節點的指針不再指向?NULL，而是指向頭節點，形成一個環形結構。根據方向性，可分為?單向循環鏈表?和?雙向循環鏈表。

?2.3.4順序表和鏈表的比較

【邏輯結構】

• 順序表和鏈表都屬于線性表，都是線性結構

【存儲結構】

• 順序表：順序存儲，使用數組存儲，元素在內存中物理地址連續。

• • 優點：支持隨機存取，存儲密度高
  • 缺點：大片連續空間分配不方便，改變容量不方便

• 鏈表：鏈式存儲，通過節點和指針鏈接，元素在內存中物理地址分散。

  • 優點：離散的小空間分配方便，改變容量方便
  • 缺點：不可隨機存取，存儲密度低

• ?核心區別

特性	順序表（數組實現）	鏈表（指針實現）
存儲方式	連續內存空間	非連續內存，通過指針鏈接節點
隨機訪問	支持，時間復雜度?O(1)	不支持，需遍歷，時間復雜度?O(n)
插入/刪除	平均?O(n)（需移動元素）	平均?O(1)（修改指針）
空間利用率	無額外指針開銷，但可能浪費預分配空間	每個節點需存儲指針，但動態擴容無浪費
內存分配	靜態（固定大小）或動態（可擴容）	動態分配（按需申請釋放）
緩存友好性	高（連續內存，預加載效率高）	低（內存分散，易引發緩存未命中）
適用場景	高頻查詢、元素數量穩定	頻繁插入/刪除、元素數量變化大

• 操作效率?

操作	順序表	鏈表
訪問第i個元素	O(1)（直接通過下標訪問）	O(n)（需從頭遍歷）
頭部插入	O(n)（需移動所有元素）	O(1)（修改頭指針）
尾部插入	O(1)（若空間足夠）	O(1)（維護尾指針時）
中間插入	O(n)	O(1)（已知前驅節點時）
擴容	O(n)（需遷移數據）	O(1)（動態分配節點）

【內存管理】

• 順序表：

  • 靜態分配：大小固定（如C靜態數組）。

  • 動態分配：可擴容但需復制數據（如C++?vector）。

• 鏈表：

  • 動態分配節點，無容量限制（除非內存耗盡）。

【總結】

維度	順序表	鏈表
本質	數組	指針鏈接的節點
核心優勢	訪問快、緩存友好	插入/刪除高效、動態擴容
核心劣勢	插入/刪除慢、擴容成本高	訪問慢、內存碎片化

2.4一些面試題?

2.4.1用一句話解釋順序表和鏈表

? 邏輯上相鄰的元素在物理存儲上也相鄰（插入刪除需要移動元素）

? 邏輯上相鄰的元素物理上不一定相鄰（插入刪除不需要移動元素）?

2.4.2?頭指針和頭結點的區別？引入頭結點的優點

區別： 頭指針是指向鏈表第一個節點的指針，是訪問鏈表的入口；而頭結點是鏈表開頭的一個附加節點，其數據域通常不存儲業務數據。

注： 頭結點的指針域指向線性表的第一個元素結點。

引入頭結點的優點：

① 由于第一個數據結點的位置被存放在頭結點的指針域中，因此在鏈表的第一個位置上的操作和在表的其他位置上的操作保持一致，無需進行特殊處理。

② 無論鏈表是否為空，其頭指針都是指向頭結點的非空指針（空表中頭結點的指針域為空），因此空表和非空表的處理也就得到了統一。

2.4.3如何判斷鏈表有環

窮舉遍歷：設一個檢測指針 k 和一個遍歷指針 q，count 記錄遍歷指針 q 走的步數。遍歷指針每走一步，檢測指針 k 就走遍歷指針 q 之前走過的節點，若發現相同的節點便說明有環，直到遍歷節點 q 遍歷完整個鏈表，即q = NULL 為止。時間復雜度O(n^2)，空間復雜度O(1)

標記法：在結點中設置一個標記變量，每走一個結點，就判斷一次。若 visit == true，則說明有環。反之，說明無環。時間復雜度O(n)，空間復雜度O(n)

快慢指針：設置兩個指針，一個慢指針 low 和一個快指針 fast。初始值 慢指針 low 指向第一個結點，快指針 fast 指向第二個結點。只要快指針不為空，則慢指針slow就先向后走一個。然后兩輪處理快指針。只要未遍歷完鏈表，則將快指針向后移動一個，并判斷快慢指針是否相遇。一旦快慢指針相遇，則說明有環。反之，則說明無環。時間復雜度O(n)，空間復雜度O(1)

set 集合大小變化：根據集合的去重特性來判斷。每遍歷一個結點，就將該結點加入集合。若加入該新結點后，集合大小不再發生變化，則說明集合中的該元素已存在，即說明存在環。倘若，遍歷完所有結點，集合大小都能正常判斷，則無環。時間復雜度O(n)，空間復雜度O(n)

2.4.4?線性表包括了順序表和鏈表，請比較它們的區別。★★

（1）存取（讀寫）方式

? ? ? ?順序表可以順序存取，也可以隨機存取。

? ? ? ?鏈表只能順序存取。

（2）邏輯結構與物理結構

? ? ? ?順序存儲：邏輯上相鄰的元素，物理存儲位置也相鄰。

? ? ? ?鏈式存儲：邏輯上相鄰的元素，物理存儲位置不一定相鄰，對應的邏輯關系是通過指針鏈接來表示的。

（3）查找、插入和刪除操作

? ? ? ?查找：

? ? ? ?對于按值查找，順序表無序時，兩者的時間復雜度均為O(n); 順序表有序時，可采用折半查找，此時的時間復雜度為O(logn) 。

? ? ? ?對于按序號查找，順序表支持隨機訪問，時間復雜度僅為0(1), 而鏈表的平均時間復雜度為O(n)。

? ? ? ?插入、刪除：

? ? ? ?順序表的插入、刪除操作，平均需要移動半個表長的元素。

? ? ? ?鏈表的插入、刪除操作，只需修改相關結點的指針域即可。由于鏈表的每個結點都帶有指針域，故而存儲密度不夠大。

?

?

?

?

?

?

?

?

?

?

?

?