本书是一本系统介绍数据结构的教材。在本书的论述过程中反复联系到计算机领域的许多重要问题，包括问题求解、算法的分析与设计、抽象数据类型、程序设计方法、程序设计语言等内容。根据目前计算机科学发展的情况，本书采用面向对象的思想组织与课程有关的内容，运用C++语言作为数据结构和算法的描述语言，保证本书的先讲性和适用性。

本书采用面向对象的思想组织数据结构的内容，运用C++语言作为讨论数据结构的工作语言。在第一版的基础上，除对各章的顺序及内容安排进行了进一步的调整之外，还补充了各章的例子、习题，并增加了若干上机实习题，使读者可以更好地对数据结构进行学习、实践。在本书的最后还附加了一个上机实习报告的例子，使其具有较强的实用性。

本书除延续了第一版的风格外，内容更加充实、完整，讲解更加清楚、透彻。可作为本科计算机专业或相关专业数据结构课程教材，也可作为面向对象程序设计课程或C++程序设计实践课程的教材和参考书。

第一章 绪论/l

1.1 问题求解/1

1.1.1问题/2

1.1.2问题的分析/2

1.1.3算法的选择/3

1.1.4解的精化/4

1.2 数据结构/4

1.3 算法/6

l.3.1算法的设计/6

1.3.2算法的分析/7

1.4 抽象数据类型/9

1.5 程序设计方法和语言/11

 小结/12

 习题/12

第二章 C++与面向对象初步/13

2.1 C++语言对c的基本扩充/13

  2.1.1注释/13

  2.1.2函数原型说明/14

  2.1.3引用和引用参数/14

  2.1.4重载/16

  2.1.5缺省参数/16

  2.1.6变量说明/17

  2.1.7输入和输出/17

  2.1.8动态存储分配/17

  2.1.9类型定义/18

  2.1.10强制类型转换/18

2.2 对象和类/18

2.3 类的界面描述和实现/22

  2.3.1类的数据域/24

  2.3.2对象的行为——成员函数/24

  2.3.3运算符作为成员函数/25

  2.3.4用构造函数进行实例的初始化/27

2.4 普通运算符和普通函数/31

  2.4.1普通运算符/31

  2.4.2普通函数/33

  2.4.3输入和输出/33

2.5 类的合成、继承和多态性/36

  2.5.1合成/36

  2.5.2继承/38

  2.5.3多态性/39

 小结/40

 习题/42

第三章 字符串二—数据封装技术/44

3.1 C语言的字符和字符串/44

3.2 字符串数据抽象的描述和实现/46

  3.2.1字符串类的定义/47

  3.2.2构造函数的定义/49

  3.2.3析构函数/52

  3.2.4基本成员函数的实现/53

  3.2.5比较运算符/57

  3.2.6串连接/59

  3.2.7输入和输出/60

3.3子串/62

3.4 模式匹配/67

  3.4.1简单字符串匹配/69

  3.4.2 Knuth-Mords-Pratt模式匹配算法/72

  3.4.3 Bovermore符串匹配算法/76

 小结/80

 习题/80

第四章 向量——类的重用技术/83

4.1 模板类/84

4.2 向量的实现/86

4.3 定界向量和枚举向量——继承方式的重用/90

  4.3.1定界向量/90

  4.3.2枚举向量/94

4.4 排序向量和矩阵——舍成方式的重用/96

  4.4.1排序向量和二分法检索/96

  4.4.2矩阵/100

4.5 向量遍历器/103

 4.5.1遍历器的抽象/103

 4.5.2向量遍历器/105

4.6 向量的排序一模板函数/110

 4.6.1插入排序/110

 4.6.2起泡排序/112

 4.6.3选择排序/113

 4.6.4快速排序算法/114

4.7 继承和多态的若干讨论/l16

 4.7.1父类与子类/116

 4.7.2静态类型和动态类型/117

 4.7.3框架和框架类/118

 4.7.4遮蔽和虚函数/118

 4.7.5虚遮蔽和非虚遮蔽/119

 4.7.6两类继承/120

 4.7.7多态的主要形式/121

 4.7.8参数多态性——归约/121

 4.7.9切割问题/123

小结/125

习题/125

第五章 动态数据结构一链表/128

5.1 单链表的定义/128

  5.1.1表类/128

  5.1.2链类/130

5.2 单链表的实现/131

  5.2.I链类的实现/131

  5.2.2表类的实现/133

5.3 表遍历器/136

  5.3.1表遍历器类/136

  5.3.2表遍历器类的实现/138

5.4 表的应用：多项式处理/142

  5.4.1项类/143

  5.4.2多项式类/145

5.5 排序表“/148

 5.5.1排序表类/148

 5.5.2排序表类的实现/148

 5.5.3排序表的应用——表插入排序/149

