数据结构(STL框架)

第1章 算法与数据结构引论.1

1.1 算法及其复杂性的概念1

1.1.1 算法与程序1

1.1.2 算法复杂性的概念1

1.1.3 算法复杂性的渐近性态2

1.2 数据结构与抽象数据类型3

1.3 用c++描述数据结构与算法4

1.3.1 指针和引用4

1.3.2 函数与参数传递4

1.3.3 c++的类5

1.3.4 类的对象6

1.3.5 模板6

1.3.6 动态存储分配7

1.4 递归8

1.5 标准模板库stl与泛型算法9

1.5.1 stl概述9

1.5.2 容器10

1.5.3 迭代器10

1.5.4 泛型算法11

1.5.5 函数对象14

.1.6 应用举例19

1.6.1 用c++的类实现抽象数据类型19

1.6.2 顺序搜索与二分搜索算法的设计与分析23

1.6.3 递归算法的设计与分析25

习题126

数据结构与算法实验127

数据结构与算法实验题1.1 实系数复变多项式问题27

数据结构与算法实验题1.2 平面几何问题28

数据结构与算法实验题1.3 m进制数问题29

第2章 向量30

2.1 向量的基本概念30

2.2 抽象数据类型向量30

2.3 向量的迭代器30

2.4 向量的实现方法31

2.5 矩阵与多维向量35

2.6 高精度整数36

2.7 应用举例47

2.7.1 搜索公共元素问题47

2.7.2 同色方块识别问题48

2.7.3 全排列问题49

习题249

数据结构与算法实验250

数据结构与算法实验题2.1 前缀与后缀和问题50

数据结构与算法实验题2.2 投票选举问题50

数据结构与算法实验题2.3 稳定婚姻问题51

数据结构与算法实验题2.4 凸多边形的三角剖分问题52

第3章 双端队列53

3.1 双端队列的基本概念53

3.2 抽象数据类型双端队列53

3.3 双端队列的实现方法54

3.4 双端队列的迭代器60

3.5 应用举例62

3.5.1 双端队列的简单应用62

3.5.2 简单多边形的凸壳问题63

习题365

数据结构与算法实验365

数据结构与算法实验题3.1 排队购票问题65

数据结构与算法实验题3.2 循环向量的极值问题66

第4章 线性表68

4.1 表的基本概念68

4.2 用数组实现表69

4.3 用指针实现表73

4.3.1 用指针实现单链表的方法73

4.3.2 单链表的迭代器75

4.4 用间接寻址方法实现表79

4.4.1 间接寻址方法的基本思想79

4.4.2 间接寻址表的迭代器82

4.5 用游标实现表84

4.5.1 用游标实现表的基本思想84

4.5.2 游标实现的表的迭代器89

4.6 循环链表90

4.6.1 实现单循环链表的基本思想90

4.6.2 单循环链表的迭代器92

4.7 双链表94

4.7.1 实现双向循环链表的基本思想94

4.7.2 双向循环链表的迭代器97

4.8 应用举例101

4.8.1 多项式函数101

4.8.2 josephus排列问题106

习题4107

数据结构与算法实验4108

数据结构与算法实验题4.1 实系数一元多项式问题108

数据结构与算法实验题4.2 josephus排列问题1109

数据结构与算法实验题4.3 向量分类问题110

数据结构与算法实验题4.4 条形图轮廓问题110

数据结构与算法实验题4.5 josephus排列问题2111

第5章 栈113

5.1 栈的基本概念113

5.2 栈的实现方法114

5.3 应用举例115

5.3.1 等价类划分问题115

5.3.2 模拟递归问题117

5.3.3 电路板布线问题119

习题5121

数据结构与算法实验5121

数据结构与算法实验题5.1 车皮编序问题121

数据结构与算法实验题5.2 单柱hanoi塔问题122

数据结构与算法实验题5.3 多栈模拟问题123

数据结构与算法实验题5.4 亲兄弟问题124

第6章 队列125

6.1 队列的基本概念125

6.2 队列的实现方法125

6.3 应用举例126

6.3.1 最优电路布线问题126

6.3.2 和谐短信问题129

习题6130

数据结构与算法实验6130

数据结构与算法实验题6.1 组队列问题130

数据结构与算法实验题6.2 双栈队列问题131

数据结构与算法实验题6.3 猴子分桃问题132

数据结构与算法实验题6.4 逆序表问题132

第7章 排序与选择134

7.1 简单排序算法134

7.1.1 冒泡排序算法134

7.1.2 插入排序算法135

7.1.3 选择排序算法136

7.1.4 简单排序算法的计算复杂性136

7.2 快速排序算法137

7.2.1 算法基本思想及实现137

7.2.2 算法性能分析139

