C++ 核心数据结构 基础概念（一）

一、前置基础概念：时间复杂度

1.1 时间复杂度

• 含义：衡量算法运行时间随数据规模 n 增长的增长趋势，不考虑常数系数，只看最高阶项，用大 O 记号表示
  • O(1)：常数复杂度，固定次数运算（随机访问数组元素）
  • O(log n)：对数复杂度，每次减半查找（二分查找、红黑树查找）
  • O(n)：线性复杂度，遍历全部元素
  • O(n log n)：线性对数复杂度（快排、归并排序）
  • O(n²)：平方复杂度（两层嵌套循环、朴素冒泡排序）
  • O(2ⁿ)：指数复杂度（暴力递归）
• 补充：还有空间复杂度，衡量额外占用内存的增长趋势

1.2 内存层面：栈(Stack内存区) vs 堆(Heap内存区)

✅ 栈内存（系统栈 / 调用栈）

• 内存特点：连续、由编译器自动分配释放、后进先出LIFO、容量很小（几MB）、分配速度极快
• 存放内容：局部变量、函数参数、函数返回地址、静态数组
• 生命周期：函数调用结束自动销毁，超出容量会发生栈溢出
• C++示例：int a; int arr[100];

✅ 堆内存（动态堆 / 自由堆）

• 内存特点：不连续、手动申请/释放、容量很大、分配速度较慢、全局有效
• 申请/释放：new / delete、malloc / free
• 生命周期：直到主动 delete / 程序结束才释放，忘记释放会造成内存泄漏
• C++示例：int *p = new int[100]; delete[] p;

注意区分：内存栈/堆和数据结构栈/堆（下文），二者不是同一个概念！

二、线性数据结构

2.1 数组

（1）定长静态数组

• 本质：连续整块内存、同类型元素、下标随机访问、长度编译期固定，不能动态扩容
• C++写法：

  intarr[10];// 栈上定长数组intarr2[5]={1,2,3,4,5};

• 特性：
  • ✅ 优点：随机访问 O(1)，遍历速度极快，缓存友好
  • ❌ 缺点：长度固定，无法灵活扩容；中间插入/删除 O(n)（需要整体移位）；易越界
  • 时间复杂度：随机访问 O(1)；头部插入/删除 O(n)；尾部追加（未满）O(1)

（2）不定长动态数组（C++：std::vector）

• 本质：底层是堆上的连续数组，自带动态扩容机制（通常容量不够时 ×2 扩容）
• 特性：
  • ✅ 优点：随机访问 O(1)，尾部增删 O(1)（ amortized 均摊），支持自动扩容
  • ❌ 缺点：中间/头部插入删除 O(n)；扩容时会拷贝全部元素产生开销
  • 时间复杂度：随机访问 O(1)，末尾 push_back 均摊 O(1)，中间插入 O(n)
  • 存储：数据存在堆内存，容器对象本身可在栈上

2.2 数据结构：栈 std::stack（容器适配器，默认底层 deque）

• 核心规则：LIFO 后进先出，只能在一端（栈顶）做插入和删除
• 核心接口：push()入栈、pop()出栈、top()取栈顶、empty()判空
• 时间复杂度：入栈、出栈、取栈顶均 O(1)
• 用途：函数调用、表达式求值、括号匹配、深度优先 DFS
• ❗不能随机访问内部元素，只能访问栈顶

2.3 队列 std::queue（容器适配器，默认底层 deque）

• 核心规则：FIFO 先进先出，一端入队（队尾），一端出队（队头）
• 核心接口：push()入队、pop()出队、front()队首、back()队尾
• 时间复杂度：入队、出队 O(1)
• 变种：
  • 双端队列std::deque：两端都可 O(1) 增删，支持下标随机访问，分段连续内存
  • 优先队列std::priority_queue：本质是堆结构，自动按优先级弹出最值
• 用途：任务排队、BFS广度优先遍历、消息缓冲

2.4 链表 & std::list

（1）原生链表（单向/双向链表）

• 本质：非连续内存节点，每个节点存数据 + 指针，指向后继/前驱节点
  • 单向链表：只有后继指针，只能向后遍历；查找 O(n)，头部增删 O(1)
  • 双向链表：同时存前驱+后继指针，可双向遍历
• ✅优点：任意已知位置插入删除 O(1)，无需整体移位、无连续内存限制、无扩容拷贝开销
• ❌缺点：不支持随机访问（访问第k个元素 O(n)），缓存不友好，额外占用指针内存

（2）std::list（C++ 标准双向链表）

• 特性：双向循环链表实现
  • 随机访问：不支持 [] 下标访问，遍历/查找 O(n)
  • 已知迭代器位置插入/删除：O(1)
  • 适合频繁中间增删、很少随机访问的场景

