Java 之道/对象数组
composition nested structure
到目前为止，我们已经看到了组合（将语言功能组合成各种排列的能力）的几个例子。我们见过的第一个例子是使用方法调用作为表达式的组成部分。另一个例子是语句的嵌套结构：你可以将 if 语句放在 while 循环中，或放在另一个 if 语句中，等等。
看到这种模式，并学习了数组和对象，你应该不会惊讶地发现你可以拥有对象数组。事实上，你也可以拥有包含数组的对象（作为实例变量）；你可以拥有包含数组的数组；你可以拥有包含对象的对象，等等。
在接下来的两章中，我们将以 Card 对象为例，研究这些组合的一些例子。
Card 对象
Card class!Card
如果你不熟悉常见的扑克牌，现在是拿一副牌的好时机，否则本章可能难以理解。一副牌中有 52 张牌，每张牌都属于四种花色之一和十三种点数之一。花色是黑桃、红心、方块和梅花（在桥牌中按降序排列）。点数是 A、2、3、4、5、6、7、8、9、10、J、Q 和 K。根据你玩的牌局，A 的点数可能是比 K 大还是比 2 小。
rank suit
如果我们想定义一个新对象来表示一张扑克牌，那么实例变量应该是什么就很明显了：点数和花色。实例变量应该是什么类型就不那么明显了。一种可能性是字符串，包含诸如 "Spade"（黑桃）的花色和 "Queen"（Q）的点数。这种实现的一个问题是，比较牌以查看哪张牌的点数或花色更高并不容易。
encode encrypt map to
另一种方法是使用整数来编码点数和花色。通过 “编码”，我不意味着有些人认为的“加密”，或者翻译成秘密代码。计算机科学家所说的 “编码” 类似于 “定义一个映射” 在数字序列和我想表示的事物之间。例如，
tabularl c l
红心 & & 2 方块 & & 1 梅花 & & 0 tabular
这种映射的明显特征是花色按顺序映射到整数，因此我们可以通过比较整数来比较花色。点数的映射相当明显；每个数字点数都映射到相应的整数，而对于面牌
tabularl c l
Q & & 12 K & & 13 tabular
它们不属于 Java 程序的一部分。它们是程序设计的一部分，但从不显式地出现在代码中。Card 类型的类定义如下
verbatim class Card
int suit, rank;
public Card () this.suit = 0; this.rank = 0;
public Card (int suit, int rank) this.suit = suit; this.rank = rank;
verbatim
像往常一样，我提供了两个构造函数，其中一个为每个实例变量获取参数，另一个不获取参数。
constructor
要创建一个表示 3 梅花的对象，我们将使用 new 命令
verbatim
Card threeOfClubs = new Card (0, 3);
verbatim
第一个参数 0 表示花色梅花。
printCard print!Card
当你创建一个新类时，第一步通常是声明实例变量并编写构造函数。第二步通常是编写每个对象都应该具有的标准方法，包括一个打印对象的方法，以及一个或两个比较对象的方法。我将从 printCard 开始。
String!array of array!of String
为了以人类易于阅读的方式打印 Card 对象，我们希望将整数代码映射到单词。一个自然的方法是使用字符串数组。你可以创建字符串数组的方式与创建基本类型的数组的方式相同
verbatim
String[] suits = new String [4];
verbatim
然后我们可以设置数组元素的值。
verbatim
suits[0] = "Clubs"; suits[1] = "Diamonds"; suits[2] = "Hearts"; suits[3] = "Spades";
verbatim
创建数组并初始化元素是一个如此常见的操作，以至于 Java 为其提供了一种特殊的语法
verbatim
String[] suits = "Clubs", "Diamonds", "Hearts", "Spades" ;
verbatim
此语句的效果与单独的声明、分配和赋值相同。该数组的状态图可能如下所示
state diagram
figure=figs/stringarray.eps
reference String!reference to
数组的元素是对字符串的引用，而不是字符串本身。这对所有对象数组都是如此，我将在后面详细讨论。现在，我们只需要另一个字符串数组来解码点数
verbatim
String[] ranks = "narf", "Ace", "2", "3", "4", "5", "6",
"7", "8", "9", "10", "Jack", "Queen", "King" ;
verbatim
"narf" 的原因是充当数组的第零个元素的占位符，该元素永远不会被使用。唯一有效的点数是 1-13。当然，这个浪费的条目不是必需的。我们可以像往常一样从 0 开始，但最好将 2 编码为 2，将 3 编码为 3，等等。
使用这些数组，我们可以通过使用花色和点数作为索引来选择合适的字符串。在 printCard 方法中，
verbatim public static void printCard (Card c)
String[] suits = "Clubs", "Diamonds", "Hearts", "Spades" ;
String[] ranks = "narf", "Ace", "2", "3", "4", "5", "6",
"7", "8", "9", "10", "Jack", "Queen", "King" ;
System.out.println (ranks[c.rank] + " of " + suits[c.suit]);
verbatim
表达式 suits[c.suit] 意味着 “使用对象 c 中的实例变量 suit 作为名为 suits 的数组的索引，并选择合适的字符串”。此代码的输出
verbatim
Card card = new Card (1, 11); printCard (card);
verbatim
是 J 方块。
sameCard 方法
sameCard
单词 “相同” 是那些在自然语言中出现的东西，直到你仔细思考它们，你才会发现它们比你预期的要多。
ambiguity natural language language!
例如，如果我说 “克里斯和我拥有相同的汽车”，我的意思是他的汽车和我的汽车是相同的品牌和型号，但它们是两辆不同的汽车。如果我说 “克里斯和我拥有同一个母亲”，我的意思是他的母亲和我的母亲是同一个。因此，根据上下文，“相同” 的概念是不同的。
当你说到对象时，也存在类似的歧义。例如，如果两张 Card 相同，是否意味着它们包含相同的数据（点数和花色），还是它们实际上是同一个 Card 对象？
要查看两个引用是否引用同一个对象，我们可以使用 == 运算符。例如
verbatim
Card card1 = new Card (1, 11); Card card2 = card1;
if (card1 == card2)
System.out.println ("card1 and card2 are the same object.");
verbatim
这种类型的相等性被称为浅层相等性，因为它只比较引用，而不比较对象的实际内容。
equality identity shallow equality deep equality
要比较对象的实际内容——深层相等性——通常会编写一个名称类似于 sameCard 的方法。
verbatim public static boolean sameCard (Card c1, Card c2)
return (c1.suit == c2.suit && c1.rank == c2.rank);
verbatim
现在，如果我们创建了两个包含相同数据的不同对象，我们可以使用 sameCard 来查看它们是否表示同一张牌
verbatim
Card card1 = new Card (1, 11); Card card2 = new Card (1, 11);
if (sameCard (card1, card2))
System.out.println ("card1 and card2 are the same card.");
verbatim
在这种情况下，card1 和 card2 是两个包含相同数据的不同对象
figure=figs/card.eps
所以条件为真。当 card1 == card2 为真时，状态图是什么样子的？
aliasing
在不可比较部分中，我说你永远不应该对字符串使用 == 运算符，因为它不会像你期望的那样工作。它不会比较字符串的内容（深层相等性），而是检查两个字符串是否为同一个对象（浅层相等性）。
compareCard operator!conditional conditional operator
对于基本类型，存在比较值的条件运算符，并确定何时一个值大于或小于另一个值。这些运算符（< 和 > 及其他运算符）不适用于对象类型。对于字符串，存在一个内置的 compareTo 方法。对于 Card，我们必须自己编写一个，我们将称之为 compareCard。稍后，我们将使用此方法对一副牌进行排序。
ordering complete ordering partial ordering
有些集合是完全有序的，这意味着您可以比较任何两个元素并判断哪个更大。例如，整数和浮点数是完全有序的。有些集合是无序的，这意味着没有有意义的方式来表示一个元素大于另一个元素。例如，水果是无序的，这就是为什么我们不能比较苹果和橘子的原因。在 Java 中，布尔类型是无序的；我们不能说 true 大于 false。
一副扑克牌是部分有序的，这意味着有时我们可以比较牌，有时则不能。例如，我知道梅花 3 比梅花 2 高，方块 3 比梅花 3 高。但是，哪个更好，梅花 3 还是方块 2？一个等级更高，但另一个花色更高。
comparable
为了使牌可比较，我们必须决定哪个更重要，等级还是花色。说实话，这个选择是完全任意的。为了选择，我会说花色更重要，因为当你买一副新牌时，它会按顺序排列，所有梅花放在一起，然后是所有方块，依此类推。
有了这个决定，我们可以编写 compareCard。它将接受两个 Card 作为参数，如果第一个牌获胜则返回 1，如果第二个牌获胜则返回 -1，如果它们平局（表示深度相等）则返回 0。有时很难记住这些返回值，但它们对于比较方法来说是相当标准的。
首先我们比较花色
verbatim
if (c1.suit > c2.suit) return 1; if (c1.suit < c2.suit) return -1;
verbatim
如果两个语句都不为真，则花色必须相等，我们必须比较等级
verbatim
if (c1.rank > c2.rank) return 1; if (c1.rank < c2.rank) return -1;
verbatim
如果这两个都不为真，则等级必须相等，因此我们返回 0。在这种排序中，A 会出现在 2 之前。
作为练习，请修复它，使 A 的等级高于 K，并将此代码封装在一个方法中。
array!of object object!array of deck
我选择 Card 作为本章的对象的原因是，有一个明显的用途是用于牌数组——一副牌。以下是一些创建一副 52 张牌的代码
verbatim
Card[] deck = new Card [52];
verbatim
以下是此对象的状图表
state diagram
figure=figs/cardarray.eps
这里要看到的重要一点是，数组只包含对对象的引用；它不包含任何 Card 对象。数组元素的值被初始化为 null。您可以按照通常的方式访问数组元素
verbatim
if (deck[3] == null)
System.out.println ("No cards yet!");
verbatim
但是，如果您尝试访问不存在的 Cards 的实例变量，您将获得 NullPointerException。
exception!NullPointer run-time error null
verbatim
deck[2].rank; // NullPointerException
verbatim
尽管如此，这仍然是访问牌组中“第二十张”牌（实际上是第三张——我们从零开始，记住吗？）的等级的正确语法。这是组合的另一个例子，它结合了访问数组元素和对象实例变量的语法。
composition loop!nested
用 Card 对象填充牌组的最简单方法是编写一个嵌套循环
verbatim
int index = 0;
for (int suit = 0; suit <= 3; suit++)
for (int rank = 1; rank <= 13; rank++)
deck[index] = new Card (suit, rank);
index++;
verbatim
外部循环枚举花色，从 0 到 3。对于每个花色，内部循环枚举等级，从 1 到 13。由于外部循环迭代 4 次，内部循环迭代 13 次，因此主体执行的总次数为 52（13 乘以 4）。
index
我使用变量 index 来跟踪下一张牌应该放在牌组中的哪个位置。以下状图表显示了分配前两张牌后牌组的样子
figure=figs/cardarray2.eps
作为练习，请将此牌组构建代码封装在一个名为 buildDeck 的方法中，该方法不接受参数并返回一个完全填充的 Cards 数组。
encapsulation
printdeck
printDeck print!array of Cards
无论何时处理数组，拥有一个能够打印数组内容的方法都很方便。我们已经多次看到遍历数组的模式，因此以下方法应该很熟悉
verbatim
public static void printDeck (Card[] deck)
for (int i=0; i<deck.length; i++)
printCard (deck[i]);
verbatim
由于 deck 的类型为 Card[]，因此 deck 的元素类型为 Card。因此，deck[i] 是 printCard 的合法参数。
findcard
searching linear search findCard
我要编写的下一个方法是 findCard，它会在一个 Card 数组中搜索，以查看它是否包含某个特定牌。为什么要用这个方法可能并不明显，但它给了我一个机会展示两种搜索方法，线性搜索和二分搜索。
traverse loop!search
线性搜索是这两种方法中更明显的；它涉及遍历牌组并将每张牌与我们要查找的牌进行比较。如果我们找到了它，我们将返回它在牌组中出现的位置索引。如果它不在牌组中，我们将返回 -1。
verbatim
public static int findCard (Card[] deck, Card card)
for (int i = 0; i< deck.length; i++)
if (sameCard (deck[i], card)) return i;
return -1;
verbatim
findCard 的参数名为 card 和 deck。使用与类型相同的名称作为变量（card 变量的类型为 Card）可能看起来很奇怪。这是合法且常见的，尽管有时它会使代码难以阅读。然而，在本例中，我认为它有效。
statement!return return!inside loop
该方法在找到牌后立即返回，这意味着如果我们找到了要查找的牌，我们不必遍历整个牌组。如果循环终止而没有找到牌，我们就知道牌不在牌组中并返回 -1。
如果牌组中的牌没有按顺序排列，那么没有比这更快的搜索方法。我们必须查看每张牌，否则就无法确定我们想要的牌是否不在牌组中。
bisection search
但是当你查字典时，你不会线性地搜索每个词。原因是这些词是按字母顺序排列的。因此，你可能使用了一种类似于二分搜索的算法
enumerate
从中间开始。
选择页面上的一个词，并将其与你要查找的词进行比较。
如果你找到了你要查找的词，停止。
如果你要查找的词位于页面上的词之后，翻到字典中的更靠后的位置，然后转到步骤 2。
如果你要查找的词位于页面上的词之前，翻到字典中的更靠前的位置，然后转到步骤 2。
enumerate
如果你到达了一个位置，页面上只有两个相邻的词，而你的词位于它们之间，那么你可以得出结论，你的词不在字典中。唯一的例外情况是你的词被错误地归档了，但这与我们假设这些词是按字母顺序排列的矛盾。
在牌组的情况下，如果我们知道这些牌是按顺序排列的，我们可以编写一个速度快得多的 findCard 版本。编写二分搜索的最佳方法是使用递归方法。这是因为二分法本质上是递归的。
findBisect
诀窍是编写一个名为 findBisect 的方法，该方法接受两个索引作为参数，low 和 high，它们表示应搜索的数组段（包括 low 和 high）。
enumerate
要搜索数组，请在 low 和 high 之间选择一个索引（称为 mid），并将其与你要查找的牌进行比较。
如果你找到了它，停止。
如果 mid 处的牌高于你的牌，则在 low 到 mid-1 范围内搜索。
如果 mid 处的牌低于你的牌，则在 mid+1 到 high 范围内搜索。
enumerate
步骤 3 和 4 看起来可疑地像递归调用。以下是将所有这些内容翻译成 Java 代码的样子
verbatim
public static int findBisect (Card[] deck, Card card, int low, int high) int mid = (high + low) / 2; int comp = compareCard (deck[mid], card);
if (comp == 0)
return mid;
else if (comp > 0)
return findBisect (deck, card, low, mid-1);
else
return findBisect (deck, card, mid+1, high);
verbatim
我没有三次调用 compareCard，而是调用了一次并保存了结果。
尽管此代码包含二分搜索的核心，但它仍然缺少一部分。以目前的形式，如果牌不在牌组中，它将永远递归。我们需要一种方法来检测这种条件并以适当的方式处理它（通过返回 -1）。
recursion
判断你的牌是否不在牌组中最简单的方法是，如果牌组中没有牌，即 high 小于 low。当然，牌组中仍然有牌，但我的意思是牌组中由 low 和 high 指定的部分中没有牌。
添加了这一行后，该方法可以正常工作
verbatim
public static int findBisect
(Card[] deck, Card card, int low, int high)
System.out.println (low + ", " + high);
if (high < low) return -1;
int mid = (high + low) / 2; int comp = deck[mid].compareCard (card);
if (comp == 0)
return mid;
else if (comp > 0)
return findBisect (deck, card, low, mid-1);
else
return findBisect (deck, card, mid+1, high);
verbatim
我在开头添加了一个打印语句，这样我就可以观察递归调用的顺序并说服自己它最终会到达基本情况。我尝试了以下代码
verbatim
Card card1 = new Card (1, 11); System.out.println (findBisect (deck, card1, 0, 51));
verbatim
并获得了以下输出
verbatim 0, 51 0, 24 13, 24 19, 24 22, 24 23 verbatim
然后，我编造了一张不在牌组中的牌（方块 15），并尝试找到它。我得到了以下结果
verbatim 0, 51 0, 24 13, 24 13, 17 13, 14 13, 12 -1 verbatim
这些测试并不能证明该程序是正确的。事实上，无论进行多少次测试都无法证明程序是正确的。另一方面，通过查看几个案例并检查代码，你或许可以说服自己。
testing correctness
递归调用的次数相当少，通常为 6 或 7 次。这意味着我们只需要调用 compareCard 6 或 7 次，而如果进行线性搜索，则最多可能需要调用 52 次。通常，二分法比线性搜索快得多，尤其是对于大型数组。
递归程序中常见的两个错误是忘记包含基本情况以及写递归调用，使基本情况永远无法到达。这两种错误都会导致无限递归，在这种情况下，Java 将（最终）抛出 StackOverflowException。
recursion!infinite infinite recursion exception!StackOverflow
deck subdeck
看看 findBisect 的接口
verbatim
public static int findBisect
(Card[] deck, Card card, int low, int high) verbatim
将三个参数中的三个，deck、low 和 high，视为一个指定子牌组的单个参数可能更有意义。我们在 Section graphics 中谈论边界框时采取了类似的观点。在那种情况下，我将 x、y、width 和 height 当作一个参数，一个边界框。
parameter!abstract abstract parameter
这种事情很常见，我偶尔会把它想成一个抽象参数。我所说的“抽象”是指在程序文本中没有明确存在的，但从更高层次描述程序功能的内容。
例如，当你调用一个方法并传递一个数组和边界 low 和 high 时，没有什么可以阻止被调用方法访问数组中超出边界的部分。因此，你并没有真正发送牌组的一个子集；你真正发送的是整个牌组。但是，只要接收方遵守规则，将它抽象地视为一个子牌组是有意义的。
您可能在“对象操作”章节中注意到了这种抽象的另一个例子，当时我提到了一个“空”数据结构。 我之所以用引号将“空”括起来，是因为它并非字面意义上的准确描述。 所有的变量都始终拥有值。 当您创建它们时，它们会被赋予默认值。 所以，不存在所谓“空”对象。
但是，如果程序保证在写入之前从未读取过变量的当前值，那么当前值就无关紧要了。 从抽象的角度来看，将这样的变量视为“空”是有意义的。
这种思维方式，即程序获得超越其字面编码的意义，是计算机科学家思维方式中非常重要的一个部分。 有时候，“抽象”一词被频繁使用，并在许多不同的语境中出现，以至于它逐渐失去了意义。 尽管如此，抽象仍然是计算机科学（以及许多其他领域）的核心概念。
abstraction
对“抽象”更一般的定义是：“对复杂系统进行简化描述的建模过程，以省略不必要的细节，同时捕捉相关的行为。”
描述
[编码:] 通过构建它们之间的映射，使用另一组值来表示一组值。
[浅层相等:] 引用相等。 两个指向同一对象的引用。
[深层相等:] 值相等。 两个指向具有相同值的对象的引用。
[抽象参数:] 一组参数，它们共同充当单个参数。
[抽象:] 以高于代码字面表示的级别来解释程序（或其他任何事物）的过程。
encode shallow equality deep equality abstract parameter abstraction
描述