C++八股文（数据结构与算法）

1. 如何实现一个链表？

单链表核心实现：

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

class LinkedList {
    ListNode* head;
public:
    LinkedList() : head(nullptr) {}
    
    void insert(int val) {  // 头插
        ListNode* node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    void remove(int val) {  // 删除节点
        ListNode dummy(0);
        dummy.next = head;
        ListNode* prev = &dummy;
        while (prev->next) {
            if (prev->next->val == val) {
                ListNode* temp = prev->next;
                prev->next = prev->next->next;
                delete temp;
                break;
            }
            prev = prev->next;
        }
        head = dummy.next;
    }
};

• 关键点：节点结构（数据+指针）、头指针管理、插入删除操作
• 双向链表：节点增加prev指针，可双向遍历
• 循环链表：尾节点指向头节点
• 常见操作：反转链表、查找中间节点、合并有序链表、检测环
• 优点：动态大小、插入删除O(1)
• 缺点：随机访问O(n)、额外指针空间

2. 如何实现栈和队列？

栈（数组实现）：

class Stack {
    vector<int> data;
public:
    void push(int x) { data.push_back(x); }
    void pop() { if (!empty()) data.pop_back(); }
    int top() { return data.back(); }
    bool empty() { return data.empty(); }
};

队列（链表实现）：

class Queue {
    list<int> data;
public:
    void push(int x) { data.push_back(x); }
    void pop() { if (!empty()) data.pop_front(); }
    int front() { return data.front(); }
    bool empty() { return data.empty(); }
};

• 栈特点：LIFO（后进先出），用于函数调用、表达式求值、DFS
• 队列特点：FIFO（先进先出），用于BFS、任务调度
• 循环队列：数组实现，避免空间浪费，需要front、rear指针
• 双端队列：两端都可插入删除，STL的deque
• STL容器：stack、queue、priority_queue（堆）

3. 如何实现二叉树的前序、中序、后序遍历？

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

// 前序：根-左-右
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

// 中序：左-根-右（二叉搜索树得到有序序列）
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// 后序：左-右-根
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

// 层序遍历（BFS）
void levelorder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

• 递归实现：简洁但可能栈溢出
• 迭代实现：用栈模拟递归，前序和中序较简单，后序稍复杂
• Morris遍历：O(1)空间，利用线索二叉树
• 应用：前序用于复制树、中序用于BST排序、后序用于删除树

4. 如何实现哈希表？

class HashTable {
    static const int SIZE = 1000;
    vector<list<pair<int, int>>> table;  // 链地址法
public:
    HashTable() : table(SIZE) {}
    
    int hash(int key) { return key % SIZE; }
    
    void insert(int key, int value) {
        int idx = hash(key);
        for (auto& p : table[idx]) {
            if (p.first == key) {
                p.second = value;  // 更新
                return;
            }
        }
        table[idx].push_back({key, value});
    }
    
    int get(int key) {
        int idx = hash(key);
        for (auto& p : table[idx]) {
            if (p.first == key) return p.second;
        }
        return -1;  // 不存在
    }
    
    void remove(int key) {
        int idx = hash(key);
        table[idx].remove_if([key](auto& p) { return p.first == key; });
    }
};

• 哈希函数：将key映射到索引，要求分布均匀、计算快速
• 冲突解决：①链地址法（拉链法）②开放地址法（线性探测、二次探测、双重哈希）
• 负载因子：元素数/桶数，过高需要rehash扩容
• 时间复杂度：平均O(1)，最坏O(n)
• STL实现：unordered_map、unordered_set

5. 如何使用 std::map 和 std::unordered_map？