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？

// map：红黑树实现，有序，O(log n)
map<string, int> m;
m["apple"] = 1;
m.insert({"banana", 2});
if (m.count("apple")) cout << m["apple"];
for (auto& [key, val] : m) cout << key << ":" << val;

// unordered_map：哈希表实现，无序，O(1)
unordered_map<string, int> um;
um["apple"] = 1;
auto it = um.find("apple");
if (it != um.end()) cout << it->second;
um.erase("apple");

map特点：有序（按key排序）、O(log n)操作、迭代器稳定
unordered_map特点：无序、平均O(1)、可能rehash导致迭代器失效
选择依据：需要有序用map，追求性能用unordered_map
自定义类型：map需要<运算符，unordered_map需要hash函数和==运算符
常用操作：insert、erase、find、count、[]运算符（不存在会插入）

6. 如何实现图的DFS和BFS？

// 邻接表表示图
vector<vector<int>> graph;

// DFS递归
void dfs(int node, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

// DFS迭代（栈）
void dfsIterative(int start) {
    vector<bool> visited(graph.size(), false);
    stack<int> s;
    s.push(start);
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        if (visited[node]) continue;
        visited[node] = true;
        cout << node << " ";
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) s.push(neighbor);
        }
    }
}

// BFS（队列）
void bfs(int start) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

DFS特点：深度优先，用栈（递归或显式），适合路径搜索、拓扑排序
BFS特点：广度优先，用队列，适合最短路径、层次遍历
时间复杂度：O(V+E)，V顶点数，E边数
应用：连通性检测、环检测、最短路径、拓扑排序

7. 如何使用 std::vector 和 std::array？

// vector：动态数组
vector<int> v = {1, 2, 3};
v.push_back(4);
v.pop_back();
v.insert(v.begin() + 1, 10);  // 位置1插入10
v.erase(v.begin());
cout << v.size() << " " << v.capacity();
v.reserve(100);  // 预分配容量
v.shrink_to_fit();  // 释放多余容量

// array：固定大小数组（C++11）
array<int, 5> arr = {1, 2, 3, 4, 5};
arr[0] = 10;
arr.at(1) = 20;  // 带边界检查
for (int x : arr) cout << x;

vector特点：动态大小、连续内存、随机访问O(1)、尾部插入删除O(1)、中间操作O(n)
扩容机制：容量不足时重新分配（通常2倍），拷贝元素，旧内存释放
array特点：编译期固定大小、栈分配、无动态分配开销、不能改变大小
选择：大小固定用array，动态变化用vector
常用操作：push_back、emplace_back（原地构造）、resize、clear、swap

8. 如何判断一个字符串是回文？

// 双指针法
bool isPalindrome(string s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

// 忽略非字母数字、忽略大小写
bool isPalindromeAlphanumeric(string s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        while (left < right && !isalnum(s[left])) left++;
        while (left < right && !isalnum(s[right])) right--;
        if (tolower(s[left]) != tolower(s[right])) return false;
        left++;
        right--;
    }
    return true;
}

时间复杂度：O(n)
空间复杂度：O(1)
变体：最长回文子串（动态规划或中心扩展）、回文链表（快慢指针+反转）
技巧：双指针、中心扩展、Manacher算法（O(n)找最长回文）

9. 如何实现快速排序和归并排序？

// 快速排序：分治，选pivot，小的左边大的右边
void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left + (right - left) / 2];
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

// 归并排序：分治，递归排序左右，合并
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (int i = 0; i < temp.size(); i++) {
        arr[left + i] = temp[i];
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

快速排序：平均O(n log n)，最坏O(n²)，不稳定，原地排序
归并排序：O(n log n)，稳定，需要O(n)额外空间
优化：快排选择随机pivot、三数取中；小数组用插入排序
STL：std::sort（快排+堆排+插入排序混合）、std::stable_sort（归并排序）

10. 如何判断一个链表是否有环？

// Floyd判圈算法（快慢指针）
bool hasCycle(ListNode* head) {
    if (!head) return false;
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;  // 相遇说明有环
    }
    return false;
}

// 找环的入口
ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // 相遇后，一个指针回到头，两个都走一步，再次相遇就是入口
            ListNode* ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    return nullptr;
}

快慢指针原理：有环则快指针会追上慢指针，无环则快指针到达末尾
时间复杂度：O(n)
空间复杂度：O(1)
数学证明：设环外长度a，环长b，相遇时慢指针走a+x，快指针走a+nb+x，2(a+x)=a+nb+x，得a=nb-x
其他方法：哈希表记录访问过的节点（O(n)空间）

C++八股文全集文章被收录于专栏

本专栏系统梳理C++技术面试核心考点，涵盖语言基础、面向对象、内存管理、STL容器、模板编程及经典算法。从引用指针、虚函数表、智能指针等底层原理，到继承多态、运算符重载等OOP特性从const、static、inline等关键字辨析，到动态规划、KMP算法、并查集等手写实现。每个知识点以面试答题形式呈现，注重原理阐述而非冗长代码，帮助你快速构建完整知识体系，从容应对面试官提问，顺利拿下offer。