数据结构（STL框架）

普通高等教育“十一五”国家级规划教材、国家精品课程主讲教材

作者：王晓东
定价：34.80元
印次：1-2
ISBN：9787302203933
出版日期：2009.09.01
印刷日期：2011.01.17

本书以ACM和IEEE/CS Computing Curricula 2005课程体系以及教育部计算机科学与技术教学指导委员会发布的“高等学校计算机科学与技术本科专业规範”中制定的关于数据结构和算法设计与分析的知识结构和体系为依据，以基本数据结构和抽象数据类型为知识单元而编写。本书一个明显的特色是在STL (Standard Template Library）框架下描述数据结构的设计思想和实现方法，使读者循序渐进地理解数据抽象，面向对象设计方法和泛型算法设计三位一体的面向高层次的现代化软体设计风格。全书共分16章，涵盖 CC2005 课程体系中有关算法与数据结构、知识结构和体系的重要内容，包括算法与数据结构引论、向量、双端伫列、表、栈和伫列、排序与选择、树、二叉搜寻树、平衡搜寻树、集合、映射、堆与优先伫列、散列、并查集、图与相关算法。

本书可作为高等学校计算机、电子信息、信息与计算科学、信息管理与信息系统等专业数据结构课程教材，也适合工程技术人员和自学者学习参考。

第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

目录数据结构(STL框架)第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.2Josephus排列问题106

习题4107

数据结构与算法实验4108

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

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

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

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

数据结构与算法实验题4.5Josephus排列问题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.2DNA排序问题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.2AVL树223

10.2.1AVL树的定义和性质223

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

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

10.3套用举例229

10.3.1条形图统计问题229

10.3.2动态选择问题230

10.3.3Josephus排列问题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.1Eratosthenes筛法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