Skip to content

数据结构源码 ​

数据结构与算法里每个知识点的完整实现,共 27 个单文件、无外部依赖的 .cpp。用 g++ -std=c++17 文件名.cpp -o demo 即可编译。

右侧目录按编号排列,点击可跳转;每段默认折叠,展开后可直接阅读和复制。

01 动态数组 ​

展开源码
cpp
// 01_vector.cpp —— 手写动态数组
// 覆盖:三指针语义、2 倍扩容、size/capacity、reserve/resize、深拷贝、移动语义
// 对应《3. 数据结构.md》§二.2、§二.3、§八.3

#include <cstddef>
#include <stdexcept>
#include <utility>

class MyVector {
public:
    MyVector() = default;

    explicit MyVector(std::size_t n) : data_(new int[n]()), size_(n), cap_(n) {}

    ~MyVector() { delete[] data_; }

    MyVector(const MyVector& other)
        : data_(other.size_ ? new int[other.size_] : nullptr),
          size_(other.size_), cap_(other.size_) {
        for (std::size_t i = 0; i < size_; ++i) data_[i] = other.data_[i];
    }

    MyVector& operator=(const MyVector& other) {
        if (this != &other) {
            MyVector tmp(other);   // 拷贝再交换,异常安全
            swap(tmp);
        }
        return *this;
    }

    MyVector(MyVector&& other) noexcept
        : data_(other.data_), size_(other.size_), cap_(other.cap_) {
        other.data_ = nullptr;
        other.size_ = other.cap_ = 0;
    }

    MyVector& operator=(MyVector&& other) noexcept {
        if (this != &other) {
            delete[] data_;
            data_ = other.data_;
            size_ = other.size_;
            cap_ = other.cap_;
            other.data_ = nullptr;
            other.size_ = other.cap_ = 0;
        }
        return *this;
    }

    void swap(MyVector& other) noexcept {
        std::swap(data_, other.data_);
        std::swap(size_, other.size_);
        std::swap(cap_, other.cap_);
    }

    void push_back(int value) {
        if (size_ == cap_) reserve(cap_ ? cap_ * 2 : 1);   // 均摊 O(1)
        data_[size_++] = value;
    }

    void pop_back() {
        if (size_ > 0) --size_;
    }

    void reserve(std::size_t new_cap) {
        if (new_cap <= cap_) return;                        // 只增不减
        int* new_data = new int[new_cap];
        for (std::size_t i = 0; i < size_; ++i) new_data[i] = data_[i];
        delete[] data_;
        data_ = new_data;
        cap_ = new_cap;
    }

    void resize(std::size_t new_size, int value = 0) {
        if (new_size > cap_) reserve(new_size);
        for (std::size_t i = size_; i < new_size; ++i) data_[i] = value;
        size_ = new_size;
    }

    void clear() noexcept { size_ = 0; }                    // 不释放 capacity

    void shrink_to_fit() {                                  // 标准语义是"请求"
        if (size_ == cap_) return;
        if (size_ == 0) {
            delete[] data_;
            data_ = nullptr;
            cap_ = 0;
            return;
        }
        int* p = new int[size_];
        for (std::size_t i = 0; i < size_; ++i) p[i] = data_[i];
        delete[] data_;
        data_ = p;
        cap_ = size_;
    }

    int& operator[](std::size_t i) { return data_[i]; }
    const int& operator[](std::size_t i) const { return data_[i]; }

    int& at(std::size_t i) {
        if (i >= size_) throw std::out_of_range("MyVector::at");
        return data_[i];
    }
    const int& at(std::size_t i) const {
        if (i >= size_) throw std::out_of_range("MyVector::at");
        return data_[i];
    }

    int& front() { return data_[0]; }
    int& back() { return data_[size_ - 1]; }

    int* begin() noexcept { return data_; }
    int* end() noexcept { return data_ + size_; }
    const int* begin() const noexcept { return data_; }
    const int* end() const noexcept { return data_ + size_; }

    std::size_t size() const noexcept { return size_; }
    std::size_t capacity() const noexcept { return cap_; }
    bool empty() const noexcept { return size_ == 0; }
    int* data() noexcept { return data_; }

private:
    int* data_ = nullptr;
    std::size_t size_ = 0;
    std::size_t cap_ = 0;
};

02 链表 ​

展开源码
cpp
// 02_linked_list.cpp —— 链表高频题
// 覆盖:反转、判环、环入口、合并、倒数第 k、相交、随机指针复制、K 个一组、排序、回文
// 对应《3. 数据结构.md》§二.8

#include <unordered_map>
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    explicit ListNode(int v) : val(v), next(nullptr) {}
};

struct RandomNode {
    int val;
    RandomNode* next;
    RandomNode* random;
    explicit RandomNode(int v) : val(v), next(nullptr), random(nullptr) {}
};

class LinkedListProblems {
public:
    // 反转链表:prev / cur / next 三指针
    static ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        return prev;
    }

    // 快慢指针判环
    static bool hasCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }

    // 环入口:相遇后一个指针回到 head,同速再相遇
    static ListNode* detectCycle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode* p = head;
                while (p != slow) {
                    p = p->next;
                    slow = slow->next;
                }
                return p;
            }
        }
        return nullptr;
    }

    // 合并两个有序链表:dummy 哨兵
    static ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (a && b) {
            if (a->val <= b->val) { tail->next = a; a = a->next; }
            else                  { tail->next = b; b = b->next; }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return dummy.next;
    }

    // 删除倒数第 n 个:快指针先走 n 步
    static ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;
        for (int i = 0; i < n; ++i) fast = fast->next;
        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* victim = slow->next;
        slow->next = victim->next;
        delete victim;                  // LeetCode 环境可去掉
        return dummy.next;
    }

    // 相交链表:长度差对齐
    static ListNode* getIntersectionNode(ListNode* a, ListNode* b) {
        int lenA = 0, lenB = 0;
        for (ListNode* p = a; p; p = p->next) ++lenA;
        for (ListNode* p = b; p; p = p->next) ++lenB;
        while (lenA > lenB) { a = a->next; --lenA; }
        while (lenB > lenA) { b = b->next; --lenB; }
        while (a != b) { a = a->next; b = b->next; }
        return a;
    }

    // 复制带随机指针的链表:哈希存「原节点 -> 新节点」
    static RandomNode* copyRandomList(RandomNode* head) {
        if (!head) return nullptr;
        std::unordered_map<RandomNode*, RandomNode*> mp;
        for (RandomNode* p = head; p; p = p->next)
            mp[p] = new RandomNode(p->val);
        for (RandomNode* p = head; p; p = p->next) {
            mp[p]->next = p->next ? mp[p->next] : nullptr;
            mp[p]->random = p->random ? mp[p->random] : nullptr;
        }
        return mp[head];
    }

    // K 个一组翻转
    static ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode* groupPrev = &dummy;
        while (true) {
            ListNode* kth = groupPrev;
            for (int i = 0; i < k && kth; ++i) kth = kth->next;
            if (!kth) break;                     // 不足 k 个,保持原样
            ListNode* groupNext = kth->next;
            ListNode* prev = groupNext;
            ListNode* cur = groupPrev->next;
            while (cur != groupNext) {
                ListNode* nxt = cur->next;
                cur->next = prev;
                prev = cur;
                cur = nxt;
            }
            ListNode* oldStart = groupPrev->next;
            groupPrev->next = kth;               // kth 成为新头
            groupPrev = oldStart;                // 旧头变成组尾
        }
        return dummy.next;
    }

    // 链表排序:归并,O(n log n)、O(log n) 递归栈
    static ListNode* sortList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* mid = slow->next;
        slow->next = nullptr;
        return mergeTwoLists(sortList(head), sortList(mid));
    }

    // 回文链表:找中点 + 反转后半 + 比较
    static bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* second = reverseList(slow);
        ListNode* first = head;
        while (second) {
            if (first->val != second->val) return false;
            first = first->next;
            second = second->next;
        }
        return true;
    }

    // 方便构造测试链表(LeetCode 里通常不需要)
    static ListNode* build(const std::vector<int>& values) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        for (int v : values) {
            tail->next = new ListNode(v);
            tail = tail->next;
        }
        return dummy.next;
    }
};

