数据结构：全成就指南

一、线性表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应用场景函数调用栈、括号匹配、表达式求值、撤销操作代码实现 - 用数组模拟栈cppclass 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]; } };面试必刷题 - 有效的括号cppbool isValid(string s) { stackchar 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广度优先搜索代码实现 - 循环队列高频考察cppclass 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]; } };二、树Tree1. 二叉树基础核心概念深度/高度根节点到最远叶子节点的路径长度满二叉树所有非叶子节点都有两个子节点完全二叉树除最后一层外全满最后一层从左到右连续二叉搜索树BST左 根 右代码实现 - 二叉树节点定义cppstruct 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// 前序遍历迭代 vectorint preorderIterative(TreeNode* root) { vectorint result; if (root nullptr) return result; stackTreeNode* 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; } // 中序遍历迭代核心理解 vectorint inorderIterative(TreeNode* root) { vectorint result; stackTreeNode* 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 vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (root nullptr) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); vectorint 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 查找cppTreeNode* 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、RLcpp// 获取高度 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)顺序无序有序适用快速查找需要有序遍历手写简单的哈希表拉链法cppclass MyHashMap { private: struct Node { int key; int value; Node* next; Node(int k, int v) : key(k), value(v), next(nullptr) {} }; vectorNode* 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、堆排序、中位数查找代码实现 - 小根堆用数组cppclass MinHeap { private: vectorint 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(vectorint nums, int k) { priority_queueint, vectorint, greaterint minHeap; for (int num : nums) { minHeap.push(num); if (minHeap.size() k) { minHeap.pop(); } } return minHeap.top(); }五、图Graph1. 图的存储方式存储方式适用场景空间复杂度邻接矩阵稠密图、快速判断边存在O(V²)邻接表稀疏图、遍历所有邻接点O(VE)代码实现 - 邻接表cppclass Graph { private: int vertexCount; vectorvectorint 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) { vectorbool visited(vertexCount, false); queueint 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) { vectorbool visited(vertexCount, false); DFSHelper(start, visited); } void DFSHelper(int node, vectorbool visited) { visited[node] true; cout node ; for (int neighbor : adjList[node]) { if (!visited[neighbor]) { DFSHelper(neighbor, visited); } } } };2. 最短路径算法Dijkstra单源、无负权cppvectorint dijkstra(int start, vectorvectorpairint, int graph) { int n graph.size(); vectorint dist(n, INT_MAX); priority_queuepairint, int, vectorpairint, 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、优先级