常见数据结构和常见算法

快来打我* 2022-08-10 10:54 190阅读 0赞

1、常见数据结构

线性：数组，链表，队列，堆栈，[块状数组（数组+链表）][Link 1]，hash表，[双端队列][Link 2]，[位图（bitmap）][bitmap]

树：[堆（大顶堆、小顶堆）][Link 3]，[trie树（字母树or字典树）][trie_or]，后缀树，[后缀树组][Link 4]，二叉排序/查找树，B+/B-，[AVL树][AVL]，[Treap][]，[红黑树][Link 5]，[splay树][splay]，[线段树][Link 6]，[树状数组][Link 7]

图：图

其它：[并查集][Link 8]

2、常见算法

（1）       基本思想：枚举，递归，分治，模拟，贪心，动态规划，剪枝，回溯

（2）       图算法：[深度优先遍历与广度优先遍历][Link 2]， 最短路径，最小生成树，拓扑排序

（3）       字符串算法：字符串查找，hash算法，KMP算法

（4）       [排序算法：冒泡，插入，选择，快排，归并排序，堆排序，桶排序][Link 9]

（5）       动态规划：[背包问题][Link 10]，最长公共子序列，最优二分检索树

（6）       数论问题：[素数问题][Link 11]，整数问题，进制转换，同余模运算，

（7）       排列组合：[排列和组合算法][Link 12]

（8）       其它：[LCA与RMQ问题][LCA_RMQ]

不断添加中……

[Link 1]: http://dongxicheng.org/structure/blocklink/
[Link 2]: http://dongxicheng.org/structure/basic-graph-search/
[bitmap]: http://dongxicheng.org/structure/bitmap/
[Link 3]: http://dongxicheng.org/structure/heap/
[trie_or]: http://dongxicheng.org/structure/trietree/
[Link 4]: http://dongxicheng.org/structure/suffix-array/
[AVL]: http://dongxicheng.org/structure/avl/
[Treap]: http://dongxicheng.org/structure/treap/
[Link 5]: http://dongxicheng.org/structure/red-black-tree/
[splay]: http://dongxicheng.org/structure/splay-tree/
[Link 6]: http://dongxicheng.org/structure/segment-tree/
[Link 7]: http://dongxicheng.org/structure/binary_indexed_tree/
[Link 8]: http://dongxicheng.org/structure/union-find-set/
[Link 9]: http://dongxicheng.org/structure/sort/
[Link 10]: http://dongxicheng.org/structure/knapsack-problems/
[Link 11]: http://dongxicheng.org/structure/prime/
[Link 12]: http://dongxicheng.org/structure/permutation-combination/
[LCA_RMQ]: http://dongxicheng.org/structure/lca-rmq/