03 LRU 缓存 ​

展开源码
cpp
// 03_lru_cache.cpp —— LRU Cache
// 哈希表 O(1) 定位 + 双向链表 O(1) 维护顺序
// 对应《3. 数据结构.md》§七.1

#include <list>
#include <unordered_map>
#include <utility>

class LRUCache {
public:
    explicit LRUCache(int capacity) : cap_(capacity) {}

    int get(int key) {
        auto it = mp_.find(key);
        if (it == mp_.end()) return -1;
        // splice 在链表内部 O(1) 移动节点,不失效迭代器
        lst_.splice(lst_.begin(), lst_, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = mp_.find(key);
        if (it != mp_.end()) {
            it->second->second = value;
            lst_.splice(lst_.begin(), lst_, it->second);
            return;
        }
        if (static_cast<int>(lst_.size()) == cap_) {
            mp_.erase(lst_.back().first);
            lst_.pop_back();
        }
        lst_.emplace_front(key, value);
        mp_[key] = lst_.begin();
    }

private:
    int cap_;
    std::list<std::pair<int, int>> lst_;   // front = 最近使用,back = 最久未使用
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> mp_;
};

// 并发追问:全局锁最简单,但争用大;工程上常按 key 哈希分片,
// 每个分片一个独立 LRU + 独立互斥锁,降低锁粒度。

04 LFU 缓存 ​

展开源码
cpp
// 04_lfu_cache.cpp —— LFU Cache(O(1) 版本)
// key -> {value, freq, 在频次链表中的位置}
// freq -> 该频次下的 key 链表(链表内按 LRU 顺序,front 为最近使用)
// 维护 minFreq,用于 O(1) 找到要淘汰的频次
// 对应《3. 数据结构.md》§七.2

#include <list>
#include <unordered_map>

class LFUCache {
public:
    explicit LFUCache(int capacity) : cap_(capacity) {}

    int get(int key) {
        auto it = keyMap_.find(key);
        if (it == keyMap_.end()) return -1;
        touch(key);
        return it->second.value;
    }

    void put(int key, int value) {
        if (cap_ <= 0) return;

        auto it = keyMap_.find(key);
        if (it != keyMap_.end()) {
            it->second.value = value;
            touch(key);
            return;
        }

        if (static_cast<int>(keyMap_.size()) == cap_) {
            // minFreq_ 对应的链表尾部就是最该淘汰的 key
            int victim = freqMap_[minFreq_].back();
            freqMap_[minFreq_].pop_back();
            pos_.erase(victim);
            keyMap_.erase(victim);
        }

        keyMap_[key] = {value, 1};
        freqMap_[1].push_front(key);
        pos_[key] = freqMap_[1].begin();
        minFreq_ = 1;
    }

private:
    struct Entry {
        int value;
        int freq;
    };

    // 把 key 从当前频次链表移到 freq+1 的链表头部
    void touch(int key) {
        Entry& e = keyMap_[key];
        auto& oldList = freqMap_[e.freq];
        oldList.erase(pos_[key]);
        if (oldList.empty() && minFreq_ == e.freq) ++minFreq_;

        ++e.freq;
        auto& newList = freqMap_[e.freq];
        newList.push_front(key);
        pos_[key] = newList.begin();
    }

    int cap_;
    int minFreq_ = 0;
    std::unordered_map<int, Entry> keyMap_;
    std::unordered_map<int, std::list<int>> freqMap_;
    std::unordered_map<int, std::list<int>::iterator> pos_;
};

05 最小栈 ​

展开源码
cpp
// 05_min_stack.cpp —— 最小栈
// 两个栈:data 存数据,mins 存「当前最小值」
// push / pop / top / getMin 全部 O(1)
// 对应《3. 数据结构.md》§七.3

#include <algorithm>
#include <stack>

class MinStack {
public:
    void push(int x) {
        data_.push(x);
        mins_.push(mins_.empty() ? x : std::min(x, mins_.top()));
    }

    void pop() {
        data_.pop();
        mins_.pop();
    }

    int top() const { return data_.top(); }

    int getMin() const { return mins_.top(); }

    bool empty() const { return data_.empty(); }

private:
    std::stack<int> data_;
    std::stack<int> mins_;
};

06 双栈队列 ​

展开源码
cpp
// 06_queue_by_two_stacks.cpp —— 两个栈实现队列 / 一个队列实现栈
// 对应《3. 数据结构.md》§七.4

#include <cstddef>
#include <queue>
#include <stack>

// 队列:in 负责入队,out 负责出队
class MyQueue {
public:
    void push(int x) { in_.push(x); }

    int pop() {
        transfer();
        int v = out_.top();
        out_.pop();
        return v;
    }

    int peek() {
        transfer();
        return out_.top();
    }

    bool empty() const { return in_.empty() && out_.empty(); }

private:
    void transfer() {
        if (!out_.empty()) return;
        while (!in_.empty()) {
            out_.push(in_.top());
            in_.pop();
        }
    }

    std::stack<int> in_;
    std::stack<int> out_;
};

// 栈:每次 push 后把前面的元素转到后面,队首始终是栈顶
class MyStack {
public:
    void push(int x) {
        q_.push(x);
        for (std::size_t i = 0; i + 1 < q_.size(); ++i) {
            q_.push(q_.front());
            q_.pop();
        }
    }

    int pop() {
        int v = q_.front();
        q_.pop();
        return v;
    }

    int top() { return q_.front(); }

    bool empty() const { return q_.empty(); }

private:
    std::queue<int> q_;
};

07 哈希表 ​

展开源码
cpp
// 07_hash_table.cpp —— 手写哈希表(链地址法 + rehash)
// 对应《3. 数据结构.md》§三.1、§三.2

#include <cstddef>
#include <functional>
#include <vector>

class MyHashMap {
public:
    MyHashMap() : buckets_(8, nullptr) {}
    ~MyHashMap() { clear(); }

