数据结构 使用C++标准模板库 STLPDF电子书下载

出版说明 1

前言 1

第1章 概论 1

1.1 数据类型和抽象数据类型 1

目录 1

1.2 用类实现抽象数据类型 5

1.3 类关系和多态性 10

1.3.1 组合 10

1.3.2 继承 10

＊1.3.3 多态性 11

1.4.1 类模板 13

1.4 模板 13

1.4.2 函数模板 14

1.5 C＋＋标准模板库（STL）和名字空间 15

1.5.1 标准模板库 15

＊1.5.2 名字空间 15

＊1.6 异常处理 17

1.7 算法及算法分析 20

1.7.1 算法的概念 20

＊1.7.2 算法分析 21

1.8 小结 28

1.9 习题 29

1.10 上机题 31

第2章 向量、矩阵和字符串 32

2.1 向量 32

2.1.1 数组 32

2.1.2 类Vector 34

2.1.3 STL的向量容器vector 39

2.2 矩阵 50

2.2.1 矩阵类Matrix 50

2.2.2 特殊矩阵 55

2.3.1 串的概念 62

2.3 字符串 62

2.3.2 串类string 64

＊2.4 模式匹配 66

2.5 小结 71

2.6 习题 72

2.7 上机题 74

第3章 表 76

3.1 抽象数据类型表 76

3.2 表的实现 77

3.2.1 表的顺序存储 77

3.2.2 表的链接存储 78

3 3.2 双向链表 82

3.3 其他表结构 82

3.3.1 循环链表 82

3.4 表类和表迭代器类 84

3.4.1 表类和表迭代器类的定义 84

3.4.2 稀疏多项式的实现 90

3.5 STL表容器list 96

＊3.6 表的应用举例 97

3.6.1 大整数加法 97

3.6.2 稀疏矩阵的链表表示 104

3.8 习题 106

3.7 小结 106

3.9 上机题 108

第4章 栈和队列 109

4.1 抽象数据类型栈 109

4.1.1 用向量（vector）实现栈 109

4.1.2 用表（list）实现栈 113

4.2 抽象数据类型队列 118

4.2.1 用数组实现队列 119

4.2.2 用表（list）实现队列 122

4.3 双端队列（deque） 126

4.4.1 stack容器 129

4.4 STL stack容器和queue容器 129

4.4.2 queue容器 130

4.5 应用举例 130

4.5.1 算术表达式求值 130

＊4.5.2 售票窗口的模拟 139

4.6 优先队列 147

4.7 小结 149

4.8 习题 149

4.9 上机题 150

5.1 递归的概念 152

第5章 递归 152

5.2 用递归求解问题 156

＊5.3 递归过程的实现 166

5.4 广义表 175

5.4.1 广义表的概念 175

5.4.2 广义表的存储表示 177

＊5.4.3 实现广义表的算法 179

5.4.4 二元多项式的表示 185

5.5 小结 186

5.6 习题 187

5.7 上机题 189

6.1 树的概念 190

第6章 树和二叉树 190

6.2 二叉树 192

6.2.1 定义和性质 192

6.2.2 存储表示 194

6.3 二叉树的遍历 196

6.3.1 先序、中序、后序和层次遍历 196

6.3.2 二叉树计数 201

6.3.3 基于遍历的其他操作 202

6.3.4 二叉树类 206

＊6.3.5 用迭代器实现二叉树的遍历 209

6.4.1 线索二叉树的概念 216

6.4 线索二叉树 216

6.4.2 线索二叉树的遍历 220

6.5 树和森林 222

6.5.1 树和森林的二叉树表示 222

＊6.5.2 树和森林的遍历 224

＊6.5.3 树和森林的数组（或向量）表示 225

6.6 堆和优先队列 228

6.6.1 堆 228

6.6.2 优先队列的实现 236

6.7 数据压缩和哈夫曼编码 237

＊6.8 抽象数据类型并查集（Union-Find Sets）的实现 243

6.9 小结 250

6.10 习题 251

6.11 上机题 253

第7章 搜索树 254

7.1 二叉搜索树 254

7.1.1 二叉搜索树的操作 254

7.1.2 二叉搜索树类BinSearchTree 255

7.1.3 类BinSearchTree的迭代器类Iterator 259

7.1.4 二叉搜索树操作的时间分析 263

7.2 平衡的二叉搜索树（AVL树） 265

7.2.1 AVL树的插入 266

7.2.2 AVL树的删除 274

7.2.3 AVL树的高度 276

＊7.3 红黑树（RED-BLACKTREES） 278

7.3.1 红黑树的概念 278

7.3.2 红黑树的插入 280

7.3.3 红黑树的删除 287

7.4 标准模板库的关联容器 289

7.4.1 关联容器 289

7.4.2 集合（set）的运算 291

7.4.3 映射（map）的下标操作 292

7.6 习题 295

7.5 小结 295

7.7 上机题 297

第8章 散列 298

8.1 散列表 298

8.2 散列函数 299

8.2.1 函数对象 299

8.2.2 构造散列函数的方法 301

8.3 处理冲突的方法 303

8.3.1 开放定址法 303

8.3.2 拉链法 305

8.4.1 散列表的元素 306

＊8.4 散列表类及迭代器类 306

8.4.2 散列表类HashTable 307

8.4.3 迭代器类 309

8.5 小结 313

8.6 习题 313

8.7 上机题 315

第9章 排序 317

9.1 插入排序 317

9.1.1 直接插入排序 317

9.1.2 二分法插入排序 319

9.2 快速排序 320

9.3 堆排序 325

9.4 归并排序 327

＊9.5 基于比较的排序方法所需时间的最小上界 333

9.6 小结 334

9.7 习题 334

9.8 上机题 335

第10章 图 337

10.1 图的概念 337

10.2 图类 339

10.2.2 图的存储表示及图类的实现 340

10.2.1 图的操作 340

10.3 图的遍历 349

10.3.1 深度优先搜索 349

10.3.2 广度优先搜索 351

10.4 最小代价生成树 354

10.5 最短路径 359

10.6 拓扑排序 365

10.7 小结 369

10.8 习题 369

10.9 上机题 370

参考文献 371