跳转到内容

Java之道/数组对象

Add links
来自 Wikibooks，开放世界中的开放书籍
< Java之道
此页面可能需要审核质量。

数组对象

[编辑 | 编辑源代码]

牌组

deck
array!of Cards

在上一章中，我们使用了对象数组，但我也提到可以有一个对象，它包含一个数组作为实例变量。在本节中，我将创建一个新的对象，称为 Deck，它包含一个 Card 数组作为实例变量。

instance variable
variable!instance

类定义如下所示

verbatim class Deck

 Card[] cards;

 public Deck (int n) 
   cards = new Card[n];

verbatim

实例变量的名称是 cards，以帮助区分 Deck 对象和它包含的 Card 数组。以下是一个状态图，显示了没有分配任何卡片的 Deck 对象的样子

state diagram
constructor


figure=figs/deckobject.eps


与往常一样，构造函数初始化实例变量，但在这种情况下，它使用 new 命令创建卡片数组。但是，它没有创建任何卡片来放入其中。为此，我们可以编写另一个构造函数，它创建一个标准的 52 张牌牌组并用 Card 对象填充它

verbatim

 public Deck () 
   cards = new Card[52];
   int index = 0;
   for (int suit = 0; suit <= 3; suit++) 
     for (int rank = 1; rank <= 13; rank++) 
       cards[index] = new Card (suit, rank);
       index++;

verbatim

注意此方法与 buildDeck 的相似之处，只是我们必须更改语法以使其成为构造函数。为了调用它，我们使用 new 命令

new
statement!new

verbatim

   Deck deck = new Deck ();

verbatim

现在我们有了 Deck 类，将所有与 Deck 相关的函数放入 Deck 类定义中是有意义的。查看我们到目前为止编写的函数，printDeck（printdeck 部分）是一个明显的候选函数。以下是它的重写版本，以便与 Deck 对象一起使用

printDeck

verbatim

 public static void printDeck (Deck deck) 
   for (int i=0; i<deck.cards.length; i++) 
     Card.printCard (deck.cards[i]);

verbatim

我们必须更改的最明显的事情是参数的类型，从 Card[] 到 Deck。第二个更改是我们不能再使用 deck.length 来获取数组的长度，因为 deck 现在是一个 Deck 对象，而不是一个数组。它包含一个数组，但它本身不是一个数组。因此，我们必须编写 deck.cards.length 来从 Deck 对象中提取数组并获取数组的长度。

出于相同的原因，我们必须使用 deck.cards[i] 来访问数组中的元素，而不是仅仅使用 deck[i]。最后一个更改是 printCard 的调用必须明确地说 printCard 在 Card 类中定义。

对于其他一些函数，不清楚它们应该包含在 Card 类还是 Deck 类中。例如，findCard 接受一个 Card 和一个 Deck 作为参数；你可以合理地将它放在任一类中。作为练习，将 findCard 移入 Deck 类并将其重写，以便第一个参数是 Deck 对象而不是 Card 数组。

洗牌

[编辑 | 编辑源代码]

shuffle

shuffling

对于大多数纸牌游戏，你需要能够洗牌；也就是说，将卡片按随机顺序排列。在随机部分，我们看到了如何生成随机数，但如何使用它们来洗牌并不明显。

一种可能性是模拟人类洗牌的方式，通常是将牌组分成两部分，然后通过交替从每个牌组中选择来重新组装牌组。由于人类通常不会完美洗牌，因此经过大约 7 次迭代后，牌组的顺序就会很好地随机化。但是，计算机程序会让人讨厌地每次都进行完美的洗牌，这实际上并不太随机。事实上，经过 8 次完美的洗牌，你会发现牌组回到了你开始时的顺序。有关此断言的讨论，请参阅http://www.wiskit.com/marilyn/craig.html或使用关键字“perfect shuffle”进行网络搜索。

更好的洗牌算法是遍历牌组中的每一张卡片，并在每次迭代中选择两张卡片并交换它们。

pseudocode

以下是此算法的工作原理概述。为了绘制程序草图，我使用的是 Java 语句和英语单词的组合，有时被称为伪代码

verbatim

   for (int i=0; i<deck.cards.length; i++) 
     // choose a random number between i and deck.cards.length
     // swap the ith card and the randomly-chosen card

verbatim

使用伪代码的好处是，它通常可以清楚地说明你需要哪些函数。在本例中，我们需要类似于 randomInt 的东西，它在参数 low 和 high 之间选择一个随机整数，以及 swapCards，它接受两个索引并交换指定位置的卡片。

random number

