数据结构 C++与面向对象的途径PDF电子书下载

第一章 预备知识 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