《数据结构 C++与面向对象的途径》求取 ⇩

第一章 预备知识1

1．1 C++语言对C的基本扩充1

1．2 对象和类6

1．3 类的界面描述和实现10

1．3．1 类的数据域11

1．3．2 对象的行为——成员函数12

1．3．3 运算符作为成员函数13

1．3．4 用构造函数进行实例的初始化15

1．3．5 普通运算符18

1．3．6 普通函数20

1．4 对象的输入和输出20

1．5 类的合成、继承和多态性24

1．5．1 合成24

1．5．2 继承27

1．5．3 多态性28

1．6 面向对象的程序设计*28

1．6．1 分析阶段29

1．6．2 设计阶段30

1．6．3 编码阶段32

1．6．4 测试和维护34

1．7 算法分析与设计*34

小结38

习题39

第二章 字符串——数据封装技术41

2．1 C++语言的字符和字符串41

2．2 字符串数据抽象的描述和实现43

2．2．1 字符串类的定义44

2．2．2 构造函数的定义46

2．2．3 析构函数49

2．2．4 基本成员函数的实现50

2．2．5 比较运算符54

2．2．6 串连接56

2．2．7 输入和输出57

2．3 子串59

2．4 模式匹配64

2．4．1 简单字符串匹配66

2．4．2 Knuth-Morris-Pratt模式匹配算法*69

2．4．3 Boyer-Moore字符串匹配算法*73

小结77

习题77

第三章 向量——程序重用技术79

3．1 模板类80

3．2 向量的实现82

3．3 程序的重用、定界向量和位向量85

3．3．1 继承方式的重用：定界向量86

3．3．2 通过合成方式的重用——位向量89

3．4 其他向量类型*94

3．4．1 用枚举类型作为指标94

3．4．2 矩阵96

3．5 排序——模板函数100

3．5．1 插入排序101

3．5．2 起泡排序102

3．5．3 选择排序103

3．5．4 快速排序算法104

小结106

习题107

4．1 遍历器（Iterator）108

第四章 遍历器——继承和多态性108

4．1．1 抽象的遍历器类109

4．1．2 向量遍历器110

4．2 有序向量和二分法检索114

4．3 继承和多态——进一步的讨论117

4．3．1 静态、动态类型和多态性117

4．3．2 框架和虚函数119

4．3．3 两类继承120

4．3．4 对虚函数和普通函数的遮蔽*121

4．4 多态性的形式和例子*122

4．4．1 参数多态性——归约122

4．4．2 切割问题124

小结125

习题126

第五章 动态数据结构——链表127

5．1 单链表的定义127

5．1．1 表类127

5．1．2 链类129

5．2 单链表的实现130

5．2．1 链类的实现130

5．2．2 表类的实现132

5．3 表遍历器136

5．3．1 表遍历器类136

5．4 表的应用：多项式处理*142

5．4．1 项类142

5．4．2 多项式类144

5．5 有序链表147

5．5．1 有序表类147

5．5．2 有序表类的实现148

5．5．3 有序表的应用——表插入排序149

5．6 其他链表150

5．6．1 自组织表150

5．6．2 双端表151

5．6．3 循环表152

5．6．4 双链表152

5．7 可利用空间表153

小结155

习题157

第六章 栈和队列158

6．1 抽象类栈和队列158

6．2 栈的实现159

6．2．1 栈的向量实现160

6．2．2 栈的链表实现162

6．3 栈的应用——表达式计算164

6．3．1 后缀表达式的求值164

6．3．2 中缀表达式到后缀表达式的转换167

5．3．2 表遍历器类的实现167

6．4 队列的实现169

6．4．1 队列的向量实现169

6．4．2 用双端表实现队列171

6．4．3 用循环表实现队列172

6．5 应用实例——农夫过河问题*174

6．5．1 广度优先搜索法176

6．5．2 深度优先搜索法178

小结179

习题180

第七章 树和二叉树182

7．1 基本概念183

7．1．1 树183

7．1．2 二叉树185

7．1．3 树与二叉树的关系187

7．2 二叉树的实现188

7．2．1 二叉树结点类188

7．2．2 基本二叉树类191

7．2．3 二叉树的构造193

7．3 二叉树的周游195

7．3．1 周游的递归实现195

7．3．2 通过遍历器实现周游197

7．3．3 前序周游器类198

7．3．4 中序周游器类201

7．3．5 后序周游器类203

7．3．6 层次周游算法（按宽度方向周游）205

7．4 二叉树的向量表示207

7．4．1 二叉树向量表示的一种基本方法207

7．4．2 记录结构信息的二叉树向量表示208

7．5 二叉排序树209

7．6 平衡的二叉排序树215

7．6．1 AVL树上的操作215

7．6．1 AVL树的实现*219

7．7 二叉树的应用——哈夫曼树227

小结230

习题231

第八章 优先队列233

8．1 优先队列的抽象233

8．2 堆236

8．3 堆排序240

8．4 斜堆241

8．5 离散事件模拟*246

8．5．1 模拟类的结构247

8．5．2 冰淇淋店的模拟250

8．5．3 随机数*252

小结255

习题255

第九章 散列结构257

9．1 散列向量257

9．2 开地址散列260

9．3 散列表——用桶解决碰撞263

9．4 散列表遍历器266

9．5 桶排序269

9．6 散列函数270

小结272

习题272

第十章 集合与字典274

10．1 集合及其运算274

10．2 位向量集合275

10．2．1 字符集278

10．2．2 应用——将字符串分解为单词*279

10．3 集合的表实现281

10．4 用散列表实现集合283

10．4．1 应用——拼写检查器*285

10．5 字典与关联287

10．6 字典的关联表实现288

10．7．1 稀疏矩阵291

10．7 字典的应用291

10．7．2 索引的实现295

10．8 用散列表实现字典297

小结300

习题301

第十一章 图303

11．1 基本概念303

11．2 图的邻接矩阵表示和Warshall算法304

11．2．2 图结点的可达性问题305

11．3 邻接表方式的图表示和深度优先搜索306

11．3．1 邻接表表示的结点类306

11．3．2 用深度优先方式求解可达性问题308

11．4 带权图的矩阵表示和Floyd算法309

11．4．2 带权图最短路径问题和Floyd算法310

11．4．1 带权图的邻接矩阵310

11．5 带权图的邻接表表示与Dijkstra算法312

11．5．1 带权图的邻接表表示312

11．5．2 从一个结点出发的最短路径和Dijkstra算法313

11．6 有限自动机*315

11．7 拓扑排序319

小结320

习题321

第十二章 文件323

12．1 外存、文件及其问题323

12．1．1 外存储器的特点与信息组织323

12．1．2 文件基本结构和操作324

12．1．3 文件与字典325

12．1．4 文件组织326

12．2 C++的字符流文件及其操作327

12．3 归并排序332

12．4 文件的随机访问*336

12．5 文件索引结构338

12．5．1 索引向量339

12．5．2 树形索引结构339

12．5．3 B树*341

12．5．4 B+树*344

小结346

习题346

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

A．1 串及其主要相关类348

A．2 向量及其主要相关类349

A．3 表及其主要相关类349

A．6 优先队列及其主要相关类350

A．4 栈及其主要相关类350

A．5 队列及其相关类350

A．7 树及其主要相关类351

A．8 散列表及其主要相关类351

A．9 字典及其主要相关类352

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

B．1 概况353

B．2 启动与退出353

B．3 菜单与会话框操作354

B．4 窗口管理355

B．5 编辑命令356

B．6 一些主要菜单命令358

B．7 编程的几个基本步骤362

参考文献365