线性表

一、线性表的概念与抽象数据类型（ADT）

• 定义：n（≥0）个数据元素 a1,a2,…,an 的有限序列。
• 抽象操作（必须掌握并能写伪码/实现）：InitList, DestroyList, ClearList, ListEmpty, ListLength, GetElem(i), LocateElem(value), PriorElem(elem), NextElem(elem), ListInsert(i,elem), ListDelete(i), ListTraverse/Print。
• 逻辑结构：线性（前后有序，唯一前驱/后继，首尾特殊）。

二、存储结构（两种基本实现）

1. 顺序存储（数组/顺序表）

• 存储方式：连续存放，按下标随机访问。
• 地址计算：第 i 个元素地址 = base + (i-1)*elem_size（下标从1开始）。
• 优点：随机访问 O(1)，空间紧凑，访问快。
• 缺点：插入/删除需移动元素 O(n)、容易溢出（固定容量）。
• 扩容策略：动态数组（按需 realloc，常见倍增策略 amortized O(1) 插入尾）。
• 常考操作复杂度（n 元素）：
  • 访问/查找（按位置）：O(1)
  • 按值查找：O(n)
  • 插入/删除（中间位置）：O(n)（平均移动 ~n/2）
• 典型题：实现顺序表的插入/删除；判断溢出；将数组按某规则调整（移除重复、合并两个有序数组等）。

1. 链式存储（单链表、双链表、循环链表）

• 节点结构：data, next（双链表多 prev）。
• 单链表操作：
  • 插入：在已知前驱 p 后插入为 O(1)（不含查找时间）。
  • 删除：若只有被删节点指针且无前驱需先找前驱，否则常用保存前驱的方法；删除已知前驱 O(1)。
  • 按位访问:O(n)。
• 双链表：
  • 在任意位置插入/删除均 O(1)（已知位置指针）。
  • 占用内存多，维护 prev 指针。
• 循环链表：
  • 头尾相连，方便尾插和循环遍历。
• 优缺点对比：
  • 链表优点：插入/删除无大量移动，灵活、不易溢出（动态分配）。
  • 链表缺点：按位访问慢，空间开销（指针），频繁 malloc/free 成本。

三、常用链表构造方法（重点掌握伪码/实现）

• 头插法（单链表）：逐个新建节点，将新节点 next 指向原首节点，更新头指针。结果为输入序列的逆序。
• 尾插法（单链表）：维护尾指针，节点插入尾部，保持原序。效率好（O(1) 每次插入），但要初始化尾指针。
• 双链表插入/删除：注意四个指针赋值顺序以免断链。
• 带头结点 vs 无头结点：带头结点可统一处理边界，操作更简洁。

四、典型算法与题型（掌握步骤与复杂度）

1. 查找与定位

• GetElem(i)：顺序表 O(1)，链表 O(i)。
• LocateElem(value)：顺序/链表均 O(n)，可指定比较函数（值/约束）。

1. 插入与删除

• 顺序表插入 i：检查容量->从 n 到 i 移动元素 ->放入 -> n++（O(n)）。
• 单链表插入在第 i 个位置：找到第 i-1 个节点 ->调整指针（O(i)）。
• 删除：顺序表删除 i：移动元素覆盖 -> n–；链表删除：找到前驱->断链->释放（O(i)）。
• 注意边界（头尾、空表、越界）。

1. 反转链表（必考）

• 迭代法（三指针 prev,curr,next）：
  • prev=null; curr=head;
  • while curr: next=curr.next; curr.next=prev; prev=curr; curr=next;
  • 最终 prev 为新头。
  • 时间 O(n)，空间 O(1)。
• 递归法：递归返回新头，尾部反转指针（注意递归深度）。
• 注意：带头结点和不带头结点实现差别。

1. 合并两个有序线性表（合并有序表/链表）

• 顺序表：双指针，从后向前合并或开新数组 O(m+n)。
• 链表：类似，移动节点指针直接链接 O(m+n)，不需额外空间（就地合并）。

1. 删除重复元素/删除指定值

• 有序表/链表删除重复：一次遍历，维护慢指针/快指针，覆盖/断链。
• 无序则需辅助结构或双重遍历 O(n^2)，或者哈希 O(n)。

1. 找倒数第 k 个节点（双指针法）

• 快指针先走 k 步，然后快慢同时走，快到尾慢即为倒数第 k（O(n)，常考）。

1. 链表判断是否有环 & 环入口（Floyd 判圈）

• 慢指针每次 +1，快指针 +2，若相遇则有环。
• 找环入口：相遇后，让一指针回到头，两个指针同速前进，相遇点即环入口（证明需理解）。

1. 求链表中点（快慢指针）

• 快每次 +2，慢 +1：当快到尾时慢为中点（对奇偶情况处理）。

1. 静态链表（游标法）

• 用数组实现链表（每个元素包含 data,next），常用于考题：初始化备用链表、模拟 malloc/free（free list）。要会实现静态链表的插入删除、合并等。

1. 空间/时间复杂度常识

• 顺序表：访问 O(1)，插入/删除 O(n)。
• 链表：插入/删除（已知位置）O(1)，按序查找/按位访问 O(n)。

五、重要细节与易错点（考研常考）

• 插入与删除时下标边界（i 的取值范围）：插入 i 的合法范围通常 1..n+1，删除 i 为 1..n。
• 链表删除时确保找到前驱（尤其是单链表无头结点时），删除首节点时需更新头指针。
• 头插法造成序列逆序；题目若要求保持原序，应用尾插法或反转一次。
• 带头结点（dummy head）能简化边界处理，考题多用此形式。
• 释放内存（C 语言）：删除节点后必须 free，防内存泄露；静态链表无 malloc/free。
• 静态链表数组下标 0 常作为头或备用列表，注意题设约定。
• 循环链表插入删除的尾节点/头节点策略与单链表不同，注意指针更新顺序。
• 合并/分解链表题常留意链表是否原地操作（是否允许改变原链表结构）。

六、常见考题类型（复习/练习建议）

• 实现顺序表/链表的基本操作（插入、删除、获取、遍历）。
• 用不同方法实现链表反转（迭代/递归）。
• 合并两个已排序的线性表（数组/链表）。
• 删除单链表中所有值为 x 的结点（空间 O(1)）。
• 在 O(1) 时间下删除已知地址的结点（给出被删除节点，注意末尾特殊情况）。
• 判断环、求环入口、求环长度、找到中间节点、求倒数第 k 个节点。
• 静态链表（游标实现）：模拟 malloc/free，初始化备用链表，插入与删除。
• 用线性表实现栈和队列（顺序/链式两种实现比较）。

七、速记表（关键复杂度）

• 顺序表：
  • 访问（按序号）: O(1)
  • 查找（按值）: O(n)
  • 插入/删除（随机位置）: O(n)
• 单链表：
  • 访问(按序号): O(n)
  • 查找(按值): O(n)
  • 插入/删除(已知位置/前驱): O(1)
• 双链表：插入/删除(已知位置): O(1)，访问 O(n)

八、复习建议与笔记结构（如何整理到一页）

• 第一部分：定义与ADT操作一览（列出函数名与作用）。
• 第二部分：顺序存储 — 结构、地址映射、主要操作伪码、复杂度。
• 第三部分：链式存储 — 单/双/循环、节点结构、头/尾插法伪码、复杂度。
• 第四部分：必会算法清单（反转、合并、删除重复、找倒数第 k、判环）— 每个写出步骤+复杂度。
• 第五部分：典型考题与注意事项（边界和常错点）。
• 第六部分：静态链表与特殊技巧（如游标法、头结点技巧）。