数据结构和算法 Python和C++语言描述

目 录

第　1 章 抽象与分析　1

1.1　概要　1

1.1.1　大型编程.　1

1.1.2　前方的道路　2

1.2　功能的抽象　3

1.2.1　契约式设计　3

1.2.2　验证先验条件　6

1.2.3　自上而下的设计.　9

1.2.4　记录副作用.　11

1.3　算法分析.　12

1.3.1　线性搜索　12

1.3.2　二分搜索　14

1.3.3　非正式的算法比较.　15

1.3.4　算法的正式分析　17

1.3.5　大O 符号与Θ 符号　21

1.4　小结　23

1.5　练习　23

第　2 章 数据的抽象.　27

2.1　概要　27

2.2　抽象数据类型　27

2.2.1　从数据类型到抽象数据

类型.　28

2.2.2　定义抽象数据类型.　28

2.2.3　实现抽象数据类型.　30

2.3　抽象数据类型和对象　32

2.3.1　规范.　32

2.3.2　实现.　34

2.3.3　改变存储方式　35

2.3.4　面向对象的设计和编程.　36

2.4　抽象数据类型的实例：

数据集（Dataset）　38

2.4.1　面向对象设计的过程　38

2.4.2　定义一个抽象数据

类型.　39

2.4.3　实现这个抽象数据类型.　41

2.5　抽象数据类型的实例：

有理数（Rational）　.42

2.5.1　运算符重载.42

2.5.2　有理数（Rational）类44

2.6　增量开发以及单元测试45

2.7　小结48

2.8　练习48

第3　章 容器类52

3.1　概要52

3.2　Python 的列表52

3.3　顺序集合：扑克牌牌组53

3.4　有序集合：手牌.56

3.4.1　创建桥牌的手牌56

3.4.2　比较扑克牌.58

3.4.3　扑克牌排序.59

3.5　Python 里列表的实现61

3.5.1　基于数组的列表61

3.5.2　效率分析62

3.6　Python 的字典（选读） .63

3.6.1　字典抽象数据类型63

3.6.2　熟悉Python 字典.64

3.6.3　字典的实现.65

3.6.4　扩展示例：马尔可夫链67

3.7　小结70

3.8　练习71

第4　章 链式结构和迭代器.75

4.1　概要75

4.2　Python 的内存模型75

传递参数80

4.3　链表实现.81

4.4　链表抽象数据类型的实现.85

4.5　迭代器95

4.5.1　Python 的迭代器95

4.5.2　在链表（LList）里

添加迭代器.96

4.5.3　通过Python 的生成器来

迭代　97

4.6　基于游标的列表API（选读） .　99

4.6.1　游标（Cursor）的

API　99

4.6.2　Python 的游标列表

（CursorList）　100

4.6.3　链式结构的游标列表

（CursorList）　102

4.7　链表vs 数组　104

4.8　小结.　104

4.9　练习.　105

第5　章 堆栈和队列　109

5.1　概要.　109

5.2　堆栈.　109

5.2.1　堆栈抽象数据类型　109

5.2.2　堆栈的简单应用　110

5.2.3　堆栈的实现　112

5.2.4　应用程序：处理算术

方程.　113

5.2.5　应用程序：语法的处理

（选读）　.　116

5.3　队列.　119

5.3.1　队列抽象数据类型　119

5.3.2　队列的简单应用　120

5.4　队列的实现.　121

5.5　应用程序示例：队列的模拟

（选读）　.　123

5.6　小结.　128

5.7　练习.　128

第6　章 递归　133

6.1　概要.　133

6.2　递归定义　134

6.3　简单的递归示例　136

6.3.1　示例：字符串反转　136

6.3.2　示例：字谜　137

6.3.3　示例：快速计算指数.　138

6.3.4　示例：二分搜索　139

6.4　递归的分析.　140

6.5　排序.142

6.5.1　递归设计：归并排序142

6.5.2　分析归并排序.144

6.6　一个“难”题：汉诺塔146

6.7　小结.149

6.8　练习.150

第7　章 树156

