994
技術社區[雲棲]
《數據結構與抽象：Java語言描述（原書第4版）》一練習
本節書摘來華章計算機《數據結構與抽象：Java語言描述（原書第4版）》一書中的第2章 ，［美］弗蘭克M.卡拉諾（Frank M. Carrano） 蒂莫西M.亨利（Timothy M. Henry） 著 羅得島大學 新英格蘭理工學院 辛運幃 饒一梅 譯 更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
練習
1.為什麼類ArrayBag中的方法getIndexOf和removeEntry是私有的而不是公有的？
2.為ADT包實現方法replace，用一個給定對象替換當前包中的對象，並返回原始對象。
3.修改2.1.7節中給出的方法clear的定義，以便更有效率且僅調用checkInitialization方法。
4.修改2.1.7節的避免重複工作中給出的方法remove，以便從包中刪除一個隨機項。這個修改會影響到類ArrayBag中的其他方法嗎？
5.為類ArrayBag定義方法removeEvery，從包中刪除給定項的所有出現。
6.類ArrayBag的實例有固定大小，而ResizableArrayBag的實例則沒有。給出一些例子，如果包的大小是
a.固定的
b.可變的
則包是合適的。
7.假定想定義類PileOfBooks來實現前一章項目2中描述的接口。包是表示一堆書的合理集合嗎？解釋之。
8.考慮2.2.2節中討論的類ResizableArrayBag的實例myBag。假定myBag的初始容量是10。
a.向myBag中添加了145項後
b.向myBag中添加20項後
數組bag的長度是多少？
9.在客戶層定義一個方法，其參數是類ArrayBag的實例，並返回類ResizableArrayBag的實例，其中含有與參數所給包中相同的項。
10.假定包中含有Comparable對象，例如字符串。一個Comparable對象屬於實現了標準接口Comparable的一個類，所以有方法compareTo。為類ArrayBag實現下列方法：
- 返回包中最小對象的方法getMin
- 返回包中最大對象的方法getMax
- 刪除並返回包中最小對象的方法removeMin
- 刪除並返回包中最大對象的方法removeMax
11.假定包中含有Comparable對象，如前一個練習中所描述的那樣。為類ArrayBag定義一個方法，返回由小於某個給定項的項組成的新包。方法的頭可以如下所示：
確保你的方法不會影響原始包的狀態。
12.為類ArrayBag定義equals方法，當兩個包的內容相同時返回真。注意，兩個相等的包應含有相同個數的項，每個項出現在每個包中的個數應相等。每個數組中的項的次序是無關的。
13.類ResizableArrayBag有一個數組，當向包中添加對象時其大小增大。修改這個類，使得當從包中刪除對象時，它的數組還可以縮小。完成這個任務需要兩個新的私有方法，如下所示：
第一個新方法檢查是否應該減小數組的大小：
如果包中的項數小於數組大小的一半且數組的大小大於20，這個方法返回真。
第二個新方法創建一個新數組，其大小是當前數組大小的3/4，且數組的大小大於20。
實現這兩個方法，然後使用它們來定義兩個remove方法。
14.考慮前一個練習中描述的兩個私有方法。
a. 方法isTooBig需要數組的大小大於20。如果沒有這個要求可能會發生什麼問題？
b. 方法reduceArray與方法doubleCapacity並不相同，它沒有讓數組的大小減小一半。如果數組的大小減到一半而不是3/4，可能會出現什麼問題？
15.為類ResizableArrayBag定義前一章練習5描述的方法union。
16.為類ResizableArrayBag定義前一章練習6描述的方法intersection。
17.為類ResizableArrayBag定義前一章練習7描述的方法difference。
項目
1.設計並實現單人猜謎遊戲，選擇n個1～m之間的隨機整數，要求用戶來猜它們。同一個整數可能被選中多次。例如，遊戲可能選中1～10之間的以下4個整數：4,6,1,6。用戶和遊戲之間的交互可能是：
輸入你猜測的1～10之間選中的4個整數：
1 2 3 4
你猜的2是正確的，再猜。
輸入你猜測的1～10之間選中的4個整數：
2 4 6 8
你猜的2是正確的，再猜。
1 4 6 6
正確！再玩一次？不
再見！
設計作為ADT的遊戲。使用包來保存遊戲選擇的整數。整數m和n由客戶指定。
2.定義一個表示1.5節描述的集合（set）並實現接口的類ArraySet。在實現中使用類ResizableArrayBag。然後寫一個程序，充分論證你的實現。
3.重複前一個項目，使用可變大小的數組而不是使用類ResizableArrayBag。
4.定義類PileOfBooks，實現前一章項目2中描述的接口。在實現中使用可變大小的數組。然後寫一個程序，充分論證你的實現。
5.定義類Ring，實現前一章項目3描述的接口。在實現中使用可變大小的數組。然後寫一個程序，充分論證你的實現。
6.可以寫一個集合或一個包，創建拚寫檢查器。集合或包用作字典，且含有一組正確拚寫的字。要看一個字是否拚寫正確，可以看它是否含在字典中。使用這種方法對外部文件中保存的字創建拚寫檢查器。為簡化任務，限製字典的規模。
7.重做前一個項目，創建拚寫檢查器，但是將你要檢查拚寫的字放入包中。字典（含有正確拚寫字的集合或包）與要檢查的字的包之間的差，是拚寫錯誤的字的包。
自測題答案
1.學生仍然在連續編號的椅子上。不需要記錄空椅子的位置。
2.不移動學生從而節省時間。
3.最大編號椅子中的學生。
4.不相等。僅當包滿時兩個值才相等。
5.如果客戶含有如下的一條語句
則myBag.getCurrentSize()將是數組bagContents中項的個數。根據設計，bagContents.length可以大於包中項的個數。
6.該語句將包的第一個元素設置為null。numberOfEntries的值不改變，所以它是5。
7.
8.包aBag為空。當調用displayBag時，執行語句
當調用toArray時，執行語句
因為aBag為空，所以numberOfEntries是0。因此新數組result是空的。跳過toArray中的循環，返回空數組且賦給bagArray。因為bagArray.length是0，所以跳過displayBag中的循環。調用displayBag(aBag)的結果是簡單的一行：
9.優點：這個定義易寫，所以可能少犯錯誤。
缺點：這個定義要花更多的執行時間，如果anEntry在包中出現多次時。注意，方法getFrequencyOf中的循環對包中的所有項重複，而2.1.6節中所給的方法contains中的循環一旦找到所需的項立即結束。
10.
11.雖然對於客戶的方法和ArrayBag中的其他方法，包會變為空的，但被刪除對象的引用仍保留在數組bag中。即使客戶不保留指向這些對象的引用，與它們相關的內存也沒被釋放。
12.設置bag[numberOfEntries]為null，該方法使得分配給被刪項的內存被回收，除非客戶還有另一個指向這個項的引用。
13.數組bag中不是最後一項的項設置為null。其餘的項不再位於數組的連續元素中。可以重新安排項來去掉null項，或者修改其他方法跳過null項。
14. a.不能。如果result是null（且這十分可能），則將出現NullPointerException。
b.能。
15.在包中找到"B"後，remove方法將它替換為數組bag中的最後項，即"C"。然後將最後項替換為null。雖然可以定義remove來得到問題中所給出的兩個其他可能的結果，但每個結果都是不好的。例如，要得到"A"，"A"，"A"，"C"，null，remove應該移動數組元素，需要更多的運行時間。在數組中留下空隙，如"A"，"A"，null，"A"，"C"，對remove來說容易辦到，但對其他方法邏輯就複雜了。
16.
17.
或者
18.
或者
19.
20.
21.簡單的賦值語句可能不是好的選擇，因為客戶可能使用指向作為參數傳給構造方法的數組的引用來破壞包的數據。複製參數數組到數組bag中是必需的，以保護包數據的完整性。
22.優點：如果你知道下標，可以直接訪問任意數組位置。
缺點：數組有固定的大小，所以或者浪費空間或者超界。調整數組大小可以避免後一個缺點，但需要將原始數組的內容複製到更大的數組中。
最後更新：2017-06-26 18:02:21