C++算法与数据结构：开发者实用指南

C++中的算法与数据结构：从理论到实际项目

掌握算法与数据结构是区分新手程序员与专业工程师的基础。在C++这种功能强大且性能卓越的语言中，理解这些概念不仅能让您编写出可运行的代码，更能构建出快速、可扩展且可靠的代码。在本文中，我们将结合现成的案例，解析关键的数据结构和算法，您可以直接将这些代码用于自己的项目。

我们不会深入抽象理论——每个小节都包含具体的C++代码及解释，说明特定构造的工作原理及原因。本文面向已熟悉C++语法但希望系统化整理算法知识的开发者。

1. 基础数据结构：数组、链表与动态结构

我们从基础开始。C++标准库（STL）提供了强大的容器，但理解其内部工作机制对于性能优化至关重要。

动态数组（std::vector）

std::vector是最常用的容器。它是一个动态数组，在添加元素时会自动扩容。但需要记住其摊还复杂度：尾部插入平均为O(1)，而中间插入为O(n)。

#include <iostream>#include <vector>

int main() {    std::vector<int> numbers = {10, 20, 30, 40};        // 尾部添加    numbers.push_back(50);        // 头部插入（代价较高的操作）    numbers.insert(numbers.begin(), 5);        // 移除最后一个元素    numbers.pop_back();        for (int num : numbers) {        std::cout << num << " ";    }    // 输出: 5 10 20 30 40    return 0;}

链表（std::list）

与vector不同，std::list实现为双向链表。当需要频繁在容器中间插入或删除元素时，它是理想选择——这些操作的时间复杂度为O(1)。但其代价是无法通过索引直接访问元素。

#include <list>

std::list<std::string> tasks = {"编写代码", "运行测试"};tasks.push_front("规划架构");tasks.push_back("编写文档");

// 在中间插入auto it = tasks.begin();std::advance(it, 2); // 将迭代器移动到第二个元素tasks.insert(it, "重构");

栈与队列（std::stack, std::queue）

这些是容器适配器，它们限制了底层容器的功能。栈遵循后进先出（LIFO）原则，队列遵循先进先出（FIFO）原则。

#include <stack>#include <queue>

// 栈std::stack<int> st;st.push(1);st.push(2);st.pop(); // 移除2

// 队列std::queue<int> q;q.push(10);q.push(20);q.pop(); // 移除10（第一个元素）

2. 排序与搜索算法：从冒泡排序到二分查找

排序是经典问题，但在实践中，重要的是知道何时使用内置算法，何时自行编写。

快速排序——C++实现

STL使用内省排序（快速排序、堆排序和插入排序的混合体）。但为了理解原理，我们编写一个经典的快速排序：

#include <iostream>#include <vector>

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 < hi