C++算法与数据结构：初学者完全指南

C++ 算法与数据结构：从基础到进阶技术

算法与数据结构是任何高效程序的基石。使用 C++，您可以完全控制内存和性能，这使得该语言成为学习算法思维的理想选择。在本文中，我们将分析关键概念，提供代码示例，并展示如何在实际中应用它们。本材料适合初学者以及希望系统化知识的开发者。

我们将讨论三大类：线性数据结构（数组、列表、栈、队列）、层次结构（树）以及处理算法（排序和搜索）。每个部分都包含现成的 C++ 代码和解释。

1. 线性数据结构：数组、链表、栈和队列

线性结构是处理数据的基础。在 C++ 中，它们既可以通过内置工具实现，也可以通过自定义类实现。

数组和动态数组 (std::vector)

数组是最简单的固定大小结构。为了灵活性，请使用 std::vector：

#include <iostream>#include <vector>

int main() {    std::vector<int> numbers = {5, 2, 8, 1, 9};        // 添加元素    numbers.push_back(3);        // 按索引访问    std::cout << "第三个元素: " << numbers[2] << std::endl;        // 遍历    for (int num : numbers) {        std::cout << num << " ";    }    return 0;}

优点： 快速访问 O(1)，缓存局部性。 缺点： 中间插入/删除为 O(n)。

链表（单向）

链表由节点组成，每个节点存储数据并指向下一个元素。C++ 实现：

struct Node {    int data;    Node* next;        Node(int val) : data(val), next(nullptr) {}};

class LinkedList {private:    Node* head;public:    LinkedList() : head(nullptr) {}        void pushFront(int val) {        Node* newNode = new Node(val);        newNode->next = head;        head = newNode;    }        void print() {        Node* current = head;        while (current) {            std::cout << current->data << " -> ";            current = current->next;        }        std::cout << "nullptr" << std::endl;    }        ~LinkedList() {        Node* current = head;        while (current) {            Node* next = current->next;            delete current;            current = next;        }    }};

何时使用： 频繁在列表开头插入/删除。搜索为 O(n)。

栈和队列

栈（LIFO）和队列（FIFO）是专用结构。C++ 中有现成的适配器：

#include <stack>#include <queue>

int main() {    // 栈    std::stack<int> st;    st.push(10);    st.push(20);    std::cout << "栈顶: " << st.top() << std::endl; // 20    st.pop();        // 队列    std::queue<int> q;    q.push(1);    q.push(2);    std::cout << "队首: " << q.front() << std::endl; // 1    q.pop();        return 0;}

2. 层次结构：二叉搜索树

树可以高效地存储层次数据。二叉搜索树（BST）是 C++ 算法中的经典。

BST 实现

struct TreeNode {    int key;    TreeNode* left;    TreeNode* right;        TreeNode(int k) : key(k), left(nullptr), right(nullptr) {}};

TreeNode* insert(TreeNode* root, int key) {    if (!root) return new TreeNode(key);        if (key < root->key)        root->left =