编辑推荐

不管你是程序设计爱好者、计算机专业的学生还是一位专业程序员，《数据结构 Python语言描述》都是你通过Python编程语言学习面向对象设计和数据结构的不错的入门教程。通过清晰的示例、按部就班的讲解以及众多实用的练习，《数据结构 Python语言描述》教你通过Python理解并使用数据结构。
●使用多态和继承来设计集合类；
●集合接口的多个实现；
●不同的集合实现的时间/空间代价分析。

内容简介

在计算机科学中，数据结构是一门进阶性课程，概念抽象，难度较大。Python语言的语法简单，交互性强。用Python来讲解数据结构等主题，比C语言等实现起来更为容易，更为清晰。
《数据结构Python语言描述》第1章简单介绍了Python语言的基础知识和特性。第2章到第4章对抽象数据类型、数据结构、复杂度分析、数组和线性链表结构进行了详细介绍，第5章和第6章重点介绍了面向对象设计的相关知识、第5章包括接口和实现之间的重点差异、多态以及信息隐藏等内容，第6章主要讲解继承的相关知识，第7章到第9章以栈、队列和列表为代表，介绍了线性集合的相关知识。第10章介绍了各种树结构，第11章讲解了集和字典的相关内容，第12章介绍了图和图处理算法。每章最后，还给出了复习题和案例学习，帮助读者巩固和思考。
《数据结构Python语言描述》不仅适合高等院校计算机专业师生阅读，也适合对Python感兴趣的读者和程序员阅读。

作者简介

KennethA.Lambert是华盛顿与李大学的计算机科学教授和系主任。他教授编程课程30年，并且是计算机科学教育的积极研究者。Lambert编著以及与人合著了一共25本教材，包括与DouglasNance和ThomasNaps编写的一系列C++入门教材，与MartinOsborne编写的一系列Java入门教材，以及一系列Python入门教材。他还是《EasyGUIProgramminginPython》的作者。

目录

