C++算法实例精讲
C++算法实例
以下是一些难度中等的C++算法实例，涵盖常见数据结构、经典算法及实际问题解决场景，每个示例均附简要说明。
二分查找
int binarySearch(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) return mid;else if (nums[mid] < target) left = mid + 1;else right = mid - 1;}return -1;
}
在有序数组中高效查找目标值，时间复杂度为O(log n)。
快速排序
void quickSort(vector<int>& arr, int low, int high) {if (low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}
}int partition(vector<int>& arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) swap(arr[++i], arr[j]);}swap(arr[i + 1], arr[high]);return i + 1;
}
分治思想实现排序，平均时间复杂度O(n log n)。
链表反转
ListNode* reverseList(ListNode* head) {ListNode *prev = nullptr, *curr = head;while (curr) {ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;
}
通过迭代修改指针方向实现链表反转。
动态规划：斐波那契数列
int fib(int n) {if (n <= 1) return n;vector<int> dp(n + 1);dp[0] = 0; dp[1] = 1;for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];return dp[n];
}
使用动态规划避免递归的重复计算。
Dijkstra最短路径算法
void dijkstra(vector<vector<pair<int, int>>>& graph, int start) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;vector<int> dist(graph.size(), INT_MAX);dist[start] = 0;pq.emplace(0, start);while (!pq.empty()) {auto [d, u] = pq.top(); pq.pop();if (d > dist[u]) continue;for (auto& [v, w] : graph[u]) {if (dist[v] > dist[u] + w) {dist[v] = dist[u] + w;pq.emplace(dist[v], v);}}}
}
基于优先队列实现带权图单源最短路径查找。
二叉树层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;queue<TreeNode*> q;if (root) q.push(root);while (!q.empty()) {int size = q.size();vector<int> level;while (size--) {auto node = q.front(); q.pop();level.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}res.push_back(level);}return res;
}
使用队列实现二叉树的广度优先遍历。
检测有向无环图依赖关系的C++实现
检测有向无环图依赖关系的C++实现
检测有向无环图（DAG）依赖关系的常见方法是拓扑排序。以下是一个完整的C++实现示例，包含图的构建、拓扑排序和依赖关系检测。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;class Graph {int V;vector<vector<int>> adj;public:Graph(int V) : V(V), adj(V) {}void addEdge(int u, int v) {adj[u].push_back(v);}vector<int> topologicalSort() {vector<int> inDegree(V, 0);for (int u = 0; u < V; ++u) {for (int v : adj[u]) {inDegree[v]++;}}queue<int> q;for (int u = 0; u < V; ++u) {if (inDegree[u] == 0) {q.push(u);}}vector<int> result;while (!q.empty()) {int u = q.front();q.pop();result.push_back(u);for (int v : adj[u]) {if (--inDegree[v] == 0) {q.push(v);}}}if (result.size() != V) {return {}; // 存在环}return result;}bool hasCycle() {return topologicalSort().empty();}void printDependencies() {auto order = topologicalSort();if (order.empty()) {cout << "Graph contains a cycle!" << endl;return;}cout << "Dependency order: ";for (int u : order) {cout << u << " ";}cout << endl;cout << "Detailed dependencies:" << endl;for (int u : order) {if (!adj[u].empty()) {cout << u << " depends on: ";for (int v : adj[u]) {cout << v << " ";}cout << endl;}}}
};
DAG依赖关系测试用例
以下是30个不同结构的DAG测试用例，可用于验证上述实现：
- 简单线性依赖
Graph g1(3);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.printDependencies();
- 多分支无交叉
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(0, 2);
g2.addEdge(1, 3);
g2.printDependencies();
- 多分支有交叉
Graph g3(5);
g3.addEdge(0, 1);
g3.addEdge(0, 2);
g3.addEdge(1, 3);
g3.addEdge(2, 3);
g3.addEdge(3, 4);
g3.printDependencies();
- 多入口点
Graph g4(6);
g4.addEdge(0, 2);
g4.addEdge(1, 2);
g4.addEdge(2, 3);
g4.addEdge(3, 4);
g4.addEdge(3, 5);
g4.printDependencies();
- 复杂依赖网
Graph g5(7);
g5.addEdge(0, 1);
g5.addEdge(0, 2);
g5.addEdge(1, 3);
g5.addEdge(2, 3);
g5.addEdge(3, 4);
g5.addEdge(3, 5);
g5.addEdge(4, 6);
g5.addEdge(5, 6);
g5.printDependencies();
6-30. 其他测试用例模式（可根据需要扩展）：
- 星型依赖结构
- 树形依赖结构
- 网格状依赖
- 分层依赖结构
- 随机生成的有效DAG
- 包含孤立节点的图
- 所有节点相互独立的图
- 单节点自环（应检测为环）
- 简单环（两个节点互依赖）
- 复杂环结构
环检测验证
以下是一些包含环的测试用例，用于验证环检测功能：
// 简单环
Graph cycle1(2);
cycle1.addEdge(0, 1);
cycle1.addEdge(1, 0);
cycle1.printDependencies();// 大环
Graph cycle2(5);
cycle2.addEdge(0, 1);
cycle2.addEdge(1, 2);
cycle2.addEdge(2, 3);
cycle2.addEdge(3, 4);
cycle2.addEdge(4, 0);
cycle2.printDependencies();// 局部环
Graph cycle3(6);
cycle3.addEdge(0, 1);
cycle3.addEdge(1, 2);
cycle3.addEdge(2, 3);
cycle3.addEdge(3, 1); // 形成局部环
cycle3.addEdge(2, 4);
cycle3.addEdge(4, 5);
cycle3.printDependencies();
实际应用示例
构建任务调度系统依赖关系检测：
Graph taskGraph(8);
// 任务0: 无依赖
taskGraph.addEdge(1, 0); // 任务1依赖任务0
taskGraph.addEdge(2, 0);
taskGraph.addEdge(3, 1);
taskGraph.addEdge(3, 2);
taskGraph.addEdge(4, 3);
taskGraph.addEdge(5, 3);
taskGraph.addEdge(6, 4);
taskGraph.addEdge(6, 5);
taskGraph.addEdge(7, 6);
taskGraph.printDependencies();
性能优化建议
对于大规模图，可以考虑以下优化：
- 使用邻接表存储图结构
- 实现并行拓扑排序算法
- 使用更高效的数据结构如Fibonacci堆
- 对静态图进行预处理
可视化建议
为了更好地理解依赖关系，可以：
- 将拓扑排序结果图形化展示
- 使用Graphviz生成DOT格式的依赖图
- 实现不同颜色标记关键路径
- 高亮显示循环依赖（如果存在）
以上实现和测试用例涵盖了DAG依赖关系检测的主要场景，可根据具体需求进行调整和扩展。
KMP算法
KMP算法简介
KMP算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，通过预处理模式串生成部分匹配表（next数组），避免主串回溯，将时间复杂度优化至O(n+m)。
核心实现步骤
1. 构建next数组
next数组记录模式串前缀与后缀的最长公共长度，用于匹配失败时快速跳转。
vector<int> buildNext(const string& pattern) {vector<int> next(pattern.size(), 0);int j = 0;for (int i = 1; i < pattern.size(); ) {if (pattern[i] == pattern[j]) {next[i++] = ++j;} else {if (j != 0) j = next[j-1];else next[i++] = 0;}}return next;
}
2. 匹配过程
利用next数组跳过不必要的比较：
int kmpSearch(const string& text, const string& pattern) {vector<int> next = buildNext(pattern);int i = 0, j = 0;while (i < text.size() && j < pattern.size()) {if (text[i] == pattern[j]) {