1. 包(bag)¶
1.1. 学习目标¶
完成本模块后,学生将能够:
说出基本 Java 数据结构的功能和用途
说明 Java 中包(bag)的关键特征
在 Java 中构建并填充包(bag)
1.1.1. 建议阅读¶
第 1-2 章:来自 Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry 的包(Bags)章节
1.2. 包简介¶
数据结构提供了一种组织和操作数据集合的模型。它们是抽象数据类型(Abstract Data Type,ADT)的一个例子。以前,如果你想存储一个表示室温恒温器温度设置的整数值,例如,你会使用这样的语句:
int temp = 75;
然而,如果你必须存储并跟踪一栋商业建筑 500 个房间的恒温器温度设置,该怎么办?为每个房间创建一个 int 变量将十分繁琐。从概念上讲,客户端代码可以把数据分组到合适的数据结构中,例如,一个线性表或一个包。然后客户端代码可以相应地与之交互,例如添加或移除条目。就恒温器温度设置的例子而言,客户端代码会向选定的数据结构添加一个整数值,用来表示商业建筑中每个房间的温度设置。当然,我们需要一种方法来识别哪个整数值与给定的房间相关联,诸如此类的问题将在本课程的后续内容中详细探讨。常见的入门级线性数据结构有包、栈、队列和线性表。数据结构也可以组织成树或图,以及多维结构,它们可以按位置索引,也可以按键索引,例如字典。
本模块介绍包抽象数据类型。它是一个没有特定顺序的有限对象集合,可以包含重复项。包在日常生活中一直用于组织和整理对象集合,例如背包中的物品、购物袋,或者你在这十年里看过的电影。一个包对象的可能行为有:获取包中存储的条目数、检查包是否为空、添加和移除对象、遍历包中的条目,以及检查包中是否包含某个特定对象。
在设计包(Bag)类时,开发者需要考虑很多事情。要实现一个包,需要规定它的数据和各种方法。在设计方法应以何种方式工作时,我们需要考虑方法预期行为的各个方面。其中关键的一点是考虑当任务无法完成时应该发生什么:代码应该静默失败,通知客户端代码任务无法完成的事实,还是采取其他某种做法?
开发者在实现数据结构时也有很多选择。一个关键的决定是如何实际存储数据。客户端代码通过调用包的公开方法与包交互,但在底层,包可能用数组或结点的链式结构来构建。其他数据结构实现决策涉及确定各种算法,以高效地实现规定的方法。
1.3. Bag 接口方法的文档¶
在查看包抽象数据类型的实现之前,我们首先来看接口。
1.3.1. BagInterface 的 UML 图¶
下图展示了 BagInterface 类的 UML 表示法。
你可能还记得,UML 是统一建模语言(Unified Modeling Language)的简称,它是一种用于捕获、可视化并交流系统设计的标准化建模语言。
UML 图有很多种。在本课程的大部分学习中,我们将使用与下图类似的图,这些图被称为 UML 类图。
观察类图如何快速传达给定系统中软件组件的名称和特征。一眼就能看出,这张图描述了一个接口的规范,它指出了所有实现 BagInterface 的类应该共有的方法,也就是说,所有包的实现中都应该存在的方法。它还指出了字段和方法的访问修饰符,以及每个方法的参数和返回类型的详细信息。在这种情况下,你会注意到每个方法名称左侧的标注表示每个方法都是公开的。
1.3.2. BagInterface 代码示例¶
下面你会找到实现 BagInterface 的示例代码。
看一下实现(代码)是如何与设计文档(UML 类图)相对应的。
包接口
package bag;
/**
An interface that describes the operations of a bag of objects.
A bag is an unordered collection of objects of a particular types.
Duplicates are allowed.
@author Frank M. Carrano
@author Timothy M. Henry
@author Margaret Ellis
@version April 2020
*/
public interface BagInterface<T>
{
/** Gets the current number of entries in this bag.
@return The integer number of entries currently in the bag. */
public int getCurrentSize();
/** Sees whether this bag is empty.
@return True if the bag is empty, or false if not. */
public boolean isEmpty();
/** Adds a new entry to this bag.
@param newEntry The object to be added as a new entry.
@return True if the addition is successful, or false if not. */
public boolean add(T newEntry);
/** Removes one unspecified entry from this bag, if possible.
@return Either the removed entry, if the removal.
was successful, or null. */
public T remove();
/** Removes one occurrence of a given entry from this bag.
@param anEntry The entry to be removed.
@return True if the removal was successful, or false if not. */
public boolean remove(T anEntry);
/** Removes all entries from this bag. */
public void clear();
/** Counts the number of times a given entry appears in this bag.
@param anEntry The entry to be counted.
@return The number of times anEntry appears in the bag. */
public int getFrequencyOf(T anEntry);
/** Tests whether this bag contains a given entry.
@param anEntry The entry to locate.
@return True if the bag contains anEntry, or false if not. */
public boolean contains(T anEntry);
/** Retrieves all entries that are in this bag.
@param values An array of generics to be filled with bag contents, if
not large enough will throw ArrayIndexOutOfBoundsException
@return The values array filled with the entries in the bag.
Note: If the bag is empty, the array is returned unmodified */
public T[] toArray(T[] values);
} // end BagInterface
1.4. 交互式:Bag 接口方法的文档¶
1.5. 交互式:使用包¶
1.6. 检查点 1¶
1.7. 包的数组实现¶
1.7.1. 建议阅读¶
第 2 章:来自 Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry 的使用数组的包实现
1.8. 交互式:固定大小数组实现¶
1.8.1. ArrayBagsWithJUnitExample 类图¶
让我们看看设计规范的演变。
固定大小数组实现视频描述了包抽象数据类型的一种 实现(realization)。我们把包的抽象 概念(concept) 用代码 实现(implement) 了,在这里,是通过使用一个名为 contents 的数组以及其他字段和方法来实现的。
这个以 ArrayBag1 为名的实现,现在是一种可以被客户端代码使用的数据结构。一旦正确实现,这种数据结构就会表现出包的特征和行为。
下面的 UML 类图展示了这种实现/转换。
注意所使用的箭头类型。
带虚线的开口箭头表示 ArrayBag1<T> 实现了 BagInterface<T> ,这实质上说明了 ArrayBag1 类旨在实现 BagInterface 所描述的 Bag 应有的操作/行为。
我们鼓励你花一点时间进一步探究这个 UML 类图,注意字段及其数据类型、方法及其 可见性(visibility)、参数和返回类型,以及 UML 表示法所提供的详细程度。
还要注意,UML 类图既可以用来捕获和交流某个设想系统中组件的 预期设计(intended design),也可以用来展示软件系统组件的 实际实现(actual implementation)。
它帮助我们快速理解给定系统中各个类所提供的功能。
例如,如果我们想要确定包中条目的数量,我们可以很容易地推断出,当我们调用 getCurrentSize() 方法时,它会返回一个 int 值来提供该信息。
我们甚至可以在简单推断的基础上更进一步:我们可以用设计图来识别那些可能返回某些所需信息,或帮助我们完成某些任务或操作的字段或方法。然后我们可以查看类的文档来确认或澄清我们最初的印象。
如果对下图中的任何一项有不清楚的地方,我们鼓励你提出疑问。
1.9. 交互式:ArrayBagsWithJUnit 示例演示¶
跟着做、练习与探索
在 Eclipse 中自行下载并运行、探索视频中的对应项目。示例项目需要 CS2-Support 项目。它也会用在你平时的课程项目中。要下载 CS2-Support,你必须先完成第一次实验的配置步骤。然后就可以通过 Eclipse 使用蓝色向下箭头图标,或使用项目菜单并选择"Download Assignment..."来下载它。
1.10. 检查点 2¶
1.11. 更多包方法实现的演示¶
1.11.1. 交互式:更多关于包的实现方法¶
1.11.2. ArrayBag 类 UML 图¶
下面是上面视频中所描述的 ArrayBag 类的 UML 类图。观察这个类图与固定大小数组实现类图的区别。
值得注意的是,contents 字段不再声明为 final。
你可能还记得,在固定大小数组实现中,我们没有一种机制来增加包的容量,把 contents 声明为 final 就意味着 contents 所引用的数组不能改变。
这个 ArrayBag 实现并没有施加这样的约束。
1.12. 检查点 3¶
1.13. 移除方法与设计改进课程和演示¶
1.13.1. 交互式:移除方法与设计改进,第 1 部分¶
1.13.2. 交互式:移除方法与设计改进,第 2 部分¶
1.13.3. 交互式:移除方法与设计改进,第 3 部分¶
1.14. 检查点 4¶
1.15. 交互式:数组扩容说明与编码演示¶
1.16. 使用数组实现包的权衡¶
优点 |
缺点 |
|---|---|
向包中添加条目很快 |
增大数组的容量需要时间复制其中的条目 |
移除一个未指定条目很快 |
移除一个指定条目需要时间定位该条目 |
