MengBridgeCourse 中文版

第 7 章 测试与异常

| 关于   英文版   «  7.6. 风格与文档   ::   目录   ::   7.8. 单元 7 实验 2 占位符  »

7.7. 袋

7.7.1. 目标

完成本模块后,学生将能够:

  • 命名基本 Java 数据结构的功能与用途

  • 陈述 Java 中 Bag 的关键特征

  • 在 Java 中构建并填充 Bag

7.7.1.1. 建议阅读

第 1 章 - 第 2 章 袋(Bag)来自 Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry

7.7.2. 袋的简介

数据结构为组织和操作数据集合提供了模型。它们是抽象数据类型(Abstract Data Type)或 ADT 的一个示例。以前,如果您想存储一个表示房间恒温器温度设置的整数值,您会使用类似

int temp = 75;

然而,如果您必须存储并跟踪商业建筑中 500 个房间的恒温器温度设置该怎么办?为它们中的每一个创建一个 int 变量将非常繁琐。从概念上讲,客户端代码可以将数据分组到适当的数据结构中,例如列表或包。客户端代码可以相应地与其交互,例如通过添加或删除项目。就恒温器温度设置示例而言,客户端代码会将整数值添加到选定的数据结构中,以代表商业建筑中每个房间的温度设置。当然,我们需要一种方法来识别与给定房间关联的整数值,此类问题将在本课程中进一步探讨。常见的入门级线性数据结构包括包、栈、队列和列表。数据结构也可以组织为树或图,在多维空间中,它们可以通过位置或由键(如字典中的键)进行索引。

本模块介绍 Bag 抽象数据类型(ADT)。它是一个无序的有限对象集合,且可以包含重复项。Bag 在日常生活中被广泛用于组织和管理工作对象集合,例如背包中的物品、购物袋中的商品,或本十年中你观看过的电影。Bag 对象的可能行为包括:获取 Bag 中存储的项数,检查 Bag 是否为空,添加和移除对象,遍历 Bag 中的项,以及检查 Bag 是否包含特定对象。

在设计 Bag 类时,开发者必须考虑许多方面。为了实现 Bag,需要指定其数据和 方法。在设计方法预期如何工作时,我们需要考虑方法预期行为的所有方面。 在此过程中至关重要的一点是考虑当任务无法完成时应发生什么:代码应静默失败,通知客户端代码任务无法完成的事实,还是采取其他某种行动方案?

开发者在实现数据结构时也有许多选择。一个关键的决策是如何实际存储数据。客户端代码通过调用其公共方法与 Bag 交互,但在底层,Bag 可能是用数组或节点链接链构建的。其他数据结构实现决策涉及确定各种算法以高效地编程指定方法。

7.7.3. Bag 接口方法的文档

在查看 Bag ADT 的实现之前,我们首先查看接口。

7.7.3.1. BagInterface 的 UML

下图展示了 BagInterface 类的 UML 表示法。

您可能还记得,UML(统一建模语言)是一种标准化的建模语言,用于捕获、可视化并传达系统的设计。

存在许多种 UML 图。本课程的大部分时间我们将使用类似于下图所示的图,这些被称为 UML 类图。

观察类图如何快速传达给定系统软件组件的名称和特性。乍一看,这张图描述了接口的规范,它指明了所有实现 BagInterface 的类应共有的方法,即所有 Bag 实现中应包含的方法。它还指明了字段和方法的访问修饰符,以及每个方法的参数和返回类型的详细信息。在此情况下,你可以注意到每个方法名称左侧的注解,表明每个方法都是公开的。

_images/2114BagInterfaceClassDiagram.png

7.7.3.2. 接口 BagInterface 代码示例

下面将找到实现 BagInterface 的示例代码。

查看实现(代码)如何与设计文档(UML 类图)相匹配。

The Bag Interface

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

7.7.4. 交互:BagInterface 接口方法的文档 [7:28]

7.7.5. 交互:使用 Bag [4:34]

7.7.6. 检查点 1

7.7.7. 编程练习:数组

7.7.8. 数组实现的 Bag

7.7.8.1. 建议阅读

第 2 章 使用数组实现的 Bag 接口 Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry

7.7.8.2. 交互:定长数组实现

7.7.8.3. 数组 Bag 与 JUnit 示例类图

