数据结构与算法 面向对象的C++设计模式PDF|Epub|txt|kindle电子书版本网盘下载

数据结构与算法 面向对象的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 渐近上界——大О表示法26

3．1．1 一个简单的例子26

第3章 渐近表示法26

3．1．2 大О表示法中的错误与陷阱27

3．1．3 大О的特性28

3．1．4 多项式30

3．1．5 对数31

3．1．6 紧凑大О界32

3．1．7 大О表示法中更多的错误与陷阱33

3．1．8 常用的大О表达式34

3．2 渐近下界——Ω表示法34

3．2．1 一个简单的例子35

3．2．2 再次关于多项式35

3．4 算法渐近分析37

3．3 更多的表示法——？及小ο表示法37

3．4．1 运行时间分析的大О规则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和ListAsLinkedList141

7．1．4 应用142

7．2 排序表145

7．2．1 排序表的数组表示法146

7．2．2 排序表的链表表示法149

7．2．3 比较SortedListAsArray和SortedListAsLinkedList150

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＋＋ Magic335

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：O/I背包问题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：再次分析O/I背包问题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