算法与数据结构 C++版PDF|Epub|txt|kindle电子书版本网盘下载

算法与数据结构 C++版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 绪论1

1.1利用计算机解决问题的几个步骤1

1.2基本概念和术语2

1.3算法及其复杂度分析4

1.4算法的描述语言5

第2章 算法分析技术7

2.1无穷大的阶7

2.2若干序列和函数的渐进性质8

2.2.1调和级数8

2.2.2 Fibonacci序列8

2.2.3 log2函数9

2.2.4基本定理9

2.2.5 Catalan数10

2.2.6一个特别序列11

2.3算法的时间复杂度11

2.4算法的空间复杂度13

2.5冒泡排序算法复杂度分析13

2.6分摊复杂度分析14

2.6.1累计法15

2.6.2势函数法16

2.6.3捐款记账法17

习题17

第3章 线性表21

3.1顺序线性表：向量21

3.1.1 Vector类模板的成员变量21

3.1.2向量的迭代子22

3.1.3获取向量的成员22

3.1.4向量元素的删除22

3.1.5向量的存储管理22

3.1.6添加函数23

3.1.7完整的Vector类23

3.2单链表25

3.2.1单链表迭代子类26

3.2.2添加和删除操作26

3.3其他形式的单链表27

3.4双链表27

3.5静态链表29

3.6动态内存管理31

3.7矩阵35

3.8对称矩阵36

3.9稀疏矩阵36

习题39

第4章 栈与队列40

4.1栈的定义与实现40

4.2栈与函数调用41

4.2.1 函数调用框架42

4.2.2汉诺塔问题43

4.2.3间接递归调用44

4.3广义栈44

4.4回溯法45

4.4.1八皇后问题46

4.4.2八皇后问题回溯法的改进47

4.5队列48

4.5.1用链表实现队列49

4.5.2用循环数组实现队列49

4.6双端队列51

4.7基数排序51

习题53

第5章 字符串与模式匹配算法54

5.1字符集与字符54

5.2字符串54

5.3简单模式匹配算法55

5.4 KMP算法55

5.4.1 KMP算法的改进59

5.4.2 KMP类61

5.5有限状态自动机模式匹配算法62

5.5.1有限状态自动机62

5.5.2模式匹配有限状态自动机62

5.6 Boyer-Moore模式匹配算法63

5.7 BM- KMP模式匹配算法65

习题65

第6章 树与二叉树66

6.1树与森林66

6.2二叉树67

6.3二叉树的二叉链表表示71

6.4二叉树的递归遍历72

6.5二叉树的非递归遍历73

6.5.1非递归先序遍历73

6.5.2非递归中序遍历74

6.5.3非递归后序遍历74

6.5.4二叉树的构造75

6.5.5二叉树的显示76

6.6中序线索化二叉树76

6.6.1中序线索化二叉树的实现76

6.6.2遍历中序线索化二叉树77

6.7二叉树的其他存储表示77

6.7.1三叉链表表示法77

6.7.2完全二叉树表示78

6.7.3三元组表示法78

6.7.4双亲表示法78

6.7.5带右链的先根序表示法78

6.7.6双标志先根序表示法79

6.8森林与二叉树的对应80

6.9树与森林的遍历80

6.10树与森林的存储表示81

6.10.1树与森林的孩子、兄弟表示法83

6.10.2无序树的双亲表示法83

6.11并查集83

6.11.1复杂度分析85

6.11.2加权合并85

6.11.3按秩合并85

6.11.4折叠查找及其分摊复杂度分析86

6.11.5并查集的完整实现88

6.11.6迷宫设计88

6.12 Huffman树89

6.12.1无前缀编码与扩充二叉树89

6.12.2 Huffman算法89

6.12.3 Huffman压缩90

习题91

第7章 选择94

7.1用数组实现的堆94

7.1.1极大堆与极小堆94

7.1.2极大极小堆96

7.1.3双端堆100

7.1.4d叉堆101

7.1.5置换选择101

7.2用二叉树或树实现的堆103

7.2.1左堆103

7.2.2扁堆106

7.2.3二项式堆109

7.2.4 Fibonacci堆110

7.2.5配对堆116

习题119

第8章 查找122

8.1查找结构122

8.2顺序查找122

8.2.1顺序查找表类模板123

8.2.2顺序表的性能分析123

8.2.3自适应顺序查找124

8.3哈希表124

8.3.1哈希函数的设计124

8.3.2哈希表长M的选取126

8.3.3冲突处理126

8.3.4哈希表的性能分析129

8.4二分查找131

8.5跳跃表132

8.5.1随机跳跃表133

8.5.2 1-2-3跳跃表134

8.6排序二叉树135

8.6.1查找、添加和删除操作136

8.6.2排序二叉树类模板137

8.6.3查找的性能分析138

8.7 AVL树139

8.7.1 AVL树的添加139

8.7.2 AVL树的删除141

8.7.3 AVL树的实现及其复杂度141