通过查看随机部分，你可能可以弄清楚如何编写 randomInt，尽管你必须注意可能生成超出范围的索引。

swapCards
reference

你也可以自己弄清楚 swapCards。唯一棘手的部分是决定是否仅交换对卡片的引用或交换卡片的内容。选择哪一个重要吗？哪一个更快？

我将把这些函数的剩余实现留给读者作为练习。

排序

[编辑 | 编辑源代码]

sorting

sorting

现在我们已经把牌组弄乱了，我们需要一种方法来将其恢复到顺序。具有讽刺意味的是，有一个排序算法非常类似于洗牌算法。此算法有时被称为选择排序，因为它通过重复遍历数组并在每次遍历时选择最小的剩余卡片来工作。

selection sort

在第一次迭代期间，我们找到最小的卡片并将其与第 0 个位置的卡片交换。在第 i 次迭代期间，我们找到第 i 个卡片右侧最小的卡片并将其与第 i 个卡片交换。

以下是选择排序的伪代码

verbatim

   for (int i=0; i<deck.cards.length; i++) 
     // find the lowest card at or to the right of i
     // swap the ith card and the lowest card

verbatim

同样，伪代码有助于辅助函数的设计。在本例中，我们可以再次使用 swapCards，因此我们只需要一个新的函数，称为 findLowestCard，它接受一个卡片数组和一个它应该开始查找的索引。

helper method
method!helper

再一次，我将把实现留给读者。


子牌组

[编辑 | 编辑源代码]
subdeck

我们应该如何表示手牌或牌组的其他子集？一个不错的选择是创建一个少于 52 张牌的 Deck 对象。

我们可能需要一个函数 subdeck，它接受一个卡片数组和一个索引范围，并返回一个包含指定牌组子集的新卡片数组

verbatim

 public static Deck subdeck (Deck deck, int low, int high) 
   Deck sub = new Deck (high-low+1);

   for (int i = 0; i<sub.cards.length; i++) 
     sub.cards[i] = deck.cards[low+i];
   
   return sub;

verbatim

子牌组的长度是 high-low+1，因为 low 卡片和 high 卡片都包含在内。这种计算可能很混乱，并会导致“差一”错误。绘制图片通常是避免它们的最佳方法。

constructor
overloading

因为我们在 new 命令中提供了一个参数，所以将调用第一个构造函数，它只分配数组，而不分配任何卡片。在 for 循环内部，子牌组将用来自牌组的引用的副本填充。

以下是使用 low=3 和 high=7 创建子牌组的状态图。结果是一手拥有 5 张与原始牌组共享的牌；也就是说，它们是别名。


figure=figs/subdeck.eps


aliasing
reference

我建议别名通常不是一个好主意，因为一个子牌组中的更改将反映在其他子牌组中，这与你对真实卡片和牌组的预期行为不符。但是，如果要处理的对象是不可变的，那么别名可能是一个合理的选择。在本例中，可能没有理由更改卡片的等级或花色。相反，我们将创建每个卡片一次，然后将其视为不可变对象。因此，对于 Cards 而言，别名是一个合理的选择。

作为练习，编写一个 findBisect 的版本，它接受一个子牌组作为参数，而不是一个牌组和一个索引范围。哪个版本更容易出错？你认为哪个版本更高效？

洗牌和发牌

[编辑 | 编辑源代码]
shuffling
dealing

在洗牌部分，我编写了洗牌算法的伪代码。假设我们有一个名为 shuffleDeck 的函数，它接受一个牌组作为参数并对其进行洗牌，我们可以创建并洗牌一个牌组

verbatim

   Deck deck = new Deck ();
   shuffleDeck (deck);

verbatim

然后，要发几手牌，我们可以使用 subdeck

verbatim

  Deck hand1 = subdeck (deck, 0, 4);
  Deck hand2 = subdeck (deck, 5, 9);
  Deck pack = subdeck (deck, 10, 51);

verbatim

此代码将前 5 张牌放在一手牌中，接下来的 5 张牌放在另一手牌中，其余的放在牌堆中。

当你想到发牌时，你是否认为我们应该以真实纸牌游戏中常见的轮流方式一次发一张牌给每个玩家？我考虑过这个问题，但随后意识到对于计算机程序来说，这样做是没必要的。轮流约定旨在减轻不完美的洗牌，并使庄家更难作弊。这两者对于计算机来说都不是问题。

此示例是工程隐喻的危险之一的有用提醒：有时我们对计算机施加了不必要的限制，或者期望计算机拥有它所缺乏的功能，因为我们无意中将隐喻扩展到了其崩溃点。当心误导性的类比。