    MyHashMap(const MyHashMap&) = delete;
    MyHashMap& operator=(const MyHashMap&) = delete;

    void put(int key, int value) {
        std::size_t idx = bucketIndex(key);
        for (Node* p = buckets_[idx]; p; p = p->next) {
            if (p->key == key) { p->value = value; return; }
        }
        buckets_[idx] = new Node(key, value, buckets_[idx]);
        ++size_;
        if (size_ > buckets_.size() * kMaxLoad) rehash(buckets_.size() * 2);
    }

    int get(int key) const {
        for (Node* p = buckets_[bucketIndex(key)]; p; p = p->next) {
            if (p->key == key) return p->value;
        }
        return -1;
    }

    void remove(int key) {
        Node** pp = &buckets_[bucketIndex(key)];
        while (*pp) {
            if ((*pp)->key == key) {
                Node* victim = *pp;
                *pp = victim->next;
                delete victim;
                --size_;
                return;
            }
            pp = &(*pp)->next;
        }
    }

    std::size_t size() const { return size_; }

private:
    struct Node {
        int key;
        int value;
        Node* next;
        Node(int k, int v, Node* n) : key(k), value(v), next(n) {}
    };

    static constexpr double kMaxLoad = 0.75;

    std::size_t bucketIndex(int key) const {
        return std::hash<int>{}(key) % buckets_.size();
    }

    void rehash(std::size_t newCount) {
        std::vector<Node*> old;
        old.swap(buckets_);
        buckets_.assign(newCount, nullptr);
        size_ = 0;
        for (Node* head : old) {
            while (head) {
                Node* next = head->next;          // 先保存 next 再改链
                std::size_t idx = bucketIndex(head->key);
                head->next = buckets_[idx];
                buckets_[idx] = head;
                ++size_;
                head = next;
            }
        }
    }

    void clear() {
        for (Node*& head : buckets_) {
            while (head) {
                Node* next = head->next;
                delete head;
                head = next;
            }
        }
        buckets_.clear();
        size_ = 0;
    }

    std::vector<Node*> buckets_;
    std::size_t size_ = 0;
};

08 二叉堆 ​

展开源码
cpp
// 08_binary_heap.cpp —— 手写堆 + TopK
// 默认 std::less 是大顶堆;传 std::greater 得到小顶堆
// 对应《3. 数据结构.md》§四.7、§四.8

#include <cstddef>
#include <functional>
#include <utility>
#include <vector>

template <class Compare = std::less<int>>
class BinaryHeap {
public:
    BinaryHeap() = default;

    explicit BinaryHeap(Compare comp) : comp_(comp) {}

    explicit BinaryHeap(std::vector<int> values) : data_(std::move(values)) {
        build();
    }

    void push(int x) {
        data_.push_back(x);
        siftUp(data_.size() - 1);
    }

    int pop() {
        int top = data_.front();
        data_.front() = data_.back();
        data_.pop_back();
        if (!data_.empty()) siftDown(0);
        return top;
    }

    int top() const { return data_.front(); }
    bool empty() const { return data_.empty(); }
    std::size_t size() const { return data_.size(); }

    // 从最后一个非叶子节点开始下沉,O(n)
    void build() {
        for (int i = static_cast<int>(data_.size()) / 2 - 1; i >= 0; --i)
            siftDown(static_cast<std::size_t>(i));
    }

    // 取最大的 k 个元素:维护大小为 k 的小顶堆
    static std::vector<int> topK(const std::vector<int>& nums, std::size_t k) {
        BinaryHeap<std::greater<int>> heap;      // 小顶堆
        for (int x : nums) {
            if (heap.size() < k) {
                heap.push(x);
            } else if (x > heap.top()) {
                heap.pop();
                heap.push(x);
            }
        }
        std::vector<int> res;
        res.reserve(heap.size());
        while (!heap.empty()) res.push_back(heap.pop());   // 升序
        return res;
    }

private:
    void siftUp(std::size_t i) {
        while (i > 0) {
            std::size_t parent = (i - 1) / 2;
            // comp_ 为 true 表示 parent 的优先级低于 child
            if (!comp_(data_[parent], data_[i])) break;
            std::swap(data_[parent], data_[i]);
            i = parent;
        }
    }

    void siftDown(std::size_t i) {
        std::size_t n = data_.size();
        while (true) {
            std::size_t best = i;
            std::size_t left = 2 * i + 1;
            std::size_t right = 2 * i + 2;
            if (left < n && comp_(data_[best], data_[left])) best = left;
            if (right < n && comp_(data_[best], data_[right])) best = right;
            if (best == i) break;
            std::swap(data_[i], data_[best]);
            i = best;
        }
    }

    std::vector<int> data_;
    Compare comp_{};
};

09 二叉树遍历 ​

展开源码
cpp
// 09_binary_tree_traversal.cpp —— 二叉树遍历
// 前序 / 中序 / 后序(迭代)+ 层序 + 最大深度
// 对应《3. 数据结构.md》§四.1

#include <algorithm>
#include <queue>
#include <stack>
#include <vector>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class TreeTraversal {
public:
    // 根 -> 左 -> 右:栈先压右再压左
    static std::vector<int> preorder(TreeNode* root) {
        std::vector<int> res;
        if (!root) return res;
        std::stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            res.push_back(node->val);
            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return res;
    }

    // 左 -> 根 -> 右:一路向左入栈,弹栈访问,转向右子树
    static std::vector<int> inorder(TreeNode* root) {
        std::vector<int> res;
        std::stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur || !st.empty()) {
            while (cur) {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }
        return res;
    }

    // 后序:按「根 -> 右 -> 左」遍历后整体反转
    static std::vector<int> postorder(TreeNode* root) {
        std::vector<int> res;
        if (!root) return res;
        std::stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            res.push_back(node->val);
            if (node->left) st.push(node->left);
            if (node->right) st.push(node->right);
        }
        std::reverse(res.begin(), res.end());
        return res;
    }

    // 层序:每层先记录 size
    static std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> res;
        if (!root) return res;
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int levelSize = static_cast<int>(q.size());
            std::vector<int> level;
            level.reserve(levelSize);
            for (int i = 0; i < levelSize; ++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(std::move(level));
        }
        return res;
    }

    static int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
    }
};

10 二叉搜索树 ​

展开源码
cpp
// 10_bst.cpp —— 二叉搜索树
// 增删查 + 验证 BST + BST 最近公共祖先 + 第 k 小
// 对应《3. 数据结构.md》§四.3

#include <limits>
#include <stack>

