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