第一章 绪论：基础概念体系
🚩算法：问题求解步骤的描述。
🚩非递归的算法效率更高。
1.1 逻辑结构 vs 存储结构
| 维度 | 逻辑结构 | 存储结构（物理结构） |
|---|
| 定义 | 数据元素之间的逻辑关系 | 数据结构在计算机中的实现方式 |
| 分类 | 线性/树形/图/集合 | 顺序/链式/索引/散列 |
| 独立性 | 独立于存储结构 | 依赖逻辑结构 |
| 示例 | 线性表、有序表、数组（抽象层面） | 顺序表、链表、静态链表 |
| ADT描述 | 描述操作语义 | 描述具体实现 |
1.2 抽象数据类型(ADT)三要素
ADT List {数据对象：D = {a_i | a_i∈ElemSet, i=1,2,...,n}数据关系：R = {<a_{i-1},a_i> | a_{i-1},a_i∈D}基本操作：InitList(&L), ListInsert(&L,i,e)...
}
第二章 三种表：具体实现对比
2.1 核心概念关系
| 术语 | 本质 | 所属层级 | 与其它概念关系 |
|---|
| 线性表 | 逻辑结构 | 逻辑层 | 可用顺序/链式存储实现 |
| 有序表 | 逻辑结构+约束 | 逻辑层 | 元素有序的线性表 |
| 顺序表 | 存储结构 | 物理层 | 线性表的顺序存储实现 |
| 数组【随机存取】 | 逻辑结构+存储结构 | 跨层概念 | 可视为特殊的顺序表 |
2.2 顺序表 vs 有序表 vs 线性表
| 特性 | 线性表（抽象） | 顺序表（实现） | 有序表（特殊） |
|---|
| 元素关系 | 前驱后继关系 | 物理相邻存储 | 按关键字有序 |
| 存储方式 | 与实现无关 | 连续内存空间 | 通常用顺序存储 |
| 查找效率 | O(n) | 按位O(1)，按值O(n) | 顺序存储时可二分O(logn) |
| 插入删除 | 依赖实现 | 移动元素O(n) | 需保持有序性O(n) |
- 栈和队列的ADT相同，即逻辑结构都是线性表。
- 顺序表具有随机存取是指：查找序号i的元素的时间，与顺序表中元素个数n无关
- 扩容问题➡顺序表插入算法：n个空间满了时，申请m个，若申请失败，则说明系统没有：n+m个可分配的存储空间（n也要被复制进新表）
- 对长度为n的、顺序存储的有序表，实现给定的算法中时间复杂度为O(1)的是：获取第i个值的算法。
- 线性表是具有n个同类型数据元素的有限序列。除开始元素外，每个元素只有唯一的前驱元素。
- 若非空线性表中的元素，既没有前驱也没有后继，则：表中只有1个元素。
- 线性表的顺序存储结构：是一种随机存取的存储结构。
- 线性表要取前驱后继则采用什么物理结构：顺序表最好。
- 线性表要取指定序号在最后插入删除：物理结构用顺序表最好。
- 按值查找一定要比较值，所以与长度有关。
第三章 存储结构
3.1 顺序存储 vs 链式存储
| 特性 | 顺序存储 | 链式存储 |
|---|
| 物理结构 | 连续内存空间 | 离散节点+指针 |
| 存储密度 | 100% ，所以密度大 | <100%（需存储指针） |
| 访问方式 | 随机存取（直接计算地址） | 顺序存取（必须遍历） |
| 插入删除 | O(n)（需移动元素） | O(1)（已知位置） |
| 扩容方式 | 需重新分配+复制 | 动态增长 |
| 缓存友好性 | 好（空间局部性） | 差 |
| 代表实现 | 顺序表、静态数组 | 单链表、双链表 |
| 典型应用 | 频繁随机访问场景 | 动态数据集合 |
| 能表示的逻辑结构 | 种类少 | 种类多 |
- 不能说某一种存储结构优于另一种
- 元素存放顺序与存储空间大小无关
- 顺序和链式都能顺序存取
3.2 数组的特殊性分析
| 视角 | 解释 | 示例 |
|---|
| 逻辑层 | 线性结构的推广（一维数组即线性表） | 矩阵是二维线性结构 |
| 物理层 | 顺序存储的典型实现 | int a[10]连续存储 |
| 操作特性 | 通过下标直接访问元素（本质是基地址+偏移量计算） | a[i] ≡ *(a+i) |
第四章 易混淆概念速查表
| 常见混淆对 | 区分关键 | 记忆技巧 |
|---|
| 顺序表 vs 数组 | 顺序表强调逻辑关系，数组侧重存储 | “数组是顺序表的具体实现” |
| 有序表 vs 顺序表 | 有序是逻辑约束，顺序是存储方式 | “有序表可以用链表实现” |
| 线性表 vs 链表 | 线性表是抽象概念，链表是具体实现 | “链表是实现线性表的方式” |
第五章 知识体系图谱
以下是补充栈（Stack）和队列（Queue）后的完整知识图谱，严格区分逻辑结构与存储结构，并标注实现方式：
