数据结构是算法的基石按照存储逻辑可分为线性结构顺序表、链表、栈、队列和非线性结构二叉树、堆、哈希表。以下从核心原理、操作复杂度、代码实现、适用场景四个维度逐一拆解全部基于 C 语言适配算法刷题与工程实践。一、线性数据结构1. 顺序表Sequence List核心本质顺序表底层是一段连续的内存空间用数组存储元素分为静态顺序表固定大小和动态顺序表可自动扩容。日常使用的数组、vector本质都是动态顺序表。核心特点支持随机访问通过下标 O (1) 时间定位元素这是最大优势内存连续缓存命中率高中间 / 头部插入删除需要移动大量元素效率低基本操作 时间复杂度表格操作时间复杂度说明按下标随机访问O(1)直接通过地址偏移计算位置尾插 / 尾删O(1)不涉及元素移动中间 / 头部插入删除O(n)需要移动操作位置后的所有元素按值查找O(n)需遍历整个数组动态扩容原理当空间不足时重新申请一块更大的连续空间通常扩容为原大小的 1.5~2 倍将原数据拷贝到新空间后释放旧空间。扩容的均摊时间复杂度为 O (1)。简易代码实现cpp运行class SeqList { private: int* data; int size; // 当前元素个数 int capacity; // 总容量 void expand() { if (size capacity) return; int newCap capacity 0 ? 4 : capacity * 2; int* newData new int[newCap]; memcpy(newData, data, size * sizeof(int)); delete[] data; data newData; capacity newCap; } public: SeqList() : data(nullptr), size(0), capacity(0) {} ~SeqList() { delete[] data; } void push_back(int val) { expand(); data[size] val; } void erase(int pos) { if (pos 0 || pos size) return; for (int i pos; i size - 1; i) data[i] data[i 1]; size--; } int operator[](int pos) { return data[pos]; } int getSize() const { return size; } };STL 对应容器vectorT动态顺序表最常用arrayT,N静态固定大小数组适用场景频繁随机访问、尾部操作多元素数量相对固定中间插入删除少对缓存性能要求高的场景2. 链表Linked List核心本质链表是离散内存存储的线性结构由若干节点串联而成每个节点包含「数据域 指针域」。常见类型单链表、双向链表、循环链表。核心特点不支持随机访问查找必须从头遍历插入删除只需修改指针无需移动元素效率高内存不连续无扩容问题但缓存命中率低分类对比表格类型结构特点优势劣势单链表仅后继指针结构简单内存占用小无法直接访问前驱节点双向链表前驱 后继指针可双向遍历删除更方便内存占用更大循环链表尾节点指向头节点可循环遍历边界处理复杂基本操作 时间复杂度表格操作时间复杂度说明头插 / 头删O(1)直接修改头指针指定节点后插入 / 删除O(1)仅修改指针前提是已找到节点按值查找 / 随机访问O(n)必须从头遍历经典操作代码单链表cpp运行struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; class LinkedList { private: ListNode* head; public: LinkedList() : head(nullptr) {} // 头插法 void push_front(int val) { ListNode* node new ListNode(val); node-next head; head node; } // 反转链表迭代法 void reverse() { ListNode* prev nullptr; ListNode* curr head; while (curr) { ListNode* next curr-next; curr-next prev; prev curr; curr next; } head prev; } // 删除指定值节点 void remove(int val) { ListNode dummy(0); dummy.next head; ListNode* curr dummy; while (curr-next) { if (curr-next-val val) { ListNode* tmp curr-next; curr-next curr-next-next; delete tmp; } else { curr curr-next; } } head dummy.next; } };STL 对应容器listT双向循环链表forward_listT单链表C11 引入顺序表 vs 链表 核心对比表格维度顺序表链表内存分布连续离散随机访问O(1)O(n)中间插入删除O(n)O (1)找到节点后缓存命中率高低空间开销有扩容冗余每个节点额外存指针适用场景频繁在头部 / 中间插入删除元素数量动态变化大不需要随机访问的场景3. 栈Stack核心本质栈是操作受限的线性表只允许在栈顶进行插入和删除遵循后进先出LIFO原则。底层可用数组或链表实现。基本操作 时间复杂度表格操作时间复杂度说明push入栈O(1)栈顶插入元素pop出栈O(1)删除栈顶元素top查看栈顶O(1)获取栈顶元素值emptyO(1)判断栈是否为空数组模拟栈实现cpp运行class ArrayStack { private: int* data; int topIdx; int capacity; public: ArrayStack(int cap 100) : capacity(cap), topIdx(-1) { data new int[capacity]; } ~ArrayStack() { delete[] data; } void push(int val) { if (topIdx 1 capacity) return; data[topIdx] val; } void pop() { if (topIdx 0) topIdx--; } int top() { return data[topIdx]; } bool empty() { return topIdx -1; } };STL 对应容器stackT栈适配器默认底层是deque也可指定vector或list经典应用场景括号匹配、表达式求值逆波兰式递归转迭代二叉树遍历、DFS 深度优先搜索单调栈解决下一个更大元素、柱状图最大矩形等问题函数调用栈、浏览器前进后退4. 队列Queue核心本质队列也是操作受限的线性表只允许队尾插入、队头删除遵循先进先出FIFO原则。常见分类普通队列一端进一端出双端队列Deque两端都可插入删除循环队列数组实现时解决 “假溢出”提高空间利用率基本操作 时间复杂度表格操作时间复杂度说明push入队O(1)队尾插入pop出队O(1)队头删除front / backO(1)查看队头 / 队尾元素循环队列实现数组版cpp运行class CircularQueue { private: int* data; int front; int rear; int capacity; public: // 牺牲一个位置区分空和满 CircularQueue(int k) : capacity(k 1), front(0), rear(0) { data new int[capacity]; } ~CircularQueue() { delete[] data; } bool enQueue(int value) { if (isFull()) return false; data[rear] value; rear (rear 1) % capacity; return true; } bool deQueue() { if (isEmpty()) return false; front (front 1) % capacity; return true; } int Front() { return data[front]; } bool isEmpty() { return front rear; } bool isFull() { return (rear 1) % capacity front; } };STL 对应容器queueT普通队列适配器默认底层dequedequeT双端队列两端均可 O (1) 插入删除priority_queueT优先级队列底层是堆经典应用场景广度优先搜索BFS任务调度、消息队列滑动窗口单调队列生产者消费者模型二、非线性数据结构5. 二叉树Binary Tree核心本质二叉树是每个节点最多有两个子节点左孩子、右孩子的树形结构是搜索树、堆、红黑树等高级结构的基础。基础概念满二叉树所有叶子节点在最后一层非叶子节点都有两个孩子完全二叉树除最后一层外其他层全满最后一层节点靠左排列二叉搜索树BST左子树 根 右子树中序遍历结果有序节点结构cpp运行struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };四大遍历方式核心考点遍历分为深度优先前 / 中 / 后序和广度优先层序是二叉树所有算法的基础。1递归遍历cpp运行// 前序根 - 左 - 右 void preorder(TreeNode* root, vectorint res) { if (!root) return; res.push_back(root-val); preorder(root-left, res); preorder(root-right, res); } // 中序左 - 根 - 右 void inorder(TreeNode* root, vectorint res) { if (!root) return; inorder(root-left, res); res.push_back(root-val); inorder(root-right, res); } // 后序左 - 右 - 根 void postorder(TreeNode* root, vectorint res) { if (!root) return; postorder(root-left, res); postorder(root-right, res); res.push_back(root-val); }2迭代遍历栈模拟面试高频以中序遍历为例cpp运行vectorint inorderIter(TreeNode* root) { vectorint res; stackTreeNode* stk; TreeNode* curr root; while (curr || !stk.empty()) { while (curr) { stk.push(curr); curr curr-left; } curr stk.top(); stk.pop(); res.push_back(curr-val); curr curr-right; } return res; }3层序遍历BFS队列实现cpp运行vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (!root) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } res.push_back(level); } return res; }时间复杂度遍历O (n)每个节点仅访问一次二叉搜索树查找平均 O (logn)最坏 O (n)退化成链表适用场景层级关系数据存储文件目录、组织架构排序与查找二叉搜索树、平衡二叉树表达式树、哈夫曼编码6. 堆Heap核心本质堆本质是一棵完全二叉树通常用数组存储分为两类大顶堆每个节点 ≥ 左右孩子堆顶是最大值小顶堆每个节点 ≤ 左右孩子堆顶是最小值数组下标规律根节点下标为 0左孩子2 * i 1右孩子2 * i 2父节点(i - 1) / 2核心操作 时间复杂度表格操作时间复杂度原理插入元素O(logn)插入数组末尾执行上浮删除堆顶O(logn)末尾元素覆盖堆顶执行下沉查看堆顶O(1)直接取数组首元素建堆O(n)从最后一个非叶子节点开始下沉核心操作代码大顶堆cpp运行class MaxHeap { private: vectorint data; // 上浮 void siftUp(int idx) { while (idx 0) { int parent (idx - 1) / 2; if (data[idx] data[parent]) break; swap(data[idx], data[parent]); idx parent; } } // 下沉 void siftDown(int idx) { int n data.size(); while (true) { int left 2 * idx 1; int right 2 * idx 2; int largest idx; if (left n data[left] data[largest]) largest left; if (right n data[right] data[largest]) largest right; if (largest idx) break; swap(data[idx], data[largest]); idx largest; } } public: void push(int val) { data.push_back(val); siftUp(data.size() - 1); } void pop() { if (data.empty()) return; data[0] data.back(); data.pop_back(); siftDown(0); } int top() { return data[0]; } bool empty() { return data.empty(); } };STL 对应容器priority_queueT优先级队列默认大顶堆小顶堆写法priority_queueint, vectorint, greaterint经典应用场景TopK 问题海量数据中找前 K 大 / 小堆排序任务优先级调度合并 K 个有序链表7. 哈希表Hash Table核心本质哈希表通过哈希函数将键key映射到数组下标实现平均 O (1) 的查找、插入、删除。核心逻辑key → 哈希函数 → 数组下标 → 存取数据。核心问题 1哈希函数要求计算速度快、分布均匀、相同 key 得到相同哈希值目的是将任意类型的 key 转为整数下标。核心问题 2哈希冲突不同 key 经过哈希函数得到相同下标称为哈希冲突。常见解决方法链地址法拉链法数组每个位置挂一个链表冲突元素放在同一条链表。STL 的unordered_map采用此方式。开放定址法冲突时向后寻找下一个空位置分为线性探测、二次探测。基本操作 时间复杂度表格操作平均时间复杂度最坏时间复杂度插入O(1)O (n)全冲突退化成链表删除O(1)O(n)查找O(1)O(n)当负载因子元素个数 / 数组长度超过阈值时哈希表会扩容 重哈希保证操作效率。STL 对应容器unordered_mapK,V键值对哈希表unordered_setT集合哈希表注意map/set底层是红黑树有序操作 O (logn)unordered_系列底层是哈希表无序平均 O (1)。经典应用场景快速查找、存在性判断频次统计、计数数组去重两数之和等经典算法题三、核心数据结构时间复杂度汇总表格数据结构随机访问查找插入删除空间顺序表O(1)O(n)O(n)O(n)O(n)单链表O(n)O(n)O (1)头插O (1)头删O(n)栈O(n)O(n)O(1)O(1)O(n)队列O(n)O(n)O(1)O(1)O(n)二叉搜索树O (logn) 平均O (logn) 平均O (logn) 平均O (logn) 平均O(n)堆O(n)O (1)堆顶O(logn)O(logn)O(n)哈希表-O (1) 平均O (1) 平均O (1) 平均O(n)四、选型总结频繁随机访问→ 顺序表vector频繁头尾插入删除→ 链表、栈、队列需要有序 快速查找→ 平衡二叉树map/set需要快速获取极值→ 堆priority_queue需要 O (1) 快速查找→ 哈希表unordered_map/unordered_set谢谢