7.2.3 随机快速排序算法139

7.3 合并排序算法140

7.3.1 算法基本思想及实现140

7.3.2 消除递归141

7.3.3 自然合并排序算法141

7.4 链表排序与索引排序算法142

7.4.1 链表排序算法142

7.4.2 索引排序算法149

7.5 线性时间排序算法151

7.5.1 计数排序算法151

7.5.2 桶排序算法152

7.6 中位数与第k小元素152

7.6.1 平均情况下的线性时间选择算法153

7.6.2 最坏情况下的线性时间选择算法154

7.7 泛型排序算法156

7.7.1 排序算法的泛化方法156

7.7.2 泛型合并排序算法158

7.7.3 泛型快速排序算法159

7.7.4 泛型选择算法160

7.8 应用举例161

7.8.1 区间覆盖问题161

7.8.2 输油管道问题161

习题7162

数据结构与算法实验7163

数据结构与算法实验题7.1 交换排序问题163

数据结构与算法实验题7.2 dna排序问题163

数据结构与算法实验题7.3 邮局选址问题164

数据结构与算法实验题7.4 最优服务次序问题165

第8章 树166

8.1 树的定义166

8.2 树的遍历168

8.3 树的表示法170

8.3.1 父结点数组表示法170

8.3.2 儿子链表表示法170

8.3.3 左儿子右兄弟表示法171

8.4 二叉树的基本概念171

8.5 二叉树的运算173

8.6 二叉树的实现174

8.6.1 二叉树的顺序存储结构174

8.6.2 二叉树的结点度表示法175

8.6.3 用指针实现二叉树176

8.7 线索二叉树179

8.8 应用举例——信号增强装置布局问题..181

习题8184

数据结构与算法实验8185

数据结构与算法实验题8.1 层序列表问题185

数据结构与算法实验题8.2 最近公共祖先问题186

数据结构与算法实验题8.3 子树问题187

数据结构与算法实验题8.4 同构二叉树问题187

数据结构与算法实验题8.5 后序中序遍历问题188

第9章 二叉搜索树189

9.1 有序集与二叉搜索树189

9.1.1 抽象数据类型字典189

9.1.2 用数组实现字典189

9.1.3 二叉搜索树的基本概念190

9.2 实现二叉搜索树190

9.3 二叉搜索树的迭代器199

9.4 二叉搜索树的效率205

9.5 应用举例——条形图统计问题207

习题9209

数据结构与算法实验9209

数据结构与算法实验题9.1 装箱问题209

数据结构与算法实验题9.2 电路板连线问题210

数据结构与算法实验题9.3 字典问题211

第10章 平衡搜索树212

10.1 红黑树212

10.1.1 红黑树的定义和性质212

10.1.2 旋转变换213

10.1.3 红黑树的插入运算与重平衡216

10.1.4 红黑树的删除运算与重平衡218

10.2 avl树223

10.2.1 avl树的定义和性质223

10.2.2 avl树的插入运算与重平衡224

10.2.3 avl树的删除运算与重平衡226

10.3 应用举例229

10.3.1 条形图统计问题229

10.3.2 动态选择问题230

10.3.3 josephus排列问题232

习题10233

数据结构与算法实验10234

数据结构与算法实验题10.1 逆序计数问题234

数据结构与算法实验题10.2 k后继问题234

数据结构与算法实验题10.3 圆内相交弦问题235

数据结构与算法实验题10.4 最小间隙问题236

数据结构与算法实验题10.5 图形周长问题237

数据结构与算法实验题10.6 动态选择问题237

第11章 集合239

11.1 集合的基本概念239

11.2 用位向量实现集合240

11.3 用平衡二叉搜索树实现集合246

11.3.1 直接应用红黑树实现集合246

11.3.2 平衡二叉搜索树的泛化247

11.3.3 符合stl标准的集合252

11.4 多重集合254

11.5 泛型集合运算256

11.6 应用举例259

11.6.1 eratosthenes筛法259

11.6.2 子集和问题260

11.6.3 拼写检查问题260

11.6.4 软件产品数据库问题261

习题11262

数据结构与算法实验11263

数据结构与算法实验题11.1 半数集问题263

数据结构与算法实验题11.2 账单支付问题263

数据结构与算法实验题11.3 张贴海报问题264

数据结构与算法实验题11.4 三色棋游戏问题265

第12章 映射266

12.1 映射的基本概念266

12.2 用平衡二叉搜索树实现映射266

12.2.1 二叉搜索树的进一步泛化266

12.2.2 符合stl标准的映射272

12.3 多重映射274

12.4 应用举例275

12.4.1 种群分布统计问题275

12.4.2 电子字典问题276

习题12278

数据结构与算法实验12278

数据结构与算法实验题12.1 工作薪酬问题278

