第三章 数据结构与算法基础
第二节 线性结构
概述
线性结构是数据结构中最基本、最常用的结构类型之一。本节内容旨在帮助考生系统掌握线性结构的核心概念、基本类型、存储方式及其基本操作。通过深入讲解顺序表、链表、栈和队列四种典型的线性结构，理解它们的工作原理和应用场景，为后续复杂数据结构和算法的学习打下坚实基础。
学习目标包括：
- 理解线性结构的定义和特点
- 掌握顺序表和链表的实现方法及区别
- 掌握栈和队列的概念与操作
- 分析各类线性结构的优缺点及适用场景
- 通过典型实例加深理解，避免常见误区
核心概念
线性结构：由n(n≥0)个数据元素组成的有序序列，数据元素之间存在一对一的线性关系。
- 数据元素：线性结构中的基本单位，存储实际数据。
- 顺序表：用一段连续的存储空间依次存放线性结构中的数据元素。
- 链表：通过指针将数据元素按线性顺序链接起来的存储结构，不要求物理地址连续。
- 栈（Stack）：一种只能在一端进行插入和删除操作的线性结构，遵循“先进后出”（LIFO）原则。
- 队列（Queue）：一种只能在一端进行插入操作，在另一端进行删除操作的线性结构，遵循“先进先出”（FIFO）原则。
原理分析
线性结构的存储原理
顺序存储方式：采用一块连续的内存空间存储元素。通过元素下标计算地址，支持随机访问，访问效率高，但插入和删除操作效率低，且存在容量固定限制。
链式存储方式：每个元素包含数据部分和指向下一个元素的指针，元素不必连续存储。插入和删除操作灵活，但访问元素需要从头遍历，访问效率较低。
关键操作原理
插入：在指定位置添加新元素。顺序表可能需要移动后续元素，链表只需调整指针。
删除：移除指定位置元素。顺序表需移动元素填补空缺，链表调整指针。
查找：根据值或位置查找元素。顺序表支持快速索引，链表需遍历。
栈和队列工作机制
栈：操作仅限于栈顶，压栈（push）和弹栈（pop）操作完成数据的存入和取出。
队列：数据从队尾入队，队头出队，保证数据先进先出。
详细内容
1. 线性结构定义与特点
线性结构中的元素呈现一条直线的逻辑关系，元素之间一对一相邻。主要特点：
- 元素有唯一直接前驱和后继（首元素无前驱，尾元素无后继）
- 结构简单，易于理解和实现
- 广泛应用于各类算法和系统设计
2. 顺序表
2.1 定义
顺序表是线性结构的一种顺序存储实现形式，采用数组连续存储。
2.2 结构特征
- 元素物理地址连续
- 支持随机访问
- 插入、删除操作时需移动元素
- 空间利用率受限，需预先分配空间
2.3 基本操作
- 初始化
- 查找元素（按值和按位置）
- 插入元素
- 删除元素
- 遍历
2.4 优缺点
| 优点 | 缺点 |
|---|---|
| 支持随机访问，访问速度快 | 插入和删除效率低，需大量移动元素 |
| 结构简单，实现方便 | 空间固定，扩容困难 |
3. 链表
3.1 定义
链表是由一系列节点组成的线性结构，节点由数据域和指针域组成，指针指向下一个节点。
3.2 结构类型
- 单链表
- 双向链表
- 循环链表
3.3 基本操作
- 创建链表
- 插入节点（头插法、尾插法）
- 删除节点
- 查找节点
3.4 优缺点
| 优点 | 缺点 |
|---|---|
| 动态分配内存，空间灵活 | 访问速度慢，需遍历 |
| 插入和删除操作效率高 | 额外存储指针，空间开销大 |
4. 栈
4.1 定义
栈是一种特殊的线性结构，只允许在一端进行插入和删除操作。
4.2 主要操作
- push：压栈，将元素放入栈顶
- pop：弹栈，从栈顶取出元素
- peek/top：查看栈顶元素
4.3 实现方式
- 顺序栈（数组实现）
- 链式栈
4.4 应用示例
- 表达式求值
- 函数调用管理
- 括号匹配
5. 队列
5.1 定义
队列是一种特殊线性结构，遵循先进先出原则。
5.2 主要操作
- enqueue：进队，在队尾插入元素
- dequeue：出队，从队头删除元素
5.3 实现方式
- 顺序队列
- 链式队列
- 循环队列
5.4 应用示例
- 任务调度
- 缓冲管理
- 广度优先搜索
实例分析
实例1：顺序表插入操作
背景：在顺序表中，在第3个位置插入元素“X”。
分析：
- 确认插入位置是否合法
- 将位置3及之后的元素依次后移一位
- 将“X”存入位置3
结论：顺序表插入需要移动大量元素，时间复杂度O(n)，适合元素少且访问多的场景。
实例2：单链表删除指定节点
背景：删除单链表中值为“5”的节点。
分析：
- 从头节点开始遍历，找到前驱节点指向值为“5”的节点
- 将前驱节点的指针指向待删节点的后继节点
- 释放待删节点内存
结论：链表删除操作只需调整指针，无需移动元素，效率较高。
实例3：栈实现括号匹配校验
背景：判断字符串“( [ ] { } )”中的括号是否匹配。
分析：
- 遍历字符串，遇到左括号push入栈
- 遇到右括号pop栈顶元素，匹配对应类型
- 最终栈为空且匹配成功则括号匹配正确
结论：栈结构适合处理匹配和回溯问题。
常见误区
认为链表一定比顺序表效率高
事实：链表插入删除快，但访问速度慢，顺序表访问快。
栈可以任意位置插入元素
实际：栈只能在栈顶操作，不能中间插入。
队列进队和出队操作可以在同一端完成
实际：队列进队和出队分别在队尾和队头操作。
顺序表容量无限大
实际：顺序表容量固定，超出需扩容。
链表中的指针域可以随意修改
实际：错误修改指针易导致链表断裂。
应用场景
- 顺序表：适合元素数量固定且访问频繁的场景，如学生成绩管理。
- 链表：适合频繁插入删除的动态数据，如操作系统中的进程管理。
- 栈：表达式计算、函数调用、撤销操作。
- 队列：任务调度、消息缓冲、打印队列。
知识拓展
- 双向链表：每个节点含有前驱和后继指针，支持双向遍历。
- 循环链表：尾节点指向头节点，适合循环任务管理。
- 链表与数组混合结构：如跳表，结合链表和数组优势。
- 栈的变种：双栈、带最小值功能的栈。
- 队列的拓展：优先队列，基于堆实现。
总结回顾
线性结构作为数据结构基础，关键在于理解其定义、存储方式及操作原理。顺序表适合访问多、插入删除少的场景，链表适合频繁修改数据。栈和队列作为特殊线性结构，解决了先进后出和先进先出的具体问题。通过实例分析和常见误区梳理，考生应牢固掌握各类线性结构的特性和适用场景，为后续学习打牢基础。