数据结构和算法是计算机科学中非常重要的概念。它们的应用范围涉及到了各种各样的问题解决方案，从字符串处理到图形算法。在C++中，有许多内置的数据结构和算法，同时也有很多第三方库可以用于更高级的应用。
在这篇博客中，我们将介绍一些常用的数据结构和算法，并提供一些实用的指南和示例。
数据结构
数组（Array）
数组是存储固定大小元素的线性数据结构。它可以通过索引访问其中的元素，索引从0开始。在C++中，有很多方式来定义和操作数组。
int arr[5]; // 声明一个包含5个整数的数组
arr[0] = 1; // 赋值给第一个元素
int length = sizeof(arr) / sizeof(arr[0]); // 获取数组的长度
链表（Linked List）
链表是一个逐个节点连接的数据结构。每个节点都包含一个值和一个指向下一个节点的指针。在C++中，我们可以自己实现链表，也可以使用标准库中的std::list。
struct Node {
int value;
Node* next;
};
Node* head = nullptr; // 头节点为空
Node* newNode = new Node(); // 创建一个新节点
newNode->value = 1;
newNode->next = nullptr;
head = newNode; // 将新节点设置为头节点
栈（Stack）
栈是一种遵循后进先出（LIFO）原则的数据结构。在C++中，可以使用std::stack来实现栈。
std::stack<int> stack;
stack.push(1); // 入栈操作
int top = stack.top(); // 获取栈顶元素
stack.pop(); // 出栈操作
队列（Queue）
队列是一种遵循先进先出（FIFO）原则的数据结构。在C++中，可以使用std::queue来实现队列。
std::queue<int> queue;
queue.push(1); // 入队操作
int front = queue.front(); // 获取队头元素
queue.pop(); // 出队操作
哈希表（Hash Table）
哈希表是一种使用哈希函数将键映射到值的数据结构。C++中可以使用std::unordered_map来实现哈希表。
std::unordered_map<std::string, int> hashMap;
hashMap["apple"] = 1;
hashMap["banana"] = 2;
int value = hashMap["apple"]; // 获取键"apple"对应的值
图（Graph）
图是一种由节点和边组成的非线性数据结构。C++中可以使用邻接矩阵或邻接表来表示图，也可以使用第三方库，如Boost库。
struct Graph {
int V; // 图中节点的数量
std::vector<int>* adj; // 邻接表
};
Graph* createGraph(int V) {
Graph* graph = new Graph();
graph->V = V;
graph->adj = new std::vector<int>[V];
return graph;
}
void addEdge(Graph* graph, int src, int dest) {
graph->adj[src].push_back(dest);
graph->adj[dest].push_back(src);
}
算法
二分查找（Binary Search）
二分查找是一种高效的查找有序数组中元素的算法。它通过将目标值与数组的中间元素进行比较，以不断缩小查找范围。
int binarySearch(int arr[], int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 目标值不存在
}
快速排序（Quick Sort）
快速排序是一种常用的排序算法，它通过选择一个基准值将数组分成两部分，之后递归地对两个子数组进行排序。
void quickSort(int arr[], int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right); // 选择一个基准值
quickSort(arr, left, pivot - 1); // 对左边子数组进行排序
quickSort(arr, pivot + 1, right); // 对右边子数组进行排序
}
}
int partition(int arr[], int left, int right) {
int pivot = arr[right]; // 选择最右边的元素作为基准值
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[right]);
return i + 1;
}
广度优先搜索（BFS）
广度优先搜索是一种用于图和树的遍历算法。它从起始节点开始，逐层遍历图中的节点，直到找到目标节点或遍历完所有节点。
void BFS(Graph* graph, int start) {
std::queue<int> queue;
std::vector<bool> visited(graph->V, false);
visited[start] = true;
queue.push(start);
while (!queue.empty()) {
int current = queue.front();
queue.pop();
std::cout << current << " ";
for (int neighbor : graph->adj[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}
}
迪杰斯特拉算法（Dijkstra's Algorithm）
迪杰斯特拉算法用于在加权图中找到从起点到目标节点的最短路径。它维护两个数据结构，一个用于存储当前节点的最短距离，另一个用于存储已经找到最短路径的节点。
void Dijkstra(Graph* graph, int start) {
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
std::vector<int> dist(graph->V, INT_MAX);
std::vector<bool> visited(graph->V, false);
dist[start] = 0;
pq.push(std::make_pair(0, start));
while (!pq.empty()) {
int current = pq.top().second;
pq.pop();
visited[current] = true;
for (int neighbor : graph->adj[current]) {
int weight = 1; // 边的权值为1
if (!visited[neighbor] && dist[current] + weight < dist[neighbor]) {
dist[neighbor] = dist[current] + weight;
pq.push(std::make_pair(dist[neighbor], neighbor));
}
}
}
}
结语
本篇博客介绍了C++中的一些常用数据结构和算法，并提供了一些实用的指南和示例。希望这些内容能够帮助你更好地理解和应用数据结构和算法。
当然，C++中还有很多其他的数据结构和算法可以探索，如AVL树、红黑树、最小生成树算法等等。学习和熟练掌握这些概念和方法对于成为一名优秀的程序员来说是非常重要的。不断学习和实践，才能在实际的编程工作中灵活运用它们。
感谢阅读！
本文来自极简博客，作者：深夜诗人，转载请注明原文链接：C++中的数据结构和算法：实用指南