5.6 其他链表/150

 5.6.1 自组织表/150

 5.6.2双端表/152

 5.6-3循环表/154

 5.6.4双链表/155

5.7 可利用空间表/155

小结/157

习题/159

第六章 栈和队列/161

6.1 抽象类栈和队列161

6.2 栈的实现/162

 6.2.1栈的向量实现/163

 6.2.2栈的链表实现/165

 6.3栈的应用——表达式计算/167

 6.3.1、后缀表达式的求值/167

 6.3.2中缀表达式到后缀表达式

的转换/170

6.4 队列的实现/172

 6.4.1队列的向量实现/172

 6.4.2队列的链表实现/174

6.5 队列的应用——农夫过河问题/177

小结/181

习题/181

第七章 树和二叉树/184

7.1 基本概念/185

 7.1.1树/185

 7.1.2二叉树/187

 7.1.3树与二叉树的关系/190

7.2 二叉树的实现/191

 7.2.1二叉树结点类/191

 7.2.2基本二叉树类/193

 7.2.3可构造二叉树类/195

7.3 二叉树的周游/197

 7.3.1周游的递归实现/197

 7.3.2通过遍历器实现周游/199

 7.3.3前序周游器类/199

 7.3.4中序周游器类/202

 7.3.5后序周游器类/203

 7.3.6层次周游算法(按宽度方向周游)/205

7.4 二叉树的向量表示/207

 7.4.1二叉树向量表示的一种基本方法/207

 7.4.2记录结构信息的二叉树向量表示/208

7.5 二叉排序树/209

7.6 平衡的二叉排序树/214

 7.6.1AVL树上的操作/215

 7.6.2AVL树的设计与实现/218

7.7 二叉树的应用——哈夫曼树/225

小、结/228

习题/228

第八章 优先队列/23l

8.1 优先队列的抽象/231

8.2 堆/234

8.3 堆排序/238

8.4 斜堆/240

8.5 离散事件模拟/244

 8.5.1模拟类的结构/246

 8.5.2冰淇淋店的模拟/248

 8.5.3随机数/251

小结/253

习题/253

第九章 集合与字典/256

9.1 集合及其运算/256

 9.1.1集合运算/257

 9.1.2集合类/258

9.2 位向量集合/259

 9.2.1位向量/260

 9.2.2位向量集合/266

 9.2.3字符集合/269

 9.2.4字符集类的应用——将字符串分解为单词/270

9.3 集合的表实现/273

9.4 关联与字典/275

9.5 字典的关联表实现/278

9.6 字典的应用/281

 9.6.1稀疏矩阵/281

 9.6.2排序字典/284

 9.6.3索引的实现/285

小结/287

习题/289

第十章散列结构/291

10.1散列结构/291

10.2散列函数/295

10.3开地址散列向量/297

10.4桶散列——用桶解决碰撞/300

 IO.4.桶散列的抽象模板类/301

 10.4.2用树作为桶的实现/302

 10.4.3桶散列结构操作时间的分析/304

lO.5桶散列结构的遍历器/305

10.6用散列表实现集合/307

 10.6.1应用——拼写检查器/309

10.7用桶散列表实现字典/311

小结/313

习题/314

第十一章 图/316

11.1 基本概念/316

11.2 图的邻接矩阵表示和Warshall算法/318

  11.2.1图的邻接矩阵表示/318

  Il.2.2图结点的可达性问题/318

11.3 邻接表方式的图表示和深度优先搜索/320

  11.3.1邻接表表示中的结点类/321

  11.3.2用深度优先方式求解可达性问题/322

11.4 带权图的矩阵表示和Floyd算法/324

  11.4.1带权图的邻接矩阵/325

  11.4.2带权图最短路径问题Floyd算法/325

11.5 带权图的邻接表表示与Dijkstra算法/327

  11.5.1带权图的邻接表表示/327

  11.5.2从一个结点出发的最短路径和Dijkstra算法/328

11.6 连通性、带权连通无向图与最小生成树/330

 11.7有限自动机/333

 11.8拓扑排序}/336

小结/338

习题/339

第十二章 文件/342

12.1 外存、文件及其问题/342

 12.1.1外存储器的特点与信息组织/342

 12.1.2文件基本结构和操作/344

 12.1.3文件与字典/345

 12.1.4文件组织/346

12.2 C++的字符流文件及其操作/347

12.3 归并排序/352

12.4 文件的随机访问/356

12.5 文件索引结构/359

 12.5.1索引向量/359

 12.5.2树形索引结构/360

 12.5.3 B树/361

 12.5.4 B+树/364

12.6 树索引文件的实现/367

小结/369

习题/369

附录/371

 附录A 主要抽象数据类及其相互关系/371

 附录B Borland C++集成开发环境使用入门/375

 附录C“多叉路口的交通管理系统”上机报告/387