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
描述