一、数据结构的基本概念1.1 什么是数据结构数据结构Data Structure是相互之间存在一种或多种特定关系的数据元素的集合即数据的组织形式。它研究的不是数据本身而是数据元素之间的相互关系以及在这些关系上定义的操作。1.2 数据结构的三要素数据结构包括三个方面缺一不可要素研究内容是否依赖计算机逻辑结构数据元素之间的逻辑关系独立于计算机存储结构物理结构逻辑结构在计算机存储器中的实现映像必须依赖计算机数据的运算对数据元素施加的一组操作及其实现运算定义依赖逻辑结构实现依赖存储结构三者关系逻辑结构是设计图存储结构是落地实现运算是在这套结构上能做什么。二、数据的逻辑结构2.1 逻辑结构的特点独立于计算机只描述数据元素之间抽象的逻辑关系与数据在计算机中如何存储无关由设计者根据业务需求赋予是数据本身应该是什么样。2.2 逻辑结构的完整分类按数据元素之间关系的不同特性逻辑结构分为四大类经典分类法逻辑结构元素间关系关系特征典型例子集合元素除同属一个集合外无其他关系无特定关系数学中的集合线性结构元素按一对一的次序排列一对一线性表、栈、队列、串树形结构元素之间有层次关系一对多二叉树、多叉树、堆图状结构网状结构元素之间任意连接多对多有向图、无向图2.3 常见逻辑结构的归类分类数据结构线性结构线性表、栈、队列、字符串串、一维数组非线性结构树、二叉树、图、多维数组、广义表、集合需要特别辨析的两个结构⚠️广义表不是简单的线性结构广义表的元素既可以是原子也可以本身是一个广义表子表是递归结构。当所有元素都是原子时它退化为线性表当元素包含子表时它可以表示树形等非线性结构。因此广义表是线性表的递归推广不宜简单归为线性结构。⚠️多维数组不是线性结构一维数组是线性结构二维及以上的多维数组其元素下标具有多个维度元素之间不是简单的一对一关系通常归为非线性结构或作为数组结构单独讨论。三、数据的存储结构存储结构物理结构是逻辑结构在计算机存储器中的映像必须依赖具体的计算机和语言。基本的存储结构有四种。3.1 顺序存储原理把逻辑上相邻的元素存储在物理位置也相邻的存储单元中元素间的逻辑关系由存储单元的邻接关系体现优点支持随机存取按下标 O(1) 访问、存储密度高无额外指针开销、内存分配简单缺点需要连续的内存空间、插入/删除需要移动大量元素O(n)、可能产生外部碎片、扩容成本高。3.2 链式存储原理不要求物理位置相邻每个节点包含数据域和指针域用指针表示元素间的逻辑关系优点不要求连续内存空间、插入/删除只需修改指针O(1)已知位置时、动态增长灵活缺点指针占用额外存储空间、只能顺序存取不能随机访问、缓存局部性差节点分散。3.3 索引存储原理在存储元素信息的同时建立附加的索引表索引项由关键字和地址组成优点检索速度快可借助索引快速定位、支持复杂查询缺点索引表占用额外存储空间、增删元素时需要同步修改索引、维护成本高。典型应用数据库索引B 树、文件系统的索引节点。3.4 散列存储哈希存储原理根据元素的关键字通过哈希函数直接计算出存储地址优点理想情况下存取速度极快O(1)、查找过程无需逐个比较缺点存在哈希冲突需要冲突处理机制、不能反映元素间的逻辑关系、不支持顺序/范围访问、占用空间可能较大。典型应用哈希表、unordered_map。3.5 四种存储结构对比存储结构物理相邻随机存取额外开销典型数据结构顺序存储✅ 相邻✅ 支持无密度最高数组、vector链式存储❌ 不相邻❌ 不支持指针空间链表、树索引存储不要求借助索引索引表数据库 B 树索引散列存储不要求按哈希地址哈希表空间哈希表同一种逻辑结构可以采用不同的存储结构。例如线性表用顺序存储就是顺序表用链式存储就是链表——逻辑结构相同存储结构不同。四、数据的运算4.1 什么是数据的运算运算是对数据元素所施加的一组操作的总称。4.2 运算的两个层面层面内容依赖于运算的定义规定运算做什么、运算的功能和输入输出依赖于逻辑结构运算的实现运算具体怎么做、代码层面的执行依赖于存储结构例如插入运算在线性表的逻辑结构上定义为在第 i 个位置增加一个元素但顺序存储通过移动元素实现链式存储通过修改指针实现——定义相同实现不同。4.3 常见的基本运算插入、删除、查找检索、修改、排序、遍历等。4.4 抽象数据类型ADT抽象数据类型Abstract Data TypeADT 数据对象逻辑结构 数据关系 定义在其上的一组操作。ADT 只描述数据是什么、能做什么把定义和实现分离使用者只需要知道操作接口不需要关心底层存储细节。例如栈的 ADT 定义了 push/pop/top/isEmpty 等操作底层用数组还是链表实现对使用者透明。五、逻辑结构、存储结构与运算的关系┌──────────────┐ │ 逻辑结构 │ 独立于计算机设计者赋予 │ 数据关系 │ └──────┬───────┘ │ 映像到 ▼ ┌──────────────┐ │ 存储结构 │ 依赖计算机具体落地 │ 物理实现 │ └──────┬───────┘ │ 决定 ▼ ┌──────────────┐ │ 运算实现 │ 定义依赖逻辑结构实现依赖存储结构 └──────────────┘核心结论逻辑结构决定能定义哪些运算存储结构决定这些运算如何高效实现同一逻辑结构 不同存储结构 不同的具体数据结构如顺序表 vs 链表。六、从数据结构到 STL 容器STL标准模板库中的容器正是逻辑结构 存储结构不同组合的产物。6.1 序列式容器STL 容器逻辑结构存储结构说明array线性表顺序存储固定大小数组C11vector线性表顺序存储动态数组尾部增删快、随机存取deque线性表双端分段连续存储中央 map 数组 多个缓冲区头尾增删都 O(1)list线性表链式存储双向循环链表任意位置增删 O(1)forward_list线性表链式存储单向链表C11更省空间6.2 容器适配器⚠️ stack/queue/priority_queue 不是独立容器而是容器适配器它们包装一个底层容器实现特定接口。适配器逻辑结构默认底层容器说明stack栈LIFOdeque后进先出queue队列FIFOdeque先进先出priority_queue堆树形vector大顶堆默认每次取最大/最小元素6.3 关联式容器底层红黑树树形结构STL 容器逻辑结构存储结构特点set/multiset树平衡二叉搜索树链式存储元素有序、不重复 / 可重复map/multimap树平衡二叉搜索树链式存储键值对、键有序、键不重复 / 可重复底层都是红黑树增删查 O(log n)元素按 key 有序排列。6.4 无序关联容器底层哈希表散列存储STL 容器逻辑结构存储结构特点unordered_set/unordered_multiset集合散列存储平均 O(1) 查找、无序unordered_map/unordered_multimap集合键值对散列存储平均 O(1) 查找、键无序底层是哈希表开链法平均 O(1)最坏 O(n)元素无序。6.5 逻辑结构 存储结构 → STL 完整映射组合对应 STL线性表 顺序存储array、vector线性表 分段连续存储deque线性表 链式存储list、forward_list栈/队列 适配底层容器stack、queue树形结构堆 顺序存储priority_queue树形结构红黑树 链式存储set、map、multiset、multimap集合 散列存储unordered_set、unordered_map字符串 顺序存储string、string_view七、核心总结基本概念数据结构三要素逻辑结构、存储结构、数据的运算。逻辑结构独立于计算机存储结构依赖计算机是逻辑结构的映像运算定义依赖逻辑结构、实现依赖存储结构。逻辑结构四大逻辑结构集合、线性结构一对一、树形结构一对多、图状结构多对多。线性结构线性表、栈、队列、串、一维数组广义表是递归结构、多维数组是非线性结构不能简单归为线性。存储结构四种存储结构顺序存储随机存取、需连续空间、链式存储指针、不连续、索引存储索引表、散列存储哈希函数、O(1)。同一逻辑结构可以有多种存储实现线性表 → 顺序表 / 链表。运算与 ADT运算分定义做什么和实现怎么做两层ADT 把定义与实现分离只暴露操作接口。STL 容器序列式vector/array顺序、deque分段连续、list/forward_list链式适配器stack、queue、priority_queue包装底层容器默认 deque/deque/vector关联式set/map红黑树、有序、O(log n)无序关联unordered_set/map哈希表、平均 O(1)、无序。