一、线性表
1. 数组 vs 链表
| 对比维度 | 数组 | 链表 |
|---|---|---|
| 存储方式 | 连续内存 | 离散内存（节点 + 指针） |
| 随机访问 | O(1) | O(n) |
| 插入/删除（头部） | O(n) | O(1) |
| 插入/删除（尾部） | O(1) | O(n)（需遍历到尾） |
| 内存利用率 | 可能有浪费（扩容） | 每个节点多存指针，有额外开销 |
| 缓存友好 | ✅ 连续内存，缓存命中率高 | ❌ 跳跃访问，缓存不友好 |
代码实现 - 单链表（必会）：
cpp
#include <iostream> using namespace std; struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; class LinkedList { private: ListNode* head; public: LinkedList() : head(nullptr) {} // 头插法 void insertHead(int val) { ListNode* newNode = new ListNode(val); newNode->next = head; head = newNode; } // 尾插法 void insertTail(int val) { ListNode* newNode = new ListNode(val); if (head == nullptr) { head = newNode; return; } ListNode* cur = head; while (cur->next != nullptr) { cur = cur->next; } cur->next = newNode; } // 删除值为 val 的节点 void remove(int val) { if (head == nullptr) return; // 头节点特殊处理 if (head->val == val) { ListNode* temp = head; head = head->next; delete temp; return; } ListNode* cur = head; while (cur->next != nullptr && cur->next->val != val) { cur = cur->next; } if (cur->next != nullptr) { ListNode* temp = cur->next; cur->next = cur->next->next; delete temp; } } // 反转链表（⭐高频） ListNode* reverse() { ListNode* prev = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* nextTemp = cur->next; cur->next = prev; prev = cur; cur = nextTemp; } head = prev; return head; } // 打印 void print() { ListNode* cur = head; while (cur != nullptr) { cout << cur->val << " -> "; cur = cur->next; } cout << "nullptr" << endl; } };2. 栈（Stack）
特点：后进先出（LIFO）
应用场景：函数调用栈、括号匹配、表达式求值、撤销操作
代码实现 - 用数组模拟栈：
cpp
class Stack { private: int* data; int capacity; int topIndex; // 栈顶索引，-1 表示空 public: Stack(int cap = 100) : capacity(cap), topIndex(-1) { data = new int[capacity]; } ~Stack() { delete[] data; } bool isEmpty() { return topIndex == -1; } bool isFull() { return topIndex == capacity - 1; } void push(int val) { if (isFull()) { cout << "栈满" << endl; return; } data[++topIndex] = val; } int pop() { if (isEmpty()) { cout << "栈空" << endl; return -1; } return data[topIndex--]; } int top() { if (isEmpty()) return -1; return data[topIndex]; } };面试必刷题 - 有效的括号：
cpp
bool isValid(string s) { stack<char> st; for (char c : s) { if (c == '(' || c == '[' || c == '{') { st.push(c); } else { if (st.empty()) return false; char top = st.top(); if ((c == ')' && top == '(') || (c == ']' && top == '[') || (c == '}' && top == '{')) { st.pop(); } else { return false; } } } return st.empty(); }3. 队列（Queue）
特点：先进先出（FIFO）
应用场景：任务调度、缓冲区、BFS广度优先搜索
代码实现 - 循环队列（高频考察）：
cpp
class CircularQueue { private: int* data; int front; // 队头索引 int rear; // 队尾索引（指向最后一个元素的下一个位置） int capacity; int count; // 当前元素个数 public: CircularQueue(int cap) : capacity(cap), front(0), rear(0), count(0) { data = new int[capacity]; } ~CircularQueue() { delete[] data; } bool isEmpty() { return count == 0; } bool isFull() { return count == capacity; } bool enqueue(int val) { if (isFull()) return false; data[rear] = val; rear = (rear + 1) % capacity; count++; return true; } int dequeue() { if (isEmpty()) return -1; int val = data[front]; front = (front + 1) % capacity; count--; return val; } int getFront() { if (isEmpty()) return -1; return data[front]; } };二、树（Tree）
1. 二叉树基础
核心概念：
深度/高度：根节点到最远叶子节点的路径长度
满二叉树：所有非叶子节点都有两个子节点
完全二叉树：除最后一层外全满，最后一层从左到右连续
二叉搜索树（BST）：左 < 根 < 右
代码实现 - 二叉树节点定义：
cpp
struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };2. 二叉树的遍历（⭐必手写）
四种遍历方式：
| 遍历方式 | 顺序 | 应用场景 |
|---|---|---|
| 前序遍历 | 根 → 左 → 右 | 复制二叉树、序列化 |
| 中序遍历 | 左 → 根 → 右 | BST有序输出 |
| 后序遍历 | 左 → 右 → 根 | 删除二叉树、表达式求值 |
| 层序遍历 | 逐层从左到右 | BFS、求树的宽度 |
递归实现（3行搞定）：
cpp
// 前序遍历 void preorder(TreeNode* root) { if (root == nullptr) return; cout << root->val << " "; preorder(root->left); preorder(root->right); } // 中序遍历 void inorder(TreeNode* root) { if (root == nullptr) return; inorder(root->left); cout << root->val << " "; inorder(root->right); } // 后序遍历 void postorder(TreeNode* root) { if (root == nullptr) return; postorder(root->left); postorder(root->right); cout << root->val << " "; }迭代实现（面试追问重点）：
cpp
// 前序遍历（迭代） vector<int> preorderIterative(TreeNode* root) { vector<int> result; if (root == nullptr) return result; stack<TreeNode*> st; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); result.push_back(node->val); // 先右后左，保证左先出栈 if (node->right) st.push(node->right); if (node->left) st.push(node->left); } return result; } // 中序遍历（迭代，核心理解） vector<int> inorderIterative(TreeNode* root) { vector<int> result; stack<TreeNode*> st; TreeNode* cur = root; while (cur != nullptr || !st.empty()) { // 一直向左走到底 while (cur != nullptr) { st.push(cur); cur = cur->left; } cur = st.top(); st.pop(); result.push_back(cur->val); cur = cur->right; // 转向右子树 } return result; } // 层序遍历（BFS） vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (root == nullptr) return result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int levelSize = q.size(); vector<int> currentLevel; for (int i = 0; i < levelSize; i++) { TreeNode* node = q.front(); q.pop(); currentLevel.push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } result.push_back(currentLevel); } return result; }3. 二叉搜索树（BST）
核心性质：中序遍历得到有序序列
时间复杂度：查找/插入/删除 O(log n)（平衡情况下）
代码实现 - BST 查找：
cpp
TreeNode* searchBST(TreeNode* root, int target) { if (root == nullptr || root->val == target) { return root; } if (target < root->val) { return searchBST(root->left, target); } else { return searchBST(root->right, target); } } // 插入节点 TreeNode* insertBST(TreeNode* root, int val) { if (root == nullptr) { return new TreeNode(val); } if (val < root->val) { root->left = insertBST(root->left, val); } else if (val > root->val) { root->right = insertBST(root->right, val); } return root; }4. 平衡二叉树（AVL）
核心：左右子树高度差（平衡因子）不超过 1
四种旋转：LL、RR、LR、RL
cpp
// 获取高度 int getHeight(TreeNode* node) { if (node == nullptr) return 0; return max(getHeight(node->left), getHeight(node->right)) + 1; } // 判断是否平衡 bool isBalanced(TreeNode* root) { if (root == nullptr) return true; int leftHeight = getHeight(root->left); int rightHeight = getHeight(root->right); if (abs(leftHeight - rightHeight) > 1) return false; return isBalanced(root->left) && isBalanced(root->right); } // 优化版（自底向上，O(n)） bool isBalancedOptimized(TreeNode* root, int& height) { if (root == nullptr) { height = 0; return true; } int leftH = 0, rightH = 0; if (!isBalancedOptimized(root->left, leftH)) return false; if (!isBalancedOptimized(root->right, rightH)) return false; if (abs(leftH - rightH) > 1) return false; height = max(leftH, rightH) + 1; return true; }三、哈希表（Hash Table）
核心：键值对存储，查找 O(1)
底层实现：数组 + 链表（拉链法）/ 开放地址法
| 对比 | unordered_map (C++) | map (C++) |
|---|---|---|
| 底层 | 哈希表 | 红黑树 |
| 查找 | O(1) 平均 | O(log n) |
| 顺序 | 无序 | 有序 |
| 适用 | 快速查找 | 需要有序遍历 |
手写简单的哈希表（拉链法）：
cpp
class MyHashMap { private: struct Node { int key; int value; Node* next; Node(int k, int v) : key(k), value(v), next(nullptr) {} }; vector<Node*> buckets; int capacity; int hash(int key) { return key % capacity; } public: MyHashMap(int cap = 1000) : capacity(cap) { buckets.resize(capacity, nullptr); } void put(int key, int value) { int index = hash(key); Node* cur = buckets[index]; while (cur != nullptr) { if (cur->key == key) { cur->value = value; return; } cur = cur->next; } // 头插 Node* newNode = new Node(key, value); newNode->next = buckets[index]; buckets[index] = newNode; } int get(int key) { int index = hash(key); Node* cur = buckets[index]; while (cur != nullptr) { if (cur->key == key) { return cur->value; } cur = cur->next; } return -1; // 不存在 } void remove(int key) { int index = hash(key); Node* cur = buckets[index]; Node* prev = nullptr; while (cur != nullptr) { if (cur->key == key) { if (prev == nullptr) { buckets[index] = cur->next; } else { prev->next = cur->next; } delete cur; return; } prev = cur; cur = cur->next; } } };四、堆（Heap）
核心：完全二叉树 + 堆序（大根堆/小根堆）
应用：优先队列、Top K、堆排序、中位数查找
代码实现 - 小根堆（用数组）：
cpp
class MinHeap { private: vector<int> heap; // 向上调整（插入时用） void siftUp(int index) { while (index > 0) { int parent = (index - 1) / 2; if (heap[parent] <= heap[index]) break; swap(heap[parent], heap[index]); index = parent; } } // 向下调整（删除堆顶时用） void siftDown(int index) { int n = heap.size(); while (index < n) { int left = 2 * index + 1; int right = 2 * index + 2; int smallest = index; if (left < n && heap[left] < heap[smallest]) smallest = left; if (right < n && heap[right] < heap[smallest]) smallest = right; if (smallest == index) break; swap(heap[index], heap[smallest]); index = smallest; } } public: void push(int val) { heap.push_back(val); siftUp(heap.size() - 1); } int pop() { if (heap.empty()) return -1; int result = heap[0]; heap[0] = heap.back(); heap.pop_back(); siftDown(0); return result; } int top() { return heap.empty() ? -1 : heap[0]; } int size() { return heap.size(); } };Top K 问题（高频）：
cpp
// 求数组中第 K 大的元素（用最小堆） int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> minHeap; for (int num : nums) { minHeap.push(num); if (minHeap.size() > k) { minHeap.pop(); } } return minHeap.top(); }五、图（Graph）
1. 图的存储方式
| 存储方式 | 适用场景 | 空间复杂度 |
|---|---|---|
| 邻接矩阵 | 稠密图、快速判断边存在 | O(V²) |
| 邻接表 | 稀疏图、遍历所有邻接点 | O(V+E) |
代码实现 - 邻接表：
cpp
class Graph { private: int vertexCount; vector<vector<int>> adjList; // 邻接表 public: Graph(int n) : vertexCount(n), adjList(n) {} // 添加边（无向图） void addEdge(int u, int v) { adjList[u].push_back(v); adjList[v].push_back(u); } // BFS 遍历 void BFS(int start) { vector<bool> visited(vertexCount, false); queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; for (int neighbor : adjList[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } // DFS 遍历 void DFS(int start) { vector<bool> visited(vertexCount, false); DFSHelper(start, visited); } void DFSHelper(int node, vector<bool>& visited) { visited[node] = true; cout << node << " "; for (int neighbor : adjList[node]) { if (!visited[neighbor]) { DFSHelper(neighbor, visited); } } } };2. 最短路径算法
Dijkstra（单源、无负权）：
cpp
vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& graph) { int n = graph.size(); vector<int> dist(n, INT_MAX); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { auto [d, node] = pq.top(); pq.pop(); if (d > dist[node]) continue; for (auto [neighbor, weight] : graph[node]) { if (dist[node] + weight < dist[neighbor]) { dist[neighbor] = dist[node] + weight; pq.push({dist[neighbor], neighbor}); } } } return dist; }六、常见题型与复杂度总结
| 数据结构 | 插入 | 删除 | 查找 | 适用场景 |
|---|---|---|---|---|
| 数组 | O(n) | O(n) | O(n) | 随机访问 |
| 链表 | O(1)（头插） | O(1)（已知节点） | O(n) | 频繁插入删除 |
| 栈 | O(1) | O(1) | - | 后进先出场景 |
| 队列 | O(1) | O(1) | - | 先进先出场景 |
| 哈希表 | O(1) 平均 | O(1) 平均 | O(1) 平均 | 快速查找 |
| 二叉搜索树 | O(log n) 平均 | O(log n) 平均 | O(log n) 平均 | 有序动态数据 |
| 堆 | O(log n) | O(log n) | O(1) 取最值 | Top K、优先级 |
