一、数据结构基本概念与术语
数据结构是计算机科学中的基础学科，它研究数据元素之间的逻辑关系、在计算机中的物理表示以及对数据的操作方法。数据结构主要包括三个层面：逻辑结构、存储结构和数据运算。
1. 基本术语
- 数据（Data）：能被计算机识别、存储和加工的符号集合，包括数值型和非数值型数据
- 数据元素（Data Element）：数据的基本单位，在程序中作为一个整体被考虑和处理，也称为记录、结点或顶点
- 数据项（Data Item）：构成数据元素的不可分割的最小单位，如学号、姓名等
- 数据对象（Data Object）：性质相同的数据元素的集合，是数据的一个子集，如整数集合、字母字符集合等
2. 逻辑结构
数据元素之间的逻辑关系，与数据的存储无关，独立于计算机，是从具体问题抽象出来的数学模型。逻辑结构分为四种基本类型：
- 集合：元素之间除了同属一个集合外，没有其他关系
- 线性结构：数据元素之间是一对一的关系，如线性表、栈、队列
- 树形结构：数据元素之间是一对多的关系，如二叉树、树与森林
- 图状结构或网状结构：数据元素之间是多对多的关系，如图结构
3. 存储结构
数据元素及其关系在计算机内存中的表示，也称为物理结构或数据的存储结构。存储结构主要分为四种：
- 顺序存储：逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，如数组
- 链式存储：不要求逻辑上相邻的元素在物理地址上也相邻，通过指针连接，如链表
- 索引存储：建立附加的索引表，索引项一般形式是（关键字，地址）
- 散列存储：哈希存储，根据关键字直接计算出该元素的存储地址
二、线性结构
线性结构是数据结构中最基础的结构，其特点是数据元素之间存在一对一的关系，形成一个线性序列。
1. 线性表
线性表是最基本的线性结构，由n(n≥0)个数据元素构成的有限序列。每个数据元素有前驱和后继，除首尾元素外，每个元素有且仅有一个前驱和一个后继。
顺序存储结构：线性表在内存中连续存放，地址递增。其操作主要包括：
- 插入：需要移动后续元素，时间复杂度O(n)
- 删除：同样需要移动后续元素，时间复杂度O(n)
- 访问：通过索引直接访问，时间复杂度O(1)
链式存储结构：通过指针连接各数据元素，不要求物理地址连续。主要包括：
- 单链表：节点包含数据域和后继指针(next)
- 插入/删除操作（给定前驱时）为O(1)，但查找需遍历，时间复杂度O(n)
- 双链表：节点包含前驱指针(prior)、数据域和后继指针(next)，可双向遍历
- 循环链表：尾节点指向头节点（或头结点），判断循环结束条件变为p != L（L为头指针）
2. 栈与队列
栈(Stack)：后进先出(LIFO)的线性表，顺序栈（数组实现）和链栈（链表实现）。主要应用包括：
- 表达式求值：利用栈的特性处理运算符优先级
- 递归实现：函数调用栈自动管理递归过程
- 括号匹配：检查括号是否正确嵌套
队列(Queue)：先进先出(FIFO)的线性表，包括顺序队列和链队列。顺序队列通常采用循环队列实现，以解决假溢出问题：
- 队空条件：Q.front == Q.rear
- 队满条件：(Q.rear + 1) % MaxSize == Q.front（牺牲一个单元）
- 链队列：通常带有头结点的单链表实现
双端队列(Deque)：两端都可插入删除的特殊队列，支持在队列头部和尾部进行操作。
三、树形结构
树形结构是一种一对多的层次结构，具有天然的层次关系，是数据结构中最重要的非线性结构之一。
1. 二叉树
基本概念与性质：
- 二叉树的定义：每个节点最多有两个子节点（左子树和右子树）的树结构
- 二叉树的五个性质：
- 第i层至多有2^(i-1)个节点（i≥1）
- 深度为k的二叉树至多有2^k -1个节点（k≥1）
- 叶子节点数n0 = 度为2的节点数n2 +1（n0 = n2 +1）
- 具有n个节点的完全二叉树深度为⌊log₂n⌋ +1
- 满二叉树和完全二叉树的区别
存储结构：
- 顺序存储：适用于完全二叉树，通常用数组实现
- 链式存储：二叉链表，每个节点包含左指针、数据域和右指针
遍历方法：
- 先序遍历（根左右）：递归或借助栈实现
- 中序遍历（左根右）：递归或借助栈实现
- 后序遍历（左右根）：递归或借助栈实现
- 层次遍历：借助队列实现，按树的层序访问节点
特殊二叉树：
- 二叉搜索树(BST)：左子树所有节点的值小于根节点的值，右子树所有节点的值大于等于根节点的值，其插入、删除及查找效率分析是重点
- 平衡二叉树(AVL树)：左右子树高度差的绝对值不超过1，需掌握平衡因子计算与旋转调整（LL、RR、LR、RL四种旋转）
- 哈夫曼树：带权路径长度(WPL)最小的二叉树，掌握构造方法（自底向上）和编码方法（前缀编码特性）
- 堆：一种特殊的完全二叉树，分为大根堆和小根堆，堆顶元素是最大或最小的元素。2025大纲新增堆的应用，如优先队列、TopK问题和动态数组中位数求解
线索二叉树：利用空指针指向遍历序列的前驱或后继（ltag和rtag标识指针含义），解决二叉树遍历需要栈或递归的问题。
2. 树与森林
树的存储结构：
- 双亲表示法：每个节点存储其双亲节点的位置
- 孩子表示法：每个节点存储其所有子节点的指针
- 孩子兄弟表示法：将树转换为二叉树，左指针指向第一个孩子，右指针指向下一个兄弟
森林与二叉树转换：掌握森林转换为二叉树的方法，每棵树转换为二叉树后，将后续二叉树作为前一颗二叉树根节点的右子树。
树和森林的遍历：
- 树的先根遍历：访问根节点，然后依次先根遍历各子树
- 树的后根遍历：先依次后根遍历各子树，然后访问根节点
- 森林的遍历：按照树的排列顺序，依次遍历各树
并查集：一种树形结构的变体，用于处理动态连通性问题。掌握其基本操作（Find、Union）和路径压缩、按秩合并的优化方法，以及在最小生成树算法（Kruskal）中的应用。
四、图状结构
图状结构是一种多对多的网状结构，能够表示复杂的关系网络。
1. 图的基本概念
图由顶点集合V和边集合E组成，边连接两个顶点。根据边是否有方向，分为有向图和无向图。根据边是否有权值，分为有权图和无权图。
存储结构：
- 邻接矩阵：二维数组表示顶点间的连接关系，适用于稠密图
- 行和列分别表示顶点，矩阵元素表示边或权值
- 邻接表：链表数组表示顶点间的连接关系，适用于稀疏图
- 每个顶点对应一个链表，存储该顶点的所有邻接顶点
2. 图的遍历
深度优先搜索(DFS)：从起始顶点出发，尽可能深地访问未被访问的顶点，直到没有未被访问的顶点为止，然后回溯。
广度优先搜索(BFS)：从起始顶点出发，依次访问其所有邻接顶点，然后访问这些邻接顶点的邻接顶点，直到所有顶点都被访问。
遍历的应用：
- 连通分量：判断图中是否存在多个不连通的子图
- 拓扑排序：对有向无环图进行线性排序，使得每个节点都在其所有前驱节点之后
- 关键路径：在AOE网（带权有向无环图）中找出从开始到结束的最长路径，表示项目完成的最短时间
3. 最短路径与最小生成树
最短路径算法：
- Dijkstra算法：单源最短路径，适用于边权非负的有向图或无向图，时间复杂度O(n²)
- Floyd算法：多源最短路径，适用于任意权值的有向图或无向图，时间复杂度O(n³)
最小生成树算法：
- Prim算法：基于贪心策略，每次选择当前最短的边，时间复杂度O(n²)
- Kruskal算法：基于并查集，按边权从小到大选择边，直到形成生成树，时间复杂度O(mlogm)
五、查找结构
查找结构用于解决在数据集合中快速定位特定元素的问题，是数据库、文件系统等实际应用中的核心技术。
1. 基本查找方法
顺序查找：从表头开始依次比较每个元素，直到找到目标或遍历完整个表。时间复杂度O(n)。
折半查找：适用于有序表，每次将查找范围缩小一半。掌握判定树构建及平均查找长度(ASL)计算方法，时间复杂度O(logn)。
分块查找：将表分为若干块，每块有序，块间无序。需掌握索引表的构建和查找过程，时间复杂度O(logm + k)，其中m为块数，k为块内元素数。
2. 散列查找
哈希表：通过哈希函数将关键字映射到存储位置。掌握构造方法（如除留余数法）和冲突处理方法（开放定址法、链地址法）。
开放定址法：冲突时寻找下一个空位置。常用方法有线性探测、平方探测和双哈希函数。
链地址法：将冲突的关键字链接成一个链表。每个哈希地址对应一个链表头，查找时遍历链表。
哈希查找的效率分析：掌握平均查找长度(ASL)的计算方法，以及如何选择合适的哈希函数和处理冲突的方法。
3. 树型查找
二叉搜索树(BST)：掌握插入、删除和查找操作，以及平衡二叉树（AVL树）的平衡调整方法。
B树与B+树：多路平衡查找树，适用于数据库和文件系统。掌握B树的插入、删除和查找操作，以及B+树的结构特点和应用场景。
红黑树：一种平衡二叉搜索树，通过颜色约束保证树的高度平衡。掌握红黑树的插入和删除操作，以及旋转和颜色调整的规则。
六、排序结构
排序是将数据元素按关键字大小排列成一个有序序列的过程，是数据处理的基础操作。
1. 内部排序
插入排序：将待排序元素插入到已排序序列的适当位置。掌握直接插入排序、希尔排序（按增量序列分组插入）的实现和时间复杂度分析。
交换排序：通过交换相邻元素的位置来实现排序。掌握冒泡排序和快速排序的实现和时间复杂度分析。快速排序的partition过程是核心，需掌握其递归实现和平均时间复杂度O(nlogn)。
选择排序：每次从未排序序列中选择最小（或最大）元素，放到已排序序列的末尾。掌握直接选择排序和堆排序的实现。堆排序通过构建堆结构实现，时间复杂度O(nlogn)，是大纲新增重点内容。
归并排序：将待排序序列分成若干个子序列，分别排序后再合并。掌握递归和迭代实现方法，时间复杂度O(nlogn)，空间复杂度O(n)，稳定性分析。
基数排序：按照关键字的各位数字进行排序。掌握LSD（最低位优先）和MSD（最高位优先）两种实现方法，适用于整数或字符串排序。
2. 排序算法比较
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模数据或基本有序的数据 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | 不稳定 | 大规模数据 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 小规模数据或基本有序的数据 |
| 快速排序 | O(nlogn) | O(n²) | O(logn)~O(n) | 不稳定 | 大规模数据 |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定 | 大规模数据 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 | 大规模数据或需要稳定排序的场景 |
| 基数排序 | O(dn) | O(dn) | O(n + k) | 稳定 | 关键字为整数或可分解为固定位数的字符串 |
七、算法设计与分析方法
算法设计与分析是数据结构应用的核心，需要掌握基本的分析方法和设计原则。
1. 时间复杂度与空间复杂度分析
时间复杂度：算法执行所需时间与问题规模n的关系，常用大O表示法表示。
基本分析方法：
- 循环结构：单层循环时间复杂度O(n)，双层循环O(n²)，三层循环O(n³)
- 递归关系：通过递归树或主定理分析递归算法的时间复杂度
- 主定理适用于形如T(n)=aT(n/b)+f(n)的递归式，其中a≥1，b>1，f(n)渐进趋正
- 根据f(n)与n^{log_b a}的关系，分为三种情况确定时间复杂度
- 摊还分析：用于评估数据结构中一系列操作的整体效率，不涉及输入概率，能够保证在最坏情况下操作的平均性能
- 聚合分析：计算所有操作的总代价除以操作次数
- 核算法：为不同操作赋予不同费用，差额部分存入数据结构作为信用
- 势能法：通过势能变化来分析摊还代价
常见时间复杂度量级：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)，量级越低，算法效率越高。
2. 算法设计方法
分治法：将问题分解为若干个规模较小的独立子问题，递归求解子问题，然后合并子问题的解形成原问题的解。典型应用包括归并排序、快速排序等。
动态规划：适用于具有最优子结构和重叠子问题性质的问题。通过定义状态和状态转移方程，自底向上或自顶向下求解各阶段子问题的最优值。典型应用包括最长公共子序列、背包问题等。
贪心法：在每一步选择中，总是做出当前局部最优的选择，不回溯，不考虑全局最优。典型应用包括哈夫曼编码、活动选择问题等。
回溯法：通过尝试各种可能的路径，当发现当前路径无法满足条件时，回溯到上一节点尝试其他路径。适用于组合优化问题，如八皇后问题、0-1背包问题等。
分支限界法：在回溯法的基础上，通过设置限界条件来剪枝，提高搜索效率。适用于组合优化问题，如任务调度问题、旅行商问题等。
3. 算法设计原则
正确性：算法必须能正确解决问题，得到预期结果。
可读性：算法应易于理解和修改，提高代码的可维护性。
健壮性：算法应能对非法输入做出适当处理，避免程序崩溃。
高效性：算法应在时间和空间上尽可能高效，减少资源消耗。
模块化：将复杂问题分解为若干个功能模块，提高代码的可重用性和可测试性。
空间换时间：通过增加空间开销来减少时间消耗，如哈希表、缓存等技术。
八、新增内容
2025年408考研大纲对数据结构部分进行了部分调整，新增了以下内容：
堆的应用：新增堆在优先队列、TopK问题和动态数组中位数求解中的应用。
数据结构的基本概念：更强调对数据元素之间特定关系的理解，以及数据结构三个层面（逻辑结构、存储结构、运算）的综合掌握。
算法的基本概念：明确算法的五个重要特性：有穷性、确定性、可行性、输入和输出。
设计一个好算法应考虑的因素：正确性、可读性、健壮性、高效率和低存储量要求。
九、总结与备考建议
数据结构是计算机考研408的基础科目，需要系统掌握基本概念、逻辑结构、存储结构和基本操作，以及算法设计与分析方法。备考时应重点掌握线性表、树、图、查找和排序五大模块的核心知识点。
对于线性结构，应掌握顺序存储和链式存储的实现方法，以及栈、队列、数组和特殊矩阵的压缩存储技术。
对于树形结构，应深入理解二叉树的性质、遍历和存储方法，以及特殊二叉树（如BST、AVL、哈夫曼树、堆）的实现和应用。
对于图状结构，应掌握邻接矩阵和邻接表的存储方法，以及DFS、BFS遍历算法，最短路径（Dijkstra、Floyd）和最小生成树（Prim、Kruskal）算法。
对于查找结构，应掌握顺序查找、折半查找、分块查找、散列查找和树型查找（如二叉搜索树、B树、红黑树）的实现和效率分析。
对于排序结构，应掌握各类排序算法的实现、时间复杂度、空间复杂度和稳定性，尤其是快速排序、归并排序、堆排序等重点内容。
对于算法设计与分析，应掌握时间复杂度和空间复杂度的分析方法，包括主定理和摊还分析等进阶内容，以及分治法、动态规划、贪心法等设计方法。
在备考过程中，建议通过画图理解数据结构的存储和操作过程，通过手写代码熟悉算法实现，通过复杂度分析掌握算法效率评估方法。同时，结合实际应用场景理解算法的价值，如堆在优先队列中的应用，哈希表在数据库索引中的应用等。通过系统梳理，构建完整的知识体系，为408考研做好充分准备。