最近评论
正在载入评论列表...
本章介绍ADT表，ADT表适用于必须通过值来管理数据的问题。我们将阐述使用数组、链表和二叉查找树的表实现，并分析各自的优缺点。
为在表的各种实现之间作出明智选择，必须分析各种实现支持表操作的效率，例如，本章分析基于数组和基于引用的表实现的效率，并得出结论：在很多应用程序中，这些实现都不能高效地执行表操作，必须使用更复杂的、基于二叉查找树的表实现。
本章还介绍了表的一个重要变体，即ADT优先队列。该ADT提供的操作能够轻松地检索和删除包含最大值的项。使用二叉查找树可以实现优先队列，但有一个更简单的树结构—— 堆，更能满足要求。
12.1 ADT表
上一章介绍过面向值的ADT，其操作形式如下：
● 插入包含值x的数据项。
● 删除包含值x的数据项。
● 查询包含值x的数据项的相关信息。
很多应用程序需要此类面向值的操作。例如，下列任务涉及值，而不涉及位置：
● 查找John Smith的电话号码。
● 删除ID号码为12908的雇员的所有信息。
本节将介绍另一种面向值的ADT。
通过ADT的名称，常令人想到具有ADT类似属性的对象。例如，“栈”令人想起一叠盘子。谈到“表”，有人会想起红褐色的咖啡桌，有人则联想到如图12-1所示的世界主要城市表。
该表包含各个城市的一些信息，您可以从中查找信息。例如，若要了解伦敦的人口，则可从“城市”列的顶端开始查找，直至找到伦敦为止。因为城市按字母表顺序排列，所以也可进行二叉查找。从靠近表中间的位置开始查找，确定伦敦在哪一半，并对伦敦所在的一半再次进行二叉查找。由前述知，二叉查找要比从头遍历整个表有效得多。
|
城市 |
国家 |
人口 |
|
雅典 |
希腊 |
2 500 000 |
|
巴塞罗纳 |
西班牙 |
1 800 000 |
|
开罗 |
埃及 |
9 500 000 |
|
伦敦 |
英国 |
9 400 000 |
|
纽约 |
美国 |
7 300 000 |
|
巴黎 |
法国 |
2 200 000 |
|
罗马 |
意大利 |
2 800 000 |
|
多伦多 |
加拿大 |
3 200 000 |
|
威尼斯 |
意大利 |
300 000 |
图12-1 一个普通的城市表
若要查找意大利有哪些主要城市，则只能遍历整个表。按字母表顺序排列的城市名对该问题不起作用。该表的组织形式方便了给定城市的查找，而对于其他问题，则需要遍历整个表。
ADT表(或词典)也可以用于查找信息，并有一个查找信息的专用操作。ADT表的项一般是包含一些数据片断的记录。为便于项的检索，可根据指定的关键字进行查找。例如，在城市表中，若需要经常检索与城市相关的信息，则可将city指定为查找关键字。改进表的实现，可以快速检索查找关键字与某个值匹配的项。不过，若要根据各个记录中未包含在查找关键字中的值检索项，则必须检索整个表。所以，查找关键字的选择为ADT实现者传递以下信息：
应恰当地排列数据，以便于根据查找关键字的值查找项。
定义ADT表的基本操作如下：
(1) 创建空表。
(2) 确定表是否为空。
(3) 确定表中的项数。
(4) 将新项插入表。
(5) 从表中删除包含给定查找关键字的项。
(6) 从表中检索包含给定查找关键字的项。
(7) 按有序的查找关键字顺序遍历表项。
为简单起见，设表中所有项的查找关键字各不相同。在这个假设下，若表中一项已存在某个查找关键字，则不能插入查找关键字与它相同的项。下面的伪码为ADT表指定了操作，且表中各项的查找关键字各不相同。图12-2是类Table的UML图。
图12-2 类Table的UML图
//TableItemType is the type of the items stored in the table,
//KeyType is the type of the search key value.
+createTable()
// Creates an empty table.
+tableIsEmpty():boolean {query}
// Determines whether a table is empty.
+tableLength():integer {query}
// Determines the number of items in a table.
+tableInsert(in newItem: TableItemType) throws
TableException
// Inserts newItem into a table whose items have distinct
// search keys that differ from newItem's search key.
// Throws TableException if the insertion is not
// successful.
+tableDelete(in searchKey:KeyType)
// Deletes from a table the item whose search key equals
// searchKey. Returns false if no such item exists.
// Returns true if the deletion was successful.
+tableRetrieve(in searchKey:KeyType) : TableItemType
// Returns the item in a table whose search
// key equals searchKey. Returns null
// if no such item exists.
+tableTraverse(): TableItemType
// Traverses a table in sorted search-key order.
当然，这些操作只是表操作的一个子集。客户程序可能需要这些操作子集，也可能需要此处未列出的其他操作，以满足应用程序的要求，还可能需要修改一些操作的定义。例如，这些操作假设，任意两个表项的查找关键字都不相同，而在很多应用程序中，要求查找关键字相同是很合理的。若出现此类情况，就必须重新定义一些操作，以消除查找关键字重复所引发的二义性。例如，若几个项的查找关键字都等于指定的值，则tableRetrieve应返回哪一项？应根据具体情况调整ADT表的定义。
对有些应用程序而言，前面操作集合中的tableInsert、tableDelete和tableRetrive可满足要求。但是，若不添加其他操作，则一些重要任务无法完成。例如，不能执行诸如“显示所有表项”的任务。这是因为，只有知道查找关键字的值，才能检索数据项。这样，只有遍历表，才能显示整个表。
在定义遍历操作时，必须指定tableTraverse的访问顺序。一种常见规范是访问按查找关键字排序的项，但也可能并不关心遍历操作的访问顺序。后面将看到，定义tableTraverse的方式可能影响实现表的方法。
表项的查找关键字对表的实现至关重要。只要数据项存储在表中，该项的查找关键字值将保持不变，这很重要。若更改表中已有元素的查找关键字，将无法查找该元素或其他表元素。也就是说，查找关键字的值不可修改。应为表项使用一个类；该类将查找关键字包含为一个数据字段，还包含一个访问该查找关键字数据字段的方法。这同于第11章介绍的KeyedItem类。
package SearchKeys;
public abstract class KeyedItem<KT extends
Comparable <? super KT>> {
private KT searchKey;
public KeyedItem(KT key) {
searchKey = key;
} // end constructor
public KT getKey() {
return searchKey;
} // end getKey
} // end KeyedItem
回顾一下，扩展KeyedItem的类只有用于初始化查找关键字的构造函数。这样，在构建数据项后，将不能更改查找关键字的值，从而满足了此处的要求。
设表项是下面的类的实例：
import SearchKeys.KeyedItem;
public class City extends KeyedItem<String> {
private String city; // city's name
private String country; // city's country
private int pop; // city's population
. . .
// implementation of methods for accessing private
// data fields
} // end City
要在该表中执行以下任务：
● 按字母表顺序显示各个城市名及人口
● 将各个城市的人口增加10%
● 删除人口小于1 000 000的所有城市
由这些任务可知，应将city指定为查找关键字。City类包含城市的所有信息，包括城市名(由被继承方法getKey返回)、国家和人口。下面是City类的Java定义。
import SearchKeys.KeyedItem;
public class City extends KeyedItem<String> {
// city's name will be designated as search key
private string country; // city's country
private int pop; // city's population
public City(String theCity, string theCountry,
int newPop) {
super(theCity); // makes city name the search key
country = theCountry;
pop = newPop;
} // end constructor
public string toString() {
return getKey() + ", "+ country + .... + pop;
} // end toString
// The methods getCountry, setCountry, getPopulation,
// and setPopulation appear here.
. . .
// end City
第一项任务要求按字母表顺序写出城市名。这样，tableTraverse必须按照查找关键字，根据字母表顺序访问各项。要实现tableTraverse，一种方法是为ADT表定义一个迭代器。用这个迭代器类的实例来访问各个表项，并将其传给displayItem方法，displayItem方法的伪码如下：
+displayItem(in anItem: TableItemType)
Display anItem.getCity()
Display anitem.getPopulation()
这个迭代器的访问顺序对其他两项任务的意义不大。要执行第二项任务，可将迭代器访问的各个项传递给updatePopulation方法：
+updatePopulation(in anItem: TableItemType)
anItem.setPopuolation(1.1*anItem.getPopulation())
要执行第三项任务，可将迭代器访问的各项传给deleteSmall方法：
deleteSmall(inout table:Table, in anItem: TableItemType)
if(anItem.getPopulation()<1000000)
table.tableDelete(anItem)
不过，该任务并不像看上去那么简单。删除一项，意味着在使用迭代器进行遍历的过程中更改了表。迭代器下一步将访问哪一项？很明显，它将访问被删除项的后一项，但是，迭代器是这么做，还是忽略该项？在使用迭代器时，一般用迭代器的remove方法来执行删除，以澄清关于迭代器的删除语义。在后面介绍的两种表实现中，迭代器的定义和remove操作留作练习。
下面的接口TableInterface归纳了表操作。注意第一个数据类型参数反映了表项的类型，第二个参数是查找关键字的数据类型。
package Tables;
import SearchKeys.KeyedItem;
public interface TableInterface<T extends KeyedItem<KT>,
KT extends Comparable <? super KT>> {
// Table operations:
// Precondition for all operations:
// No two items of the table have the same search key.
// The table's items are sorted by search key.
public boolean tableIsEmpty();
// Determines whether a table is empty.
// Postcondition: Returns true if the table is
// empty; otherwise returns false.
public int tableLength();
// Determines the length of a table.
// Postcondition: Returns the number of items in the
// table.
public void tableInsert(T newItem)
throws TableException;
// Inserts an item into a table in its proper sorted
// order according to the item's search key.
// Precondition: The item to be inserted into the
// table is newItem, whose search key differs from
// all search keys presently in the table.
// Postcondition: If the insertion was successful,
// newItem is in its proper order in the table.
// Otherwise, the table is unchanged, and
// TableException is thrown.
public boolean tableDelete(KT searchKey);
// Deletes an item with a given search key from a
// table.
// Precondition: searchKey is the search key of the
// item to be deleted.
// Postcondition: If the item whose search key equals
// searchKey existed in the table, the item was
// deleted and method returns true. Otherwise, the
// table is unchanged and the method returns false.
public KeyedItem tableRetrieve(KT searchKey);
// Retrieves an item with a given search key from a
// table.
// Precondition: searchKey is the search key of the
// item to be retrieved.
// Postcondition: If the retrieval was successful,
// the table item with the matching search key is
// returned. If no such item exists, the method
// returns a null reference.
} // end TableInterface
12.1.1 选择实现
在前面各章，ADT实现要么基于数组，要么基于引用，即用数组或链表存储ADT的项。这样的实现统称为线性实现，因为它们逐一表示数据结构中的各个项，体现出图12-1中城市表的平面的、类似于列表的外观。
表的线性实现当然可行，包括以下四种类型：
● 无序，基于数组
● 无序，基于引用
● 有序(按查找关键字)，基于数组
● 有序(按查找关键字)，基于引用
无序的实现不按顺序存储元素，可以将新项插入任意位置。而有序的实现必须将新元素插入由查找关键字确定的适当位置。不管无序还是有序，基于数组和基于引用的线性实现都包含如图12-3所示的基本结构。这些实现都维护表中的当前项数。后面将看到，无序实现和有序实现各有优缺点。
图12-3 图12-1中ADT表的两种有序线性实现的数据字段：(a)基于数组；(b)基于引用
回顾前面介绍的ADT可发现，表的实现还有其他选择。例如，可用ADT列表、有序表或二叉查找树来实现ADT表。图12-4显示了使用二叉查找树的实现，这是一个非线性实现的例子；与线性实现方式相比，它有多种优点。例如，可以重用第11章介绍的基于ADT二叉查找树的实现。基于ADT列表和ADT有序表的实现也有这个优点。将此作为编程问题，请读者自己分析。
图12-4 图12-1中ADT表的二叉查找树实现的数据字段
本章的一个主要目标是：说明应用程序的要求如何影响实现的选择。此处阐释第10章的10.1.4节的论述。有些应用程序需要前面给出的ADT表的所有操作，而其他应用程序只需要其中的一个子集，还需要更多的操作。在选择ADT表的实现前，应认真分析应用程序需要哪些操作。总是选择所有的操作是一种错误的策略，因为就某些操作而言，一种实现比另一种实现更高效。因此，若包含一个从不使用的操作，则最终选择的ADT实现并不完全符合要求。
我们不仅要了解给定的应用程序需要哪些操作，还必须了解该应用程序执行各个操作的大体频率。有些应用程序要求多次执行每个操作，而其他应用程序则不然。例如，若维护如图12-1所示的主要城市列表，则要频繁执行检索操作，插入和删除操作的执行次数就相对较少。若很少插入元素，则表实现方案包含低效的插入操作是可接受的；只要常用操作的效率高，就达到了目的。当然，如第10章所述，若一个ADT操作用于事关生死的情况，则该操作必须高效，即使很少使用，也必须确保效率。在为应用程序选择ADT的实现时，需要考虑的因素有：需要什么操作，这些操作的执行频率，以及操作要求的响应时间。当然，如第10章所述，除效率外，也要考虑其他因素。
现在考虑几种不同的应用场景，在这些场景中，都需要表操作的某种组合。通过分析ADT表的各种实现，将说明算法分析的一些基本注意事项。了解如何为给定的应用程序选择实现方式，以高效地支持需要的表操作组合。
1. 场景A：无序插入和遍历
Mary的女生联谊会计划为一家本地慈善团体募集资金。Mary对以前的募捐者颇为不满，建议开一个座谈会，以征求新的募捐策略。每当女生联谊会的成员提出意见后，Mary就将其想法插入表，记录下来。此后，打印当前表中的所有意见。设报表的组织形式无关紧要，可以是有序的，也可以是无序的。另设检索、删除或有序遍历等操作不发生，或极少发生，不影响实现方式的选择。
对这个应用程序而言，有序维护元素没有意义。实际上，若不有序地维护表，tableInsert操作会非常高效。两种无序的线性实现都可将新元素插入任何方便的位置。基于数组的无序实现可将新元素插入数组的最后一项，即位置item[size]。图12-5(a)显示在更新size后的插入结果。基于引用的实现只需将新元素插入链表开头。如图12-5(b)所示，head引用新项，而新项引用链表原来的第一项。这样，不仅可将新项快速插入表的无序实现中，也可使tableInsert为O(1)：无论表有多大，两种实现需要的时间都不变。
图12-5 无序线性实现的插入操作：(a)基于数组；(b)基于引用
是选择基于数组的实现，还是基于引用的实现？与其他ADT一样，若预先不知道表有多大，则使用动态分配内存的实现较合适。Mary的座谈会就属于这种类型。另一方面，若已经知道表的最大项数不会远超预期的项数，则可任意选择。
这个应用程序应考虑基于二叉查找树的实现吗？因为这个实现要排序表项，所以工作量超出了应用程序的要求。如第11章所述，实际上，在平均情况下，二叉查找树的插入操作为O(logn)。
2. 场景B：检索
在使用字处理程序的词典来查找单词的同义词时，将用到检索操作。若ADT表用来表示词典，则每个表项都是一个记录，其中包含两个单词：一个是查找关键字，一个是单词的同义词。因为经常执行检索操作，所以要求表的实现能根据查找关键字的值高效地查找项目。但一般不会更改词典，所以不需要插入或删除操作。
对于基于数组的实现，若数组已排序，则可用二叉查找来检索某个单词的记录。而基于引用的实现需要从头遍历链表，直至找到该单词为止。很明显，二叉查找需要的时间远远少于遍历链表的时间。此时，出现了两个问题：
(1) 链表可以使用二叉查找吗？
(2) 数组的二叉查找比链表的顺序查找高效，但其效率高出多少？
能在基于引用的实现中执行二叉查找吗？可以，但效率过低，无法应用于实际。考虑二叉查找算法的第一个步骤：
查找表中的“中间”项
若链表中有n项，如何得到链表的中间项？可从头遍历链表，直至访问了n/2项为止。通过第二个问题的答案可以看到，仅第一步占用的时间通常就超过了数组整个二叉查找的时间。而且，在每个递归步骤，都包含查找“中间”元素的问题。因此，为基于引用的线性实现执行二叉查找不切实际。这个结论非常重要。
另一方面，若数组items中有n项，则中间项在位置n/2，并可直接访问。与必须检查表中每一项的算法相比，数组的二叉查找需要的时间要少得多。“少得多”的含义是什么？由前述知，若不能执行二叉查找，则必须检查表中的每一项，要么找到查找关键字中包含指定值的项，要么确定该项不存在。换言之，若表的大小为n，则需要检查n项，查找操作为O(n)。使用二叉查找，效率能提高多少？由第10章知，在最坏的情况下，二叉查找为O(log2 n)，O(log2 n)比O(n)算法高效得多。例如，log21 024=10，log21 048 567=20。对于大型表而言，二叉查找的优点十分突出。
词典可能很大，所以必须选择可使用二叉查找的实现。由上面的分析可知，不应使用基于引用的线性实现。因为知道词典的大小，所以基于数组的有序实现符合本例的要求。
对于检索占主导地位的应用程序而言，基于二叉查找树的实现也是一个不错的选择。如第11章所述，对于平衡树，二叉查找树的查找操作为O(log n)。因为词典不发生变化，所以可构建一棵平衡树，并确保查找的高效性。
3. 场景C：有序插入、删除、检索和遍历
若本地图书馆的图书编目已实现计算机化，则在访问编目时可执行检索操作。图书管理员使用插入和删除操作更新编目，并遍历编目，以将整个编目存入文件。可以想象，检索是最频繁的操作，而其他操作也时有发生，不能忽略(若可忽略，则该问题等同于场景B)。
要在表中插入查找关键字为X的项，则首先要确定该项在表中的正确位置。同样，要在表中删除查找关键字为X的项，则必须首先定位该项。这样，tableInsert和tableDelete操作将执行以下步骤：
(1) 在表中查找某项的位置。
(2) 在这个位置插入(或删除)。
若表的实现基于数组(而不基于引用)，则第1步更高效。对于基于数组的实现，在插入时，可用二叉查找确定新项X的插入位置，在删除时，可用二叉查找来定位。而对于基于引用的实现，由场景B的讨论知，二叉查找不适用，而必须从头遍历链表，直至找到链表中的适当位置为止。由场景B还可知，数组的二叉查找比遍历链表省时得多。
对于tableInsert和tableDelete操作的第1步，基于数组的实现非常便于执行二叉查找，因而更高效。但在第2步实际插入或删除数据项时，情况迥异，基于引用的实现要好得多。在基于数组的实现中，tableInsert必须移动数组项，为新项腾出空间，见图12-6(a)；tableDelete则必须移动数组项，以填充删除数据项时留下的间隙。在最坏的情况下，需要移动所有的数组项。而基于引用的实现只需更改两个引用，即可完成第2步，如图12-6(b)所示。
图12-6 有序链表实现中的插入操作：(a)基于数组；(b)基于引用
纵观第1步和第2步可知，对于tableInsert和tableDelete，基于数组的有序实现与基于引用的有序实现所需的时间大体相同，都是O(n)。这两种实现都不能很好地支持这些操作。不过，基于二叉查找树的实现组合了两种线性实现的最佳特性。它基于引用，避免了移动数据，而且表可根据需要动态增长。另外，还可从二叉查找树中高效地检索数据项。
4. 小结
ADT表的基于数组的无序实现可在数组末端高效地插入数据项。但是，在执行删除操作时，需要移动数据，以消除数组中留下的空隙。因为数据项是无序的，所以执行检索时，需要进行顺序查找。
基于数组的有序实现一般在插入和删除时都需要移动数据。但在执行检索操作时，可使用高效的二叉查找，因为数据项是有序的。
基于引用的无序实现可在链表开头高效地插入项。删除操作需要顺序查找，但不需要移动数据。检索操作也要求顺序查找。
基于引用的有序实现在执行插入和删除时，都需要顺序查找，但不需要移动数据。检索操作也需要顺序查找。
这些线性实现不够精巧，需要的时间一般也比基于二叉查找树的实现多，但在很多应用程序中，它们仍然很有用。线性实现在概念上易于理解，如果表包含的项不多，可以将它们运用于表。在这种情况下，简单性和清晰性比效率显得更重要。对于可以使用无序表，而且很少执行删除操作的应用程序而言，即使表包含的项很多，也可以用线性实现。
相对于线性实现，ADT表的非线性二叉查找树一般是一个更好的选择。若n节点的二叉树具有最小高度，即高为
，则ADT表的基于二叉查找树的实现显著优于线性实现。在插入和删除的第1步以及检索操作中，定位项的效率相当于二叉查找的效率。另外，二叉查找树的基于引用的实现允许动态分配节点，因此可以处理最大项数未知的表。该实现还可以高效地执行插入和删除操作的第2步：在实际插入和删除节点时，只需更改几个引用 (如果要删除的节点有两个子节点，还需要遍历到中序后继，这个遍历过程很短)，而不需要像基于数组的实现那样，移动所有的表项。总之，基于二叉查找树的实现兼具两种线性实现的最佳特性，同时摒弃了它们的缺点。
如第11章所述，二叉查找树的高度取决于在树中执行插入和删除操作的顺序，最高为n。若插入和删除操作的顺序是随机的，则二叉查找树的高度非常接近于其最小值。本例不需要考虑树高的增长，不过，高度的增长会降低效率。如果使用第13章介绍的一直保持平衡的二叉查找树的变体，则可将树的高度保持在log2(n)附近。
图12-7总结了本章讨论的表实现的插入、删除、检索和遍历操作的阶。
插入 删除 检索 遍历
无序，基于数组 O(1) O(n) O(n) O(n)
无序，基于指针 O(1) O(n) O(n) O(n)
有序，基于数组 O(n) O(n) O(log n) O(n)
有序，基于指针 O(n) O(n) O(n) O(n)
二叉查找树 O(log n) O(log n) O(log n) O(n)
图12-7 各种实现的ADT表操作的平均阶
12.1.2 ADT表的基于数组的有序实现
由前述知，ADT表采用二叉查找树的实现尽乎完美。尽管如此，还需要研究ADT表的线性实现。原因有三：第一，也是最重要的，具体问题应具体分析。如第9章所述，不要过度地分析问题。若问题的规模很小，则各种解决方案的效率并没有明显的区别。对于ADT表，若表很小，使用线性实现就足够了，而且，这样做还易于理解。
第二个原因是效率。在某些情况下，线性实现非常高效。例如，对于场景A，线性实现最佳，因为主要操作是无序的插入和遍历。在场景B中，主要操作是检索，若最大项数已知，采用基于数组的有序实现就足够了。在此类情况下，从简单的角度讲，即使对于大型表，也应使用线性实现，而不应使用二叉查找树。
第三个原因是动机。在分析不适于采用线性实现的场景时：必须摒弃数组实现方案，去考虑其他实现，如二叉查找树。比较线性实现和二叉查找树，可以更明确地看到这些不足。
下面基于数组的有序实现设查找关键字唯一。章末的练习题7要求去除这个假设。为节省空间，此处省略了初始条件和结束条件，实际上，它们与本章前面TableInterface的描述是相同的。
package Tables;
import SearchKeys.KeyedItem;
import java.util.ArrayList;
//****************************************************************
// ADT table.
// Sorted array-based implementation.
// Assumption: A table contains at most one item with a
// given search key at any time.
//****************************************************************
public class TableArrayBased<T extends KeyedItem<KT>, KT extends
Comparable<? Super KT>> implements TableInterface<T, KT>{
final int MAX_TABLE = 100; // maximum size of table;
protected ArrayList<T> items; // table items
public TableArrayBased() {
items = new ArrayList<T>(MAX_TABLE);
} // default constructor
public boolean tableIsEmpty()
return size==0;
} // end tableIsEmpty
public int tableLength() {
return items.size();
} // end tableLength
public void tableInsert(T newItem)
throws TableException {
// Calls: position.
if (tableLength()< MAX TABLE) {
// there is room to insert;
// locate the position where newItem belongs
int spot = position(newItem.getKey());
if ((spot < tableLength()) &&
(items[spot].getKey()).compareTo(newItem.getKey())==0) {
// we have found a duplicate key
throw new TableException("Table Exception: "+
"Insertion failed, duplicate key item");
}
else {
// ArrayList automatically shifts items to make room
// for the new item
Items.add(spot, newItem);
} // end if
}
else {
throw new TableException("TableException: Table full");
} // end if
} // end tableInsert
public boolean tableDelete(KT searchKey) {
// Calls: position.
// locate the position where searchKey exists/belongs
int spot = position(searchKey);
// is searchKey present in the table?
boolean success = (spot <= tableLength()) &&
(items.get(spot).getKey().compareTo(searchKey)==0);
if (success) {
// searchKey in table
// ArrayList automatically shifts items
Items.remove(spot);
} // end if
return success;
} // end tableDelete
public T tableRetrieve(KT searchKey) {
// Calls: position.
// locate the position where searchKey exists/belongs
int spot = position(searchKey);
// is searchKey present in table?
boolean success = (spot <= tableLength()) &&
(items.get(spot).getKey().compareTo(searchKey)==0);
if (success) {
return items.get(spot); // item present; retrieve it
}
else {
return null;
} // end if
} // end tableRetrieve
protected int position(KT searchKey) {
// Finds the position of a table item or its insertion
// point.
// Precondition: searchKey is the value of the search key
// sought in the table.
// Postcondition: Returns the index (between 0 and
// size - 1) of the item in the table whose search key
// equals searchKey. If no such item exists, returns the
// position (between 0 and size) that the item would
// occupy if inserted into the table. The table is
// unchanged.
int pos = 0;
while ((pos < tableLength()) &&
(searchKey.compareTo(items.get(pos).getKey()) > 0)) {
pos++;
} // end while
return pos;
} // end position
} // end TableArrayBased
12.1.3 ADT表的基于二叉查找树的实现
线性实现只适用于特定的应用程序，不适于作为ADT表的通用实现。
下面基于引用的非线性实现使用二叉查找树表示ADT表的项。换言之，TableBSTBased类将二叉查找树作为一个数据字段。这样，TableBSTBased重用了第11章的BinarySearchTree类。此处省略了初始条件和结束条件，实际上，它们与本章前面给出的描述是相同的。
package Tables;
import BinaryTrees.BinarySearchTrees;
import BinaryTrees.TreeException;
import SearchKeys.KeyedItem;
// Assumes that the binary search tree created in Chapter 11
// is contained in a package called BinaryTrees.
// *****************************************************
// Implementation of a tabie using a binary search tree.
// Assumption: A table contains at most one item with a
// given search key at any time.
// *****************************************************
public class TableBSTBased<T extends KeyedItem<KT>, KT extends
Comparable<? Super KT>> implements TableInterface<T, KT> {
// binary search tree that contains the table's items
protected BinarySearchTree<T, KT> bst;
protected int size; // number of items in the table
public TableBSTBased() {
bst = new BinarySearchTree<T, KT> ();
size = 0;
} // end default constructor
// table operations:
public boolean tableIsEmpty() {
return size == 0;
} // end tableIsEmpty
public int tableLength() {
return size;
} // end tableLength
public void tableInsert(T newItem)
throws TableException {
if (bst.retrieve(newItem.getKey()) == null) {
bst.insert(newItem);
++size;
}
else {
throw new TableException("Table Exception: Insertion"
+" failed, duplicate key item");
} // end if
} // end tableInsert
public T tableRetrieve(KT searchKey) {
return bst.retrieve(searchKey);
} // end tableRetrieve
public boolean tableDelete(KT searchKey) {
try {
bst.delete(searchKey);
} // end try
catch (TreeException e) {
return false;
} // end catch
--size;
return true;
} // end tableDelete
protected void setSize(int newSize) {
size = newSize;
} // end setSize
} // end TableBSTBased
下面的语句显示了如何在需要ADT表的程序中使用该类。
import Tables.*;
class TestTable {
public static void displayCity(City c)
System.out.println(c.getCity());
} // end displayCity
// Main entry point
public static void main(String[] args) {
TableInterface<City, String> chart =
new TableBSTBased<City, String> ();
City c;
c = new City("Narragansett", "USA", 12000);
chart.tableInsert(c);
c = new City("Ocracoke", "USA", 3000);
chart.tableInsert(c);
// If a table iterator class called TableIteratorBST
// is available for the class TableBSTBased (as created
// in Programming Problem 2), you also can do the
// following:
TableIteratorBST<City> iter = new TableIteratorBST<City> (chart);
while (iter.hasNext()) {
displayCity((City)iter.next());
} // end while
} // end main
} // end TestTable
