---
title: 线性结构
tags:
  - module
  - data-structure-and-algorithm
  - linear-structure
  - joplin
type: module
source_type: reconstructed
created: 2026-04-22
updated: 2026-04-22
---

# 线性结构

> [!abstract]
> 这一模块处理最基础也最常考的一类结构。核心不是把表、栈、队列分开死记，而是理解“线性关系”和“操作受限”如何改变实现方式与复杂度。

## 模块结论

- [[顺序表]] 和 [[链表]] 解决的是同类线性关系，但一个偏随机访问，一个偏灵活插删。
- [[栈]] 和 [[队列]] 不是新结构，而是在一般线性表上增加操作限制。
- 串本质上也是特殊线性表，其重点在模式匹配，典型代表是 [[KMP]]。

## 一、线性表的两种基本实现

### 顺序表

- 用连续存储空间组织元素。
- 优点是随机访问快，按位查找方便。
- 缺点是中间插入删除通常需要大量移动元素。

### 链表

- 结点在逻辑上线性相连，物理上可不连续。
- 优点是插入删除灵活。
- 缺点是不能像数组一样直接按下标 O(1) 访问。

### 如何比较两者

- 查找某个位置的元素：顺序表更直接。
- 已知位置附近做插删：链表更灵活。
- 内存是否连续、是否需要扩容，也会影响选择。

## 二、单链表与双链表

- 单链表每个结点只记录后继。
- 双链表同时记录前驱和后继，删除与逆向访问更方便。
- 带头结点和不带头结点是另一条重要区分线。

### 复习重点

- 头结点常用于统一空表和首元结点操作。
- 删除链表结点时要分清是“已知前驱”还是“仅知当前结点”。

## 三、栈

- 后进先出，LIFO。
- 典型操作是入栈、出栈、取栈顶。
- 顺序栈和链栈分别对应顺序存储和链式存储。

### 高频应用

- 括号匹配
- 中缀表达式转后缀表达式
- 函数调用与递归过程

## 四、队列

- 先进先出，FIFO。
- 典型操作是入队、出队、取队头。
- 顺序队列的重点是循环队列与判空判满设计。
- 链队列的重点是 `front`、`rear` 指针维护。

### 循环队列常见判满方式

- 牺牲一个存储单元
- 额外维护 `size`
- 额外维护 `tag`

## 五、串与模式匹配

- 串是元素类型固定为字符的线性表。
- 重点不在存储本身，而在子串查找。
- 朴素匹配每次失配后回溯主串，[[KMP]] 则利用模式串自身信息减少回退。

## 六、易错点

- 不要把“顺序表查找快”误解为所有查找都快，它只是按位访问快。
- 链表插删快的前提通常是已经找到插删位置。
- 队列中 `front` 和 `rear` 的具体含义要结合实现约定看，不能脱离代码模板死记。
- KMP 的难点不是模板代码，而是 `next` / `nextVal` 表示什么。

## 七、复习提问

- 顺序表和链表分别适合什么操作场景？
- 栈和队列为什么说是“操作受限的线性表”？
- 循环队列为什么会出现判空判满冲突？
- KMP 相比朴素模式匹配到底省掉了什么回溯？

## 来源

- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/1.线性表 -- 顺序表.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/2.线性表 -- 单链表.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/3.线性表 -- 双链表.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/4.操作受限的线性表 -- 栈 -- 顺序栈.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/5.操作受限的线性表 -- 栈 -- 链栈.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/6.操作受限的线性表 -- 队列 -- 顺序队列.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/7.操作受限的线性表 -- 队列 -- 链队列.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/8.栈和队列的应用.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/9.串.md]]

## 相关页面

- [[数据结构与算法]]
- [[顺序表]]
- [[链表]]
- [[栈]]
- [[队列]]
- [[KMP]]