国外著名高等院校信息科学与技术优秀教材 数据结构和算法 Python和C++语言描述
作者：戴维 M.瑞德，约翰 策勒 著，肖鉴明 译
出版时间： 2020年版
内容简介
本书使用Python 和C++两种编程语言来介绍数据结构。全书内容共15 章。书中首先介绍了抽象与分析、数据的抽象等数据结构的基本原理和知识，然后结合Python 的特点介绍了容器类、链式结构和迭代器、堆栈和队列、递归、树；随后，简单介绍了C++语言的知识，并进一步讲解了C++类、C++的动态内存、C++的链式结构、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
