《C++中的数据结构及其相关算法》
数据结构与算法是计算机科学的基石，尤其在C++这类强调性能与底层控制的编程语言中，合理选择数据结构并实现高效算法是开发高质量软件的关键。本文将系统梳理C++中常见的数据结构（如线性结构、树形结构、图结构等）及其核心算法，结合代码示例分析其实现原理与性能优化方法。
一、线性数据结构及其算法
1. 数组与动态数组（vector）
数组是C++中最基础的数据结构，提供连续内存存储和O(1)时间复杂度的随机访问。但静态数组的大小固定，而C++标准库中的std::vector通过动态扩容机制解决了这一问题。
#include
#include
int main() {
std::vector vec = {1, 2, 3};
vec.push_back(4); // 动态扩容
std::cout 关键算法：二分查找（O(log n)）
int binarySearch(const std::vector& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left 2. 链表与双向链表（list）
链表通过指针连接节点，支持O(1)时间复杂度的插入/删除操作，但随机访问效率为O(n)。C++的std::list实现了双向链表。
#include
#include
int main() {
std::list lst = {3, 1, 4};
lst.sort(); // 链表排序（O(n log n)）
auto it = std::find(lst.begin(), lst.end(), 4);
if (it != lst.end()) lst.erase(it); // 删除元素
return 0;
}
链表反转算法：
struct ListNode {
int val;
ListNode* next;
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
while (head) {
ListNode* next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}3. 栈与队列
栈（LIFO）和队列（FIFO）是特殊的线性结构。C++中可通过std::stack和std::queue实现。
#include
#include
int main() {
std::stack stk;
stk.push(1); stk.push(2);
std::cout q;
q.push(3); q.push(4);
std::cout 经典应用：括号匹配检测
bool isValid(const std::string& s) {
std::stack stk;
for (char c : s) {
if (c == '(') stk.push(')');
else if (c == '{') stk.push('}');
else if (c == '[') stk.push(']');
else if (stk.empty() || stk.top() != c) return false;
else stk.pop();
}
return stk.empty();
} 二、树形数据结构及其算法
1. 二叉树与二叉搜索树（BST）
二叉树每个节点最多有两个子节点。BST满足左子树值小于根节点、右子树值大于根节点的性质。
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
// BST插入操作
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode{val};
if (val val) root->left = insertIntoBST(root->left, val);
else root->right = insertIntoBST(root->right, val);
return root;
}中序遍历（升序输出）：
void inorderTraversal(TreeNode* root) {
if (!root) return;
inorderTraversal(root->left);
std::cout val right);
}2. 平衡二叉搜索树（AVL/红黑树）
普通BST在最坏情况下可能退化为链表。AVL树通过旋转操作维持平衡（高度差≤1），C++的std::map和std::set基于红黑树实现。
#include 3. 堆与优先队列
堆是完全二叉树，分为最大堆和最小堆。C++的std::priority_queue默认实现最大堆。
#include
int main() {
std::priority_queue max_heap;
max_heap.push(3); max_heap.push(1); max_heap.push(4);
std::cout , std::greater> min_heap;
min_heap.push(3); min_heap.push(1);
std::cout 堆排序算法（O(n log n)）：
void heapSort(std::vector& arr) {
std::make_heap(arr.begin(), arr.end());
std::sort_heap(arr.begin(), arr.end());
} 三、图数据结构及其算法
1. 图的表示方法
邻接矩阵（适合稠密图）和邻接表（适合稀疏图）是两种主流表示方式。
#include
#include
// 邻接表表示
std::unordered_map> graph = {
{0, {1, 2}},
{1, {2}},
{2, {0, 3}},
{3, {3}}
}; 2. 深度优先搜索（DFS）与广度优先搜索（BFS）
DFS使用栈（递归或显式栈），BFS使用队列。
// DFS递归实现
void dfs(const std::unordered_map>& graph,
int node, std::unordered_set& visited) {
visited.insert(node);
std::cout >& graph, int start) {
std::queue q;
std::unordered_set visited;
q.push(start);
visited.insert(start);
while (!q.empty()) {
int node = q.front(); q.pop();
std::cout 3. 最短路径算法
Dijkstra算法解决带权图单源最短路径问题（非负权重），使用优先队列优化。
#include
#include
struct Edge {
int to;
int weight;
};
std::vector dijkstra(const std::vector<:vector>>& graph, int start) {
int n = graph.size();
std::vector dist(n, INT_MAX);
dist[start] = 0;
std::priority_queue<:pair int>,
std::vector<:pair int>>,
std::greater<:pair int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
int current_dist = pq.top().first;
pq.pop();
if (current_dist > dist[u]) continue;
for (const Edge& edge : graph[u]) {
int v = edge.to;
int new_dist = dist[u] + edge.weight;
if (new_dist 四、哈希表与字符串算法
哈希表通过键值对存储数据，C++的std::unordered_map和std::unordered_set基于哈希表实现。
#include
int main() {
std::unordered_map<:string int> wordCount = {
{"hello", 1},
{"world", 2}
};
wordCount["cpp"]++; // 插入或更新
for (const auto& pair : wordCount) {
std::cout 字符串匹配算法（KMP）：
std::vector computeLPS(const std::string& pattern) {
int n = pattern.size();
std::vector lps(n, 0);
int len = 0, i = 1;
while (i lps = computeLPS(pattern);
int i = 0, j = 0;
while (i 五、高级数据结构与算法
1. 并查集（Disjoint Set Union）
用于处理不相交集合的合并与查询问题，路径压缩优化可降低时间复杂度。
class DSU {
std::vector parent;
public:
DSU(int n) : parent(n) {
for (int i = 0; i 2. 字典树（Trie）
用于高效存储和检索字符串集合，每个节点代表一个字符。
class TrieNode {
public:
std::unordered_map children;
bool isEnd;
TrieNode() : isEnd(false) {}
};
class Trie {
TrieNode* root;
public:
Trie() { root = new TrieNode(); }
void insert(const std::string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->isEnd = true;
}
bool search(const std::string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) return false;
node = node->children[c];
}
return node->isEnd;
}
}; 六、性能优化与STL应用
C++标准模板库（STL）提供了丰富的数据结构与算法实现。选择容器时应考虑：
-
std::vector：随机访问频繁时优先选择 -
std::list：频繁插入/删除时使用 -
std::deque：双端操作需求时 -
std::unordered_map：哈希表实现，平均O(1)时间复杂度 -
std::map：红黑树实现，自动排序
算法复杂度分析示例：
// O(n)复杂度的查找
template
int linearSearch(const std::vector& arr, const T& target) {
for (int i = 0; i 结语
本文系统梳理了C++中核心数据结构及其算法实现，从基础线性结构到复杂图算法均有涉及。实际应用中需根据具体场景（如数据规模、操作频率、内存限制等）选择合适的数据结构，并结合STL容器与算法库提升开发效率。理解底层原理有助于编写出更高效、更健壮的C++程序。
关键词：C++、数据结构、算法、数组、链表、树、图、哈希表、STL、复杂度分析
简介：本文详细阐述C++中常见数据结构（数组、链表、树、图、哈希表等）的实现原理与核心算法（排序、搜索、最短路径等），结合代码示例分析性能优化方法，并总结STL容器的选择策略与复杂度分析技巧。
