第13章 数据结构

数据结构不是“背一堆结构名称”，而是在回答三个问题：数据之间是什么逻辑关系，计算机如何存放它们，某个操作为什么快或慢。软考上午题常把概念、公式、遍历过程和算法模拟混在一起考，所以本章要按“结构特征 -> 存储方式 -> 操作代价 -> 典型题型”的顺序学。

本章主线

模块	学习页面	要掌握的核心
线性结构	线性结构概述、顺序表与链表、队列与栈、串	一对一逻辑关系、顺序/链式存储、受限操作、模式匹配
数组与矩阵	数组与矩阵概述、数组、矩阵	地址计算、按行/按列存储、特殊矩阵压缩
树	树概述、二叉树性质1、二叉树性质2、遍历、二叉排序树、最优二叉树、特殊二叉树	层次关系、二叉树性质、遍历序列、查找与构造
图	图概述、图的存储、图的遍历、拓扑排序、最小生成树与最短路径	多对多关系、邻接矩阵/表、遍历、路径与生成树算法

数据结构的四层理解

层次	关注点	例子
逻辑结构	元素之间有什么关系	线性表是一对一，树是一对多，图是多对多
存储结构	关系在内存中如何表示	顺序存储靠连续地址，链式存储靠指针
基本操作	插入、删除、查找、遍历如何执行	顺序表插入要移动元素，链表插入改指针
算法代价	时间复杂度和空间复杂度	数组随机访问 $O(1)$，链表按序查找 $O(n)$

本章常见题型

题型	做题方法
概念辨析	把相似结构放在同一张表中比较，不孤立背定义
地址计算	先确认下标起点、维度大小、按行还是按列，再套公式
栈/队列序列	手工模拟入栈、出栈、入队、出队
树遍历	用根、左、右的相对顺序重建过程
图算法	每一步记录访问集合、候选边、入度或距离

一张总览图

flowchart TD
  DS["数据结构"] --> Linear["线性结构"]
  DS --> Tree["树结构"]
  DS --> Graph["图结构"]
  Linear --> Seq["顺序表/数组"]
  Linear --> Link["链表"]
  Linear --> Stack["栈"]
  Linear --> Queue["队列"]
  Linear --> String["串"]
  Tree --> BT["二叉树"]
  Tree --> BST["二叉排序树"]
  Tree --> Huffman["最优二叉树"]
  Graph --> Storage["邻接矩阵/邻接表"]
  Graph --> Traverse["DFS/BFS"]
  Graph --> Path["最小生成树/最短路径"]

学习时的重点提醒

1. 不要只记“顺序表查找快、链表插入快”，要能说出原因。
2. 公式题不要直接套，先看下标从 0 还是从 1 开始。
3. 栈序列题一定画过程，不能凭感觉判断。
4. 树和图的算法题一定记录中间状态，考试就是考你每一步有没有走对。