第1章Python编程基础1
1．1基本程序要素1
1．1．1程序和模块1
1．1．2Python程序示例：猜数字1
1．1．3编辑、编译并运行
Python程序2
1．1．4程序注释3
1．1．5词法元素3
1．1．6拼写和命名惯例3
1．1．7语法元素4
1．1．8字面值4
1．1．9字符串字面值4
1．1．10运算符和表达式5
1．1．11函数调用5
1．1．12print函数5
1．1．13input函数5
1．1．14类型转换函数和
混合模式运算6
1．1．15可选的和关键字
函数参数6
1．1．16变量和赋值语句6
1．1．17Python数据类型7
1．1．18import语句7
1．1．19获取关于程序组件
的帮助7
1．2控制语句8
1．2．1条件式语句8
1．2．2使用if__name__==
"__main__"9
1．2．3循环语句10
1．3字符串及其运算10
1．3．1运算符10
1．3．2格式化字符串以便输出11
1．3．3对象和方法调用13
1．4内建Python集合及其操作13
1．4．1列表14
1．4．2元组14
1．4．3遍历序列14
1．4．4字典15
1．4．5搜索一个值15
1．4．6对集合应用模式匹配15
1．5编写新的函数16
1．5．1函数定义16
1．5．2递归函数17
1．5．3嵌套的函数定义19
1．5．4高阶函数19
1．5．5使用lambda表达式
创建匿名函数20
1．6捕获异常20
1．7文件及其操作21
1．7．1文本文件的输出22
1．7．2将数字写入到一个
文本文件22
1．7．3从文本文件读取文本23
1．7．4从文件读取数字24
1．7．5使用pickle读写对象24
1．8创建新的类25
1．9编程项目28
第2章集合概览30
2．1集合类型30
2．1．1线性集合30
2．1．2层级集合31
2．1．3图集合31
2．1．4无序集合31
2．1．5有序集合31
2．1．6集合类型的分类32
2．2集合上的操作32
2．3集合的实现34
2．4小结35
2．5复习题35
2．6编程项目36
第3章搜索、排序和复杂度分析37
3．1评估算法的性能37
3．1．1度量算法的运行时间37
3．1．2统计指令39
3．1．3度量算法所使用的内存41
3．1．4练习3．141
3．2复杂度分析41
3．2．1复杂度的阶41
3．2．2大O表示法43
3．2．3常量比例的作用43
3．2．4练习3．243
3．3搜索算法44
3．3．1搜索最小值44
3．3．2顺序搜索一个列表44
3．3．3最好情况、最坏情况和
平均情况的性能45
3．3．4有序列表的二叉搜索45
3．3．5比较数据项47
3．3．6练习3．348
3．4基本排序算法48
3．4．1选择排序48
3．4．2冒泡排序49
3．4．3插入排序50
3．4．4再谈最好情况、最坏情
况和平均情况的性能52
3．4．5练习3．452
3．5更快的排序53
3．5．1快速排序简介53
3．5．2合并排序56
3．5．3练习3．559
3．6指数算法：递归式的
Fibonacci59
3．7案例学习：算法探查器61
3．7．1需求61
3．7．2分析61
3．7．3设计62
3．7．4实现（编写代码）63
3．8小结65
3．9复习题66
3．10编程项目67
第4章数组和链表结构69
4．1数组数据结构69
4．1．1随机访问和连续内存71
4．1．2静态内存和动态内存72
4．1．3物理大小和逻辑大小72
4．1．4练习4．173
4．2数组的操作73
4．2．1增加数组的大小73
4．2．2减小数组的大小74
4．2．3在数组中插入一项74
4．2．4从数组中删除一项75
4．2．5复杂度权衡：时间、
空间和数组76
4．2．6练习4．276
4．3二维数组77
4．3．1处理网格77
4．3．2创建并初始化网格77
4．3．3定义Grid类78
4．3．4杂乱的网格和多维数组79
4．3．5练习4．379
4．4链表结构80
4．4．1单链表结构和双链表
结构80
4．4．2非连续性内存和节点81
4．4．3定义一个单链表节点类82
4．4．4使用单链表节点类82
4．4．5练习4．484
4．5单链表结构上的操作84
4．5．1遍历84
4．5．2搜索85
4．5．3替换86
4．5．4在开始处插入86
4．5．5在末尾插入87
4．5．6从开始处删除87
4．5．7从末尾删除88
4．5．8在任何位置插入89
4．5．9从任意位置删除90
4．5．10复杂度权衡：时间、
空间和单链表结构91
4．5．11练习4．592
4．6链表的变体92
4．6．1带有一个哑头节点
的循环链表结构92
4．6．2双链表结构93
4．6．3练习4．695
4．7小结95
4．8复习题96
4．9编程项目96
第5章接口、实现和多态98
5．1开发接口98
5．1．1定义包接口98
5．1．2指定参数和返回值99
5．1．3构造方法和实现类101
5．1．4先验条件、后验条件、
异常和文档101
5．1．5用Python编写接口102
5．1．6练习5．1103
5．2开发一个基于数组的实现103
5．2．1选择并初始化数据
结构103
5．2．2先完成容易的方法104
5．2．3完成迭代器105
5．2．4完成使用迭代器
的方法106
5．2．5in运算符和__contains__
方法106
5．2．6完成remove方法107
5．2．7练习5．2107
5．3开发一个基于链表的实现107
5．3．1初始化数据结构108
5．3．2完成迭代器109
5．3．3完成clear和add方法109
5．3．4完成remove方法109
5．3．5练习5．3110
5．4两个包实现的运行时性能110
5．5测试两个包实现111
5．6用UML图表示包资源112
5．7小结113
5．8复习题113
5．9编程项目114
第6章继承和抽象类115
6．1使用继承定制一个已有的类115
6．1．1已有类的子类化115
6．1．2再谈__init__方法116
6．1．3添加新的contains方法117
6．1．4修改已有的add方法117
6．1．5ArraySortedBag的运行
时间性能118
6．1．6Python中的类层级118
6．1．7练习6．1119
6．2使用抽象类去除代码冗余性119
6．2．1设计一个
AbstractBag类119
6．2．2重新编写AbstractBag
中的__init__方法120
6．2．3修改AbstractBag
的子类120
6．2．4将AbstractBag中的
__add__方法泛化121
6．3所有集合的一个抽象类122
6．3．1将AbstractCollection
整合到集合层级中122
6．3．2在__eq__方法中使用
两个迭代器123
6．3．3练习6．2124
6．4小结124
6．5复习题124
6．6编程项目125
第7章栈127
7．1栈概览127
7．2使用栈128
7．2．1栈接口128
7．2．2初始化一个栈129
7．2．3示例应用程序：
匹配括号129
7．2．4练习7．1131
7．3栈的3种应用131
7．3．1计算算术表达式131
7．3．2计算后缀表达式132
7．3．3练习7．2133
7．3．4将中缀表达式转换为
后缀表达式133
7．3．5练习7．3135
7．3．6回溯算法135
7．3．7内存管理137
7．4栈的实现138
7．4．1测试驱动程序138
7．4．2将栈添加到集合层级中139
7．4．3数组实现140
7．4．4链表实现141
7．4．5AbstractStack类的
作用144
7．4．6两种实现的时间和
空间分析144
7．4．7练习7．4145
7．5案例学习：计算后缀表达式145
7．5．1要求145
7．5．2分析145
7．5．3设计148
7．5．4实现150
7．6小结153
7．7复习题153
7．8编程项目154
第8章队列156
8．1队列概览156
8．2队列接口及其应用157
练习8．1158
8．3队列的两个应用159
8．3．1模拟159
8．3．2轮询CPU调度161
8．3．3练习8．2161
8．4队列的实现161
8．4．1队列的链表实现161
8．4．2数组实现163
8．4．3两种实现的时间和
空间复杂度分析164
8．4．4练习8．3165
8．5案例学习：模拟超市排队
结账165
8．5．1要求165
8．5．2分析165
8．5．3用户界面166
8．5．4类及其作用166
8．6优先队列171
练习8．4175
8．7案例学习：急症室调度175
8．7．1需求175
8．7．2分析175
8．7．3类176
8．7．4设计和实现177
8．8小结179
8．9复习题179
8．10编程项目180
第9章列表182
9．1概览182
9．2使用列表183
9．2．1基于索引的操作183
9．2．2基于内容的操作183
9．2．3基于位置的操作184
9．2．4列表的接口187
9．2．5练习9．1188
9．3列表的应用188
9．3．1堆存储管理188
9．3．2组织磁盘上的文件189
9．3．3其他集合的实现190
9．4列表实现191
9．4．1AbstractList类的角色191
9．4．2基于数组的实现192
9．4．3链表实现194
9．4．4两种实现的时间和
空间分析196
9．4．5练习9．2197
9．5实现列表迭代器197
9．5．1列表迭代器的角色
和作用197
9．5．2设置和实例化一个
列表迭代器类198
9．5．3列表迭代器中的导
航方法199
9．5．4列表迭代器中的修
改器方法200
9．5．5链表列表的列表迭
代器的设计201
9．5．6列表迭代器实现的
时间和空间分析201
9．6案例学习：开发一个有序
的列表201
9．6．1要求201
9．6．2分析202
9．6．3设计202
9．6．4实现（代码）204
9．7小结205
9．8复习题205
9．9编程项目206
第10章树208
10．1树的概览208
10．1．1树的术语208
10．1．2普通的树和二叉树209
10．1．3树的递归定义210
10．1．4练习10．1210
10．2为什么要使用树210
10．3二叉树的形状211
练习10．2213
10．4二叉树的3种常见应用213
10．4．1堆213
10．4．2二叉搜索树214
10．4．3表达式树215
10．4．4练习10．3216
10．5二叉树的遍历216
10．5．1前序遍历216
10．5．2中序遍历217
10．5．3后序遍历217
10．5．4层序遍历217
10．6开发二叉搜索树217
10．6．1二叉搜索树接口218
10．6．2链表实现的数据结构219
10．6．3二叉搜索树的复杂度
分析223
10．6．4练习10．4224
10．7递归的后代解析和编程语言224
10．7．1语法简介224
10．7．2在语言中识别、解析
和解释句子226
10．7．3词法分析和扫描器226
10．7．4解析策略227
10．8案例学习：解析和表达式树227
10．8．1要求227
10．8．2分析228
10．8．3节点类的设计和实现228
10．8．4解析器类的设计和
实现230
10．9二叉树的数组实现231
练习10．5232
10．10实现堆232
练习10．6234
10．11小结234
10．12复习题235
10．13编程项目236
第11章集和字典238
11．1使用集238
11．2Python的set类239
11．2．1集的一个示例会话239
11．2．2集的应用240
11．2．3集和包的关系240
11．2．4集和字典的关系240
11．2．5集的实现240
11．2．6练习11．1241
11．3集的基于数组和链表的实现241
11．3．1AbstractSet类241
11．3．2ArraySet类242
11．4使用字典243
11．5基于数组和基于链表的
字典实现244
11．5．1Item类244
11．5．2AbstractDict类245
11．5．3ArrayDict类246
11．5．4集和字典的基于数组
和列表的实现的复杂
度分析247
11．5．5练习11．2248
11．6哈希策略248
11．6．1冲突和密度的关系249
11．6．2非数字键的哈希250
11．6．3线性探测251
11．6．4二次探测252
11．6．5链化253
11．6．6复杂度分析253
11．6．7练习11．3254
11．7案例学习：探查哈希策略254
11．7．1需求255
11．7．2分析255
11．7．3设计256
11．8集的哈希实现258
11．9字典的哈希实现261
练习11．4263
11．10有序的集和字典263
11．11小结264
11．12复习题264
11．13编程项目265
第12章图267
12．1图的术语267
练习12．1269
12．2为什么使用图270
12．3图的表示270
12．3．1相邻矩阵270
12．3．2邻接表271
12．3．3两种表示的分析272
12．3．4运行时间的进一步
考虑272

