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

本书使用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.2Python的列表52
3.3顺序集合：扑克牌牌组53
3.4有序集合：手牌56
3.4.1创建桥牌的手牌56
3.4.2比较扑克牌58
3.4.3扑克牌排序59
3.5Python里列表的实现61
3.5.1基于数组的列表61
3.5.2效率分析62
3.6Python的字典（选读）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.2Python的内存模型75
传递参数80
4.3链表实现81
4.4链表抽象数据类型的实现85
4.5迭代器95
4.5.1Python的迭代器95
4.5.2在链表（LList）里添加迭代器96
4.5.3通过Python的生成器来迭代97
4.6基于游标的列表API（选读）99
4.6.1游标（Cursor）的API99
4.6.2Python的游标列表（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.2C++的历史和背景178
8.3注释、代码块、变量名和关键字182
8.4数据类型和变量声明183
8.5Include语句、命名空间以及输入/输出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.16Python程序员编写C++程序时的常见错误215
8.17其他的C++相关话题（选读）216
8.17.1C++的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.2C++的指针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.2C++链式结构的类286
11.3C++链表288
11.4C++链接的动态内存错误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.1Kruskal算法358
14.5.2不交集数据结构358
14.5.3Prim算法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.5NP接近问题383
15.6小结384
15.7练习385
术语表387