数据结构和算法：全面的算法代码库

￡神魔★判官ぃ 2022-07-13 10:21 141阅读 0赞

原文链接：[https://github.com/Dev-XYS/Algorithms][https_github.com_Dev-XYS_Algorithms]

# Algorithms #

本次README修订为算法仓库Algorithms的第100次commit，首先我们庆祝自2016年8月4日本仓库建立以来Dev-XYS在算法学习方面取得的显著进步！

这里有各种算法的C++代码，任何人可以在自己的任何程序中使用，欢迎大家指出代码中的错误以及有待改进的地方。

本仓库内所有代码的授权方式为Unlicense，大家如果使用我的代码开发自己的软件挣了大钱，或是参考我的代码在NOI中得了金牌，我都会很高兴的。使用这里的代码之后，你可以自主选择是否公开源代码。总而言之，你可以把这里的代码当作你自己写的一样，无论怎样使用都是被允许的。但是，我不对本仓库内代码的正确性负责。大家要是使用我的代码开发软件而导致程序崩溃，或是参考我的代码在考试时出错，请不要向我抱怨。如果你愿意，遇到问题可以在Issues中提出来，我们共同解决。我们不赞成Pull Request，因为本仓库主要储存作者已经学习的算法，全部代码均由作者本人负责维护与更新。

以下索引提供了本仓库内算法的中文名，方便大家查找。更新可能有很长时间的延迟，不保证所有算法的名称都在列表中出现。

## Index ##

<table> 
 <thead> 
  <tr> 
   <th>Contents</th> 
   <th>FileName</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>AC自动机</td> 
   <td>Aho-Corasick-Automation</td> 
  </tr> 
  <tr> 
   <td>单源最短路径（SPFA）</td> 
   <td>Bellman-Ford(Queue-Optimised)</td> 
  </tr> 
  <tr> 
   <td>单源最短路径（Bellman-Ford）</td> 
   <td>Bellman-Ford</td> 
  </tr> 
  <tr> 
   <td>使用Edmonds-Karp进行二分图匹配</td> 
   <td>Bigrpah-Matching(Edmonds-Karp)</td> 
  </tr> 
  <tr> 
   <td>普通的二叉搜索树</td> 
   <td>Binary-Search-Tree</td> 
  </tr> 
  <tr> 
   <td>广度优先搜索</td> 
   <td>Breadth-First-Search</td> 
  </tr> 
  <tr> 
   <td>冒泡排序</td> 
   <td>Bubble-Sort</td> 
  </tr> 
  <tr> 
   <td>桶排序</td> 
   <td>Bucket-Sort</td> 
  </tr> 
  <tr> 
   <td>组合数的递推求解</td> 
   <td>Combination(Recursion)</td> 
  </tr> 
  <tr> 
   <td>枚举组合</td> 
   <td>Combination</td> 
  </tr> 
  <tr> 
   <td>基本的复数类</td> 
   <td>Complex-Number</td> 
  </tr> 
  <tr> 
   <td>割点</td> 
   <td>Cut-Vertex</td> 
  </tr> 
  <tr> 
   <td>深度优先搜索</td> 
   <td>Depth-First-Search</td> 
  </tr> 
  <tr> 
   <td>堆优化的Dijkstra算法</td> 
   <td>Dijkstra(Heap-Optimised)</td> 
  </tr> 
  <tr> 
   <td>并查集</td> 
   <td>Disjoint-Set-Union</td> 
  </tr> 
  <tr> 
   <td>最大流Edmonds-Karp算法</td> 
   <td>Edmonds-Karp</td> 
  </tr> 
  <tr> 
   <td>欧拉函数</td> 
   <td>Euler’s-Totient-Function</td> 
  </tr> 
  <tr> 
   <td>有向图的欧拉回路</td> 
   <td>Eulerian-Tour(Digraph)</td> 
  </tr> 
  <tr> 
   <td>拓展欧几里得算法</td> 
   <td>Extended-Euclid</td> 
  </tr> 
  <tr> 
   <td>简单的快速幂</td> 
   <td>Fast-Exponentiation</td> 
  </tr> 
  <tr> 
   <td>树状数组</td> 
   <td>Fenwick-Tree</td> 
  </tr> 
  <tr> 
   <td>所有结点对之间的最短路径（Floyd）</td> 
   <td>Floyd-Warshall</td> 
  </tr> 
  <tr> 
   <td>凸包算法（Graham扫描法）</td> 
   <td>Graham-Scan</td> 
  </tr> 
  <tr> 
   <td>辗转相除法求最大公约数</td> 
   <td>Greatest-Common-Divisor</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>Heap-Sort</td> 
  </tr> 
  <tr> 
   <td>ISAP算法</td> 
   <td>Improved-Shortest-Augmenting-Path(Naive)</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>Insertion-Sort</td> 
  </tr> 
  <tr> 
   <td>字符串匹配（KMP）</td> 
   <td>Knuth-Morris-Pratt</td> 
  </tr> 
  <tr> 
   <td>最小生成树（Kruskal）</td> 
   <td>Kruskal</td> 
  </tr> 
  <tr> 
   <td>最近公共祖先（Tarjan）</td> 
   <td>Least-Common-Ancestor(Tarjan)</td> 
  </tr> 
  <tr> 
   <td>使用后缀数组求解最长公共子串</td> 
   <td>Longest-Common-Substring</td> 
  </tr> 
  <tr> 
   <td>最长上升子序列（n·log(n)）</td> 
   <td>Longest-Increasing-Subsequence(n·log(n))</td> 
  </tr> 
  <tr> 
   <td>倍增法求最近公共祖先</td> 
   <td>Lowest-Common-Ancestor(Doubling)</td> 
  </tr> 
  <tr> 
   <td>朴素的矩阵乘法</td> 
   <td>Matrix-Multiplication(Naive)</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>Merge-Sort</td> 
  </tr> 
  <tr> 
   <td>最小堆</td> 
   <td>Min-Heap</td> 
  </tr> 
  <tr> 
   <td>乘法逆元</td> 
   <td>Modular-Multiplicative-Inverse</td> 
  </tr> 
  <tr> 
   <td>仅支持单点修改的可持久化线段树(维护区间和值）</td> 
   <td>Persistent-Segment-Tree(Sum)</td> 
  </tr> 
  <tr> 
   <td>试除法素数测试</td> 
   <td>Prime-Check(Naive)</td> 
  </tr> 
  <tr> 
   <td>线性的素数筛法</td> 
   <td>Prime-Sieve(Linear)</td> 
  </tr> 
  <tr> 
   <td>队列的基本操作</td> 
   <td>Queue</td> 
  </tr> 
  <tr> 
   <td>快速排序的优化版本</td> 
   <td>Quick-Sort(Extra-Optimised)</td> 
  </tr> 
  <tr> 
   <td>快速排序的随机化版本</td> 
   <td>Quick-Sort(Randomized)</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>Quick-Sort</td> 
  </tr> 
  <tr> 
   <td>使用向量叉积判断两个有向线段的时针关系</td> 
   <td>Segment-Direction</td> 
  </tr> 
  <tr> 
   <td>线段树维护区间最大值</td> 
   <td>Segment-Tree(Maximum)</td> 
  </tr> 
  <tr> 
   <td>线段树维护区间最小值</td> 
   <td>Segment-Tree(Minimum)</td> 
  </tr> 
  <tr> 
   <td>线段树维护区间和值</td> 
   <td>Segment-Tree(Sum)</td> 
  </tr> 
  <tr> 
   <td>普通的选择算法</td> 
   <td>Selection</td> 
  </tr> 
  <tr> 
   <td>Eratosthenes素数筛法</td> 
   <td>Sieve-of-Erotosthenes</td> 
  </tr> 
  <tr> 
   <td>指针版的单向链表</td> 
   <td>Singly-Linked-List(Pointer)</td> 
  </tr> 
  <tr> 
   <td>跳表</td> 
   <td>Skip-List</td> 
  </tr> 
  <tr> 
   <td>ST表</td> 
   <td>Sparse-Table</td> 
  </tr> 
  <tr> 
   <td>伸展树</td> 
   <td>Splay</td> 
  </tr> 
  <tr> 
   <td>博弈论SG函数</td> 
   <td>Sprague-Grundy</td> 
  </tr> 
  <tr> 
   <td>栈的基本操作</td> 
   <td>Stack</td> 
  </tr> 
  <tr> 
   <td>递推法求解无符号第一类斯特林数</td> 
   <td>Stirling-Number(Cycle,Unsigned,Recursion)</td> 
  </tr> 
  <tr> 
   <td>递推法求解第二类斯特林数</td> 
   <td>Stirling-Number(Subset,Recursion)</td> 
  </tr> 
  <tr> 
   <td>倍增法求解后缀数组</td> 
   <td>Suffix-Array(Doubling)</td> 
  </tr> 
  <tr> 
   <td>倍增法求解后缀数组（附带Height数组）</td> 
   <td>Suffix-Array-with-Height(Doubling)</td> 
  </tr> 
  <tr> 
   <td>使用Tarjan算法求解强连通分量</td> 
   <td>Tarjan(Strongly-Connected-Components)</td> 
  </tr> 
  <tr> 
   <td>数组版的字典树</td> 
   <td>Trie(Array)</td> 
  </tr> 
  <tr> 
   <td>指针版的字典树</td> 
   <td>Trie(Pointer)</td> 
  </tr> 
 </tbody> 
</table>

[https_github.com_Dev-XYS_Algorithms]: https://github.com/Dev-XYS/Algorithms