C++ 提供了多种数据结构，可以帮助开发者高效地存储和管理数据。数据结构不仅是算法的基础，也在许多应用程序中发挥着重要作用。C++ 标准库（STL）提供了多种常见数据结构的实现，如数组、链表、栈、队列、堆、哈希表等。除此之外，我们还可以手动实现一些特定的数据结构。
1. 数组 (Array)
数组是最基本的数据结构，用于存储一组相同类型的数据元素。
- 静态数组：大小在编译时确定，无法动态扩展。
- 动态数组：可以动态调整大小，如
std::vector。
示例：
#include <iostream>
int main() {
int arr[5] = {1, 2, 3, 4, 5};
// 遍历数组
for (int i = 0; i < 5; ++i) {
std::cout << arr[i] << " ";
}
return 0;
}2. 链表 (Linked List)
链表是一种由节点构成的数据结构，其中每个节点包含数据和指向下一个节点的指针。链表具有动态内存分配的优势，可以在任意位置插入或删除元素。
- 单向链表：每个节点指向下一个节点。
- 双向链表：每个节点指向下一个节点和前一个节点。
示例：
#include <iostream>
struct Node {
int data;
Node* next;
};
int main() {
Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
// 遍历链表
Node* temp = head;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
return 0;
}3. 栈 (Stack)
栈是一种后进先出 (LIFO) 的数据结构。栈的操作有两个基本操作：
- push()：将元素添加到栈顶。
- pop()：从栈顶删除元素。
C++ 中可以使用 std::stack 实现栈。
示例：
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
// 入栈
s.push(10);
s.push(20);
s.push(30);
// 出栈
while (!s.empty()) {
std::cout << s.top() << " "; // 查看栈顶元素
s.pop(); // 移除栈顶元素
}
return 0;
}4. 队列 (Queue)
队列是一种先进先出 (FIFO) 的数据结构。队列的操作有两个基本操作：
- enqueue()：将元素添加到队列尾部。
- dequeue()：从队列头部删除元素。
C++ 中可以使用 std::queue 实现队列。
示例：
#include <iostream>
#include <queue>
int main() {
std::queue<int> q;
// 入队
q.push(10);
q.push(20);
q.push(30);
// 出队
while (!q.empty()) {
std::cout << q.front() << " "; // 查看队列头元素
q.pop(); // 移除队列头元素
}
return 0;
}5. 堆 (Heap)
堆是一种完全二叉树，可以分为最大堆和最小堆：
- 最大堆：父节点大于或等于子节点。
- 最小堆：父节点小于或等于子节点。
C++ 提供了 std::priority_queue 来实现堆。
示例：
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq;
// 插入元素
pq.push(10);
pq.push(30);
pq.push(20);
// 弹出最大元素
while (!pq.empty()) {
std::cout << pq.top() << " "; // 查看堆顶元素
pq.pop(); // 移除堆顶元素
}
return 0;
}6. 哈希表 (Hash Table)
哈希表（或称为哈希映射）是一种基于哈希函数的数据结构，可以在常数时间内进行插入、删除和查找操作。
C++ 提供了 std::unordered_map 和 std::unordered_set 来实现哈希表。
示例：
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> map;
// 插入键值对
map["apple"] = 5;
map["banana"] = 3;
// 查找元素
std::cout << "apple: " << map["apple"] << std::endl;
std::cout << "banana: " << map["banana"] << std::endl;
return 0;
}7. 集合 (Set)
集合是一种存储不重复元素的数据结构，支持高效查找、插入和删除。
C++ 提供了 std::set 和 std::unordered_set 来实现集合。
- std::set：有序集合，元素按顺序排列。
- std::unordered_set：无序集合，元素存储无特定顺序。
示例：
#include <iostream>
#include <set>
int main() {
std::set<int> s;
// 插入元素
s.insert(10);
s.insert(20);
s.insert(10); // 插入重复元素将被忽略
// 遍历集合
for (int x : s) {
std::cout << x << " ";
}
return 0;
}8. 映射 (Map)
映射是一种关联容器，用于存储键值对。每个键是唯一的，且与一个值相关联。
C++ 提供了 std::map 和 std::unordered_map 来实现映射。
- std::map：有序映射，键按升序排列。
- std::unordered_map：无序映射，键无特定顺序。
示例：
#include <iostream>
#include <map>
int main() {
std::map<int, std::string> m;
// 插入键值对
m[1] = "one";
m[2] = "two";
m[3] = "three";
// 查找并输出键值对
for (const auto& pair : m) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}9. 二叉树 (Binary Tree)
二叉树是一种树形数据结构，其中每个节点最多有两个子节点。它常用于实现 搜索树、堆、平衡树 等。
示例：
#include <iostream>
struct Node {
int data;
Node* left;
Node* right;
};
int main() {
Node* root = new Node{10, nullptr, nullptr};
root->left = new Node{5, nullptr, nullptr};
root->right = new Node{20, nullptr, nullptr};
// 打印根节点数据
std::cout << "Root node: " << root->data << std::endl;
return 0;
}总结
- 数组 (Array)：基础的线性数据结构，适合存储固定大小的元素。
- 链表 (Linked List)：适合动态插入和删除。
- 栈 (Stack)：后进先出，适用于递归、表达式求值等问题。
- 队列 (Queue)：先进先出，适用于任务调度、缓冲区等问题。
- 堆 (Heap)：支持优先级队列的实现。
- 哈希表 (Hash Table)：高效的查找和插入操作，适用于需要快速查找的数据。
- 集合 (Set)：存储不重复元素，适用于去重、集合运算等。
- 映射 (Map)：存储键值对，适用于关联数据存储。
- 二叉树 (Binary Tree)：树形结构，广泛应用于搜索、排序等。
以上是 C++ 中常见的数据结构，结合实际应用，可以帮助你更好地处理数据并优化性能。