让我们来看看设计规范的演变。

固定大小数组实现视频描述了 Bag ADT 的 实现。我们抽象地 概念 化了 Bag,并在代码中 实现 了这个概念,在本例中通过使用名为 contents 的数组以及其他字段和方法来实现。

此实现被称为 ArrayBag1,现在是一种可供客户端代码使用的数据结构。一旦正确实现,该数据结构将表现出 Bag 的特征和行为。

下方的 UML 类图可视化了这一实现/具体化。

注意所使用的箭头类型。

带虚线的开放箭头表示 ArrayBag1<T> 实现了 BagInterface<T>,这本质上说明了 ArrayBag1 类旨在实现 Bag(如 BagInterface 所述)所期望的操作/行为。

我们鼓励您花点时间进一步探索 UML 类图,注意字段及其数据类型、方法及其 可见性、参数和返回类型,以及 UML 记法所提供的细节程度。

同样观察 UML 类图如何用于捕获和传达某些设想系统的组件的 预期设计 以及软件系统组件的 实际实现。

它帮助我们快速理解给定系统中类所提供的功能。

例如,如果我们想要确定 Bag 中的项目数量,我们可以很容易地推断出通过调用该方法返回一个 int 值,getCurrentSize() 将提供该信息。

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

如果您对上述任何图示内容不清楚,我们鼓励您提出问题。

_images/2114ArrayBagClassDiagram.png

7.7.8.4. 交互:ArrayBagsWithJUnit 示例演示 [8:17]

Follow Along, Practice and Explore

在 Eclipse 中,使用 Project > Download Assignment... 菜单命令下载名为"ex07.07-ArrayBagsWithJUnit"的练习项目。

如需回顾下载 Eclipse 项目的说明,请参见 01.02: Lab: LightBot for Beginners。

7.7.9. 检查点 2

7.7.10. 演示更多数组接口的实现

7.7.10.1. 交互:关于 Bag 方法实现的更多内容 [5:28]

Follow Along and Engage

下载与视频对应的幻灯片。观看视频时做笔记,亲自练习绘制图表!

Video Slides 7.7.7.1-ArrayBagMethods.pdf

7.7.10.2. 数组类 UML 图

下面是上面视频中描述的 ArrayBag1 类的 UML 类图。注意该类的类图与固定大小数组实现的类图有何不同。

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

正如您可能从固定大小数组实现中回忆起来,我们并没有一种机制来增加袋的容量;声明 contents 为 final 意味着 contents 所引用的数组不能改变。

该数组 Bag 实现并未施加此类约束。

_images/2114ArrayBagClassDiagram2.png

7.7.11. 检查点 3

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

7.7.12.1. 交互式:移除方法与设计改进,第 1 部分 [5:28]

Follow Along and Engage

下载与视频对应的幻灯片。观看视频时做笔记,亲自练习绘制图表!

Video Slides 7.7.8.1-BagsDesignImprovePart1.pdf

7.7.12.2. 交互式:移除方法与设计改进,第二部分 [6:45]

Follow Along and Engage

下载与视频对应的幻灯片。观看视频时做笔记,亲自练习绘制图表!

Video Slides 7.7.8.2-BagsDesignImprovePart2.pdf

7.7.12.3. 交互式:移除方法与设计改进,第 3 部分 [9:03]

Follow Along and Engage

下载与视频对应的幻灯片。观看视频时做笔记,亲自练习绘制图表!

Video Slides 7.7.8.3-BagsDesignImprovePart3.pdf

7.7.13. 检查点 4

7.7.14. 交互式:数组扩容说明与编码演示 [14:47]

Follow Along and Engage

下载与视频对应的幻灯片。观看视频时做笔记,亲自练习绘制图表!

DoubleArray.pdf
Video Slides 7.7.9.1-DoubleArray.pdf

7.7.15. 使用数组实现 Bag 的权衡

Tradeoffs

优点

缺点

向数组中添加条目是快速的

增加数组的大小需要时间来复制其条目

移除未指定的条目是快速的

移除指定的条目需要时间来定位该条目

7.7.16. 编程实践:BagInterface 接口

   «  7.6. 风格与文档   ::   目录   ::   7.8. 单元 7 实验 2 占位符  »

关闭窗口