Project 1：数据结构

截止日期：2021 年 2 月 16 日

本项目的截止日期是 02/16，不过为了帮助你按计划推进，我们在 02/05 设置了一个额外加分检查点。该检查点是项目自动评分器的一个较小版本。更详细的信息会在本规格后面给出。

你还需要在作业结束时推送你的 snaps-sp21-s*** 仓库，以便把 Gradescope 分数传入 Beacon。后文会进一步说明。

请记住，由于 Project 1 与 Lab 4 之间存在依赖关系，本项目最多只能使用 2 个 slip days。

介绍#

在 Project 1 中，我们将分别使用链表和数组构建“双端队列”（Double Ended Queue）的实现，并把它们放进一个可供其他类使用的包中。这个项目大致分成两半：数据结构部分和应用部分。

在项目的数据结构部分，你将创建两个 Java 文件：LinkedListDeque.java 和 ArrayDeque.java，并实现下文列出的 public 方法。你需要利用在 Lab 3 中掌握的随机测试和计时测试技能，自行验证这些数据结构是否正确。

在项目的应用部分，你将创建 Java 文件 MaxArrayDeque.java，还会使用自己的包，最终实现一个能够播放 Guitar Hero 音乐的声音合成器。你必须自行测试 MaxArrayDeque；声音合成器部分的测试由课程提供。

我们提供的脚手架会比较少。换句话说，我们会告诉你应该做什么，但不会告诉你具体应该怎样实现。

本项目必须独立完成。请仔细阅读课程的协作与作弊政策，了解这项要求的确切含义。

此外，本项目会强制检查代码风格。你必须遵守课程风格指南，否则自动评分器会扣分。

获取骨架文件#

与 Project 0 一样，你应该先下载骨架文件。

进入包含你个人仓库副本的文件夹。例如，如果你的登录名是 s101，就进入 sp21-s101 文件夹，或其任意子目录。

为了确保你拥有最新的骨架文件，请使用命令：

git pull skeleton master

bash

如果你使用的是较新的 Git 版本，可能需要运行：

git pull skeleton master --allow-unrelated-histories

bash

此时应该出现一个 proj1 目录，其中包含两个文件夹：

proj1
├── deque
│   └── LinkedListDequeTest.java
└── gh2
    ├── GuitarHeroLite.java
    ├── GuitarPlayer.java
    ├── GuitarString.java
    ├── TTFAF.java
    └── TestGuitarString.java

text

如果遇到任何形式的错误，请停下来，仔细阅读课程 Git 指南并解决问题，或前往 Office Hours / Ed 求助。与其猜测并反复尝试 Git 命令，这样做很可能会为你省下许多麻烦。如果你发现自己正准备使用 Google 推荐的 force push 一类命令，不要这样做。即使 Stack Overflow 上的帖子说可以，也不要使用 force push。

骨架中只提供了 deque/LinkedListDequeTest.java，以及位于 gh2 文件夹中的本项目第二部分（Guitar Hero 2）的一些骨架。deque/LinkedListDequeTest.java 给出了如何编写测试来验证代码正确性的例子。我们强烈建议你运行这些测试，也编写自己的测试，因为已给出的测试并不全面。

这个文件中的测试也正是检查点中用于评估 LinkedListDeque 实现的测试。对于 ArrayDeque，我们还会使用一些不提供给你的额外测试。关于检查点的更多信息会在后面给出。

在进入 Deque API 和具体实现要求之前，我们先简要讨论包，以及本项目为什么要使用包。

包#

本项目的一部分目标是使用包来分离不同的逻辑和功能。项目结束时，你将拥有两个包：提供 Deque 数据结构实现的 deque 包，以及实现 Guitar Hero 合成器的 gh2 包。起始代码中应该已经存在这两个同名文件夹，而你的任务就是实现其中的内容。下面具体看看“包”究竟是什么。

包是一组为了共同目标协同工作的 Java 类。其实我们已经在 CS 61B 中使用过包，只是此前没有明确这样称呼。例如，org.junit 是一个包，其中包含许多对测试有用的类，包括我们熟悉的 Assert 类；这个类中包含 assertEquals 等有用的 static 方法。也就是说，在 org.junit.Assert.assertEquals 中，org.junit 是包名，Assert 是类名，assertEquals 是方法名。

