Obsidian-Knowledge-Base/X-Knowledge-Base/wiki/线性结构.md

---

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]]