数据结构与算法 面向对象的C++设计模式PDF电子书下载

第1章 概要 1

1.1 本书的主要内容 1

1.2 面向对象的设计 1

1.3 对象分级与设计方法 2

1.4 需要了解的C＋＋特性 3

1.5 本书是如何组织的？ 4

第2章 算法分析 5

2.1.1 基本公理 6

2.1 一个细化的计算机模型 6

2.1.2 例1：算术级数求和 8

2.1.3 数组下标操作 8

2.1.4 例2：霍纳（Horner）法则 9

2.1.5 分析递归函数 10

2.1.6 例3：找出数组中最大元素 11

2.1.7 平均运行时间 13

2.1.8 关于调和数 13

2.1.9 最佳情况与最差情况的运行时间 15

2.1.10 最后的公理 16

2.2.1 例1：求几何级数之和 17

2.2 一个简化的计算机模型 17

2.2.2 关于算术级数求和 18

2.2.3 例2：再次求几何级数之和 19

2.2.4 关于几何级数求和 20

2.2.5 例3：幂计算 20

2.2.6 例4：再三求几何级数之和 23

习题 24

设计项目 25

3.1 渐近上界——大O表示法 26

3.1.1 一个简单的例子 26

第3章 渐近表示法 26

3.1.2 大O表示法中的错误与陷阱 27

3.1.3 大O的特性 28

3.1.4 多项式 30

3.1.5 对数 31

3.1.6 紧凑大O界 32

3.1.7 大O表示法中更多的错误与陷阱 33

3.1.8 常用的大O表达式 34

3.2 渐近下界——Ω表示法 34

3.2.1 一个简单的例子 35

3.2.2 再次关于多项式 35

3.4 算法渐近分析 37

3.3 更多的表示法——Θ及小o表示法 37

3.4.1 运行时间分析的大O规则 38

3.4.2 例1：求级数的前项和 39

3.4.3 例2：Fibonacci数 41

3.4.4 例3：桶式排序 44

3.4.5 现实检查 45

3.4.6 检查你的分析 46

习题 47

设计项目 49

4.1 动态数组 50

第4章 基本数据结构 50

4.1.1 缺省构造函数 52

4.1.2 数组构造函数 52

4.1.3 备份构造函数 52

4.1.4 析构函数 53

4.1.5 数组成员函数 54

4.1.6 数组下标操作符 54

4.1.7 数组大小的重调 55

4.2 单链表 55

4.2.1 链表的实现 57

4.2.3 缺省构造函数 59

4.2.2 链表元素 59

4.2.4 析构函数与Purge成员函数 60

4.2.5 存取器 60

4.2.6 First与Last函数 61

4.2.7 前插 61

4.2.8 添加 62

4.2.9 备份构造函数与赋值操作符 62

4.2.10 析取函数 63

4.2.11 InsertAfter与InsertBefore函数 64

4.3.1 数组下标计算 66

4.3 多维数组 66

4.3.2 二维数组的实现 67

4.3.3 C＋＋中多维数组的下标 68

4.3.4 例：规范矩阵相乘 69

习题 71

设计项目 72

第5章 数据类型与抽象 73

5.1 抽象数据类型 73

5.2 设计模式 74

5.2.1 类层次 74

5.2.2 对象 74

5.2.3 NullObject单元集类 78

5.2.4 内嵌类型的对象包装 79

5.2.5 容器 81

5.2.6 访问者 82

5.2.7 迭代器 85

5.2.8 NullIterator类 87

5.2.9 直接存储与间接存储 88

5.2.10 被包含对象的所有权 89

5.2.11 关联 90

5.2.12 可搜索容器 93

习题 94

设计项目 95

第6章 栈、队列及双端队列 97

6.1 栈 97

6.1.1 栈的数组表示法 98

6.1.2 栈的链表表示法 103

6.1.3 应用 107

6.2 队列 110

6.2.1 队列的数组表示法 110

6.2.2 队列的链表表示法 113

6.2.3 应用 115

6.3 双端队列 117

6.3.1 双端队列的数组表示法 119