我们把 org.junit.Assert.assertEquals 称为这个方法的“规范名称”（canonical name），把 assertEquals 称为这个方法的“简单名称”（simple name）。

创建包时，我们在文件顶部使用 package 关键字指定代码所属的包。例如，如果想声明某个文件属于 deque 包，就在文件顶部添加：

package deque;

java

如果程序员想使用 deque 包中的类或方法，就必须使用完整的规范名称，例如 deque.ArrayDeque；或者先写 import deque.ArrayDeque，之后便可以只使用简单名称 ArrayDeque。因此，import 语句只是让你可以使用类或方法的简单名称。

通常，包名是编写代码的实体所拥有的网址倒序。例如，JUnit 库托管在 junit.org，因此它的包名是 org.junit。

包为什么有用？关键就在“规范”这个词。只要不同程序员没有为自己的包使用同一个包名，我们就可以在不同上下文中自由使用相同的类名。例如，可能存在一个 com.hrblock.TaxCalculator 类，也可能存在另一个不同的 com.turbotax.TaxCalculator 类。由于我们必须使用完整规范名称，或先执行 import，因此不会在想使用一个类时意外用到另一个类。

从概念上说，你可以把包理解为电脑中的不同文件夹。构建大型系统时，把它组织成不同的包是一种好做法。

从现在开始，CS 61B 中的大多数代码都会属于某个包。

介绍完这些内容后，下面讨论 Deque 应该具有的方法。

Deque API#

双端队列与课堂上讨论过的 SLList 和 AList 类非常相似。下面是 cplusplus.com 给出的定义：

Deque（通常读作 “deck”）是 double-ended queue 的一种不规则缩写。双端队列是一种大小可动态变化的序列容器，可以在两端（前端或后端）扩张或收缩。

具体而言，任何 Deque 实现都必须恰好具有以下操作：

public void addFirst(T item)：把类型为 T 的元素添加到 Deque 前端。可以假设 item 永远不会是 null。
public void addLast(T item)：把类型为 T 的元素添加到 Deque 后端。可以假设 item 永远不会是 null。
public boolean isEmpty()：如果 Deque 为空则返回 true，否则返回 false。
public int size()：返回 Deque 中的元素数量。
public void printDeque()：从第一个元素到最后一个元素打印 Deque 中的元素，元素之间以空格分隔。打印完所有元素后，再输出一个换行。
public T removeFirst()：删除并返回 Deque 前端的元素。如果不存在这样的元素，则返回 null。
public T removeLast()：删除并返回 Deque 后端的元素。如果不存在这样的元素，则返回 null。
public T get(int index)：获取指定索引处的元素，其中 0 表示前端，1 表示下一个元素，依此类推。如果不存在这样的元素，则返回 null。不得改变 Deque！

此外，我们还希望两个 Deque 实现具有以下两个特殊方法：

public Iterator<T> iterator()：我们要创建的 Deque 对象是可迭代的（也就是 Iterable<T>），因此必须提供此方法来返回一个迭代器。
public boolean equals(Object o)：返回参数 o 是否与该 Deque 相等。如果 o 是一个 Deque，并且按照泛型 T 的 equals 方法判断，它以相同顺序包含完全相同的内容，那么 o 就被视为相等。（2/12 新增：你需要使用 instanceof 关键字。）

**2/12 新增：**不要让 Deque 接口实现 Iterable；应当只让两个实现类 LinkedListDeque 和 ArrayDeque 实现它。若采用前一种做法，自动评分器会报告 API 错误。

你会在 Lecture 11（2/12）中学习 Iterator，所以现在无需担心。这一项目本来就应随着课堂和讨论课讲授更多内容而一点一点完成，也是练习本课程所学知识的绝佳机会。

你的类必须能够接受任何泛型类型，而不只是整数。关于创建和使用泛型数据结构的信息，请参阅 Lecture 5，尤其注意最后一张幻灯片中关于泛型的经验规则。

