数据结构大纲

作者：姚博文 · 2026-08-09

数据结构学习笔记（考研复习大纲）

1\. 数据结构概述

1.1 基本概念

· **数据**：信息的载体，是对客观事物的符号表示。

· **数据元素**：数据的基本单位，在程序中通常作为一个整体考虑。

· **数据项**：构成数据元素的不可分割的最小单位。

:::annotation 30

:::

· **数据对象**：性质相同的数据元素的集合，是数据的子集。

1.2 数据结构的三要素

1. **逻辑结构**：数据元素之间的逻辑关系。

· 线性结构（线性表、栈、队列、串）

· 非线性结构（树、图、集合）

2. **存储结构（物理结构）**：数据结构在计算机中的表示。

· 顺序存储：逻辑相邻，物理相邻（如数组）

· 链式存储：逻辑相邻，物理不一定相邻（如链表）

· 索引存储：建立索引表

· 散列存储：根据关键字直接计算存储地址

3. **数据的运算**：对数据施加的操作（如插入、删除、查找、排序）。

**易错点**：逻辑结构是独立于计算机的，存储结构是依赖计算机的。**同一逻辑结构可以有多种存储结构**。

1.3 算法与时间复杂度

· **算法特性**：有穷性、确定性、可行性、输入、输出。

· **时间复杂度**：$T(n)$ 表示算法执行时间随问题规模 $n$ 的增长趋势。

· 常见复杂度排序：$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

· **空间复杂度**：$S(n)$ 表示算法运行所需的辅助空间大小。

**易错点**：计算时间复杂度时，**忽略常数项和低阶项**，只保留最高阶项。递归算法的时间复杂度常与递推式相关，如 $T(n) = 2T(n/2) + O(n) \Rightarrow O(n\log n)$。

· * *

2\. 线性表

2.1 定义

线性表是具有相同数据类型的 $n$（$n \geq 0$）个数据元素的有限序列。

2.2 顺序存储（顺序表）

· 用一组地址连续的存储单元依次存储元素。

· **随机访问**：$O(1)$ 时间访问第 $i$ 个元素。

· 插入/删除：平均移动约 $n/2$ 个元素，时间复杂度 $O(n)$。

**易错点**：顺序表插入时，从后往前移动元素；删除时，从前往后移动元素。注意数组下标从 0 开始，逻辑位序从 1 开始。

2.3 链式存储（链表）

· **单链表**：每个结点含数据域和指针域（指向后继）。

· **双链表**：每个结点含前驱指针和后继指针。

· **循环链表**：尾结点指向头结点。

| 操作 | 顺序表 | 单链表 |

| --- | --- | --- |

| 查找第 $i$ 个 | $O(1)$ | $O(n)$ |

| 插入/删除（已知位置） | $O(n)$ | $O(1)$（已知前驱） |

| 空间 | 预分配，可能浪费 | 按需分配 |

**易错点**：单链表在插入/删除时，**必须先处理后继指针**，再处理前驱指针，否则会丢失结点。头结点不存储数据，其作用是统一空表与非空表的操作。

· * *

3\. 栈和队列

3.1 栈（Stack）

· **后进先出（LIFO）**。

· 基本操作：`Push`（入栈）、`Pop`（出栈）、`Top`（取栈顶）。

· 顺序栈：利用数组实现，栈顶指针 `top` 指向栈顶元素。

· 共享栈：两个栈共享一个数组，节省空间。

3.2 队列（Queue）

· **先进先出（FIFO）**。

· 基本操作：`EnQueue`（入队）、`DeQueue`（出队）。

· **循环队列**：解决假溢出问题。

· 队空条件：$front == rear$

· 队满条件：$(rear + 1) \% MaxSize == front$

· 队列长度：$(rear - front + MaxSize) \% MaxSize$

**易错点**：循环队列**牺牲一个存储单元**来区分队空和队满。若题中不牺牲空间，则需设置标志位或计数器。

3.3 栈的代码实现

**顺序栈（C 语言