c++常用算法模板库.doc

常用算法模板库(C++)

1 排序算法.................................................................................................................................................3

1.1 冒泡排序..........................................................................................................................................3

1.2 选择排序..........................................................................................................................................4

1.3 插入排序..........................................................................................................................................5

1.4 快速排序..........................................................................................................................................6

1.5 哈希排序..........................................................................................................................................8

2 数学问题.................................................................................................................................................9

2.3.2

组合数

.....................................................................................................................................11

2.3.3

全排列算法

............................................................................................................................12

2.3.4

从

n

个数中选

2.4 进制转换........................................................................................................................................14

2.4.1

十进制转

2.4.2 N

.....................................................................................................................15

3 查找.......................................................................................................................................................16

3.1 二分查找........................................................................................................................................16

4 栈...........................................................................................................................................................17

4.1 栈的定义........................................................................................................................................17

6.1.2

比较大小（字典顺序）

........................................................................................................25

6.2 模式匹配........................................................................................................................................26

6.2.1

一般匹配算法

........................................................................................................................26

6.2.2 KMP

算法

...............................................................................................................................27

7 树...........................................................................................................................................................28

7.1 二叉树的定义................................................................................................................................28

7.2 根据先序序列和中序序列建立二叉树........................................................................................32

7.3 二叉排序树....................................................................................................................................33

7.4 建立哈夫曼树................................................................................................................................34

8.1 图的定义........................................................................................................................................40

8.2 图的最短路径................................................................................................................................44

8.2.1 Dijkstra

算法

..........................................................................................................................44

8.2.2 Floyd

算法

..............................................................................................................................45

8.5 关键路径........................................................................................................................................49

9 高精度计算...........................................................................................................................................51

9.2 减法................................................................................................................................................52

9.3 乘法................................................................................................................................................53

1 排序算法

1.1 冒泡排序

1.2 选择排序

1.3 插入排序