在本项目中，你将为 Deque 接口提供两种实现：一种由链表支持，另一种由可调整大小的数组支持。

项目任务#

1. 链表 Deque#

注意：除了迭代器之外，完成这一部分所需的一切内容都已经在 Lecture 4 和 Lecture 5（1/27 和 1/25）中讲过；迭代器会在 Lecture 11（2/12）中介绍。

在 proj1/deque 目录中创建名为 LinkedListDeque.java 的文件。确保使用特殊的 package 关键字声明它属于 deque 包。

作为第一种 Deque 实现，你将构建基于链表的 LinkedListDeque 类。

你的操作必须遵守以下规则：

add 和 remove 操作不得涉及任何循环或递归。单次这样的操作必须花费“常数时间”，也就是执行时间不能依赖 Deque 的大小。这意味着不能使用遍历全部或大多数元素的循环。
get 必须使用迭代，而不是递归。
size 必须花费常数时间。
使用 for-each 循环遍历 LinkedListDeque 所需的时间，应与元素数量成正比。
不要保留对已不在 Deque 中的元素的引用。程序在任意时刻使用的内存量必须与元素数量成正比。例如，如果先添加 10,000 个元素，再删除其中 9,999 个，最终内存使用量应与只有 1 个元素的 Deque 相当，而不是仍与 10,000 个元素相当。请记住，只有当不再存在指向某个对象的指针时，Java 垃圾回收器才会为我们“删除”它。

实现前面“Deque API”一节列出的所有方法。

此外，还需要实现：

public LinkedListDeque()：创建一个空的链表 Deque。
public T getRecursive(int index)：与 get 相同，但使用递归。

如有需要，可以在 LinkedListDeque.java 中添加任何 private 辅助类或辅助方法。如果这样做，请为了你自己和助教的方便，添加有帮助的 Javadoc 注释。

虽然听起来很简单，但其中有许多设计问题需要考虑，你可能会发现实现比预想中更困难。请务必复习双向链表讲义，尤其是关于哨兵节点的幻灯片：双哨兵拓扑和循环哨兵拓扑。我更喜欢循环方法。

实现中不得使用 Java 内置的 LinkedList 数据结构，也不得使用任何 java.util.* 中的数据结构。如果自动评分器检测到导入了这些数据结构，会立即给你 0 分。

2. 数组 Deque#

注意：除了迭代器之外，完成这一部分所需的内容会在 Lecture 7（2/03）之前全部讲完；迭代器会在 Lecture 11（2/12）中介绍。

在 proj1/deque 目录中创建名为 ArrayDeque.java 的文件。同样，使用 package 关键字告诉该文件它属于 deque 包。

作为第二种 Deque 实现，你将构建 ArrayDeque 类。这个 Deque 必须以数组作为核心数据结构。

对于该实现，你的操作必须遵守以下规则：

除了调整数组大小的操作外，add 和 remove 必须花费常数时间。
get 和 size 必须花费常数时间。
数组的初始大小应为 8。
程序在任意时刻使用的内存量必须与元素数量成正比。例如，如果先添加 10,000 个元素，再删除其中 9,999 个，就不应该仍然使用长度约为 10,000 的数组。对于长度为 16 或更大的数组，使用率必须始终至少达到 25%。

这意味着，在执行一次会使数组中元素数量低于数组长度 25% 的删除操作之前，应当缩小数组。对于较小的数组，使用率可以任意低。

实现前面“Deque API”一节列出的所有方法。

此外，还需要实现：

public ArrayDeque()：创建一个空的数组 Deque。

如有需要，可以在 ArrayDeque.java 中添加任何 private 辅助类或辅助方法。

你需要以某种方式记录哪些数组索引保存着 Deque 的前端元素和后端元素。我们强烈建议在本练习中把数组视为循环数组。换句话说，如果前端元素位于位置 0，而你执行 addFirst，新的前端应绕回数组末尾，因此新的 Deque 前端元素位于底层数组的最后一个位置。与非循环方法相比，这会少带来许多麻烦。

更多细节可参阅 Project 1 演示幻灯片。