class BST {
public:
    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
    };

    BST() = default;
    ~BST() { destroy(root_); }

    BST(const BST&) = delete;
    BST& operator=(const BST&) = delete;

    void insert(int val) { root_ = insert(root_, val); }
    bool contains(int val) const { return contains(root_, val); }
    void erase(int val) { root_ = erase(root_, val); }
    bool empty() const { return root_ == nullptr; }

    // 不能只比较父子,要传上下界
    static bool isValidBST(TreeNode* root) {
        return validate(root, std::numeric_limits<long long>::lowest(),
                               std::numeric_limits<long long>::max());
    }

    // BST 的 LCA:两个值都小往左,都大往右,否则当前就是
    static TreeNode* lca(TreeNode* root, int p, int q) {
        while (root) {
            if (p < root->val && q < root->val) root = root->left;
            else if (p > root->val && q > root->val) root = root->right;
            else return root;
        }
        return nullptr;
    }

    // 第 k 小:中序遍历计数
    static int kthSmallest(TreeNode* root, int k) {
        std::stack<TreeNode*> st;
        TreeNode* cur = root;
        while (cur || !st.empty()) {
            while (cur) {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            if (--k == 0) return cur->val;
            cur = cur->right;
        }
        return -1;   // k 非法
    }

private:
    static TreeNode* insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);
        if (val < node->val) node->left = insert(node->left, val);
        else if (val > node->val) node->right = insert(node->right, val);
        return node;   // 重复值不插入
    }

    static bool contains(const TreeNode* node, int val) {
        while (node) {
            if (val == node->val) return true;
            node = val < node->val ? node->left : node->right;
        }
        return false;
    }

    static TreeNode* erase(TreeNode* node, int val) {
        if (!node) return nullptr;
        if (val < node->val) {
            node->left = erase(node->left, val);
            return node;
        }
        if (val > node->val) {
            node->right = erase(node->right, val);
            return node;
        }
        // 找到:0 / 1 个孩子直接顶替
        if (!node->left) {
            TreeNode* right = node->right;
            delete node;
            return right;
        }
        if (!node->right) {
            TreeNode* left = node->left;
            delete node;
            return left;
        }
        // 两个孩子:用中序后继替换值,再删除后继
        TreeNode* succ = minNode(node->right);
        node->val = succ->val;
        node->right = erase(node->right, succ->val);
        return node;
    }

    static TreeNode* minNode(TreeNode* node) {
        while (node->left) node = node->left;
        return node;
    }

    static bool validate(TreeNode* node, long long lower, long long upper) {
        if (!node) return true;
        if (node->val <= lower || node->val >= upper) return false;
        return validate(node->left, lower, node->val) &&
               validate(node->right, node->val, upper);
    }

    static void destroy(TreeNode* node) {
        if (!node) return;
        destroy(node->left);
        destroy(node->right);
        delete node;
    }

    TreeNode* root_ = nullptr;
};

11 AVL 树 ​

展开源码
cpp
// 11_avl.cpp —— AVL 树:四种旋转 + 插入 + 删除
// LL -> 右旋;RR -> 左旋;LR -> 先左旋孩子再右旋;RL -> 先右旋孩子再左旋
// 对应《3. 数据结构.md》§四.4

#include <algorithm>
#include <vector>

class AVLTree {
public:
    struct Node {
        int val;
        int height;
        Node* left;
        Node* right;
        explicit Node(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
    };

    AVLTree() = default;
    ~AVLTree() { destroy(root_); }

    AVLTree(const AVLTree&) = delete;
    AVLTree& operator=(const AVLTree&) = delete;

    void insert(int val) { root_ = insert(root_, val); }
    void erase(int val) { root_ = erase(root_, val); }
    bool empty() const { return root_ == nullptr; }

    std::vector<int> inorder() const {
        std::vector<int> res;
        inorder(root_, res);
        return res;
    }

private:
    static int height(const Node* node) { return node ? node->height : 0; }

    static int balanceFactor(const Node* node) {
        return height(node->left) - height(node->right);
    }

    static void update(Node* node) {
        node->height = 1 + std::max(height(node->left), height(node->right));
    }

    /* 右旋示意(把 y 的左孩子 x 提上来):
           y              x
          / \            / \
         x   T3   ->    T1  y
        / \                / \
       T1 T2              T2  T3
    */
    static Node* rotateRight(Node* y) {
        Node* x = y->left;
        Node* t2 = x->right;
        x->right = y;
        y->left = t2;
        update(y);
        update(x);
        return x;
    }

    static Node* rotateLeft(Node* x) {
        Node* y = x->right;
        Node* t2 = y->left;
        y->left = x;
        x->right = t2;
        update(x);
        update(y);
        return y;
    }

    static Node* balance(Node* node) {
        update(node);
        int bf = balanceFactor(node);
        if (bf > 1) {                               // 左重
            if (balanceFactor(node->left) < 0)      // LR
                node->left = rotateLeft(node->left);
            return rotateRight(node);               // LL / LR 收尾
        }
        if (bf < -1) {                              // 右重
            if (balanceFactor(node->right) > 0)     // RL
                node->right = rotateRight(node->right);
            return rotateLeft(node);                // RR / RL 收尾
        }
        return node;
    }

    static Node* insert(Node* node, int val) {
        if (!node) return new Node(val);
        if (val < node->val) node->left = insert(node->left, val);
        else if (val > node->val) node->right = insert(node->right, val);
        else return node;                           // 重复值不插入
        return balance(node);
    }

    static Node* erase(Node* node, int val) {
        if (!node) return nullptr;
        if (val < node->val) {
            node->left = erase(node->left, val);
        } else if (val > node->val) {
            node->right = erase(node->right, val);
        } else {
            if (!node->left || !node->right) {
                Node* child = node->left ? node->left : node->right;
                delete node;
                return child;                       // 子树本身平衡
            }
            Node* succ = minNode(node->right);
            node->val = succ->val;
            node->right = erase(node->right, succ->val);
        }
        return balance(node);
    }

    static Node* minNode(Node* node) {
        while (node->left) node = node->left;
        return node;
    }

    static void inorder(const Node* node, std::vector<int>& out) {
        if (!node) return;
        inorder(node->left, out);
        out.push_back(node->val);
        inorder(node->right, out);
    }

    static void destroy(Node* node) {
        if (!node) return;
        destroy(node->left);
        destroy(node->right);
        delete node;
    }

    Node* root_ = nullptr;
};

12 前缀树 ​

展开源码
cpp
// 12_trie.cpp —— Trie 前缀树
// insert / search / startsWith 均为 O(L)
// 对应《3. 数据结构.md》§四.9

#include <string>

class Trie {
public:
    Trie() : root_(new Node()) {}
    ~Trie() { destroy(root_); }

    Trie(const Trie&) = delete;
    Trie& operator=(const Trie&) = delete;

    void insert(const std::string& word) {
        Node* cur = root_;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->child[idx]) cur->child[idx] = new Node();
            cur = cur->child[idx];
        }
        cur->end = true;
    }

    bool search(const std::string& word) const {
        const Node* node = findNode(word);
        return node && node->end;
    }

    bool startsWith(const std::string& prefix) const {
        return findNode(prefix) != nullptr;
    }

