一、线性表基础概念

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考试中避免低级失误，实现高分突破。建议将本文中的代码片段与真题结合练习，强化手写代码能力。