C++ Algorithms：高效算法实现与实用示例

icy 昨天 12 抢沙发

默认

摘要： C++ Algorithms：高效算法实现与实用示例项目概述 C++ Algorithms 是一个由 xtaci 维护的开源项目，致力于提供高质量、高效率的 C++ 算法实现。该...

C++ Algorithms：高效算法实现与实用示例

项目概述

C++ Algorithms 是一个由 xtaci 维护的开源项目，致力于提供高质量、高效率的 C++ 算法实现。该项目包含了从基础数据结构到复杂算法的完整实现，是学习和应用 C++ 算法的绝佳资源库。

项目特点

1. 全面的算法覆盖

项目涵盖了排序、搜索、图论、动态规划、字符串处理等多个领域的经典算法，每个实现都经过精心优化。

2. 清晰的代码结构

每个算法都有独立的实现文件，代码结构清晰，注释详细，便于理解和学习。

3. 实际应用导向

算法实现注重实际应用场景，提供了丰富的使用示例和测试用例。

核心算法实现示例

1. 排序算法

text

// 快速排序实现示例
template<typename T>
void quick_sort(T arr[], int left, int right) {
    if (left >= right) return;
    
    int i = left, j = right;
    T pivot = arr[(left + right) / 2];
    
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            std::swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    
    quick_sort(arr, left, j);
    quick_sort(arr, i, right);
}

2. 图算法 - Dijkstra 最短路径

text

// Dijkstra 算法实现
vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    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[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    
    return dist;
}

3. 动态规划 - 最长公共子序列

text

// LCS 动态规划实现
string longest_common_subsequence(const string& s1, const string& s2) {
    int m = s1.length(), n = s2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 构建 DP 表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    // 回溯构建 LCS
    string lcs;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1[i-1] == s2[j-1]) {
            lcs = s1[i-1] + lcs;
            i--;
            j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    
    return lcs;
}

实用示例：解决实际问题

示例1：使用并查集解决连通性问题

text

class UnionFind {
private:
    vector<int> parent, rank;
    
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            // 按秩合并
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

示例2：使用 KMP 算法进行字符串匹配

text

vector<int> kmp_search(const string& text, const string& pattern) {
    vector<int> result;
    if (pattern.empty()) return result;
    
    // 构建部分匹配表
    vector<int> lps(pattern.length(), 0);
    int length = 0;
    for (int i = 1; i < pattern.length();) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    // 执行搜索
    int i = 0, j = 0;
    while (i < text.length()) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        
        if (j == pattern.length()) {
            result.push_back(i - j);
            j = lps[j - 1];
        } else if (i < text.length() && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return result;
}