三、堆（数据结构堆，优先队列底层）

✅概念

• 本质：完全二叉树结构，通常用数组/vector存储，分为大顶堆、小顶堆
  • 大顶堆：父节点值 ≥ 子节点值，堆顶是最大值
  • 小顶堆：父节点值 ≤ 子节点值，堆顶是最小值
  • 索引规律：下标 i 的父节点 i/2；左孩子 2i+1；右孩子 2i+2
• C++：std::priority_queue默认是大顶堆
• 时间复杂度：
  • 建堆：O(n)
  • 插入元素、弹出堆顶元素：O(log n)
  • 获取最值：O(1)
• 用途：TopK 问题、堆排序、任务调度、Dijkstra最短路径算法

四、树、二叉树、二叉搜索树、红黑树

4.1 树

• 概念：n 个节点的非线性层级结构，1个根节点；其余节点分为若干互不相交子树，无环、连通
  • 节点：根节点、父节点、子节点、叶子节点、深度、高度
  • 特点：适合存储层级数据（目录、组织结构）
  • 遍历：前序、中序、后序、层序遍历

4.2 二叉树

• 概念：每个节点最多只有 2 个子节点（左子树、右子树）
  • 满二叉树：每一层节点都填满
  • 完全二叉树：除最后一层外全部填满，最后一层靠左排布（堆的底层结构）
  • 遍历：前序(根左右)、中序(左根右)、后序(左右根)、层序遍历
  • 普通二叉树：查找效率差，最坏退化成链表 O(n)

4.3 二叉搜索树 BST（Binary Search Tree）

• 核心规则：
  • 左子树所有节点值 < 根节点值
  • 右子树所有节点值 > 根节点值
  • 中序遍历 = 升序序列
• 理想时间复杂度：查找/插入/删除 O(log n)
• ❌ 缺陷：极端数据下退化成单侧链表，复杂度退化 O(n)，失去平衡
• 目的：快速查找、有序遍历

4.4 红黑树（平衡二叉搜索树）

• 概念：自平衡二叉搜索树，通过变色+旋转保持平衡，解决普通BST退化问题
• 五大核心规则：
  1. 节点颜色只有 红色 / 黑色
  2. 根节点一定是黑色
  3. 所有叶子节点（NIL空节点）都是黑色
  4. 红节点的子节点必须都是黑色（不能有连续红节点）
  5. 任意节点到其所有后代叶子节点的路径上，黑节点数量相同（黑高一致）
• 特性：保证最长路径不超过最短路径的 2 倍，始终保持近似平衡
  • 查找/插入/删除：稳定 O(log n)
  • C++：std::map/std::set底层默认实现就是红黑树
• ✅优点：查找稳定高效、有序遍历；❌缺点：插入删除需要额外旋转变色开销

五、哈希结构 & 关联容器

5.1 哈希表（Hash Table）

• 核心原理：通过哈希函数把 key 映射到数组下标，直接定位存储位置；存在哈希冲突（不同key映射同一位置）
  • 冲突解决方法：链地址法（链表/红黑树）、开放寻址法
  • C++：std::unordered_map/unordered_set
  • 时间复杂度：平均查找/插入/删除 O(1)；最坏情况（大量冲突）退化为 O(n)
  • ✅优点：查询速度极快；❌缺点：无序、占用内存更大、存在哈希冲突风险，不支持有序遍历

5.2 std::map

• 底层：红黑树（平衡BST）
  • 键值对 key-value，key 唯一，默认按 key 升序排序
  • 查找/插入/删除：稳定 O(log n)
  • ✅优点：有序遍历、范围查找稳定；❌缺点：比 unordered_map 查询慢
  • 支持：[]访问、迭代器有序遍历

5.3 std::unordered_map

• 底层：哈希表
  • key 唯一，无序存储，不保证遍历顺序
  • 平均查找/插入/删除 O(1)，查询速度更快
  • ✅优点：高频单点查询性能优秀；❌缺点：无序、迭代器不稳定、存在哈希冲突
  • 适合：高频单点查找，不需要有序遍历的场景

5.4 std::set / std::unordered_set

- set：红黑树，有序、唯一元素、O(log n) - unordered_set：哈希表，无序、唯一元素、平均 O(1)

六、快速对比总结

七、补充记忆要点

1. 内存栈 ≠ 数据结构栈、内存堆 ≠ 数据结构堆，两套概念务必区分开
2. 连续数组：擅长随机访问，不擅长中间插入；链表反之
3. 红黑树：稳定 O(log n)、有序；哈希表：平均 O(1)、无序
4. BST 的隐患：不平衡会退化成链表；红黑树本质就是用来保持 BST 平衡