正确调整数组大小非常棘手，需要认真思考。请尝试在纸上画出不同方案。找到正确方法可能要花不少时间，我们鼓励你与同学或助教讨论核心思路，但实际实现必须完全由你独立完成。

额外加分：检查点#

为了帮助你按计划推进，本项目设有一个 2/05 截止、价值 16 额外加分的检查点。检查点自动评分器会测试 LinkedListDeque 和 ArrayDeque 的基础功能。具体来说，它会使用 LinkedListDequeTest.java 中给出的测试检查 LinkedListDeque，并使用课程自行编写的测试检查 ArrayDeque。

这里的“基础功能”指所有 add 方法、所有 remove 方法、size 方法、isEmpty 方法和 get 方法。这意味着检查点不会测试 equals(Object o) 或 iterator()。

注意：isEmpty 从一开始就在评分器中，但我们在今天（2/5）才把这一点补进规格。不过，如果已经实现了 size，这个方法应该非常简单，可以只写一行。

尤其重要的是，我们在 ArrayDeque 中最多只会插入 8 个元素，因此你无需为了这个检查点处理扩容。

你可以选择不完成检查点，不过我们强烈建议完成它，这既能帮助你保持进度，也能获得一些额外分。

作业的其余部分不会在检查点中评分。

测试#

测试是工业界和学术界编写代码的重要组成部分。它是一项必不可少的技能，能够避免工业中的金钱损失和危险缺陷；对你而言，也能避免丢分。学习如何编写优秀、全面的单元测试，并养成在发布代码之前始终测试代码的习惯，是 CS 61B 的核心目标之一。

起始代码中提供了一个非常简单的健全性检查文件 LinkedListDequeTest.java。要使用这个测试样例，必须取消样例测试中相应代码行的注释。只有在实现了某个测试所用的全部方法之后，才取消该测试的注释，否则代码无法编译。执行 main 方法即可运行测试。测试项目时，请记得可以使用 IntelliJ 中的可视化工具。

你不需要提交 LinkedListDequeTest.java。为了自己的利益，提交之前应为 LinkedListDeque 和 ArrayDeque 编写更全面的测试。请注意，通过 LinkedListDequeTest.java 中提供的测试，并不一定意味着能够通过自动评分器的全部测试或在完整自动评分器中获得满分。

本项目的目标之一，是让你构建某个东西并自行评估其正确性，因此我们不希望你过度依赖完整自动评分器来验证正确性。你会获得一个每 8 小时恢复一次的自动评分器 token。这些 token 不能“叠加”；即使连续 3 天没有向自动评分器提交内容，你仍然只有一个 token。

从 2/13 星期六开始，恢复时间会永久缩短为每 20 分钟一次。

那么应如何验证数据结构的正确性呢？使用你在 Lab 3 中获得的技能！我们鼓励你复制为 SList 和 AList 编写的测试，然后把它们改造成适用于这些数据结构的测试。它们会非常相似，只需要做一些基本修改。

在只能极少使用自动评分器的情况下完成整个项目，可能显得非常吓人；但如果随机测试规模足够大，你应当对实现很有信心。只用几行代码，就可以在数十万规模的数据结构上，以随机顺序调用各种随机方法。

换句话说，你是在数据结构上测试大量情形，很可能覆盖所有可能的边界情况。这正是随机测试的魅力：它把构想边界情况的创造性工作交给随机性。

你创建的测试不会被评分，不过本项目另有一个额外加分部分，要求你编写自己的自动评分器。详细信息见本规格后面。

在实现 Deque 接口和所有必需方法之前，你的代码无法在完整自动评分器上编译。因此，如果只完成了规格到当前为止的内容，应使用检查点评分器，而不是完整评分器。

额外加分：自动评分器#

你可以编写自己的 Deque 自动评分器，获得 32 分额外加分。完整细节位于单独的规格中，以免让本规格更加杂乱。其截止日期与 Project 1 相同，即 2/16。额外加分作业可以使用 slip days，但请理解，工作人员在 Ed 和 Office Hours 中会优先帮助必做部分。

在完成整个项目之前，我们不建议开始这项额外加分作业。现在先记住它，然后继续完成主项目。