private:
    struct Node {
        Node* child[26] = {};
        bool end = false;
    };

    const Node* findNode(const std::string& s) const {
        const Node* cur = root_;
        for (char c : s) {
            int idx = c - 'a';
            if (idx < 0 || idx >= 26) return nullptr;
            cur = cur->child[idx];
            if (!cur) return nullptr;
        }
        return cur;
    }

    static void destroy(Node* node) {
        if (!node) return;
        for (Node* child : node->child) destroy(child);
        delete node;
    }

    Node* root_;
};

13 并查集 ​

展开源码
cpp
// 13_union_find.cpp —— 并查集
// 路径压缩 + 按秩合并,单次操作摊还 O(α(n)) ≈ O(1)
// 对应《3. 数据结构.md》§六.7

#include <numeric>
#include <utility>
#include <vector>

class UnionFind {
public:
    explicit UnionFind(int n) : parent_(n), rank_(n, 0), count_(n) {
        std::iota(parent_.begin(), parent_.end(), 0);
    }

    int find(int x) {
        while (parent_[x] != x) {
            parent_[x] = parent_[parent_[x]];   // 路径减半
            x = parent_[x];
        }
        return x;
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) std::swap(a, b);
        parent_[b] = a;
        if (rank_[a] == rank_[b]) ++rank_[a];
        --count_;
        return true;
    }

    bool connected(int a, int b) { return find(a) == find(b); }

    int count() const { return count_; }

private:
    std::vector<int> parent_;
    std::vector<int> rank_;
    int count_;
};

14 拓扑排序 ​

展开源码
cpp
// 14_topo_sort.cpp —— 拓扑排序
// Kahn(入度队列,可判环)+ DFS 三色(可判环)
// 对应《3. 数据结构.md》§六.3

#include <algorithm>
#include <queue>
#include <utility>
#include <vector>

class TopoSort {
public:
    // edges: {from, to} 表示 from -> to
    static std::vector<int> kahn(int n, const std::vector<std::pair<int, int>>& edges) {
        std::vector<std::vector<int>> adj(n);
        std::vector<int> indeg(n, 0);
        for (const auto& [u, v] : edges) {
            adj[u].push_back(v);
            ++indeg[v];
        }

        std::queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (indeg[i] == 0) q.push(i);
        }

        std::vector<int> order;
        order.reserve(n);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            order.push_back(u);
            for (int v : adj[u]) {
                if (--indeg[v] == 0) q.push(v);
            }
        }
        // 输出节点数不足 n,说明有环
        return static_cast<int>(order.size()) == n ? order : std::vector<int>{};
    }

    // DFS 三色:0 未访问,1 访问中,2 已完成
    static std::vector<int> dfs(int n, const std::vector<std::pair<int, int>>& edges) {
        std::vector<std::vector<int>> adj(n);
        for (const auto& [u, v] : edges) adj[u].push_back(v);

        std::vector<int> state(n, 0);
        std::vector<int> order;
        order.reserve(n);
        bool hasCycle = false;

        auto visit = [&](auto&& self, int u) -> void {
            state[u] = 1;
            for (int v : adj[u]) {
                if (state[v] == 1) {               // 遇到访问中的节点 -> 有环
                    hasCycle = true;
                    return;
                }
                if (state[v] == 0) {
                    self(self, v);
                    if (hasCycle) return;
                }
            }
            state[u] = 2;
            order.push_back(u);                    // 后序
        };

        for (int i = 0; i < n; ++i) {
            if (state[i] == 0) visit(visit, i);
        }
        if (hasCycle) return {};
        std::reverse(order.begin(), order.end());  // 后序的逆序才是拓扑序
        return order;
    }
};

15 Dijkstra 最短路 ​

展开源码
cpp
// 15_dijkstra.cpp —— Dijkstra 单源最短路(非负权)
// 优先队列 + 惰性删除,O((V + E) log V)
// 对应《3. 数据结构.md》§六.4

#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

class Dijkstra {
public:
    struct Edge {
        int to;
        int w;
    };

    // adj[u] 存 u 出发的边;返回 dist 数组,不可达为 INF/2
    static std::vector<long long> shortest(
        int n, const std::vector<std::vector<Edge>>& adj, int src) {
        const long long INF = std::numeric_limits<long long>::max() / 2;
        std::vector<long long> dist(n, INF);
        dist[src] = 0;

        using State = std::pair<long long, int>;   // {dist, node}
        std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
        pq.push({0, src});

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) continue;             // 惰性删除:过期状态

            for (const Edge& e : adj[u]) {
                if (dist[u] + e.w < dist[e.to]) {
                    dist[e.to] = dist[u] + e.w;
                    pq.push({dist[e.to], e.to});
                }
            }
        }
        return dist;
    }
};

16 快速排序 ​

展开源码
cpp
// 16_quick_sort.cpp —— 快速排序 + 快速选择
// 三数取中、小区间插入排序、先递归较小一侧控制栈深
// 对应《3. 数据结构.md》§五.2

#include <algorithm>
#include <utility>
#include <vector>

class QuickSort {
public:
    static void sort(std::vector<int>& a) {
        if (a.size() > 1)
            sortRange(a, 0, static_cast<int>(a.size()) - 1);
    }

    // 第 k 小(1 <= k <= size),平均 O(n),最坏 O(n²)
    static int quickSelect(std::vector<int>& a, int k) {
        int l = 0;
        int r = static_cast<int>(a.size()) - 1;
        int target = k - 1;
        while (l <= r) {
            int p = partition(a, l, r);
            if (p == target) return a[p];
            if (p < target) l = p + 1;
            else r = p - 1;
        }
        return -1;   // k 非法
    }

private:
    static void sortRange(std::vector<int>& a, int l, int r) {
        while (l < r) {
            if (r - l < 16) {
                insertionSort(a, l, r);
                return;
            }
            int p = partition(a, l, r);
            // 先递归较小的一侧,较大的一侧循环处理,栈深 O(log n)
            if (p - l < r - p) {
                sortRange(a, l, p - 1);
                l = p + 1;
            } else {
                sortRange(a, p + 1, r);
                r = p - 1;
            }
        }
    }

    static void insertionSort(std::vector<int>& a, int l, int r) {
        for (int i = l + 1; i <= r; ++i) {
            int value = a[i];
            int j = i - 1;
            while (j >= l && a[j] > value) {
                a[j + 1] = a[j];
                --j;
            }
            a[j + 1] = value;
        }
    }

    static int partition(std::vector<int>& a, int l, int r) {
        // 三数取中,避免有序输入退化为 O(n²)
        int mid = l + (r - l) / 2;
        if (a[mid] < a[l]) std::swap(a[mid], a[l]);
        if (a[r] < a[l]) std::swap(a[r], a[l]);
        if (a[r] < a[mid]) std::swap(a[r], a[mid]);
        std::swap(a[l], a[mid]);          // 中位数放到 l 作为 pivot

        int pivot = a[l];
        int i = l;
        for (int j = l + 1; j <= r; ++j) {
            if (a[j] < pivot) std::swap(a[++i], a[j]);
        }
        std::swap(a[l], a[i]);
        return i;
    }
};

17 归并排序 ​

