第二章 线性表
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顺序表的概念
- 顺序表：用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
- 顺序表的特点
- 随机访问，即可以在O(1)时间内找到第i个元素。
- 存储密度高，每个节点只存储数据元素。
- 扩展容量不方便。
- 插入删除操作不方便，需移动大量元素：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) | 索引越界 |
- 单链表的建立
- Step 1:初始化一个单链表
- 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)。
插入、删除：
顺序表的插入、删除操作，平均需要移动半个表长的元素。
链表的插入、删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。