6.3.2 双端队列的链表表示法 121

6.3.3 双向链表及循环链表 122

习题 123

设计项目 124

第7章 有序线性表与排序表 127

7.1 有序线性表 127

7.1.1 有序线性表的数组表示法 128

7.1.2 有序线性表的链表表示法 136

7.1.3 比较ListAsArray和ListAsLinkedList 141

7.1.4 应用 142

7.2 排序表 145

7.2.1 排序表的数组表示法 146

7.2.2 排序表的链表表示法 149

7.2.3 比较SortedListAsArray和SortedListAsLinkedList 150

7.2.4 应用 151

习题 154

设计项目 155

第8章 散列、哈希表及分散表 156

8.1 散列的基本知识 156

8.1.1 关键字和散列函数 157

8.2 散列法 158

8.2.1 相除散列法 158

8.2.2 平方取中散列法 159

8.2.3 相乘散列法 160

8.2.4 Fibonacci散列法 161

8.3 散列函数的实现 162

8.3.1 整型关键字 163

8.3.2 浮点型关键字 163

8.3.3 字符串关键字 164

8.3.4 散列对象 167

8.3.5 散列容器 168

8.3.6 使用关联 168

8.4 哈希表 169

8.4.1 拉链法 170

8.4.2 平均情况分析 173

8.5 分散表 174

8.5.1 链式分散表 174

8.5.2 平均情况分析 181

8.6 使用开地址法的分散表 181

8.6.1 线性探查 182

8.6.2 二次探查 183

8.6.4 开地址法的实现 184

8.6.3 双散列法 184

8.6.5 平均情况分析 191

8.7 应用 192

习题 194

设计项目 195

第9章 树 197

9.1 基础 197

9.2 N叉树 200

9.4 树的遍历 203

9.3 二叉树 203

9.5 表达式树 205

9.6 树的实现 207

9.6.1 树的遍历 208

9.6.2 树迭代器 212

9.6.3 广义树 215

9.6.4 N叉树 218

9.6.5 二叉树 223

9.6.6 二叉树的遍历 225

9.6.7 树的比较 226

9.6.8 应用 227

习题 230

设计项目 231

第10章 查找树 233

10.1 基础知识 233

10.1.1 M路查找树 233

10.1.2 二叉查找树 233

10.2 搜索查找树 234

10.2.1 搜索M路查找树 234

10.2.2 搜索二叉树 235

10.3.1 搜索成功 236

10.3 平均情况分析 236

10.3.2 递归关系的求解——拓展递归法 237

10.3.3 搜索失败 238

10.3.4 查找树的遍历 239

10.4 查找树的实现 240

10.4.1 二叉查找树 241

10.4.2 在二叉查找树中插入数据项 243

10.4.3 从二叉查找树中删除数据项 244

10.5 AVL查找树 246

10.5.1 AVL树的实现 248

10.5.2 在AVL树中插入数据项 250

10.5.3 从AVL树中删除数据项 255

10.6 M路查找树 255

10.6.1 M路查找树的实现 256

10.6.2 在M路查找树中查找数据项 258

10.6.3 在M路查找树中插入数据项 260

10.6.4 从M路查找树中删除数据项 261

10.7 B树 263

10.7.1 B树的实现 264

10.7.2 在B树中插入数据项 265

10.7.3 从B树中删除数据项 270

10.8 应用 271

习题 273

设计项目 274

第11章 堆和优先队列 275

11.1 基础知识 275

11.2 二叉堆 277

11.2.1 完全树 277

11.2.2 二叉堆的实现 280

11.2.3 在二叉堆中插入数据项 281

11.2.4 从二叉堆中删除数据项 283

11.3 左翼堆 284

11.3.1 左翼树 285

11.3.2 左翼堆的实现 286

11.3.3 左翼堆的合并 287

11.3.4 在左翼堆中插入数据项 288

11.3.5 从左翼堆中删除数据项 289

11.4 二项队列 290

11.4.1 二项树 290

11.4.2 二项队列 293

11.4.3 实现 294

11.4.4 二项队列的合并 297

