2. 有序线性表¶
2.1. 学习目标¶
区分有序顺序（Ordered）与排序顺序（Sorted Order）
描述线性表抽象数据类型与有序线性表抽象数据类型之间的区别
实现并使用有序线性表抽象数据类型
根据需要从其他课程页面添加学习目标
2.1.1. 建议阅读：¶
选自 Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry 的第 16 章：有序线性表（Sorted Lists）
2.2. 思考顺序（Order）与排序顺序（Sorted Order）¶
考虑一下目前讨论过的各种数据结构。这些数据结构各自都提供了若干特征、属性（字段）和行为（操作或方法），以及排列和操作所存数据的方式。
某个给定的数据结构有时可能被认为适合用于某些应用，通常是因为它所提供的特性支持该特定应用需求的实现和运行。
而在其他时候，某个给定的数据结构又可能被认为不适合用于某个应用，或许是因为它提供的特性是多余的、受限的、无益的，并且不支持该软件应用的需求和运行。
例如，我们可能还记得，Bags 在顺序无关紧要的应用中很有用，即结构中存储的数据顺序不影响应用需求和系统运行的场合。
Bags 本质上就是无序的。
然而，有些应用保持顺序，更具体地说是保持 已排序 的顺序，是非常重要的。值得注意的是，我们刻意对 顺序（Order） 与 排序顺序（Sorted Order） 做了区分。
2.2.1. 交互式：有序线性表简介¶
跟着做、练习与探索
下载并自行探索视频中的接口文件（见下面）。同时跟着视频的幻灯片一起学习。
ListInterface.java
(right click-> save link as...)
SortedListInterface.java
(right click-> save link as...)
SortedListsOrderVsSorted.pdf
2.3. 线性表 ADT¶
线性表（List）被认为是元素或对象的有序集合（ordered collection），也称为元素序列。
这意味着客户端代码可以通过元素的整数索引或在线性表中的"位置"来访问线性表的元素。线性表的元素被认为是按这个索引或"位置"排列的。
虽然集合中的元素被认为具有特定的顺序，但这些线性表元素的排列并不是基于元素的值，而是基于它们的索引。
线性表未必处于排序顺序，例如一个数字线性表可能是 7,22,-45,89。
2.3.1. 有序线性表抽象数据类型¶
因此，有序线性表（Sorted List）是以排序顺序排列的元素或对象的集合，其中：
元素的排列基于与元素的值或对象的"状态"相关的属性（所谓对象的状态，指的是它的每个字段的值）
每个元素都是相同类型（通过继承和多态，线性表可以用来容纳可比较类型的某种组合）
有序线性表的一个例子可以是名字列表，即以字母顺序排列的 String 存储。在计算机领域，我们通常称之为字典序（lexicographic 或 lexical order）。
就像线性表和许多其他数据结构一样，有必要实现一些方法，使客户端代码能够添加新元素、移除元素，并跟踪和管理有序线性表中的元素数量。在本模块的后续学习中，你将探索线性表与有序线性表及其实现之间的异同。
2.4. 有序线性表接口（Sorted ListInterface）¶
注意 SortedListInterface 的 UML 只包含一个 add 方法，并且没有 replace 方法。
跟着做、练习与探索
下载并在 Eclipse 中自行运行和探索视频中的对应项目。示例项目需要 CS-GraphWindowLib 项目。它也会用在你平时的课程项目中。要下载 CS-GraphWindowLib，你必须先完成第一次实验的配置步骤。然后就可以通过 Eclipse 使用蓝色向下箭头图标，或使用项目菜单并选择"Download Assignment..."来下载。
exSortedLists.zip
2.5. 检查点 1¶
2.6. 有序线性表抽象数据类型的实现方法¶
在很多方面，我们可以从概念上把有序线性表抽象数据类型看作具有修改特征和额外"排序"逻辑的线性表抽象数据类型。因此，回顾线性表抽象数据类型的实现将有助于我们思考实现有序线性表抽象数据类型的各种方法。
此外，线性表抽象数据类型的实现与有序线性表抽象数据类型的实现往往非常相似，这为代码复用提供了机会。
事实上，仔细考虑和比较某些线性表抽象数据类型方法与有序线性表抽象数据类型方法的预期行为就会发现，其中不少方法具有相同的行为，因此可以用完全相同的方式实现。例如 getEntry(givenPosition)、getLength()、isEmpty() 和 toArray() 只是其中几个无论在线性表实现还是有序线性表实现中实现方式都相同的方法。
另一方面，也有一些线性表抽象数据类型方法，与有序线性表抽象数据类型中名称相同但行为不同。
add(newEntry) 方法是线性表抽象数据类型中一个需要重大修改才能作为有序线性表抽象数据类型 add(newEntry) 方法使用的方法。线性表抽象数据类型的 add(newEntry) 方法只是把 newEntry 添加到下一个可用的线性表位置，而有序线性表抽象数据类型的 add(newEntry) 方法则必须为要添加的 newEntry 找到合适的位置，一个能够保持排序顺序的位置。
实现有序线性表抽象数据类型有多种设计方法，例如：从头编写、使用组合（composition）、使用继承。
2.6.1. 从头编写¶
实现有序线性表抽象数据类型的一种方式就是简单地从头编写。我们已经熟悉线性表抽象数据类型的实现，可以借鉴这一经验来实现有序线性表抽象数据类型。由于两种抽象数据类型之间的相似性，大部分方法都可以采用与其他线性表相同的方式编写。少数特定的方法需要以不同的方式编写，以确保保持排序顺序，即线性表在其整个生命周期和方法执行过程中始终保持有序。
选择从头编写时，我们还有两个进一步的选择。与实现线性表抽象数据类型类似，我们可以选择以下方式之一：
使用数组实现
使用链式实现
2.6.2. 使用组合（包装器）实现¶
这种方法使用线性表抽象数据类型的实现来支持有序线性表抽象数据类型的实现。在这种实现方法中，有序线性表（Sorted List）使用一个线性表抽象数据类型的实例（它拥有（has-a）一个线性表，因此使用组合（Composition）这个术语），这个线性表抽象数据类型实例被设置为 SortedList 的一个字段，然后 SortedList 充当客户端代码，调用并管理线性表方法的使用，为 SortedList 的操作服务。这将在本模块后面的内容中进一步详细阐述。
2.6.3. 使用继承实现¶
这种方法同样使用线性表抽象数据类型的实现来支持有序线性表抽象数据类型的实现，不过这次是通过 is-a（是一种）或继承关系。
既然我们可以把有序线性表（SortedList）看作具有修改特征和额外"排序"逻辑的线性表，那么就可以得出结论：有序线性表是一种线性表（is-a List），从而获得继承的好处。线性表成为父类，有序线性表成为线性表的子类，继承父类的方法。由于某些有序线性表的方法与线性表抽象数据类型的对应方法相比必须表现不同，因此在定义有序线性表类时，我们必须重写这些方法。具体来说，我们必须重写那些无助于保持排序顺序的方法。例如，add(int newPosition, T newEntry) 和 replace(givenPosition,newEntry) 这样的方法会让客户端代码控制新条目的位置，这并不合适，因为它可能影响有序线性表的排序顺序。add(newEntry) 方法也需要修改。此外，有序线性表还需要线性表不具备的特性，这就要求我们添加这些新方法，例如有序线性表抽象数据类型的 remove(anEntry) 和 getPosition(anEntry) 方法。
2.7. 从头实现有序线性表抽象数据类型¶
2.7.1. 使用底层数组实现有序线性表抽象数据类型¶
2.7.2. 使用底层链式结构实现有序线性表抽象数据类型¶
2.7.3. 反思效率¶
下面给出了线性表抽象数据类型和有序线性表抽象数据类型上各操作的最坏情况效率，包括基于数组的实现和基于链式的实现。请查看每张表，注意异同，然后思考实现细节会如何影响各个方法的效率。
下表描绘了两种实现下有序线性表抽象数据类型各操作的最坏情况效率。
例如，考虑一下新的有序线性表抽象数据类型方法 getPosition(…)。
getPosition(…) 方法接收 anEntry 作为参数，然后搜索整个线性表，以定位 anEntry 在线性表中的位置。在其最基本的实现中，getPosition(...) 方法使用线性查找在线性表中定位 anEntry，将线性表中每个位置的内容与 anEntry 比较，直到找到 anEntry 或检查完所有位置。
找到 anEntry 后，方法返回 anEntry 在线性表中首次或唯一出现的整数位置。如果在线性表中未找到 anEntry，方法随后返回一个整数，其值表示未在线性表中找到 anEntry。设置这个值来表示未找到 anEntry 的方法有很多：有些开发者会返回一个无效位置，例如 -1，作为查找失败的标志。其他开发者可能会选择返回一个大于线性表条目数的值，还有些人则倾向于返回如果 anEntry 存在时它在线性表中应该出现的位置，但以负整数表示。
请注意，当前该方法的效率在基于数组和基于链式的实现中都是 $O(n)$。这在意料之中，因为线性表有 n 个元素，那么对线性表进行线性查找 anEntry 自然需要检查全部 n 个元素。
然而这并不是最高效的选择。利用有序线性表（SortedList）处于排序顺序这一事实，可以提高该方法的效率。不必为了查找 anEntry 而遍历整个线性表，一旦搜索越过该元素应该在的位置就可以停止；如果在找到 anEntry 之前搜索遇到的元素大于 anEntry，方法就可以确定 anEntry 不在线性表中。getPosition() 方法还可以进一步改进，使用二分查找而不是线性查找。
2.8. 使用组合实现有序线性表抽象数据类型¶
2.8.1. 组合方法的效率¶
下面给出了组合实现下线性表抽象数据类型和有序线性表抽象数据类型上各操作的最坏情况效率。请查看每张表，注意异同，然后思考实现细节会如何影响各个方法的效率。注意图 16-9 中链式有序线性表组合方法的最坏情况效率与图 16-5 中从头编写有序线性表方法的最坏情况效率有明显不同。
下表描绘了使用线性表抽象数据类型实例实现时，有序线性表抽象数据类型各操作的最坏情况效率。
下表描绘了使用数组或链式结构实现时有序线性表抽象数据类型各操作的最坏情况效率，作为与组合实现的对比。