MaxArrayDeque#

在完整实现并测试 ArrayDeque 的正确性后，你将构建 MaxArrayDeque。MaxArrayDeque 拥有 ArrayDeque 的全部方法，此外还具有 2 个额外方法和一个新构造器：

public MaxArrayDeque(Comparator<T> c)：使用给定的 Comparator 创建一个 MaxArrayDeque。
public T max()：按照先前给出的 Comparator 返回 Deque 中的最大元素。如果 MaxArrayDeque 为空，只需返回 null。
public T max(Comparator<T> c)：按照参数 Comparator c 返回 Deque 中的最大元素。如果 MaxArrayDeque 为空，只需返回 null。

MaxArrayDeque 可以使用构造器中提供的 Comparator<T> 判断自身的最大元素，也可以使用一个与构造器中给出的比较器不同的任意 Comparator<T>。

我们不关心这个类的 equals(Object o) 方法，所以你可以按照自己认为最恰当的方式定义它。我们不会测试此方法。

如果你发现自己准备把整个 ArrayDeque 实现复制到一个 MaxArrayDeque 文件中，那就做错了。这是一项关于整洁代码的练习，而在对抗复杂性时，重复是我们最大的敌人之一。作为提示，请重新阅读本节上面的第二句话。

这些额外方法没有运行时间要求，我们只关心答案是否正确。有时 MaxArrayDeque 中可能有多个相等、因而同为最大值的元素；在这种情况下，可以返回其中任意一个，都会被视为正确。

你也应当为这一部分编写测试。因为新增功能比较简单，所以这些测试不必像为两个 Deque 实现编写的随机测试和计时测试那样健壮。为了测试代码，你很可能会创建多个 Comparator<T> 类——这正是本任务的目的：练习使用 Comparator 对象完成有用的事情（找出最大元素），并练习编写自己的 Comparator 类。

你不需要提交这些测试，但为了自己，我们仍强烈建议编写它们。

在下一部分中不会使用你创建的 MaxArrayDeque。它是一个独立练习。

Deque 接口#

在项目最后一部分，我们将真正使用刚刚创建的数据结构来解决一个现实问题。

回忆一下，我们使用以下方法定义了 Deque API，也就是它的行为：

public void addFirst(T item)
public void addLast(T item)
public boolean isEmpty()
public int size()
public void printDeque()
public T removeFirst()
public T removeLast()
public T get(int index)

java

由于程序依赖的是这些行为，因此无论提供的是哪种 Deque 实现——ArrayDeque 还是 LinkedListDeque——程序都不应在意，并且都应该正常工作。为了做到这一点，我们会使用接口的力量。

第一个任务会有一点繁琐，但不会花太久。

新建名为 Deque.java 的文件，并在其中创建一个包含上述所有方法的接口。在 IntelliJ 中使用 “New → Java Class”。IntelliJ 会假设你想创建一个类，因此要确保把 class 关键字替换为 interface。不要忘记声明 Deque 接口属于 deque 包。

修改 LinkedListDeque 和/或 ArrayDeque，在类声明行中加入 implements Deque<T>，让它们实现 Deque 接口。如果 IntelliJ 用类似下面的错误信息对你大喊：

The method ... of type LinkedListDeque has the same erasure as ... of type Deque but does not override it.

text

这意味着你忘记在 implements 行中写泛型 T，也就是写成了 implements Deque，而不是 implements Deque<T>。

如果你为泛型类型参数使用了 T 以外的名字，就使用你自己的名字。为每个重写 Deque 方法的方法添加 @Override 标记。

现在，在 Deque 接口中为 isEmpty() 提供一个 default 实现：当 size() 为 0 时返回 true。由于 LinkedListDeque 和 ArrayDeque 实现了 Deque 接口，因此有了默认 isEmpty() 实现后，可以从先前实现的 LinkedListDeque 和 ArrayDeque 中删除该方法。

实现 Deque 接口，并从 LinkedListDeque 与 ArrayDeque 实现中删除 isEmpty() 方法后，你的代码就可以在完整自动评分器上编译。

Guitar Hero#