归并排序

[编辑 | 编辑源代码]

mergesort

efficiency
sorting
mergesort

在排序部分，我们看到了一种简单的排序算法，事实证明它效率不高。为了对项目进行排序，它必须遍历数组 次，每次遍历花费的时间与 成正比。因此，总时间与 成正比。

在本节中，我将概述一种更有效的算法，称为归并排序。为了对项目进行排序，归并排序花费的时间与 成正比。这可能看起来并不令人印象深刻，但是随着 的增大， 和 之间的差异可能会变得巨大。尝试几个 的值并看看。

归并排序背后的基本思想是：如果你有两个子牌组，每个子牌组都已排序，那么将它们合并成一个排序的牌组很容易（而且很快）。尝试用一副牌试试

enumerate

将一副牌分成两副，每副大约 10 张牌。 将它们排序，使得牌面朝上时，最小牌在最上面。 将两副牌面朝上地放在你的面前。

比较两副牌顶端的牌，选择较小的牌。 翻转它并将其添加到合并后的牌堆中。

重复步骤 2，直到其中一副牌为空。 然后，将剩余的牌添加到合并后的牌堆中。

enumerate

最终结果应该是一副排序好的牌。 下面是伪代码示例：

verbatim

 public static Deck merge (Deck d1, Deck d2) 
   // create a new deck big enough for all the cards
   Deck result = new Deck (d1.cards.length + d2.cards.length);

   // use the index i to keep track of where we are in
   // the first deck, and the index j for the second deck
   int i = 0;
   int j = 0;

   // the index k traverses the result deck
   for (int k = 0; k<result.cards.length; k++) 

     // if d1 is empty, d2 wins; if d2 is empty, d1 wins;
     // otherwise, compare the two cards

     // add the winner to the new deck
   
   return result;

verbatim

测试合并算法的最佳方法是：构建一副牌并洗牌，使用 `subdeck` 方法创建两副（小）牌，然后使用上一章的排序例程对两副牌进行排序。 然后，将这两副牌传递给 `merge` 函数，以查看它是否正常工作。

testing

如果能够使其正常工作，请尝试实现一个简单的 `mergeSort` 函数。

verbatim

 public static Deck mergeSort (Deck deck) 
   // find the midpoint of the deck
   // divide the deck into two subdecks
   // sort the subdecks using sortDeck
   // merge the two halves and return the result

verbatim

然后，如果它也能正常工作，真正的乐趣就开始了！合并排序算法的神奇之处在于它是一种递归算法。 当你对子牌堆进行排序时，为什么使用旧的、速度慢的排序算法？ 为什么不用你正在编写的新的 `mergeSort` 算法呢？

recursion

这不仅是一个好主意，也是为了获得我承诺的性能优势所必需的。 但是，为了使其工作，你必须添加一个基本情况，以防止它无限递归。 一个简单的情况是包含 0 或 1 张牌的子牌堆。 如果 `mergeSort` 收到这样的小牌堆，它可以直接返回，因为它们已经排序。

递归版本的 `mergeSort` 应该类似于：

verbatim

 public static Deck mergeSort (Deck deck) 
   // if the deck is 0 or 1 cards, return it

   // find the midpoint of the deck
   // divide the deck into two subdecks
   // sort the subdecks using mergesort
   // merge the two halves and return the result

verbatim

像往常一样，思考递归程序有两种方式：你可以思考整个执行流程，或者你可以跳过“信任的跳跃”。 为了鼓励你进行信任的跳跃，我故意构建了这个示例。

leap of faith

当使用 `sortDeck` 函数对子牌堆进行排序时，你并没有强迫自己遵循执行流程，对吧？ 你只是假设 `sortDeck` 方法会正常工作，因为你已经调试过了。 好吧，为了让 `mergeSort` 成为递归函数，你所做的只是用另一种排序算法替换了一个。 没有理由用不同的方式阅读程序。

好吧，实际上你需要考虑正确地获取基本情况，并确保最终能到达它，除此之外，编写递归版本应该没有问题。 祝你好运！

术语表

[edit | edit source]

描述

[伪代码：] 一种通过使用英语和 Java 代码的组合编写程序草稿的方法。

[辅助方法：] 通常是一个小方法，它本身并不做任何特别有用的事情，但它可以帮助另一个更有用的方法。

pseudocode
helper method
method!helper


描述

Retrieved from "https://wikibooks.cn/wiki/The_Way_of_the_Java/Objects_of_Arrays"
华夏公益教科书