用C++描述数据结构PDF电子书下载

第一章基本概念 1

1.1 综述：系统生命周期 1

1.2 面向对象程序设计 3

1.2.1 算法分解与面向对象分解 3

1.2.2 面向对象程序设计的基本定义和概念 3

1.2.3 程序设计语百的演变相C++的历史 4

1.3 数据抽象和封装 4

1.4 C++基础 8

1.4.1 C++中的程序结构 8

1.4.2 C++中的表达式和操作符 9

1.4.2 C++中的作用域 9

1.4.4 C++中的数据声明 10

1.4.5 C++中的注释 10

1.4.6 C++中的输入／输出 11

1.4.7 C++个的函数 12

1.4.8 C++中的参数传递 12

1.4.9 C++中的函数名重裁 13

1.4.10 内联函数 13

1.4.11 C++中的动态存储器分配 14

1.5 算法详述 14

1.5.1 引言 14

4.8 稀疏矩阵 15

1.5.2 递归算法 15

1.6 性能分济与测定 21

1.6.1 性能分析 21

第七章 排序 29

7.1 引言 29

1.6.2 性能测定 37

2.1.2 C++中的数据抽象与封装 42

1.6.3 产生测试数据 42

2.1.1 C++类简介 45

2.1.3 声明类对象和调用成员函数 46

第二章 数组 47

2.1 抽象数据类型和C++类 47

2.1.4 持殊的类操作 49

2.1.5 其他方面的概述 51

2.1.6 抽象数据类型(ADT)和C++的类 52

2.2 作为抽象数据类型的数组 53

2.3 多项式抽象数据类型 55

2.3.1 多项式表示 57

2.3.2 多项式相加 59

2.3.3 由数组表示多项式的缺点 60

2.4 稀疏矩阵 62

2.4.1 引言 62

2.4.2 稀疏矩阵的表示方式 63

2.4.3 矩阵的转置 64

2.4.4 短阵相乘 67

2.4.5 由数组表示稀疏短阵的缺点 71

2.5 数组的表示 73

2.6 字符串抽象数据类型 76

2.6.1 字符串模式匹配：一种简单算法 77

2.6.2 字符串模式匹配：K—M—P算法 77

2.7 附加练习 81

第三章 栈和队列 86

3.1.1 模板函数 86

3.1 C++中的模板 86

3.1.2 采用摸板表示包容类 87

3.2 栈抽象数据类型 91

3.3 队列抽象数据类型 95

3.4 C++中的子类型和继承 99

3.5 迷宫问题 102

3.6表达式的计算 107

3.6.1 表达式 107

3.6.2 后缀表示法 108

3.6.3 中缀转换为后缀 109

3.7 多栈和多队列 112

3.8 附加练习 115

4.1 单链表 117

第四章 链表 117

4.2.1 用C++定义一个链表结点 119

4.2 用C++表示链表 119

4.2.2 用C++设计链表 120

4.2.3 C++中的指针使用 123

4.2.4 表处理操作 124

4.3 可重用的链表类 127

4.3.1 采用模板实现链表 127

4.3.2 链麦重复体 128

4.3.3 链表操作 131

4.3.4 重用一个类 132

4.4 循环链表 133

4.5 链接栈和链接队列 135

4.6 多项式 137

4.8.1 稀疏矩阵表示 151

4.8.2 稀疏矩阵的输入 154

4.8.3 清除稀疏距阵 155

4.9 双向链表 158

4.10.1 广义表的表示 160

4.10 广义表 160

4.10.2 链表的递归算法 164

4.10.3 共享链表、递归链表和引用数 167

4.11 C++中的虚函数和动态联编 171

4.12 异质表 174

第五章 树 179

5.1 引言 179

5.1.1 术语 179

5.1.2 树的表示法 181

5.2 二叉树 183

5.2.1 抽象数据类型 183

5.2.2二叉树的性质 185

5.2.3二叉树的表示法 186

5.3.1 引言 189

5.3 二叉树遍历 189

5.3.2 中序遍历 190

5.3.3 中序遍历 191

5.3.4 后序遍历 192

5.3.5 迭代中序遍历 192

5.3.6 层序温历 194

5.3.7 不用栈的遍历 195

5.4 二叉树的其他操作 197

5.4.1 复制二叉树 197

5.4.2 测试等价性 198

5.4.3 可满足性问题 198

5.5.1 线索 202

5.5 线索二叉树 202

5.5.2 中序遍历线索二叉树 203

5.5.3 向线索二叉树小插入结点 205

5.6 堆 206

5.6.1 优先级队列 206

5.6.2 最大准的定义 207

5.6.3 向最大堆中插入元素 209

5.6.4 从最大堆小删除元索 210

5.7 二叉查找树 212

5.7.1 定义 212

5.7.2 检索一棵二叉查找树 213

5.7.3 向二叉查找树中插入元素 215

5.7.4 从二叉查找树中删除元素 216

5.7.5 连接和分裂二叉树 216

