一、線性表基礎概念
1.1 定義與分類
定義：線性表是由n（n≥0）個相同類型數據元素構成的有限序列，元素間呈線性關系。
分類：
- 順序表：元素按邏輯順序存儲在一段連續的物理空間中（數組實現）。
- 鏈表：元素通過指針鏈接，物理存儲非連續（單鏈表、雙鏈表、循環鏈表等）。
易錯點提醒：
順序表與鏈表的本質區別：順序表支持隨機訪問（時間復雜度O(1)），鏈表僅支持順序訪問（時間復雜度O(n)）。
常見誤區：誤認為鏈表插入/刪除操作時間復雜度一定是O(1)。只有當已知插入位置的前驅節點時，時間復雜度才是O(1)；否則需要先遍歷查找，此時時間復雜度為O(n)。
二、順序表核心考點與易錯點
2.1 順序表插入操作
算法步驟：
檢查插入位置合法性（1 ≤ i ≤ length+1）。
檢查存儲空間是否已滿（若滿需擴容）。
將第i至第n個元素后移一位。
將新元素插入位置i。
表長+1。
易錯點示例：
// 錯誤代碼：未處理插入位置越界或空間不足
void InsertSeqList(SeqList *L, int i, ElemType e) { for (int j = L->length; j >= i; j--) L->data[j] = L->data[j-1]; L->data[i-1] = e; L->length++;
}
錯誤分析：未檢查i的范圍（如i=0或i>length+1），且未處理存儲空間已滿的情況。
正確解法：
int InsertSeqList(SeqList *L, int i, ElemType e) { if (i < 1 || i > L->length + 1) return 0; // 越界檢查 if (L->length >= MAXSIZE) return 0; // 空間檢查 for (int j = L->length; j >= i; j--) L->data[j] = L->data[j-1]; L->data[i-1] = e; L->length++; return 1;
}
總結提醒：
邊界條件：插入位置i的合法范圍是[1, length+1]，需特別注意循環終止條件。
擴容策略：考研題目中若未明確要求動態擴容，通常假設空間足夠，但需在代碼中注釋說明。
2.2 順序表刪除操作
算法步驟：
檢查刪除位置合法性（1 ≤ i ≤ length）。
取出被刪除元素。
將第i+1至第n個元素前移一位。
表長-1。
易錯點示例：
// 錯誤代碼：未處理空表或越界
ElemType DeleteSeqList(SeqList *L, int i) { ElemType e = L->data[i-1]; for (int j = i; j < L->length; j++) L->data[j-1] = L->data[j]; L->length--; return e;
}
錯誤分析：未檢查順序表是否為空（length=0）或i是否超出范圍。
正確解法：
int DeleteSeqList(SeqList *L, int i, ElemType *e) { if (i < 1 || i > L->length) return 0; // 空表或越界 *e = L->data[i-1]; for (int j = i; j < L->length; j++) L->data[j-1] = L->data[j]; L->length--; return 1;
}
總結提醒：
刪除后的空間處理：順序表刪除元素后無需釋放內存，但需維護length值。
時間復雜度：刪除操作的平均時間復雜度為O(n)，最壞情況（刪除第一個元素）需要移動n-1個元素。
三、鏈表核心考點與易錯點
3.1 單鏈表頭插法與尾插法
頭插法：新節點插入鏈表頭部，生成逆序鏈表。
void CreateList_Head(LinkList *L, int n) { *L = (LinkList)malloc(sizeof(LNode)); (*L)->next = NULL; for (int i = 0; i < n; i++) { LNode *p = (LNode*)malloc(sizeof(LNode)); p->data = rand() % 100; p->next = (*L)->next; (*L)->next = p; }
}
尾插法：新節點插入鏈表尾部，生成正序鏈表。
void CreateList_Tail(LinkList *L, int n) { *L = (LinkList)malloc(sizeof(LNode)); LNode *r = *L; // 尾指針 for (int i = 0; i < n; i++) { LNode *p = (LNode*)malloc(sizeof(LNode)); p->data = rand() % 100; r->next = p; r = p; } r->next = NULL;
}
易錯點提醒：
頭結點處理：頭插法中頭結點的next域需初始化為NULL，否則可能導致野指針。
尾指針更新：尾插法中忘記更新尾指針r的位置，導致鏈表斷裂。
真題示例：
（2021年408真題） 下列關于單鏈表插入操作的描述中，正確的是？
A. 頭插法建立的鏈表與輸入順序一致
B. 尾插法需要維護尾指針以保證時間復雜度O(1)
C. 在p節點后插入新節點的時間復雜度為O(n)
D. 刪除p節點后繼節點的時間復雜度為O(1)
答案：B、D
解析：
頭插法生成逆序鏈表（A錯誤）。
尾插法若沒有尾指針，每次插入需遍歷到鏈表尾部，時間復雜度O(n)；維護尾指針可優化至O(1)（B正確）。
在已知p節點的情況下，插入操作時間復雜度為O(1)（C錯誤）。
刪除p的后繼節點只需修改p的next指針（D正確）。
3.2 鏈表刪除操作
標準刪除邏輯：
// 刪除p節點的后繼節點q
q = p->next;
p->next = q->next;
free(q);
易錯點示例：
// 錯誤代碼：未處理空指針或尾節點
void DeleteNode(LinkList L, ElemType x) { LNode *p = L->next, *pre = L; while (p != NULL) { if (p->data == x) { pre->next = p->next; free(p); break; } pre = p; p = p->next; }
}
錯誤分析：釋放p后，p成為野指針，但循環中繼續執行p = p->next，導致未定義行為。
正確解法：
void DeleteNode(LinkList L, ElemType x) { LNode *p = L->next, *pre = L; while (p != NULL) { if (p->data == x) { pre->next = p->next; LNode *temp = p; p = p->next; free(temp); } else { pre = p; p = p->next; } }
}
總結提醒：
指針安全：釋放節點前需保存其地址，避免后續操作訪問已釋放內存。
循環鏈表處理：刪除尾節點時需特別處理，防止形成環。
四、綜合應用與高頻考點## 標題
4.1 順序表與鏈表的比較
操作 順序表 鏈表
隨機訪問 O(1) O(n)
插入/刪除（已知位置） O(n) O(1)
存儲密度 高（無指針開銷） 低（需要指針）
擴容代價 高（需整體復制） 低（動態分配）
真題示例：
（2023年408真題） 若線性表需要頻繁進行插入和刪除操作，且元素個數變化較大，最適合的存儲結構是？
A. 順序表
B. 單鏈表
C. 靜態鏈表
D. 雙向循環鏈表
答案：B
解析：鏈表在動態插入/刪除時效率更高，且無需預先分配固定空間。
4.2 鏈表逆置算法
頭插法逆置：
void ReverseList(LinkList L) { LNode *p = L->next, *q; L->next = NULL; while (p != NULL) { q = p->next; // 保存后繼節點 p->next = L->next; // 頭插 L->next = p; p = q; }
}
易錯點：未保存p的后繼節點q，導致鏈表斷裂。
4.3 雙鏈表刪除節點
// 刪除p節點
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
易錯點提醒：
若p是尾節點，則p->next->prior會訪問NULL指針，需增加條件判斷：
if (p->next != NULL) p->next->prior = p->prior;
五、線性表解題策略總結
畫圖輔助分析：對鏈表操作，務必先畫出指針變化示意圖。
邊界檢查：對空表、頭節點、尾節點等特殊情況優先處理。
復雜度優化：若題目要求時間或空間優化，優先考慮雙指針、哈希表等技巧。
代碼魯棒性：所有操作前檢查指針是否為空，避免運行時崩潰。
通過系統梳理線性表的核心知識點與易錯陷阱，結合真題實戰分析，考生可精準把握命題規律，在408考試中避免低級失誤，實現高分突破。建議將本文中的代碼片段與真題結合練習，強化手寫代碼能力。