展开源码
cpp
// 17_merge_sort.cpp —— 归并排序 + 逆序对
// 稳定排序,O(n log n),额外空间 O(n)
// 对应《3. 数据结构.md》§五.3

#include <vector>

class MergeSort {
public:
    static void sort(std::vector<int>& a) {
        if (a.size() < 2) return;
        std::vector<int> tmp(a.size());
        sortRange(a, tmp, 0, static_cast<int>(a.size()) - 1);
    }

    // 求逆序对数量:合并时 a[i] > a[j] 则 a[i..mid] 都大于 a[j]
    static long long countInversions(std::vector<int> a) {
        if (a.size() < 2) return 0;
        std::vector<int> tmp(a.size());
        return countRange(a, tmp, 0, static_cast<int>(a.size()) - 1);
    }

private:
    static void sortRange(std::vector<int>& a, std::vector<int>& tmp, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        sortRange(a, tmp, l, mid);
        sortRange(a, tmp, mid + 1, r);

        int i = l;
        int j = mid + 1;
        int k = l;
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) tmp[k++] = a[i++];   // <= 保证稳定
            else tmp[k++] = a[j++];
        }
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= r) tmp[k++] = a[j++];
        for (int p = l; p <= r; ++p) a[p] = tmp[p];
    }

    static long long countRange(std::vector<int>& a, std::vector<int>& tmp, int l, int r) {
        if (l >= r) return 0;
        int mid = l + (r - l) / 2;
        long long inv = countRange(a, tmp, l, mid) + countRange(a, tmp, mid + 1, r);

        int i = l;
        int j = mid + 1;
        int k = l;
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                tmp[k++] = a[j++];
                inv += mid - i + 1;                // 一次合并的贡献
            }
        }
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= r) tmp[k++] = a[j++];
        for (int p = l; p <= r; ++p) a[p] = tmp[p];
        return inv;
    }
};

18 堆排序 ​

展开源码
cpp
// 18_heap_sort.cpp —— 堆排序
// 建堆 O(n) + n 次取堆顶 O(n log n),原地、不稳定
// 对应《3. 数据结构.md》§五.4

#include <utility>
#include <vector>

class HeapSort {
public:
    static void sort(std::vector<int>& a) {
        int n = static_cast<int>(a.size());
        // 建大顶堆:从最后一个非叶子节点开始下沉
        for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, i, n);
        // 每次把堆顶换到末尾,缩小堆范围
        for (int end = n - 1; end > 0; --end) {
            std::swap(a[0], a[end]);
            siftDown(a, 0, end);
        }
    }

private:
    static void siftDown(std::vector<int>& a, int i, int n) {
        while (true) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < n && a[left] > a[largest]) largest = left;
            if (right < n && a[right] > a[largest]) largest = right;
            if (largest == i) break;
            std::swap(a[i], a[largest]);
            i = largest;
        }
    }
};

19 二分查找 ​

展开源码
cpp
// 19_binary_search.cpp —— 二分查找与二分答案
// lower_bound / upper_bound / 旋转数组 / 峰值 / 分割数组 / sqrt
// 对应《3. 数据结构.md》§五.6、§五.7

#include <algorithm>
#include <vector>