数据结构与算法实验题12.2 扑克游戏智能分析问题279

数据结构与算法实验题12.3 最优行驶路线问题280

数据结构与算法实验题12.4 库存调整问题281

数据结构与算法实验题12.5 双字符字频分析问题282

数据结构与算法实验题12.6 英文词汇分析问题283

第13章 散列285

13.1 符号表285

13.2 开散列286

13.3 闭散列292

13.4 散列函数的效率297

13.5 重新散列298

13.6 散列集299

13.6.1 用散列表实现集合299

13.6.2 用散列表实现多重集合300

13.7 散列映射301

13.7.1 开散列表的泛化301

13.7.2 用散列表实现映射307

13.7.3 用散列表实现多重映射308

13.8 应用举例309

13.8.1 字符串频率统计问题309

13.8.2 拼写检查问题310

13.8.3 种群分布统计问题311

13.8.4 电子字典问题312

习题13313

数据结构与算法实验13313

数据结构与算法实验题13.1 伪随机排列问题313

数据结构与算法实验题13.2 字符串散列问题314

数据结构与算法实验题13.3 英文文本分析问题314

数据结构与算法实验题13.4 最长模式串问题315

第14章 堆与优先队列316

14.1 优先队列的基本概念316

14.2 优先级树和堆316

14.3 堆的顺序存储方式317

14.4 堆的有关算法318

14.5 堆的泛型算法323

14.6 用堆实现优先队列326

14.7 可并优先队列327

14.7.1 左偏树的定义327

14.7.2 用左偏树实现可并优先队列328

14.7.3 泛化左偏树331

14.8 应用举例332

14.8.1 优先队列的比较模式332

14.8.2 哈夫曼编码问题334

14.8.3 活动安排问题337

习题14338

数据结构与算法实验14338

数据结构与算法实验题14.1 区间相交问题338

数据结构与算法实验题14.2 整数字典问题338

数据结构与算法实验题14.3 最小权语言问题339

数据结构与算法实验题14.4 二叉搜索堆问题339

数据结构与算法实验题14.5 区间覆盖问题340

数据结构与算法实验题14.6 批作业调度问题341

第15章 并查集342

15.1 并查集的基本概念342

15.2 用父结点向量实现并查集343

15.3 应用举例——离线最小值问题346

习题15347

数据结构与算法实验15348

数据结构与算法实验题15.1 二进制方程问题348

数据结构与算法实验题15.2 网络连通问题349

数据结构与算法实验题15.3 朋友问题349

数据结构与算法实验题15.4 等价类划分问题350

第16章 图352

16.1 图的基本概念352

16.2 抽象数据类型图355

16.3 图的表示法355

16.3.1 邻接矩阵表示法355

16.3.2 邻接表表示法356

16.3.3 紧缩邻接表356

16.4 用邻接矩阵实现图357

16.4.1 用邻接矩阵实现图的方法357

16.4.2 邻接矩阵图的顶点迭代器359

16.5 用邻接表实现图360

16.5.1 用邻接表实现图的方法360

16.5.2 邻接表图的顶点迭代器362

16.6 用邻接矩阵实现赋权图362

16.6.1 用邻接矩阵实现赋权图的方法362

16.6.2 邻接矩阵赋权图的顶点迭代器365

16.7 用邻接表实现赋权图365

16.7.1 用邻接表实现赋权图的方法365

16.7.2 邻接表赋权图的顶点迭代器368

16.8 图的遍历搜索算法369

16.8.1 广度优先搜索369

16.8.2 深度优先搜索370

16.9 最短路径算法371

16.9.1 单源最短路算法371

16.9.2 bellman-ford最短路算法374

16.9.3 所有顶点对之间的最短路算法375

16.10 无圈有向图dag376

16.10.1 拓扑排序376

16.10.2 dag的最短路径378

16.10.3 dag的最长路径379

16.10.4 dag所有顶点对之间的最短路径379

16.11 最小支撑树380

16.11.1 最小支撑树的性质380

16.11.2 最小支撑树的prim算法380

16.11.3 最小支撑树的kruskal算法382

16.12 图匹配算法383

16.13 应用举例386

16.13.1 最长嵌套序列问题386

16.13.2 套汇问题388

习题16388

数据结构与算法实验16390

数据结构与算法实验题16.1 图的二着色问题390

数据结构与算法实验题16.2 有向赋权图中心问题390

数据结构与算法实验题16.3 最长简单路径问题391

数据结构与算法实验题16.4 计算机网络问题392

数据结构与算法实验题16.5 差分约束问题393

数据结构与算法实验题16.6 有截止时间的工作排序问题393

数据结构与算法实验题16.7 无向图的连通分支问题394

参考文献...396