C++ 数据结构（手把手讲解）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

在编程世界中，数据结构如同搭建软件系统的“建筑材料”，而C++作为一门高效且灵活的编程语言，为开发者提供了直接操作内存和优化数据结构的底层能力。本文将从基础到进阶，系统讲解C++中常用的数据结构实现原理与应用场景，并通过代码示例和生活化比喻帮助读者建立直观理解。

一、线性数据结构：基础与核心

1.1 数组：有序的连续存储空间

数组是C++中最基础的数据结构，它通过连续的内存块存储相同类型的数据。例如，一个包含5个整数的数组int arr[5]，其底层表现为一块连续的内存区域。
特性：

• 快速随机访问：通过索引直接定位元素，时间复杂度为O(1)。
• 固定大小：创建后无法动态调整长度。

代码示例：

#include <iostream>  
int main() {  
    int scores[3] = {85, 92, 78};  
    std::cout << "Second score: " << scores[1] << std::endl;  // 输出92  
    return 0;  
}  

1.2 栈：后进先出（LIFO）的“托盘堆叠”

栈的特性类似于将托盘逐层堆叠，新元素总被放置在栈顶，取出时也从顶部开始。C++中可通过std::stack或自定义类实现。

比喻：
想象图书馆的书架，每次放书都放在最上层，取书时只能取最上面的那本。

代码示例（自定义栈类）：

#include <vector>  
template<typename T>  
class Stack {  
    std::vector<T> container;  
public:  
    void push(const T& value) { container.push_back(value); }  
    void pop() { container.pop_back(); }  
    T top() const { return container.back(); }  
    bool empty() const { return container.empty(); }  
};  

应用场景：括号匹配、函数调用栈、表达式求值。

二、链式结构：灵活的动态内存管理

2.1 链表：分散节点的“铁路车厢”

链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。这如同铁路车厢通过挂钩连接，可动态增删车厢。

优点：

• 动态扩展：无需预先分配内存。
• 高效插入/删除：操作时间复杂度为O(1)（假设已知目标节点）。

代码示例（单链表实现）：

struct Node {  
    int data;  
    Node* next;  
};  

// 插入节点操作  
void insert(Node*& head, int value) {  
    Node* newNode = new Node{value, nullptr};  
    if (!head) {  
        head = newNode;  
    } else {  
        Node* current = head;  
        while (current->next) { current = current->next; }  
        current->next = newNode;  
    }  
}  

2.2 队列：先进先出（FIFO）的“超市收银台”

队列遵循“先来先服务”原则，新元素添加到队尾，取出时从队头开始。C++中可通过std::queue或链表实现。

比喻：
超市排队付款，第一个到达的人最先完成交易。

代码示例（环形队列数组实现）：

class CircularQueue {  
    int front, rear, size;  
    int* arr;  
public:  
    CircularQueue(int capacity) {  
        size = capacity;  
        arr = new int[size];  
        front = rear = -1;  
    }  
    void enqueue(int value) {  
        if ((rear + 1) % size == front) {  
            std::cout << "Queue full!" << std::endl;  
            return;  
        }  
        rear = (rear + 1) % size;  
        arr[rear] = value;  
    }  
    // 其他方法略  
};  

三、树与图：复杂关系的抽象建模

3.1 二叉树：分叉结构的“家族族谱”

二叉树每个节点最多有两个子节点，适用于表示层级关系。例如，家族族谱中每个人可有至多两个孩子。

特性：

• 遍历方式多样：前序、中序、后序遍历对应不同的访问顺序。
• 高效搜索：平衡二叉树（如AVL树）的时间复杂度为O(log n)。

代码示例（二叉搜索树插入）：

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

TreeNode* insert(TreeNode* root, int value) {  
    if (!root) {  
        return new TreeNode(value);  
    }  
    if (value < root->val) {  
        root->left = insert(root->left, value);  
    } else {  
        root->right = insert(root->right, value);  
    }  
    return root;  
}  

3.2 图：复杂关系网络的“交通路网”

图由节点（顶点）和边组成，适用于表示社交网络、地图路径等复杂关系。C++中可通过邻接表或邻接矩阵实现。

比喻：
城市中的道路系统，每个交叉口是顶点，道路是边。

代码示例（邻接表实现无向图）：

#include <vector>  
using namespace std;  

class Graph {  
    int V;  
    vector<vector<int>> adj;  
public:  
    Graph(int vertices) : V(vertices), adj(vertices) {}  
    void addEdge(int u, int v) {  
        adj[u].push_back(v);  
        adj[v].push_back(u);  
    }  
    // 其他方法略  
};  

四、高级数据结构：结合算法的综合应用

4.1 哈希表：快速查找的“图书馆索引”

哈希表通过哈希函数将键映射到存储位置，实现平均O(1)时间复杂度的查找。C++中可通过std::unordered_map或自定义实现。

比喻：
图书馆的目录卡片，通过书名快速定位书架位置。

代码示例（简单哈希实现）：

#include <vector>  
#include <list>  

class HashTable {  
    int size;  
    std::vector<std::list<int>> table;  
public:  
    HashTable(int sz) : size(sz), table(sz) {}  
    int hash(int key) { return key % size; }  
    void insert(int key) {  
        int index = hash(key);  
        table[index].push_back(key);  
    }  
    // 其他方法略  
};  

4.2 优先队列：按优先级排序的“急诊室”

优先队列中元素按优先级排列，常用于任务调度或Dijkstra算法。C++的std::priority_queue默认实现最大堆。

比喻：
医院急诊室中，伤势最重的患者优先接受治疗。

代码示例（最小堆实现）：

#include <queue>  
#include <functional>  

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;  
minHeap.push(5);  
minHeap.push(3);  
std::cout << "Top element: " << minHeap.top() << std::endl;  // 输出3  

五、实践案例：数据结构的综合应用

5.1 括号匹配验证

利用栈的特性，可以验证字符串中的括号是否匹配：

bool isValid(const std::string& s) {  
    std::stack<char> st;  
    for (char c : s) {  
        if (c == '(' || c == '{' || c == '[') {  
            st.push(c);  
        } else {  
            if (st.empty()) return false;  
            char top = st.top(); st.pop();  
            if ((c == ')' && top != '(') ||  
                (c == '}' && top != '{') ||  
                (c == ']' && top != '[')) {  
                return false;  
            }  
        }  
    }  
    return st.empty();  
}  

5.2 图的最短路径算法

通过邻接表和广度优先搜索（BFS）实现无权图的最短路径计算：

#include <queue>  

void bfs(const Graph& graph, int start, std::vector<int>& dist) {  
    std::queue<int> q;  
    dist.assign(graph.V, -1);  
    dist[start] = 0;  
    q.push(start);  
    while (!q.empty()) {  
        int u = q.front(); q.pop();  
        for (int v : graph.adj[u]) {  
            if (dist[v] == -1) {  
                dist[v] = dist[u] + 1;  
                q.push(v);  
            }  
        }  
    }  
}  

结论

C++的数据结构不仅是编程的基础工具，更是理解计算机底层逻辑的关键。从简单的数组到复杂的图结构，每种数据结构都对应着特定的算法场景和优化方向。对于开发者而言，掌握这些结构的实现原理与实际应用，能够显著提升代码的效率与可维护性。建议读者通过实际项目（如实现一个简易数据库或游戏AI）来巩固知识，并结合STL容器（如vector、map）探索更高效的解决方案。

（全文约 1800 字）