| 关于   «  9. 编程练习 2   ::   目录   ::   2. 实验 3 电影数据库  »

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 的类应该共有的方法,也就是说,所有包的实现中都应该存在的方法。它还指出了字段和方法的访问修饰符,以及每个方法的参数和返回类型的详细信息。在这种情况下,你会注意到每个方法名称左侧的标注表示每个方法都是公开的。

_images/2114BagInterfaceClassDiagram.png

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 值来提供该信息。

我们甚至可以在简单推断的基础上更进一步:我们可以用设计图来识别那些可能返回某些所需信息,或帮助我们完成某些任务或操作的字段或方法。然后我们可以查看类的文档来确认或澄清我们最初的印象。

如果对下图中的任何一项有不清楚的地方,我们鼓励你提出疑问。

_images/2114ArrayBagClassDiagram.png

1.9. 交互式:ArrayBagsWithJUnit 示例演示

跟着做、练习与探索

在 Eclipse 中自行下载并运行、探索视频中的对应项目。示例项目需要 CS2-Support 项目。它也会用在你平时的课程项目中。要下载 CS2-Support,你必须先完成第一次实验的配置步骤。然后就可以通过 Eclipse 使用蓝色向下箭头图标,或使用项目菜单并选择"Download Assignment..."来下载它。

exArrayBagsWithJUnit.zip

1.10. 检查点 2

1.11. 更多包方法实现的演示

1.11.1. 交互式:更多关于包的实现方法

跟着做并参与

下载视频对应的幻灯片。观看视频时在幻灯片上做笔记,自己练习画图!

ArrayBagMethods.pdf

1.11.2. ArrayBag 类 UML 图

下面是上面视频中所描述的 ArrayBag 类的 UML 类图。观察这个类图与固定大小数组实现类图的区别。

值得注意的是,contents 字段不再声明为 final。

你可能还记得,在固定大小数组实现中,我们没有一种机制来增加包的容量,把 contents 声明为 final 就意味着 contents 所引用的数组不能改变。

这个 ArrayBag 实现并没有施加这样的约束。

_images/2114ArrayBagClassDiagram2.png

1.12. 检查点 3

1.13. 移除方法与设计改进课程和演示

1.13.1. 交互式:移除方法与设计改进,第 1 部分

跟着做并参与

下载视频对应的幻灯片。观看视频时在幻灯片上做笔记,自己练习画图!

BagsDesignImprovePart1.pdf

1.13.2. 交互式:移除方法与设计改进,第 2 部分

跟着做并参与

下载视频对应的幻灯片。观看视频时在幻灯片上做笔记,自己练习画图!

BagsDesignImprovePart2.pdf

1.13.3. 交互式:移除方法与设计改进,第 3 部分

跟着做并参与

下载视频对应的幻灯片。观看视频时在幻灯片上做笔记,自己练习画图!

BagsDesignImprovePart3.pdf

1.14. 检查点 4

1.15. 交互式:数组扩容说明与编码演示

跟着做并参与

下载视频对应的幻灯片。观看视频时在幻灯片上做笔记,自己练习画图!

DoubleArray.pdf

1.16. 使用数组实现包的权衡

Tradeoffs

优点

缺点

向包中添加条目很快

增大数组的容量需要时间复制其中的条目

移除一个未指定条目很快

移除一个指定条目需要时间定位该条目

1.17. 编程实践:包接口

   «  9. 编程练习 2   ::   目录   ::   2. 实验 3 电影数据库  »

关闭窗口