数据结构与算法分析

1.1　数据结构讨论的范畴 1

第1章　绪论 1

1.2　基本概念及术语 2

1.2.1　数据 2

1.2.2　数据元素 3

1.2.3　数据对象 3

1.2.4　数据结构 3

1.2.5　数据类型 4

1.2.6　抽象数据类型 4

1.3.1 C++的简单程序 5

1.3　抽象数据类型的实现 5

1.3.2 C++作用域的说明 6

1.3.3 C++的类和对象 6

1.3.4 C++的参数传递 8

1.3.5 C++的输入输出 10

1.3.6 C++的动态存储分配 11

1.3.7 C++的友元函数 13

1.3.8 C++的运算符重载 13

1.3.9 结构与类 15

1.3.10 C++的模板 15

1.4.1　算法 18

1.4　算法和算法分析 18

1.4.2　算法分析 19

第2章　线性表 23

2.1　线性表的逻辑结构 23

2.2　线性表的顺序存储结构 25

2.3　线性表的链式存储结构 33

2.3.1　单链表 33

2.3.2　循环链表 41

2.3.3　双向链表 45

2.3.4　保存当前位置和元素个数 48

3.1.1　栈的基本概念 61

第3章　栈和队列 61

3.1　栈 61

3.1.2　顺序栈 62

3.1.3　链式栈 67

3.1.4　栈的应用 74

3.2　队列 77

3.2.1　队列的基本概念 77

3.2.2　链式队列 79

3.2.3　循环队列——队列的顺序存储结构 82

第4章　串 88

4.1 串的定义 88

4.2.1　定长顺序存储表示 90

4.2　串的存储表示 90

4.2.2　堆分配存储表示 92

4.2.3　链表存储表示 95

4.3　串的模式匹配算法 96

4.3.1　简单算法 96

4.3.2　首尾匹配算法 98

4.3.3 KMP算法 98

第5章　数组和广义表 103

5.1　数组 103

5.1.1　数组的基本概念 103

5.1.2　数组的存储实现 104

5.2　数组的类定义 105

5.2.1　一维数组的类定义及实现 106

5.2.2　二维数组的类定义及实现 108

5.3　矩阵 111

5.3.1　矩阵的定义和操作 111

5.3.2　特殊矩阵 116

5.3.3　稀疏矩阵 120

5.4 广义表 126

5.4.1　基本概念 126

5.4.2　广义表的存储结构 128

6.1.1　树的定义 135

6.1　树的基本概念 135

第6章　树和二叉树 135

6.1.2　基本术语 136

6.2　二叉树 137

6.2.1　二叉树的定义 137

6.2.2　二叉树的性质 138

6.3　二叉树的存储结构 139

6.3.1　顺序存储结构 140

6.3.2　链式存储结构 141

6.4　二叉树遍历 145

6.4.1　遍历的定义 145

6.4.2　遍历算法 146

6.4.3　二叉树遍历的应用 151

6.5　线索化二叉树 153

6.5.1　线索化的概念 153

6.5.2　线索化算法 156

6.5.3　遍历线索化二叉树 157

6.6　树和森林 159

6.6.1　树的存储表示 159

6.6.2　树和森林的遍历 161

6.6.3　树和森林与二叉树的转换 163

6.7　哈夫曼树与哈夫曼编码 164

6.7.1　哈夫曼树的基本概念 164

6.7.2　哈夫曼树构造算法 165

6.7.3　哈夫曼编码 168

6.8　树的计数 170

第7章　图 175

7.1　图的定义和术语 175

7.2　图的存储表示 179

7.2.1　邻接矩阵 179

7.2.2　邻接表 185

7.3　图的遍历 193

7.3.1　深度优先搜索 194

7.3.2 广度优先搜索 195

7.4.1 Prim算法 197

7.4　图的最小代价生成树 197

7.4.2 Kruskal算法 200

7.5　有向无环图及应用 203

7.5.1　拓扑排序 204

7.5.2　关键路径 206

7.6　最短路径 211

7.6.1　单源点最短路径问题 211

7.6.2　所有顶点之间的最短路径 214

第8章　查找 219

8.1　查找的基本概念 219

8.2.1　顺序查找 220

8.2　静态表的查找 220

8.2.2　有序表的查找 221

8.2.3　分块查找 224

8.3　动态查找表 225

8.3.1　二叉排序树 225

8.3.2　二叉平衡树 233

8.3.3 B树和B+树 252

8.4　散列表 254

8.4.1　散列表的概念 254

8.4.2　构造散列函数的方法 254

8.4.3　处理冲突的方法 255

8.4.4　散列表的实现 256

8.4.5　散列法性能分析 261

第9章　排序 263

9.1　概述 263

9.2　插入排序 264

9.3　希尔排序 266

9.4　交换排序 268

9.4.1　起泡排序 268

9.4.2　快速排序 269

9.5　选择排序 272

9.5.1　简单选择排序 272

9.5.2　堆排序 273

9.6　归并排序 277

9.7　基数排序 279

9.7.1　多关键排序 280

9.7.2　基数排序 280

9.8　外部排序 283

9.8.1　外部排序基础 283

9.8.2　外部排序的方法 283

第10章　文件 287

10.1　主存储器和辅助存储器 287

10.2　磁盘 288

10.2.1　磁盘结构 288

10.2.2　磁盘访问代价分析 292

10.2.3　磁盘缓存 293

10.3　文件结构 295

10.3.1　顺序文件 295

10.3.2　索引文件 297

10.3.3 ISAM文件和VSAM文件 298

10.3.4　散列文件 301

10.3.5　多关键字文件 302

第11章　算法设计技术 305

11.1　算法设计 305

11.2.1　算法思想 308

11.2.2　应用 308

11.2　贪心算法 308

11.3　分治算法 311

11.3.1　算法思想 311

11.3.2　应用 311

11.4　回溯算法 315

11.4.1　算法思想 315

11.4.2　应用 315

11.5　分支定界 318

11.5.1　算法思想 318

11.5.2　应用 318

11.6.2　应用 322

11.6.1　算法思想 322

11.6　动态规划 322

第12章　分析技术与可计算问题 325

12.1　分析技术 325

12.1.1　求和分析 325

12.1.2　递归分析 326

12.1.3　均摊分析 328

12.1.4　算法分析举例 329

12.2　可计算问题 332

12.2.1　归约 332

12.2.2　难解问题 334

12.2.3　不可解问题 338