12．3．5练习12．2273
12．4图的遍历273
12．4．1泛型遍历算法273
12．4．2广度优先遍历和深度
优先遍历274
12．4．3图区域275
12．4．4练习12．3276
12．5图中的树276
12．5．1生成树和森林276
12．5．2最小生成树277
12．5．3最小生成树的算法277
12．6拓扑排序279
12．7最短路径问题279
12．7．1Dijkstra算法280
12．7．2初始化步骤280
12．7．3计算步骤281
12．7．4无限的表示和用法282
12．7．5分析282
12．7．6练习12．4282
12．7．7Floyd算法283
12．7．8分析283
12．8开发一个图集合284
12．8．1使用图集合的示例284
12．8．2LinkedDirected-
Graph类285
12．8．3LinkedVertex类288
12．8．4LinkedEdge类289
12．9案例学习：测试图算法290
12．9．1需求290
12．9．2分析290
12．9．3GraphDemoView类和
GraphDemoModel类291
12．9．4实现（代码）292
12．10小结295
12．11复习题296
12．12编程项目297
附录供Python程序员使用的
集合框架299

精彩书摘

　　《数据结构Python语言描述》：
　　这些因素也可以输入到一个模拟程序中，程序随后确定要接待的顾客的数目、每位顾客等待服务的平均时间，以及在模拟时间段的最后还在排队的顾客的数目。通过改变输入，特别是顾客到达的频率和可用的收银员的数目，模拟程序就能够帮助经理在每天的繁忙时段和空闲时段做出有效的人手调配决策。通过添加一个输入来量化不同的结账设备的效率，经理甚至可以判断增加更多的收银员还是购买更好、更多的高效设备更划算。
　　这两个例子有-个共同的特征，这通常也是模拟问题的特征，就是基本的因素是随时变化的。考虑顾客到达收款台的频率，如果顾客按照准确的时间间隔到达，每个人都购买相同数目的商品，确定需要多少个收银员在岗就变得很容易了。然而，这样的规律并不能反映出超市的实际情况。有的时候，几个顾客实际上会在同一时刻出现，另一些时候，则是几分钟也没有新的顾客到来。此外，每个顾客所购买的商品数目不同，因此，每个顾客所需服务的工作量也不同。所有这些变化使得很难设计出一个公式来解决有关该系统的简单问题，例如，顾客的等待时间是如何随着在岗的收银员的数目而变化的。另一方面，一个模拟程序通过模拟实际情况并收集相应的统计数据，从而避免了公式化的需要。
　　模拟程序使用一种简单的技术来模拟可变性。例如，假设新的顾客按照平均每4分钟一次的频率达到。那么，在每分钟的模拟时间中，一个程序可以生成0到1之间的一个随机数。如果这个数小于1／4，程序会给结账队伍添加一个新的顾客；否则，它不会这么做。基于概率分布函数的一个较为复杂的方案，能够产生更加逼真的结果。显然，每次程序运行的时候，结果都会略有改变，但是，这只会增加模拟的真实性。
　　……

其他推荐