C++数据结构知识点汇总
编程小白也能轻松理解的数据结构指南
数据结构是编程世界的基石！本指南用通俗易懂的方式解释C++中常见的数据结构概念，配合简单示例和生动比喻，帮助你快速掌握核心知识点。
数组 (Array)
📦 就像一排连续的储物柜，每个柜子都有编号（索引），可以存放物品（数据）。
核心特点
- 元素在内存中连续存储
- 通过索引（从0开始）快速访问元素
- 大小固定（创建后不能改变容量）
- 所有元素类型相同
访问
O(1)
插入/删除
O(n)
搜索
O(n)
代码示例
// 创建包含5个整数的数组
int scores[5] = {95, 87, 92, 78, 88};
// 访问第三个元素（索引2）
cout << "第三位成绩：" << scores[2] << endl;
// 修改第一个元素
scores[0] = 97;
链表 (Linked List)
🔗 就像寻宝游戏，每个线索（节点）告诉你宝藏位置（数据）和下一个线索的位置（指针）。
核心特点
- 元素（节点）包含数据和指向下一个节点的指针
- 内存中非连续存储
- 动态大小（可以随时增加/删除节点）
- 有单链表、双链表、循环链表等变体
访问
O(n)
插入/删除
O(1)（已知位置）
搜索
O(n)
代码示例
// 定义链表节点
struct Node {
int data;
Node* next;
};
// 创建简单链表：1 -> 2 -> 3
Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};
// 遍历链表
Node* current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
栈 (Stack)
📚 就像一摞书，你只能从最上面取书（后进先出 – LIFO）。
核心特点
- 后进先出（LIFO）原则
- 主要操作：push（入栈）、pop（出栈）、top（查看栈顶）
- 常用于：函数调用、撤销操作、表达式求值
push/pop
O(1)
搜索
O(n)
代码示例
#include <stack>
stack<string> books;
// 入栈操作
books.push(“C++ Primer”);
books.push(“算法导论”);
books.push(“设计模式”);
// 查看栈顶
cout << "最上面的书：" << books.top() << endl;
// 出栈
books.pop(); // 移除"设计模式"
队列 (Queue)
🚶 就像排队买票，先来的人先服务（先进先出 – FIFO）。
核心特点
- 先进先出（FIFO）原则
- 主要操作：enqueue（入队）、dequeue（出队）、front（查看队首）
- 常用于：任务调度、消息传递、BFS算法
enqueue/dequeue
O(1)
搜索
O(n)
代码示例
#include <queue>
queue<string> ticketLine;
// 入队
ticketLine.push(“张三”);
ticketLine.push(“李四”);
ticketLine.push(“王五”);
// 查看队首
cout << "下一位：" << ticketLine.front() << endl;
// 出队
ticketLine.pop(); // 张三离开
树 (Tree)
🌳 就像家族树，有祖先（根节点）、后代（子节点），每个节点可以有多个孩子。
核心特点
- 分层数据结构（非线性的）
- 基本概念：根节点、子节点、父节点、叶节点
- 常见类型：二叉树、二叉搜索树、平衡树
- 遍历方式：前序、中序、后序、层序
二叉树遍历
// 二叉树节点结构
struct TreeNode {
int value;
TreeNode* left;
TreeNode* right;
};
// 前序遍历：根 -> 左 -> 右
void preOrder(TreeNode* node) {
if (node == nullptr) return;
cout << node->value << " "; // 访问根节点
preOrder(node->left); // 遍历左子树
preOrder(node->right); // 遍历右子树
}
哈希表 (Hash Table)
📇 就像图书馆的索引系统，书名（键）通过特定规则映射到书架位置（值）。
核心特点
- 通过哈希函数将键映射到存储位置
- 平均情况下提供O(1)的插入、删除和查找
- 需要处理哈希冲突（不同键映射到同一位置）
- C++中对应unordered_map和unordered_set
平均情况
O(1)
最坏情况
O(n)
代码示例
#include <unordered_map>
#include <string>
// 创建电话簿（名字->电话号码）
unordered_map<string, string> phonebook;
// 添加联系人
phonebook[“张三”] = “13800138000”;
phonebook[“李四”] = “13900139000”;
// 查找号码
if (phonebook.find(“张三”) != phonebook.end()) {
cout << "张三的电话：" << phonebook["张三"] << endl;
}
// 删除联系人
phonebook.erase("李四");