Python数据结构之集合（文末赠书）
点击标题下「异步社区」可快速关注
集合（collection），正如其名称所示，是可以作为概念性的单位来处理的一组零个或多个项。几乎软件的每一个重要部分都涉及集合的使用。尽管我们在计算机科学中所学的一些内容已经随着技术的变化逐渐消失，但组织集合的基本原理并没有变化。尽管集合在结构和用法上各不相同，但是，所有的集合都有着相同的基本作用，即帮助程序员有效地在程序中组织数据。
可以从两个视角来看待集合。集合的用户和客户关注它们在各种应用程序中能做些什么。集合的开发者和实现者关注它们作为通用资源的最佳性能。
本章将从这些集合的用户的角度给出不同类型的集合的概览。本章介绍了不同类型的集合、集合上常用的和可用的操作，以及常用的实现。
2.1 集合类型
你已经知道了，Python包含了几种内建的集合类型：字符串、列表、元组、集（set）和字典。字符串和列表可能是最常用和最基本的集合类型了。其他重要的集合类型还包括栈、队列、优先队列、二叉搜索树、堆、图、包（bag）和各种类型的有序集合。
集合可以是同构的，这意味着集合中的所有项必须具有相同的类型；也可以是异构的，这意味着这些项可以是不同的类型。尽管大多数的Python集合可以包含多种类型的对象，但是在很多编程语言中，集合是同构的。
集合通常是动态的而不是静态的，这意味着，它们可以随着问题的需要增加或缩小。此外，在程序的整个过程中，它们的内容是可以改变的。这一规则的一个例外是不可变集合，例如Python的字符串和元组。不可变集合的项是在其创建的过程中添加的，在此之后，就不能够再添加、删除或替换项了。
区分集合的另一个重要的特征是，它们的组织方式不同。本章介绍了集合的几个广泛分类的用法，包括线性集合、层级集合、图集合、无序集合和有序集合。
2.1.1 线性集合
线性集合中的项就像是排队的人一样，都是按照位置来有序的。除了第1项外，每个项都有一个唯一的前驱，并且除了最后一项，每个项都有一个唯一的后继。D2的前驱是D1，后继是D3，如图2.1所示。
图2.1 线性集合
线性集合的示例包括购物清单、一堆餐盘和ATM前等待的一队顾客。
2.1.2 层级集合
层级集合中的数据项，在结构中的顺序类似于一棵上下颠倒的树。除了最顶端的第一个数据项，每个数据项都只有一个前驱，称为其父亲，但是，可能有多个后继，称为其孩子。D3的前驱（父亲）是D1，其后继（孩子）是D4、D5和D6，如图2.2所示。
图2.2 层级集合
一个文件系统、一家公司的组织结构树，以及一本书的目录，都是层级集合的例子。
2.1.3 图集合
图集合也叫作图，这个集合中的每一项都可能有多个前驱和多个后继。如图2.3所示，连接到D3的所有元素，都被认为是其前驱和后继，并且它们也称为其邻居。
图2.3 图集合
城市之间的航线图和建筑物之间的电力连线图，都是图的例子。
2.1.4 无序集合
正如其名称所示，无序集合中的项没有特定的顺序，并且讨论一个项的前驱或后继也是没有意义的。图2.4展示了这样的一个结构。
图2.4 无序集合
一袋玻璃球就是无序集合的一个例子。尽管你可以将玻璃球放入到袋子之中，并且按照你想要的任何顺序从袋子中取出玻璃球，但玻璃球还是没有特定的顺序。
2.1.5 有序集合
有序集合在其项之上施加了一个自然的顺序。示例就是电话簿中的条目（20世纪的各种纸版的电话簿）和班级花名册中的条目。
为了施加一种自然的顺序，必须要有某种规则来比较各项，例如，itemi<= itemi+1，以便能够访问有序集合中的各个项。
有序列表是有序集合的一个最常见的例子，有序集合并不需要是线性的或者是按照位置来排序的。从客户的视角来看，集、包和字典可能都是有序的，即便它们的项并不是按照位置来访问的。层级集合的一种特殊的类型叫作二叉搜索树，它也是在其各项上施加了一种自然的顺序。
一个有序的集合，允许客户按照排好的顺序来访问其所有的项。一些操作，例如搜索，在有序的集合上可能也比在无序集合上更为高效。
2.1.6 集合类型的分类
记住了集合的主要类型，现在，我们可以将不同的常用集合类型分类了，如图2.5所示。这种分类的方法，将有助于我们组织在本书后面的各章中用来表示这些类型的Python类。
图2.5 集合类型的分类
注意，这个分类中的类型名称并不意味着集合的一个特定的实现，因为你稍后将会看到，一种特定类型的集合可能有多种实现。此外，其中的一些名称，例如“集合”和“线性集合”，指定了集合类型的分类，而不是指定了一个特殊的集合类型。然而，这些分类对于组织拥有相似性的特定类型的集合的特征和行为来说，还是很有用的。
2.2 集合上的操作
在一个集合上可以执行的操作，会根据所使用的集合类型的不同而有所不同，这些操作可以分为表2.1所示的几种类型。
表2.1 集合的操作的分类
操作分类 说明
确定大小 使用Python的len函数来获取集合中当前项的数目
测试项的成员关系 使用Python的in运算符在集合中搜索一个给定的目标项。如果找到这个项，返回True；否则的话，返回False
遍历集合 使用Python的for循环来访问集合中的每一个项。访问项的顺序取决于集合的类型
获取一个字符串表示 使用Python的str函数来获取集合的字符串表示
测试相等性 使用Python的==运算符来确定两个集合是否相等。如果两个集合具有相同的类型并且包含相同的项，那么它们是相等的。比较哪两对项的顺序，则取决于集合的类型
连接两个集合 使用Python的+运算符来获取和运算数相同类型的一个新的集合，并且这个新的集合中包含了两个运算数中的项
转换为另一种类型的集合 使用源集合中相同的项，来创建一个新的集合。克隆是类型转换的一种特例，其中，两个集合具有相同的类型
插入一项 给集合添加一项，可能在一个给定的位置添加
删除一项 从集合中删除一项，可能在一个给定的位置删除
替换一项 将删除和插入组合到一个操作之中
访问或获取一项 获取一项，可能从一个给定的位置获取
注意，这些操作中有几个和标准Python运算符、函数或控制语句相关，例如，in、+，len、str和for循环。我们已经熟悉了如何对Python字符串和列表使用它们。
对于Python中的插入、删除、替换或访问操作来说，并没有单独的名称。然而，有一些标准的变体。例如，pop方法用于从Python列表中给定的位置删除项，或者从Python字典中删除给定键的值。remove方法用于从Python集或列表中删除给定的项。随着在Python中尚未得到支持的新的集合类型被开发出来，针对它们的操作，我们将会尽全力使用标准的运算符、函数或方法名。
你可能不熟悉的一项集合操作是类型转换。我们已经了解了类型转换在输入数字时候的用法。在该环境中，我们从键盘接收数字的一个字符串，并对输入字符串应用int或float函数，将其转换为一个整数和浮点数（参见第1章了解详细情况）。
可以用相似的方式，把一种类型的集合转换为另一种类型的集合。例如，可以将Python字符串转换为Python列表，并且将Python列表转换为Python元组，如下面的代码所示：
message = "Hi there!"
lyst = list(message)
lyst
[’H’, ’i’, ’’, ’t’, ’h’, ’e’, ’r’, ’e’, ’!’]
toople tuple(lyst)
toople
(’H’, ’i’, ’’, ’t’, ’h’, ’e’, ’r’, ’e’, ’!’)list或tuple函数的参数不需要是另一个集合，它可以是任何可迭代的对象。可迭代的对象允许程序员使用Python的for循环来访问项的一个序列（是的，这听上去就像是一个集合，所有的集合也都是可迭代的对象）。例如，我们可以通过一个range函数来创建一个列表，如下所示：
lyst = list(range(1, 11, 2))
lyst
[1, 3, 5, 7, 9]其他的函数，如用于字典的dict函数，期待类型更加具体的可迭代对象作为其参数，例如(key, value)的元组的列表。
通常，如果省略了参数，集合的类型转换函数会返回该类型的一个新的、空的集合。
克隆是一种特殊的类型转化，它将参数的一个完全的副本返回给转换函数。在这种情况下，参数的类型和转换函数的类型应该是相同的。例如，如下的代码段产生了列表的一个副本，然后，使用is和==运算符来比较两个列表。如果两个列表不是相同的对象，is会返回False。尽管两个列表是不同的对象，但是由于它们具有相同的类型并且拥有相同的结果（两个列表中的每一个位置上的每一对元素都是相同的），==返回True。
lyst1 = [2, 4, 8]
lyst2 = list(lyst1)
lyst1 is lyst2
False
lyst1 == lyst2
True这个示例中的两个列表不仅拥有相同的结构，而且它们还拥有相同的项。也就是说，list函数对其参数列表进行了浅复制，这些项并没有在添加到新列表之前进行了自身的复制。
当这些项是不可变的时候（数字、字符串或Python元组），这一策略不会有问题。然而，当集合共享可变的项，将会引起副作用。为了防止这种情况发生，程序员可以通过编写在源集合上的一个for循环来创建深复制，这会在把项添加到新的集合之前，显式地复制其项。
后续的各章将会采取为大多数集合类型提供类型转换函数的策略。这个函数接受一个可迭代的对象作为可选的参数，并且对访问的各项执行浅复制。
2.3 集合的实现
实际上，和最初负责实现集合的程序员相比，负责编写使用集合的程序的那些程序员对这些集合有着不同的视角。
使用集合的程序员需要知道如何实例化和使用每一种集合类型。从他们的视角来看，集合是以某种预定义的方式存储和访问数据项的一种手段，他们并不关心集合实现的细节。换句话说，从用户的视角来看，集合是一个抽象体，正因为此，在计算机科学中，集合也称为抽象数据类型（abstract data types，ADT）。ADT的用户只关心其接口，或者说关心该类型的对象所识别的一组操作。
另一方面，集合的开发者则关心能以可能的、最为高效的方式来实现集合的行为，其目标是为集合的用户提供最佳性能。通常可能有大量的实现。然而，很多的实现都会占用太多的空间，或者运行得太慢，以至于我们认为不值得这么做。而剩下的那些实现，则倾向于基于几种基本的方法来组织和访问计算机内存。第3章和第4章将会详细介绍这些方法。
一些编程语言，例如Python，针对每种可用的集合类型只提供了一种实现。而像Java等其他语言，则提供数种实现。例如，Java的java.util包包含了列表的两个实现，分别是ArrayList和LinkedList。还有集和映射（就像Python的字典一样）各自的两个实现，分别是HashSet、TreeSet、HashMap和TreeMap。Java程序员对于每一个实现都使用相同的接口（一组操作），但是能够根据各种实现的性能特征和其他标准，从实现中自由地选取。本书的一个主要的目标是，让Python程序员能够具备和Java程序员一样的选择权。本书同时还会介绍抽象数据类型，并指出它们在任何一种语言中不可用的实现。对于每一种类型的集合（线性的、层级的、图的、无序的和有序的）。你将会看到一种或多种抽象集合类型，以及一种或多种实现。
抽象的思路并不是讨论集合的时候所独有的。在计算机科学领域之内和之外的很多场合，抽象都是一个重要的原理。例如，当学习下落物体上的重力作用的时候，你可能会尝试搭建一个实验条件，其中，你可以忽略掉物体的颜色和味道（例如，砸到牛顿的脑袋上的苹果）等无关紧要的细节。当学习数学的时候，你不需要关心用什么数字来统计鱼钩或箭镞，而是要试图发现数字的抽象和持久不变的原理。房屋的装修设计规划，是实体的房屋的一个抽象，它使你能够关注结构性要素而不必被诸如橱柜的颜色这样无关紧要的细节所淹没。结构性要素是那些对整个房屋的整体外观很重要的细节，并不涉及房屋的主要部件之间的关系。
在计算机科学中，抽象用于忽略或隐藏那些不重要的细节。软件系统通常是一层一层地构建的，每一层都被使用它的上一层当作是一个抽象体来对待。没有了抽象，你将需要同时考虑软件设计的所有方面，这是一项不可能完成的任务。当然，你最终必须考虑细节，但是，你可以在一个较小的、可管理的环境中做这些事情。
在Python中，函数和方法是抽象的最小单位，类是下一个较大的单位，而模块是最大的单位。本书介绍了将抽象集合类型作为类以及模块中相关的一组类而实现。组织这些类的通用性技术，则涉及面向对象编程，我们将会在第5章和第6章中介绍。本书所介绍的集合类的完整列表，可参见附录A。
2.4 小结
集合是保存0个或多个其他对象的对象。集合拥有访问对象、插入对象、删除对象、确定集合的大小以及遍历或访问集合的对象的操作。
集合的5个主要类别是：线性集合、层次集合、图集合、无序集合和有序集合。
线性集合按照位置来排列其项，除了第一项，每一项都有唯一的一个前驱，除了最后一项，每一个项都有唯一的一个后继。
层次集合中的项都拥有唯一的前驱（只有一个例外，就是顶层的项），以及0个或多个后继。单个的称为根的项是没有前驱的。
图中的项拥有0个或多个后继，以及0个或多个前驱。
无序集合中的项没有特定的顺序。
集合是可迭代的，可以用一个for循环来访问包含在集合中的每一项。
抽象的数据类型是一组对象，以及这些对象上的操作。因此，集合是抽象数据类型。
数据结构是表示集合中包含的数据的一个对象。
2.5 复习题
1．线性集合的例子是（ ）。
a．集和树
b．列表和栈
2．无序集合的例子是（ ）。
a．队列和列表
b．集和字典
3．层级集合可以表示（ ）。
a．银行排队的顾客
b．城市之间的航线
4．图集合可以表示（ ）。
a．数与集合
b．城市之间的航线图
2.6 编程项目
1．在一个shell提示符窗口中，使用dir和help函数，研究Python的内建集合类型str、list、tuple、set和dict。使用这两个函数的语法分别是dir()和help()。
2．为了和Python进行比较，浏览位于Java的java.util包中的集合类型，参见http:// docs.oracle.com/javase/7/docs/api/。
本文摘自《数据结构——python语言描述》
数据结构（Python语言描述）
作者： 【美】Kenneth A. Lambert（兰伯特）
在计算机科学中，数据结构是一门进阶性课程，概念抽象，难度较大。Python语言的语法简单，交互性强。用Python来讲解数据结构等主题，比C语言等实现起来更为容易，更为清晰。
本书第1章简单介绍了Python语言的基础知识和特性。第2章到第4章对抽象数据类型、数据结构、复杂度分析、数组和线性链表结构进行了详细介绍，第5章和第6章重点介绍了面向对象设计的相关知识、第5章包括接口和实现之间的重点差异、多态以及信息隐藏等内容，第6章主要讲解继承的相关知识，第7章到第9章以栈、队列和列表为代表，介绍了线性集合的相关知识。第10章介绍了各种树结构，第11章讲解了集和字典的相关内容，第12章介绍了图和图处理算法。每章最后，还给出了复习题和案例学习，帮助读者巩固和思考。
本书目录：(滑动手机查看)
第1章 Python编程基础 1
1．1 基本程序要素 1
1．1．1 程序和模块 1
1．1．2 Python程序示例：猜数字 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．12 print函数 5
1．1．13 input函数 5
1．1．14 类型转换函数和
混合模式运算 6
1．1．15 可选的和关键字
函数参数 6
1．1．16 变量和赋值语句 6
1．1．17 Python数据类型 7
1．1．18 import语句 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．1 41
3．2 复杂度分析 41
3．2．1 复杂度的阶 41
3．2．2 大O表示法 43
3．2．3 常量比例的作用 43
3．2．4 练习3．2 43
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．3 48
3．4 基本排序算法 48
3．4．1 选择排序 48
3．4．2 冒泡排序 49
3．4．3 插入排序 50
3．4．4 再谈最好情况、最坏情
况和平均情况的性能 52
3．4．5 练习3．4 52
3．5 更快的排序 53
3．5．1 快速排序简介 53
3．5．2 合并排序 56
3．5．3 练习3．5 59
3．6 指数算法：递归式的
Fibonacci 59
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．1 73
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．2 76
4．3 二维数组 77
4．3．1 处理网格 77
4．3．2 创建并初始化网格 77
4．3．3 定义Grid类 78
4．3．4 杂乱的网格和多维数组 79
4．3．5 练习4．3 79
4．4 链表结构 80
4．4．1 单链表结构和双链表
结构 80
4．4．2 非连续性内存和节点 81
4．4．3 定义一个单链表节点类 82
4．4．4 使用单链表节点类 82
4．4．5 练习4．4 84
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．5 92
4．6 链表的变体 92
4．6．1 带有一个哑头节点
的循环链表结构 92
4．6．2 双链表结构 93
4．6．3 练习4．6 95
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．1 103
5．2 开发一个基于数组的实现 103
5．2．1 选择并初始化数据
结构 103
5．2．2 先完成容易的方法 104
5．2．3 完成迭代器 105
5．2．4 完成使用迭代器
的方法 106
5．2．5 in运算符和__contains__
方法 106
5．2．6 完成remove方法 107
5．2．7 练习5．2 107
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．3 110
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．5 ArraySortedBag的运行
时间性能 118
6．1．6 Python中的类层级 118
6．1．7 练习6．1 119
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．2 124
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．1 131
7．3 栈的3种应用 131
7．3．1 计算算术表达式 131
7．3．2 计算后缀表达式 132
7．3．3 练习7．2 133
7．3．4 将中缀表达式转换为
后缀表达式 133
7．3．5 练习7．3 135
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．5 AbstractStack类的
作用 144
7．4．6 两种实现的时间和
空间分析 144
7．4．7 练习7．4 145
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．1 158
8．3 队列的两个应用 159
8．3．1 模拟 159
8．3．2 轮询CPU调度 161
8．3．3 练习8．2 161
8．4 队列的实现 161
8．4．1 队列的链表实现 161
8．4．2 数组实现 163
8．4．3 两种实现的时间和
空间复杂度分析 164
8．4．4 练习8．3 165
8．5 案例学习：模拟超市排队
结账 165
8．5．1 要求 165
8．5．2 分析 165
8．5．3 用户界面 166
8．5．4 类及其作用 166
8．6 优先队列 171
练习8．4 175
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．1 188
9．3 列表的应用 188
9．3．1 堆存储管理 188
9．3．2 组织磁盘上的文件 189
9．3．3 其他集合的实现 190
9．4 列表实现 191
9．4．1 AbstractList类的角色 191
9．4．2 基于数组的实现 192
9．4．3 链表实现 194
9．4．4 两种实现的时间和
空间分析 196
9．4．5 练习9．2 197
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．1 210
10．2 为什么要使用树 210
10．3 二叉树的形状 211
练习10．2 213
10．4 二叉树的3种常见应用 213
10．4．1 堆 213
10．4．2 二叉搜索树 214
10．4．3 表达式树 215
10．4．4 练习10．3 216
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．4 224
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．5 232
10．10 实现堆 232
练习10．6 234
10．11 小结 234
10．12 复习题 235
10．13 编程项目 236
第11章 集和字典 238
11．1 使用集 238
11．2 Python的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．1 241
11．3 集的基于数组和链表的实现 241
11．3．1 AbstractSet类 241
11．3．2 ArraySet类 242
11．4 使用字典 243
11．5 基于数组和基于链表的
字典实现 244
11．5．1 Item类 244
11．5．2 AbstractDict类 245
11．5．3 ArrayDict类 246
11．5．4 集和字典的基于数组
和列表的实现的复杂
度分析 247
11．5．5 练习11．2 248
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．3 254
11．7 案例学习：探查哈希策略 254
11．7．1 需求 255
11．7．2 分析 255
11．7．3 设计 256
11．8 集的哈希实现 258
11．9 字典的哈希实现 261
练习11．4 263
11．10 有序的集和字典 263
11．11 小结 264
11．12 复习题 264
11．13 编程项目 265
第12章 图 267
12．1 图的术语 267
练习12．1 269
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．2 273
12．4 图的遍历 273
12．4．1 泛型遍历算法 273
12．4．2 广度优先遍历和深度
优先遍历 274
12．4．3 图区域 275
12．4．4 练习12．3 276
12．5 图中的树 276
12．5．1 生成树和森林 276
12．5．2 最小生成树 277
12．5．3 最小生成树的算法 277
12．6 拓扑排序 279
12．7 最短路径问题 279
12．7．1 Dijkstra算法 280
12．7．2 初始化步骤 280
12．7．3 计算步骤 281
12．7．4 无限的表示和用法 282
12．7．5 分析 282
12．7．6 练习12．4 282
12．7．7 Floyd算法 283
12．7．8 分析 283
12．8 开发一个图集合 284
12．8．1 使用图集合的示例 284
12．8．2 LinkedDirected-
Graph类 285
12．8．3 LinkedVertex类 288
12．8．4 LinkedEdge类 289
12．9 案例学习：测试图算法 290
12．9．1 需求 290
12．9．2 分析 290
12．9．3 GraphDemoView类和
GraphDemoModel类 291
12．9．4 实现（代码） 292
12．10 小结 295
12．11 复习题 296
12．12 编程项目 297
附录 供Python程序员使用的
集合框架 299
上期获奖名单小福利
关注【异步社区】服务号，转发本文至朋友圈或 50 人以上微信群，截图发送至异步社区服务号后台，并在文章底下留言，分享你的python开发经验或者本书的试读体验，我们将从符合活动规则的读者中，随机选出 3位用户送出《数据结构 python语言描述》1本，赶快积极参与吧！
活动截止时间：2017 年 12月31日
lkkkkkkkkk 和 手持木剑入江湖
请获奖读者填写下方获奖信息，活动名称《异步社区 TensorFlow机器学习项目实战》https://www.wenjuan.in/s/m2iaqif/
点击图片参与活动
在“异步社区”后台回复“关注”，即可免费获得2000门在线视频课程；推荐朋友关注根据提示获取赠书链接，免费得异步图书一本。赶紧来参加哦！
扫一扫上方二维码，回复“关注”参与活动！
点击阅读原文，购买《数据结构 Python语言描述》
