1
常用算法模板库(C++)
目录............................................................................................................................................................1
1 排序算法 ...............................................................................................................................................3
1.1 冒泡排序.........................................................................................................................................3
1.2 选择排序.........................................................................................................................................4
1.3 插入排序.........................................................................................................................................5
1.4 快速排序.........................................................................................................................................6
1.5 哈希排序.........................................................................................................................................8
2 数学问题 ...............................................................................................................................................8
2.1 求最大公约数最小公倍数.............................................................................................................8
2.2 求素数.............................................................................................................................................9
2.2.1
穷举法
.....................................................................................................................................9
2.2.2
筛法
........................................................................................................................................10
2.3 排列组合.......................................................................................................................................10
2.3.1
排列数
...................................................................................................................................10
2.3.2
组合数
...................................................................................................................................11
2.3.3
全排列算法
...........................................................................................................................12
2.3.4
从
n
个数中选
m
个的组合
..................................................................................................13
2.4 进制转换.......................................................................................................................................14
2.4.1
十进制转
N
进制
..................................................................................................................14
2.4.2 N
进制转十进制
....................................................................................................................14
3 查找......................................................................................................................................................15
3.1 二分查找.......................................................................................................................................15
4 栈..........................................................................................................................................................16
4.1 栈的定义.......................................................................................................................................16
4.2 表达式求值...................................................................................................................................19
5 队列......................................................................................................................................................21
5.1 队列的定义...................................................................................................................................21
6 串..........................................................................................................................................................24
6.1 基本操作.......................................................................................................................................24
6.1.1
赋值
.......................................................................................................................................24
6.1.2
比较大小(字典顺序)
.......................................................................................................24
6.2 模式匹配.......................................................................................................................................25
6.2.1
一般匹配算法
.......................................................................................................................25
6.2.2 KMP
算法
...............................................................................................................................26
7 树..........................................................................................................................................................27
7.1 二叉树的定义...............................................................................................................................27