7.1　概要.156

7.2　树的术语156

7.3　示例应用程序：表达式树158

7.4　树的存储方式159

7.5　应用：二叉搜索树.160

7.5.1　二分查找属性.160

7.5.2　实现一个二叉搜索树161

7.5.3　遍历整个二叉搜索树

（BST）　166

7.5.4　二叉搜索树（BST）的

运行时分析168

7.6　使用二叉搜索树（BST）来

实现映射（选读）169

7.7　小结.171

7.8　练习.172

第8　章 为Python 程序员准备的

C 简介.177

8.1　概要.177

8.2　C 的历史和背景178

8.3　注释、代码块、变量名和

关键字.182

8.4　数据类型和变量声明183

8.5　Include 语句、命名空间

以及输入/输出186

8.6　编译.189

8.7　表达式和运算符优先级191

8.8　条件语句193

8.9　数据类型转换196

8.10　循环语句197

8.11　数组199

8.11.1　一维数组199

8.11.2　多维数组201

8.11.3　字符数组.　201

8.12　函数的细节　202

8.12.1　声明、定义以及原型.　202

8.12.2　值传递　205

8.12.3　引用传递.　205

8.12.4　将数组作为参数传递.　206

8.12.5　常量参数　208

8.12.6　默认参数.　208

8.13　头文件和内联函数　209

8.14　断言与测试　213

8.15　变量的作用域以及生命周期.　214

8.16　Python 程序员编写C 程序

时的常见错误.　215

8.17　其他的C 相关话题

（选读）　216

8.17.1　C 的Switch 语句.　216

8.17.2　创建C 的命名空间.　218

8.17.3　全局变量.　219

8.18　小结　220

8.19　练习　220

第9　章 C 类.　224

9.1　基本的语法和语义.　224

9.2　字符串　232

9.3　文件输入和输出　234

9.4　运算符重载.　236

9.5　类变量和方法　242

9.6　小结.　246

9.7　练习.　246

第　10 章 C 的动态内存.　250

10.1　概要　250

10.2　C 的指针　254

10.3　动态数组　259

10.4　动态内存类　263

10.4.1　析构函数.　263

10.4.2　复制构造函数　265

10.4.3　赋值运算符　268

10.4.4　完整的动态数组类　270

10.4.5　引用返回类型　275

10.5　动态内存错误.　276

10.5.1　内存泄漏.276

10.5.2　访问无效内存277

10.5.3　内存错误总结280

10.6　小结281

10.7　练习281

第　11 章 C 的链式结构285

11.1　概要285

11.2　C 链式结构的类286

11.3　C 链表.288

11.4　C 链接的动态内存错误.298

11.5　小结299

11.6　练习300

第　12 章 C 模板.302

12.1　概要302

12.2　模板方法303

12.3　模板类.305

12.3.1　标准模板库的

vector　类305

12.3.2　用户定义的模板类.308

12.4　小结　311

12.5　练习312

第　13 章 堆、平衡树和散列表314

13.1　概要314

13.2　优先队列和堆.314

13.2.1　堆排序320

13.2.2　关于堆和优先队列

实现的说明320

13.3　平衡树.321

13.4　其他的树结构.329

13.5　散列表.329

13.6　小结339

13.7　练习339

第　14 章 图.343

14.1　概要343

14.2　图数据结构344

14.3　*短路径算法.347

14.3.1　无权*短路径347

14.3.2　加权*短路径350

14.4　深度优先算法.353

14.5　*小生成树　357

14.5.1　Kruskal 算法.　358

14.5.2　不交集数据结构.　358

14.5.3　Prim 算法　361

14.6　小结　361

14.7　练习　362

第　15 章 算法技术　365

15.1　概要　365

15.2　分治算法　365

15.2.1　分析递归函数　366

15.2.2　快速排序.368

15.3　贪心算法372

15.4　动态规划378

15.4.1　*长公共子序列379

15.4.2　记忆化382

15.4.3　矩阵链乘法382

15.5　NP 完全问题383

15.6　小结384

15.7　练习385

术语表387