在项目这一部分，我们会创建另一个包，使用刚刚完成的 deque 包来生成合成乐器。我们会借助自己的数据结构，实现一个能够模拟拨动吉他弦的算法。

GH2 包#

gh2 包只有一个你需要编辑的主要组件：

GuitarString：一个使用 Deque<Double> 实现 Karplus-Strong 算法、合成吉他弦声音的类。

我们已经提供了 GuitarString 的骨架代码，你将在这里使用项目第一部分完成的 deque 包。

GuitarString#

我们要完成 GuitarString 文件。它应使用 deque 包来复现拨弦的声音。我们将使用 Karplus-Strong 算法；这个算法用 Deque 很容易实现。

Karplus-Strong 算法可以简单地概括为以下三个步骤：

用随机噪声替换 Deque 中的每个元素，也就是介于 -0.5 和 0.5 之间的 double 值。
删除 Deque 前端的 double，并将它与 Deque 中下一个 double 的平均值（提示：使用 removeFirst() 和 get()）乘以能量衰减系数 0.996；我们把整个结果称为 newDouble。然后把 newDouble 添加到 Deque 后端。
播放步骤 2 中出队的 double。回到步骤 2，并永远重复。

从图形上看，假设顶部所示 Deque 的前两个值为 0.2 和 0.4，那么我们会删除 0.2，把它与 0.4 结合得到 0.2988，将 0.2988 添加到队尾，并播放 0.2。

Karplus-Strong 环形缓冲区示意图

可以使用 StdAudio.play 方法播放一个 double 值。例如，StdAudio.play(0.333) 会告诉扬声器振膜向前伸展到其总行程的三分之一；StdAudio.play(-0.9) 会告诉它把自己的小心脏几乎尽可能向后拉伸。扬声器振膜的运动会移动空气；如果以漂亮的模式移动空气，经过数十亿年的进化，你的意识就会把这些扰动理解为悦耳的声音。

可以阅读原页面链接了解更多。如果只执行一次 StdAudio.play(0.9)，之后再也不播放任何内容，那么图中振膜就只会静止在向前行程的十分之九处。

完成 GuitarString.java，使其实现 Karplus-Strong 算法的步骤 1 和步骤 2。请注意，在 GuitarString 构造器中，需要先用 0 填满 Deque 缓冲区。步骤 3 将由 GuitarString 类的客户端完成。

与往常一样，请确保使用 Maven 打开项目，否则 IntelliJ 无法找到 StdAudio。

例如，提供的 TestGuitarString 类包含一个样例测试 testPluckTheAString，它会尝试在吉他弦上播放 A 音。运行这个测试时应该能听到 A 音。如果没有听到，请尝试运行 testTic 方法并从那里开始调试。可以考虑在 GuitarString.java 中添加一个 print 或 toString 方法，以帮助自己观察各次 tic 之间发生了什么。

请注意，我们在这里说的是 Deque，但没有指定使用哪一种 Deque 实现。这是因为我们只需要 addLast、removeFirst 和 get 这些操作，而任何实现 Deque 的类都具备这些操作。因此，实际实现中可以自由选择 LinkedListDeque 或 ArrayDeque。

作为一项可选但强烈推荐的练习，请思考使用二者各自的权衡，并与朋友讨论哪一种更合适，或它们是否同样适合。

GuitarHeroLite#

现在你也应该能够使用 GuitarHeroLite 类。运行它会提供一个图形界面，让用户（也就是你）能够使用 gh2 包中的 GuitarString 类交互式地播放声音。

以下部分不计分。

考虑创建一个与 GuitarHeroLite 类似的程序 GuitarHero，但它支持从 110 Hz 到 880 Hz 的半音阶共 37 个音。使用下面的 37 个按键表示键盘，从最低音到最高音：

String keyboard = "q2we4r5ty7u8i9op-[=zxdcfvgbnjmk,.;/' ";

java

这种键盘排列模仿钢琴键盘：“白键”位于 qwerty 和 zxcv 行，“黑键”位于键盘的 12345 和 asdf 行。

字符串 keyboard 的第 i 个字符对应频率：

$440 \cdot 2^{(i - 24) / 12}$