class BinarySearch {
public:
    // 第一个 >= target
    static int lowerBound(const std::vector<int>& a, int target) {
        int l = 0;
        int r = static_cast<int>(a.size());       // [l, r)
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (a[mid] < target) l = mid + 1;
            else r = mid;
        }
        return l;
    }

    // 第一个 > target
    static int upperBound(const std::vector<int>& a, int target) {
        int l = 0;
        int r = static_cast<int>(a.size());
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (a[mid] <= target) l = mid + 1;
            else r = mid;
        }
        return l;
    }

    // 旋转有序数组:先判断哪一半有序
    static int searchRotated(const std::vector<int>& a, int target) {
        if (a.empty()) return -1;
        int l = 0;
        int r = static_cast<int>(a.size()) - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (a[mid] == target) return mid;
            if (a[l] <= a[mid]) {                 // 左半有序
                if (a[l] <= target && target < a[mid]) r = mid - 1;
                else l = mid + 1;
            } else {                              // 右半有序
                if (a[mid] < target && target <= a[r]) l = mid + 1;
                else r = mid - 1;
            }
        }
        return -1;
    }

    // 峰值下标:比右边小就往右走,否则往左收
    static int findPeak(const std::vector<int>& a) {
        if (a.empty()) return -1;
        int l = 0;
        int r = static_cast<int>(a.size()) - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (a[mid] < a[mid + 1]) l = mid + 1;
            else r = mid;
        }
        return l;
    }

    // 分割数组的最大值:最小化 m 段中的最大和
    static int splitArrayMinMax(const std::vector<int>& a, int m) {
        int lo = 0;
        long long hi = 0;
        for (int x : a) {
            lo = std::max(lo, x);                 // 下界:单个元素
            hi += x;                              // 上界:全部放一段
        }
        while (lo < hi) {
            int mid = lo + static_cast<int>((hi - lo) / 2);
            if (canSplit(a, m, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    static int mySqrt(int x) {
        if (x < 2) return x;
        int l = 1;
        int r = x / 2;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            long long sq = 1LL * mid * mid;
            if (sq == x) return mid;
            if (sq < x) l = mid + 1;
            else r = mid - 1;
        }
        return r;
    }

private:
    static bool canSplit(const std::vector<int>& a, int m, int limit) {
        int parts = 1;
        long long sum = 0;
        for (int x : a) {
            if (sum + x > limit) {
                ++parts;
                sum = x;
                if (parts > m) return false;
            } else {
                sum += x;
            }
        }
        return true;
    }
};

20 无锁环形队列 ​

展开源码
cpp
// 20_ring_buffer_spsc.cpp —— 无锁 SPSC 环形队列
// 容量必须是 2 的幂;牺牲一个槽位区分空 / 满
// 生产者只写 tail_,消费者只写 head_,acquire/release 建立 happens-before
// 对应《3. 数据结构.md》§二.7、§七.8

#include <atomic>
#include <cstddef>
#include <stdexcept>
#include <vector>

template <typename T>
class SpscRingBuffer {
public:
    explicit SpscRingBuffer(std::size_t capacity)
        : buffer_(capacity), mask_(capacity - 1) {
        if (capacity < 2 || (capacity & (capacity - 1)) != 0)
            throw std::invalid_argument("capacity must be a power of two >= 2");
    }

    bool push(const T& value) {
        const std::size_t tail = tail_.load(std::memory_order_relaxed);
        const std::size_t next = (tail + 1) & mask_;
        // 先读对方下标,再写数据:acquire 保证能看到消费者的释放
        if (next == head_.load(std::memory_order_acquire)) return false;
        buffer_[tail] = value;
        tail_.store(next, std::memory_order_release);   // 发布:数据先可见
        return true;
    }

    bool pop(T& out) {
        const std::size_t head = head_.load(std::memory_order_relaxed);
        if (head == tail_.load(std::memory_order_acquire)) return false;
        out = buffer_[head];
        head_.store((head + 1) & mask_, std::memory_order_release);
        return true;
    }

    std::size_t capacity() const { return buffer_.size() - 1; }
    bool empty() const {
        return head_.load(std::memory_order_acquire) ==
               tail_.load(std::memory_order_acquire);
    }

private:
    std::vector<T> buffer_;
    std::size_t mask_;
    // 分开到不同缓存行,避免伪共享
    alignas(64) std::atomic<std::size_t> head_{0};   // 消费者写
    alignas(64) std::atomic<std::size_t> tail_{0};   // 生产者写
};

21 布隆过滤器 ​

展开源码
cpp
// 21_bloom_filter.cpp —— 布隆过滤器
// k 个哈希函数、m 个 bit;无假阴性,有假阳性,不支持删除
// 对应《3. 数据结构.md》§三.6

#include <cmath>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <string>
#include <utility>
#include <vector>

class BloomFilter {
public:
    BloomFilter(std::size_t expectedItems, double falsePositiveRate) {
        auto [m, k] = optimalParams(expectedItems, falsePositiveRate);
        bitCount_ = m;
        hashCount_ = k;
        bits_.assign((bitCount_ + 63) / 64, 0);
    }

    void add(const std::string& key) {
        for (std::size_t i = 0; i < hashCount_; ++i) {
            std::size_t idx = index(key, i);
            bits_[idx >> 6] |= (std::uint64_t{1} << (idx & 63));
        }
    }

    bool contains(const std::string& key) const {
        for (std::size_t i = 0; i < hashCount_; ++i) {
            std::size_t idx = index(key, i);
            if ((bits_[idx >> 6] & (std::uint64_t{1} << (idx & 63))) == 0)
                return false;                       // 任一位为 0 就一定不存在
        }
        return true;                                // 全为 1,可能存在
    }

    std::size_t bitCount() const { return bitCount_; }
    std::size_t hashCount() const { return hashCount_; }

    // m = -n ln p / (ln 2)^2, k = (m / n) ln 2
    static std::pair<std::size_t, std::size_t> optimalParams(std::size_t n, double p) {
        const double ln2 = std::log(2.0);
        std::size_t m = static_cast<std::size_t>(
            -(static_cast<double>(n) * std::log(p)) / (ln2 * ln2));
        std::size_t k = static_cast<std::size_t>(
            std::round((static_cast<double>(m) / static_cast<double>(n)) * ln2));
        if (m == 0) m = 1;
        if (k == 0) k = 1;
        return {m, k};
    }

private:
    static std::uint64_t mix(std::uint64_t x) {
        x ^= x >> 33;
        x *= 0xff51afd7ed558ccdULL;
        x ^= x >> 33;
        x *= 0xc4ceb9fe1a85ec53ULL;
        x ^= x >> 33;
        return x;
    }

    // 双重哈希派生 k 个位置:h + i * delta 再混合
    std::size_t index(const std::string& key, std::size_t i) const {
        std::uint64_t h = std::hash<std::string>{}(key);
        h += (i + 1) * 0x9e3779b97f4a7c15ULL;
        return static_cast<std::size_t>(mix(h) % bitCount_);
    }

    std::vector<std::uint64_t> bits_;
    std::size_t bitCount_ = 0;
    std::size_t hashCount_ = 0;
};

22 位图 ​

展开源码
cpp
// 22_bitmap.cpp —— 位图
// set / clear / test / flip / count 均为 O(1)(count 为 O(n/64))
// 40 亿个整数约需 512MB
// 对应《3. 数据结构.md》§三.5

#include <cstddef>
#include <cstdint>
#include <vector>

class Bitmap {
public:
    explicit Bitmap(std::size_t n) : bits_((n + 63) / 64, 0), n_(n) {}

    void set(std::size_t i) {
        bits_[i >> 6] |= (std::uint64_t{1} << (i & 63));
    }

    void clear(std::size_t i) {
        bits_[i >> 6] &= ~(std::uint64_t{1} << (i & 63));
    }

    bool test(std::size_t i) const {
        return (bits_[i >> 6] >> (i & 63)) & 1ULL;
    }

    void flip(std::size_t i) {
        bits_[i >> 6] ^= (std::uint64_t{1} << (i & 63));
    }

    std::size_t count() const {
        std::size_t total = 0;
        for (std::uint64_t word : bits_)
            total += static_cast<std::size_t>(__builtin_popcountll(word));
        return total;
    }

    // 从 from 开始第一个置位的位置;没有则返回 n_
    std::size_t nextSet(std::size_t from) const {
        for (std::size_t i = from; i < n_; ++i)
            if (test(i)) return i;
        return n_;
    }

    std::size_t size() const { return n_; }

private:
    std::vector<std::uint64_t> bits_;
    std::size_t n_;
};

23 跳表 ​

展开源码
cpp
// 23_skiplist.cpp —— 跳表
// 多层索引 + 随机层数,期望 O(log n);Redis zset 用它 + 哈希表
// 对应《3. 数据结构.md》§四.10

#include <cstdlib>
#include <vector>

class Skiplist {
public:
    Skiplist() : head_(new Node(-1, kMaxLevel)), level_(1) {}

    ~Skiplist() {
        // 只沿第 0 层释放,避免同一节点被重复 delete
        Node* p = head_->next[0];
        while (p) {
            Node* next = p->next[0];
            delete p;
            p = next;
        }
        delete head_;
    }

    Skiplist(const Skiplist&) = delete;
    Skiplist& operator=(const Skiplist&) = delete;

    bool search(int target) const {
        const Node* cur = head_;
        for (int i = level_ - 1; i >= 0; --i) {
            while (cur->next[i] && cur->next[i]->val < target)
                cur = cur->next[i];
        }
        cur = cur->next[0];
        return cur && cur->val == target;
    }

    void add(int num) {
        std::vector<Node*> update(kMaxLevel, nullptr);
        Node* cur = head_;
        for (int i = level_ - 1; i >= 0; --i) {
            while (cur->next[i] && cur->next[i]->val < num)
                cur = cur->next[i];
            update[i] = cur;
        }

        int newLevel = randomLevel();
        if (newLevel > level_) {
            for (int i = level_; i < newLevel; ++i) update[i] = head_;
            level_ = newLevel;
        }

        Node* node = new Node(num, newLevel);
        for (int i = 0; i < newLevel; ++i) {
            node->next[i] = update[i]->next[i];
            update[i]->next[i] = node;
        }
    }

    bool erase(int num) {
        std::vector<Node*> update(kMaxLevel, nullptr);
        Node* cur = head_;
        for (int i = level_ - 1; i >= 0; --i) {
            while (cur->next[i] && cur->next[i]->val < num)
                cur = cur->next[i];
            update[i] = cur;
        }

        Node* victim = cur->next[0];
        if (!victim || victim->val != num) return false;

        for (int i = 0; i < level_; ++i) {
            if (update[i]->next[i] == victim)
                update[i]->next[i] = victim->next[i];
        }
        delete victim;

        while (level_ > 1 && !head_->next[level_ - 1]) --level_;
        return true;
    }

private:
    struct Node {
        int val;
        std::vector<Node*> next;
        Node(int v, int level) : val(v), next(level, nullptr) {}
    };

    static constexpr int kMaxLevel = 16;

    // p = 1/4:每 4 个节点期望升一层
    static int randomLevel() {
        int level = 1;
        while (level < kMaxLevel && std::rand() % 4 == 0) ++level;
        return level;
    }

    Node* head_;
    int level_;
};

24 KMP 算法 ​

展开源码
cpp
// 24_kmp.cpp —— KMP 字符串匹配
// pi[i] = pat[0..i] 的最长相等真前缀 / 真后缀长度
// 预处理 O(m),匹配 O(n)
// 对应《3. 数据结构.md》§二.9

#include <cstddef>
#include <string>
#include <vector>

class KMP {
public:
    static std::vector<int> buildPi(const std::string& pat) {
        std::vector<int> pi(pat.size(), 0);
        for (std::size_t i = 1, j = 0; i < pat.size(); ++i) {
            while (j > 0 && pat[i] != pat[j]) j = pi[j - 1];
            if (pat[i] == pat[j]) ++j;
            pi[i] = static_cast<int>(j);
        }
        return pi;
    }

    // 返回所有匹配的起始下标
    static std::vector<int> search(const std::string& text, const std::string& pat) {
        std::vector<int> res;
        if (pat.empty()) return res;

        std::vector<int> pi = buildPi(pat);
        for (std::size_t i = 0, j = 0; i < text.size(); ++i) {
            while (j > 0 && text[i] != pat[j]) j = pi[j - 1];
            if (text[i] == pat[j]) ++j;
            if (j == pat.size()) {
                res.push_back(static_cast<int>(i - j + 1));
                j = pi[j - 1];                     // 继续找下一处
            }
        }
        return res;
    }

    // 最短循环节:n % (n - pi[n-1]) == 0 时返回该节,否则返回原串
    static std::string shortestPeriod(const std::string& s) {
        if (s.empty()) return s;
        std::vector<int> pi = buildPi(s);
        int n = static_cast<int>(s.size());
        int p = n - pi[n - 1];
        if (n % p == 0) return s.substr(0, p);
        return s;
    }
};

25 随机集合 ​

展开源码
cpp
// 25_randomized_set.cpp —— O(1) 随机插入 / 删除 / 取随机元素
// vector + 哈希表(值 -> 下标),删除用「与末尾交换再 pop」
// 对应《3. 数据结构.md》§七.5

#include <cstddef>
#include <cstdlib>
#include <unordered_map>
#include <vector>

class RandomizedSet {
public:
    bool insert(int val) {
        if (pos_.count(val)) return false;
        pos_[val] = nums_.size();
        nums_.push_back(val);
        return true;
    }

    bool remove(int val) {
        auto it = pos_.find(val);
        if (it == pos_.end()) return false;

        std::size_t idx = it->second;
        int last = nums_.back();
        nums_[idx] = last;          // 末尾元素填到待删位置
        pos_[last] = idx;
        nums_.pop_back();
        pos_.erase(it);             // 注意在覆盖之后删,val == last 也正确
        return true;
    }

    int getRandom() const {
        return nums_[static_cast<std::size_t>(std::rand()) % nums_.size()];
    }

    bool contains(int val) const { return pos_.count(val) > 0; }

    std::size_t size() const { return nums_.size(); }

private:
    std::vector<int> nums_;
    std::unordered_map<int, std::size_t> pos_;
};

26 合并 K 个有序链表 ​

展开源码
cpp
// 26_merge_k_lists.cpp —— 合并 K 个有序链表
// 小顶堆 O(N log k);分治两两合并 O(N log k),常数更小
// 对应《3. 数据结构.md》§七.6

#include <queue>
#include <vector>

struct ListNode {
    int val;
    ListNode* next;
    explicit ListNode(int v) : val(v), next(nullptr) {}
};

class MergeKLists {
public:
    // 小顶堆:比较器返回 true 表示 a 的优先级低于 b
    static ListNode* mergeHeap(std::vector<ListNode*>& lists) {
        auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
        std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(cmp)> pq(cmp);

        for (ListNode* head : lists) {
            if (head) pq.push(head);
        }

        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (!pq.empty()) {
            ListNode* node = pq.top();
            pq.pop();
            tail->next = node;
            tail = node;
            if (node->next) pq.push(node->next);
        }
        return dummy.next;
    }

    // 分治:两两合并
    static ListNode* mergeDivide(std::vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        return divide(lists, 0, static_cast<int>(lists.size()) - 1);
    }

private:
    static ListNode* divide(std::vector<ListNode*>& lists, int l, int r) {
        if (l == r) return lists[l];
        int mid = l + (r - l) / 2;
        return mergeTwo(divide(lists, l, mid), divide(lists, mid + 1, r));
    }

    static ListNode* mergeTwo(ListNode* a, ListNode* b) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while (a && b) {
            if (a->val <= b->val) {
                tail->next = a;
                a = a->next;
            } else {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return dummy.next;
    }
};

27 线程安全队列 ​

展开源码
cpp
// 27_thread_safe_queue.cpp —— 有界阻塞队列
// mutex + 两个条件变量;wait 必须带谓词(防虚假唤醒)
// close 后仍会把队列剩余任务消费完,再返回 false(优雅关闭)
// 对应《3. 数据结构.md》§七.7

#include <condition_variable>
#include <cstddef>
#include <mutex>
#include <queue>
#include <utility>

template <typename T>
class BoundedBlockingQueue {
public:
    explicit BoundedBlockingQueue(std::size_t capacity) : capacity_(capacity) {}

    bool push(T value) {
        std::unique_lock<std::mutex> lock(mutex_);
        notFull_.wait(lock, [this] { return closed_ || queue_.size() < capacity_; });
        if (closed_) return false;
        queue_.push(std::move(value));
        notEmpty_.notify_one();
        return true;
    }

    bool pop(T& out) {
        std::unique_lock<std::mutex> lock(mutex_);
        notEmpty_.wait(lock, [this] { return closed_ || !queue_.empty(); });
        if (queue_.empty()) return false;   // 已关闭且队列已排空
        out = std::move(queue_.front());
        queue_.pop();
        notFull_.notify_one();
        return true;
    }

    void close() {
        {
            std::lock_guard<std::mutex> lock(mutex_);
            closed_ = true;
        }
        notEmpty_.notify_all();
        notFull_.notify_all();
    }

    bool closed() const {
        std::lock_guard<std::mutex> lock(mutex_);
        return closed_;
    }

    std::size_t size() const {
        std::lock_guard<std::mutex> lock(mutex_);
        return queue_.size();
    }

private:
    std::size_t capacity_;
    std::queue<T> queue_;
    bool closed_ = false;
    mutable std::mutex mutex_;
    std::condition_variable notEmpty_;
    std::condition_variable notFull_;
};