8.8 B树142

8.8.1 B树的查找142

8.8.2 B树的添加142

8.8.3 B树的删除143

8.8.4 B树144

8.9 AA树144

8.9.1 AA树的添加145

8.9.2 AA树的实现145

8.9.3 AA树类模板147

8.10红黑树148

8.10.1红黑树的添加148

8.10.2红黑树的删除149

8.10.3自上而下的添加和删除151

8.11排序二叉堆152

8.11.1排序二叉堆的添加152

8.11.2排序二叉堆类模板153

8.12最佳排序二叉树153

8.13 Splay树155

8.13.1Splay运算156

8.13.2查找操作的分摊复杂度分析156

8.14多关键字查找158

8.14.1双链树158

8.14.2 Trie树159

8.15索引结构160

习题161

第9章 排序163

9.1插入排序164

9.1.1插入排序的实现164

9.1.2插入排序算法的复杂度分析165

9.1.3插入排序的改进165

9.2选择排序166

9.3 Shell排序166

9.4堆排序169

9.4.1极大堆及堆排序的实现169

9.4.2堆排序的性能分析170

9.5快速排序171

9.5.1快速排序的性能分析171

9.5.2快速排序的初步实现173

9.5.3快速排序的改进173

9.5.4中位数175

9.6自省排序177

9.7间接排序177

9.8归并排序179

9.8.1归并的工作量180

9.8.2归并排序及其性能分析180

9.8.3数组的归并排序及其性能分析180

9.8.4单链表的归并181

9.9基于比较的排序算法的时间复杂度下界183

9.10基数排序184

9.11外部排序185

9.11.1初始序串的生成：双堆实现185

9.11.2 K路归并的实现：败者树186

9.11.3最佳归并树187

习题188

第10章 图190

10.1图的定义及相关基本术语190

10.2图的存储与表示191

10.2.1单重图的邻接矩阵表示法191

10.2.2有向图的邻接表表示法191

10.2.3有向图的逆邻接表表示法191

10.2.4无向图的多重邻接表表示法192

10.3图的抽象界面192

10.3.1弧边的界面193

10.3.2图的构造函数193

10.3.3弧边迭代子193

10.4抽象界面的邻接矩阵实现194

10.4.1 Weight-traits类模板194

10.4.2矩阵模板195

10.4.3弧边类型的定义196

10.4.4弧边迭代子基类197

10.4.5有向图弧边迭代子基类197

10.4.6无向图弧边迭代子基类197

10.4.7无向图弧边迭代子199

10.4.8图的基类200

10.4.9有向图类模板200

10.4.10无向图类模板201

10.4.11应用例子201

10.5图的遍历及其应用202

10.5.1深度优先遍历及其应用202

10.5.2深度优先遍历的非递归程序204

10.5.3深度优先遍历的复杂度205

10.5.4 Kosaraju算法205

10.5.5 Tarjan算法206

10.5.6无向图的深度优先遍历208

10.5.7重连通图208

10.5.8宽度优先遍历及其应用210

10.6有向无圈图211

10.6.1集合上的偏序211

10.6.2拓扑排序211

10.6.3 AOE网和关键路径212

10.7最小代价生成树214

10.7.1 Kruskal算法215

10.7.2 Prim算法216

10.8最短路径问题219

10.8.1 Dijkstra算法219

10.8.2 Peter算法221

10.8.3 Bellman-Ford算法221

10.8.4 Floyd算法224

10.9最大流问题224

10.9.1广义路径法225

10.9.2预置推送法228

习题232

第11章 STL简介234

11.1迭代子234

11.1.1半开半闭区间235

11.1.2自白迭代子类236

11.2泛函240

11.2.1纯泛函241

11.2.2拟序泛函241

11.2.3自白泛函类241

11.2.4自白泛函转换模板243

11.3算法245

11.3.1几个实用的函数模板245

11.3.2日常事务类算法246

11.3.3查找类算法250

11.3.4排序类算法251

11.3.5工作类算法253

11.3.6已排序区间上的算法256

11.3.7有关堆的算法260

11.3.8处理未经初始化的内存260

11.4容器261

11.4.1 STL容器的共有界面261

11.4.2顺序容器262

11.4.3排序容器265

11.4.4哈希容器267

11.5适配器268

11.5.1容器适配器268

11.5.2迭代子适配器270

11.5.3泛函适配器274

11.5.4应用举例276

11.5.5后记277

第12章 C＋＋语言概要279

12.1注释279

12.2变量280

12.3引用280

12.4常量281

12.5强制类型转换282

12.6名字空间284

12.7动态内存分配287

12.8输入／输出287

12.9函数原型声明、函数名重载及默认参数288

12.10类289

12.11类模板291

12.12函数模板292

第13章 伪随机数产生与高精度计时器294

13.1线性同余方法294

13.2加法方法296

13.3抽牌技术298

13.4高精度计时器298

参考文献301

索引303