因此字符 q 是 110 Hz，i 是 220 Hz，v 是 440 Hz，空格是 880 Hz。千万不要考虑创建 37 个独立的 GuitarString 变量或 37 路 if 语句。应创建一个包含 37 个 GuitarString 对象的数组，并使用 keyboard.indexOf(key) 判断按下了哪个键。确保按下不对应这 37 个音符的按键时，程序不会崩溃。

仅供娱乐：TTFAF#

当你比较确信 GuitarString 工作正常之后，尝试运行 TTFAF。确保声音已经打开。

可以阅读 GuitarPlayer 和 TTFAF 类，弄清楚它们的工作方式。尤其是 TTFAF，其中以注释代码的形式给出了另一种使用方式的示例。

为什么它能工作#

让 Karplus-Strong 算法发挥作用的两个主要组成部分，是环形缓冲区反馈机制和求平均操作。

**环形缓冲区反馈机制。**环形缓冲区模拟能量来回传播的介质，也就是两端固定的弦。环形缓冲区的长度决定所得声音的基频。从听觉上说，反馈机制只会加强基频及其谐波，也就是基频整数倍的频率。

能量衰减系数（这里是 0.996）模拟波在琴弦中完成一次往返时发生的轻微能量耗散。

**求平均操作。**求平均操作是一种温和的低通滤波器，它会去除较高频率，同时允许较低频率通过，这也是“低通”名称的由来。因为该操作位于反馈路径中，所以它会逐渐削弱较高次谐波，同时保留较低次谐波；这与真实拨动吉他弦的声音非常接近。

提交与评分#

要提交项目，请添加并提交文件，然后推送到远程仓库。接着在 Gradescope 中进入相应作业并提交。

在 Gradescope 完成最终提交之后，必须推送你的 snaps 仓库。

在推送 snaps 仓库并提交 Snaps Gradescope 作业之前，你的 Gradescope 分数不会传入 Beacon。要推送 snaps 仓库，请运行：

cd $SNAPS_DIR
git push

bash

推送 snaps 仓库后，Gradescope 上有一项作业需要你提交 snaps-sp21-s*** 仓库，方式与 Lab 1A 类似。这只适用于完整评分器，不适用于检查点或额外加分作业。

即使忘记了，也可以在截止日期之后一周内完成这一步。如果超过一周仍未推送，就必须使用 slip days。

**注意：**截至 2/07，我们略微修改了上面的 snaps 要求：从仅仅推送 snaps 仓库，改为推送后还要在 Gradescope 提交，这样学生能够更清楚地确认提交已经成功。

整个项目价值 640 分：

deque/LinkedListDeque：230 分
deque/ArrayDeque：230 分
deque/MaxArrayDeque：80 分
gh2/GuitarString：80 分

此外共有 48 分额外加分：

检查点满分：16 分
制作自动评分器：32 分

常见问题#

Deque#

问：当我不知道 Deque 元素的类型时，应该怎样打印它们？#

答：使用默认打印出来的字符串即可。这个字符串来自对象对 toString() 的实现，我们会在本学期稍后讨论。例如，如果类中的泛型类型名叫 Jumanji，要打印 Jumanji j，可以调用 System.out.print(j)。

问：我无法让 Java 创建泛型对象数组！#

答：使用课堂上见过的奇怪语法：T[] a = (T[]) new Object[1000];。这里 T 是泛型类型，是 “String” 或 “Integer” 等其他对象类型的占位符。

问：我这样做了，但编译器发出警告怎么办？#

答：抱歉，这是 Java 设计者在为 Java 引入泛型时留下的问题，没有优雅的绕过方法。享受你的编译警告吧。我们会在几周后进一步讨论。

问：怎样让图中的箭头指向数据结构的特定字段？#

在课堂图示中，箭头看起来能够指向数组中间，或者节点的特定字段。

答：课堂上每当我画出指向某个对象的箭头时，指针都指向整个对象，而不是对象的某个特定字段。事实上，在 Java 中，引用不可能指向对象的字段。

Guitar Hero#

我遇到了 “class file contains wrong class” 错误。#