5.7.6 二叉杏找树的高度 218

5.8 选拔树 219

5.8.1 引言 219

5.8 2 优胜者树 220

5.8.3 失败者树 221

5.9森林 222

5.11 树数据结构的面向对象系统 223

5.9.1 把森林转换成二叉树 223

5.9.2 森林的遍历 223

5.10 集合的表示方法 224

5.10.1 引言 224

5.10.2 归并和查找操作 225

5.10.3 在等价类中的应用 231

5.12 二叉树的计数 236

5.12.1 不相同的二叉树 236

5.12.2 栈排列 237

5.12.3 矩阵乘法 238

5.12.4 不同二叉树数 239

第六章 图 241

6.1 图抽象数据类型 241

6.1.1 引言 241

6.1.2 定义 242

6.1.3 图的表示方法 245

6.2.1 深度优先搜索 251

6.2 图的基本操作 251

6.2.3 连通分量 253

6.2.2 广度优先搜索 253

6.2.4 生成树 254

6.2.5 重连通分量 255

6.3 最小代价生成树 260

6.3.2 普里姆算法 263

6.3.3 索林算法 264

6.4 最短路径和传北递闭包 265

6.4.1 边带非负权值时从一个源点到其余所有顶点的最短路径 266

6.4.2 边带任意权值时从一个源点到其余所有顶点的最短路径 268

6.4.4 传递闭包 273

6.5 活动网络 276

6.5.1 顶点表示活动的网络（AOV网） 276

6.5.2 边表示活动的网络（AOE网） 281

6.6 附加练习 288

7.2 插入排序 295

7.3 快速排序 296

7.4 排序的最小时间复杂度 299

7.5 归并排序 301

7.5.1 归并 301

7.5.2 迭代归并排序 305

7.5.3 递归归并排序 306

7.6 堆排序 310

7.7 对多个关键码的排序 313

7.8 链表排序和列表排序 316

7.9 内部排序的总结 323

7.10 外部排序 326

7.10.1 引言 326

7.10.2 k一路归并 329

7.10.3 对并行操作的缓冲区管理 330

7.10.4 归并段产生 335

7.10.5 归并段的最健归并 337

第八章 散列 341

8.1 符号表抽象数据类型 341

8.2 静态散列 342

8.2.1 哈希表 342

8.2.2 哈希函数 343

8.2.3 溢出处理 346

8.3 动态散列 353

8.3.1 引言 354

8.3.2 使用目录的动态散列 354

8.3.3 基于目录的动态散列方法的分析 359

8.3.4 无目录的动态散列 361

9.1.1 定义 365

9.1 最小一最大堆 365

第九章 堆结构 365

9.1.2 向最小一最大堆中插入元素 366

9.1.3 删除最小元素 369

9.2 双端堆 372

9.2.1 定义 372

9.2.2 向双端堆中插入元素 374

9.2.3 删除最小元素 376

9.3 左树 378

9.4 二项堆 384

9.4.1 代价分摊 384

9.4.2 二项堆的定义 385

9.4.3 向二项堆中插入元素 386

9.4.4 结合两个二项堆 386

9.4.5 删除最小元素 387

9.4.6 分析 388

9.5.1 定义 390

9.5 斐波那契堆 390

9.5.2 从F—堆中删除结点 391

9.5.3 减—码 391

9.5.4 级联购切 392

9.5.5 分析 392

9.5.6 在最短路径问题中的应用 394

9.6 附加练习 396

第十章 查找结构 398

10.1 最优二叉查找树 398

10.2 AVL树 404

10.3 2—3树 416

10.3.1 定义和性质 416

10.3.2 查找一裸2—3树 417

10.3.3 向2—3树中插入元素 418

10.3.4 从2—3树中剿除元素 420

10.4.1 定义和性质 426

10.4 2—3—4树 426

10.4.2 自顶向下插入 428

10.4.3 自顶向下删除 431

10.5 红—黑树 432

10.5.1 定义和性质 432

10.5.2 查找红—黑树 434

10.5.3 自顶向下插入 435

10.5.4 自底向上插入 437

10.5.5 从红—黑树中删除元素 438

10.5.6 连接和分裂红—黑树 439

10.6 B—树 443

10.6.1 m—路查找树的定义 443

10.6.2 查找一棵m—路查找树 444

10.6.3 B—树的定义和性质 445

10.6.4 向B—树中插入 447

10.6.5 从B—树中插入 449

10.6.6 可变大小的关键码 452

10.7 扁树 454

10.8 数字查找树 459

10.8.1 定义 459

10.8.2 二叉trie树 460

10.8.3 Patricia 462

10.9 trie树 466

10.9.1 定义 466

10.9.2 查找一棵trie树 467

10.9.3 采样策略 467

10.9.4 向trie树中插入关键码 468

10.9.5 从trie树中删除关键吗 469

10.9.6 结点结构 470

10.10 差异文件 471

10.10.1 概念 471

10.10.2 布卢姆过滤程序 472