24、数据结构与算法实现：链表、栈与队列、二叉树、排序算法（快排、归并）、STL算法自定义实现

说实话，数据结构与算法这块，是很多C++初学者的分水岭。有人觉得它抽象，有人觉得它枯燥。但我个人觉得，它恰恰是编程最有意思的部分——你想想看，你是在用代码搭建一套逻辑体系，让数据按照你的规则流动、排序、查找。

我在项目中遇到过好几次，业务逻辑本身不复杂，但数据量一上来，性能就崩了。最后定位下来，往往不是代码写得不对，而是数据结构选错了。所以这一章，咱们就扎扎实实地把几个最常用的数据结构手写一遍，再聊聊STL里那些算法的底层逻辑。

24.1 链表：最基础的动态结构

链表这东西，说白了就是一个个节点串起来。每个节点存着数据，还存着下一个节点的地址。它不像数组那样需要连续内存，所以插入和删除特别快——O(1)就能搞定，只要你已经找到了位置。

我习惯把链表分为三种：单向链表、双向链表、循环链表。实际工作中，双向链表用得最多，因为STL的list就是它。

核心要点： 链表的插入和删除是O(1)，但查找是O(n)。如果你需要频繁随机访问，别用链表，用vector。 
// 单向链表节点定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 插入节点到链表头部
void insertHead(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
}

// 遍历链表
void traverse(ListNode* head) {
    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
}
小技巧： 写链表操作时，我习惯先画图。把指针的指向画清楚，代码自然就写对了。千万别硬想，人脑不是CPU。

24.2 栈与队列：两种经典线性结构

栈是后进先出（LIFO），队列是先进先出（FIFO）。这两个概念，你肯定在生活里见过——栈就像一摞盘子，你只能从最上面拿；队列就像排队买奶茶，先来的先买。

我曾经在写一个表达式求值的模块时，就用栈来处理运算符优先级。当时调试了好久，最后发现是栈顶元素判断写反了。嗯，这里要注意：栈的pop操作不返回元素，top才返回。这是C++的一个设计选择，很多人刚接触时会踩坑。

// 用数组实现栈
class MyStack {
private:
    int* data;
    int capacity;
    int topIdx;
public:
    MyStack(int cap) : capacity(cap), topIdx(-1) {
        data = new int[capacity];
    }
    ~MyStack() { delete[] data; }

    void push(int val) {
        if (topIdx < capacity - 1) {
            data[++topIdx] = val;
        }
    }

    int pop() {
        if (topIdx >= 0) {
            return data[topIdx--];
        }
        return -1; // 空栈
    }

    int top() {
        if (topIdx >= 0) return data[topIdx];
        return -1;
    }

    bool empty() { return topIdx == -1; }
};
注意： 用数组实现栈时，一定要考虑容量问题。我见过有人忘记检查栈满，结果数据越界，把别的内存给覆盖了。这种bug极难排查。

24.3 二叉树：递归的天然舞台

二叉树是我个人觉得最优雅的数据结构。它的定义本身就是递归的：一个节点，有左子树和右子树。你想想看，这种结构天生就适合用递归来处理。

二叉树的遍历有四种：前序、中序、后序、层序。前三种用递归写起来特别简洁，层序则需要借助队列。我在项目中用二叉树做过一个简单的文件系统目录树，每个节点代表一个文件夹，子节点就是子文件夹。查找路径时，用前序遍历就能搞定。

// 二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

// 中序遍历：左-根-右
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    std::cout << root->val << " ";
    inorder(root->right);
}

// 后序遍历：左-右-根
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    std::cout << root->val << " ";
}
记忆口诀： 前序是“根左右”，中序是“左根右”，后序是“左右根”。记住根的位置，其他就好办了。

24.4 排序算法：快排与归并

排序算法里，快排和归并是面试常客，也是实际工程中最常用的两种。我个人的经验是：快排适合内存排序，归并适合外部排序（比如磁盘上的大数据）。

快排的核心是分治：选一个基准值，把比它小的放左边，比它大的放右边，然后递归处理左右两边。归并也是分治，但它先递归到底，再合并两个有序数组。

// 快速排序
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {
            ++i;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 归并排序
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    std::vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
避坑指南： 快排的基准值选择很关键。我曾经用固定选最后一个元素的方式，结果遇到一个已经排好序的数组，直接退化成了O(n²)。后来我改用“三数取中”法，才稳定下来。

24.5 STL算法自定义实现

STL里有很多算法，比如std::find、std::copy、std::sort。但有时候，你需要自己实现一个类似的函数，来满足特定需求。比如，我想找一个容器里第一个大于某个值的元素，但STL的std::find_if需要传一个lambda，有时候写起来不够直观。

我建议你试着手写几个常用的STL算法，不是为了造轮子，而是为了理解它们的底层逻辑。你想想看，当你自己实现过std::copy，你就知道它为什么比手写循环快——因为它用了memmove优化。

// 自定义 find_if
template<typename InputIt, typename UnaryPredicate>
InputIt my_find_if(InputIt first, InputIt last, UnaryPredicate pred) {
    while (first != last) {
        if (pred(*first)) return first;
        ++first;
    }
    return last;
}

// 自定义 copy
template<typename InputIt, typename OutputIt>
OutputIt my_copy(InputIt first, InputIt last, OutputIt d_first) {
    while (first != last) {
        *d_first++ = *first++;
    }
    return d_first;
}

// 自定义 accumulate
template<typename InputIt, typename T>
T my_accumulate(InputIt first, InputIt last, T init) {
    while (first != last) {
        init = init + *first++;
    }
    return init;
}
个人习惯： 我写自定义算法时，会尽量保持和STL一致的接口风格——用迭代器而不是容器。这样你的算法就能适配任何容器，vector、list、deque都能用。

24.6 知识体系总览

这一章的内容比较多，我画了一张图帮你梳理一下整体结构。你看，从线性结构到树形结构，再到排序和算法，其实有一条清晰的脉络。

数据结构与算法实现 线性结构 树形结构 算法 链表 栈 队列 二叉树（前/中/后序遍历） 快排 归并 STL算法 核心思想：分治 + 递归 + 迭代器 选择合适的数据结构，比写出完美的算法更重要

这张图把本章的知识点分成了三大块：线性结构、树形结构、算法。你看，链表、栈、队列都属于线性结构，它们的数据排列是一条线。二叉树则是树形结构的代表，它的遍历方式很有规律。排序算法和STL算法则属于算法范畴，它们解决的是“怎么处理数据”的问题。

我个人建议你按照这个顺序来学习：先手写链表，再实现栈和队列，然后攻克二叉树，最后挑战排序和STL算法。每一步都动手敲代码，别光看。你想想看，光看不练，就像看菜谱学做菜，永远做不出那道菜。

本章总结：
  • 链表：动态插入删除快，随机访问慢
  • 栈：后进先出，适合括号匹配、表达式求值
  • 队列：先进先出，适合BFS、任务调度
  • 二叉树：递归结构，前/中/后序遍历是基础
  • 快排：平均O(n log n)，注意基准值选择
  • 归并：稳定排序，适合外部排序
  • STL算法：理解迭代器模式，自己实现一遍更深刻

好了，这一章的内容就到这里。代码我都贴出来了，你最好自己敲一遍，跑一跑。遇到问题别怕，调试器是你最好的朋友。下一章咱们会聊更高级的话题，先把这些基础打牢。

← 上一章 📖 返回目录 下一章 →