11.4.5 在二项队列中插入数据项 299

11.4.6 从二项队列中删除数据项 300

11.5 应用 301

11.5.1 离散事件模拟 301

11.5.2 实现 302

习题 304

设计项目 306

第12章 集合、多重集和分区 307

12.1 基础知识 308

12.1.1 集合的实现 308

12.2 数组和位矢量集合 309

12.2.1 位矢量集合 312

12.3 多重集 315

12.3.1 多重集的数组表示法 315

12.3.2 多重集的链表表示法 318

12.4 分区 320

12.4.1 用森林表示分区 322

12.4.2 折叠查找 326

12.4.3 按大小合并 328

12.4.4 按高度或层号合并 329

12.5 应用 330

习题 332

设计项目 333

第13章 动态存储分配：另一种堆 334

13.1 基础 334

13.1.1 C++ Magic 335

13.1.2 堆 338

13.2 单链自由存储器 339

13.2.1 实现 339

13.3 双链自由存储器 345

13.3.1 实现 346

13.4 伙伴存储管理系统 351

13.4.1 实现 353

13.5 应用 358

13.5.1 实现 359

习题 360

设计项目 361

第14章 算法模式和问题求解 363

14.1 蛮干算法和贪心算法 363

14.1.1 例1：数钱 363

14.1.2 例2：0/1背包问题 364

14.2.1 例1：平衡称 366

14.2 回溯算法 366

14.2.2 解空间的表示 367

14.2.3 抽象回溯求解程序 368

14.2.4 分支界限求解程序 371

14.2.5 例2：再次分析0/1背包问题 372

14.3 自顶向下算法：分治算法 373

14.3.1 例1：二分法查找 373

14.3.2 例2：求解Fibonacci数 374

14.3.3 例3：归并排序 376

14.3.4 分治算法的运行时间 377

14.3.5 例4：矩阵相乘 379

14.4 自底向上算法：动态程序设计 381

14.4.1 例1：广义Fibonacci数 381

14.4.2 例2：求解二项式系数 382

14.4.3 应用：排版问题 384

14.5 随机化算法 387

14.5.1 产生随机数 387

14.5.2 随机变量 390

14.5.3 蒙特卡罗法 392

14.5.4 模拟退火法 394

习题 395

设计项目 396

第15章 排序算法和排序器 398

15.1 基础知识 398

15.2 排序和排序器 398

15.3 插入排序 401

15.3.1 直接插入排序 402

15.3.2 平均运行时间 402

15.3.3 二分法插入排序 403

15.4 交换排序 405

15.4.1 冒泡排序 405

15.4.2 快速排序 406

15.4.3 运行时间分析 410

15.4.4 平均运行时间 411

15.4.5 轴值的选择 413

15.5 选择排序 414

15.5.1 直接选择排序 414

15.5.2 堆排序 416

15.5.3 堆的建立 418

15.6 归并排序 421

15.7 排序算法的下界 425

15.8.1 桶式排序 426

15.8 分配排序 426

15.8.2 基数排序 428

15.9 算法性能分析 431

习题 433

设计项目 435

第16章 图和图算法 436

16.1 基础知道 437

16.1.1 图的表示法 440

16.2 图的实现 443

16.2.1 顶点的实现 443

16.2.3 抽象图和有向图 444

16.2.4 无向图的实现 447

16.2.5 边带权图和顶点带权图 448

16.2.6 图表示法的比较 449

16.3 图的遍历 451

16.3.1 深度优先遍历 451

16.3.2 广度优先遍历 453

16.3.3 拓扑排序 455

16.3.4 图遍历的应用：检查图的回路及连通性 458

16.4 最短路径算法 462

16.4.1 单源最短路径 462

16.4.2 每对顶点间的最短路径 467

16.5 最小支撑树 470

16.5.1 Prim算法 472

16.5.2 Kruskal算法 474

16.6 应用：关键路径分析 477

习题 482

设计项目 484

附录A C＋＋与面向对象编程 485

附录B 类层次图 505

附录C 字符码 506

参考答案 507