确保所有 Java 文件顶部都有正确的 package 声明。还要确保属于 gh2 包的所有内容都位于名为 gh2 的文件夹中。

程序说我没有重写某个抽象方法，但我明明重写了！#

很可能存在拼写错误。重写方法时应始终使用 @Override 标记，这样编译器就能发现这类拼写错误。

运行提供的测试时出现 “No runnable methods”。#

确保已经取消测试代码的注释，包括 @Test 注解。

编译代码时，它说类型 K#1 与 K#2 不兼容，或出现类似内容。#

如果正在定义内部类，请确保它没有重新声明一个新的泛型类型参数。例如，private class MapWizard<Z> implements Iterator<Z>{ 中第一个 <Z> 不应该存在。

我遇到了奇怪的自动评分器错误！#

虽然 GuitarString 是一个吉他弦模拟器，但它本身不应播放任何声音。播放操作应由 GuitarString 的客户端完成。

鸣谢：RingBuffer 图示来自 Wikipedia。本作业改编自 Kevin Wayne 的 Guitar Heroine 作业。

提示#

查看 Project 1 幻灯片，其中包含一些更偏视觉化的额外提示。
如果卡住了，甚至不知道从哪里开始：一个很好的第一步是实现 SLList 和/或 AList。为了最高效率，可以与一两个或三个朋友一起练习这些课堂数据结构。
一次只做一点。一次写大量代码只会带来痛苦，而且只会带来痛苦。如果写了太多内容并感到不知所措，请把不必要的部分注释掉。
如果第一次尝试进展很糟，不要害怕丢弃代码并重新开始。每个类实际需要的代码并没有那么多；课程参考实现的每个 .java 文件大约 130 行，包括所有注释和空白行。
对于 ArrayDeque，可以先完全不实现扩缩容，直到确认没有扩缩容时的代码正确。调整大小是一项性能优化，也是获得满分的必需要求。
在尝试编写代码之前，先在纸上画出数据结构的样子。如果能找到愿意配合的朋友，让对方发出命令，而你尝试把每一步都画出来。试着设计一些能够暴露实现问题的操作。
仔细考虑数据结构从空变为某个非零大小（例如 4 个元素），再回到 0，然后再次变为非零大小时会发生什么。这是常见疏漏。
一旦理解哨兵节点，它们会让生活轻松很多。
循环数据结构可能需要一段时间才能理解，但会让两种实现都轻松很多，尤其是 ArrayDeque。
考虑编写辅助函数完成计算数组索引等小任务。例如，在课程的 ArrayDeque 实现中，编写了一个 int minusOne(int index) 函数，用来计算给定索引“前一个”位置的索引。
考虑使用 Lab 2 中安装的 Java Visualizer，在调试器逐步执行时可视化你的 Deque。该工具的图标是一只带眼睛的蓝色咖啡杯，位于调试器面板中 “Console” 标签旁边。如果无法显示，请参阅 CS 61B 插件指南。

Java Visualizer 示例

原始页面：https://sp21.datastructur.es/materials/proj/proj1/proj1 ↗

Project 1：数据结构

介绍#

获取骨架文件#

包#

Deque API#

项目任务#

1. 链表 Deque#

2. 数组 Deque#

额外加分：检查点#

测试#

额外加分：自动评分器#

MaxArrayDeque#

Deque 接口#

Guitar Hero#

GH2 包#

GuitarString#

GuitarHeroLite#

仅供娱乐：TTFAF#

更多娱乐内容#

为什么它能工作#

提交与评分#

常见问题#

Deque#

问：当我不知道 Deque 元素的类型时，应该怎样打印它们？#

问：我无法让 Java 创建泛型对象数组！#

问：我这样做了，但编译器发出警告怎么办？#

问：怎样让图中的箭头指向数据结构的特定字段？#

Guitar Hero#

我遇到了 “class file contains wrong class” 错误。#

程序说我没有重写某个抽象方法，但我明明重写了！#

运行提供的测试时出现 “No runnable methods”。#

编译代码时，它说类型 K#1 与 K#2 不兼容，或出现类似内容。#

我遇到了奇怪的自动评分器错误！#

提示#