867
《數據結構與抽象：Java語言描述（原書第4版）》一2.1.7 刪除項的方法
本節書摘來華章計算機《數據結構與抽象：Java語言描述（原書第4版）》一書中的第2章 ，第2.1.7節，［美］弗蘭克M.卡拉諾（Frank M. Carrano） 蒂莫西M.亨利（Timothy M. Henry） 著 羅得島大學 新英格蘭理工學院 辛運幃 饒一梅 譯 更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
2.1.7 刪除項的方法
我們將從包中刪除項的3個方法推遲到現在，因為3個方法中的一個有些困難，它涉及的查找機製與contains中用到的相似。我們從更容易定義的另兩個方法入手。
方法clear。方法clear從包中刪除所有的項，一次刪除一個。下麵這個clear的定義調用方法remove，直到包為空。
循環中每次要刪除哪個項是不重要的。所以，我們調用刪除一個不確定項的remove方法。另外，不保存方法返回的這個項。
注意，因為remove方法將調用checkInitialization，所以clear不需要顯式地調用它。
注：我們可以根據尚未定義的方法remove來定義方法clear。但是，在定義remove之前，我們不能完全測試clear。
自測題10 修改方法clear的定義，讓它不調用isEmpty。
提示：while語句應該有一個空循環體。
自測題11 用下列語句
替換上一段的clear定義中的循環，有什麼缺點？
刪除不確定項。不帶參數的方法remove從包中刪除一個不確定項，隻要包不為空。回憶程序清單1-1所示的接口中給出的方法的規格說明，該方法返回被它刪除的項：
如果方法執行前包是空的，則返回null。
從包中刪除一個項，涉及從數組中刪除它。雖然我們能訪問數組bag中的任何項，但最後一項是最容易刪除的。為此，
- 訪問最後一項，它能被返回。
- 將項的數組元素設置為null。
- numberOfEntries減1。
numberOfEntries減1，就會忽略最後一項，意味著它已被高效地刪除了，即使我們沒有將它在數組中的位置設置為null。但是不要跳過這一步。
將前麵的步驟轉換為Java程序，得到如下的方法定義：
安全說明：將數組元素bag[numberOfEntries???-???1]設置為null，標記被刪除對象可進行垃圾回收，並防止惡意代碼來訪問它。
安全說明：在正確計數後更新計數器。在前麵的代碼中，刪除數組最後一項後才將numberOfEntries減1，即使計算了3次numberOfEntries-1。雖然下麵的改進可以避免這個重複，但時間上微不足道的節省不值得冒太早減小計數器帶來的不安全
風險：
不可否認，在這種情形下，數組和計數器不同步的情況還是有可能的。不管怎樣，如果邏輯更複雜，則數組處理過程中可能會發生異常。這個中斷將導致已更新的計數器不準確。
自測題12 為什麼方法remove將從數組bag中刪除的項替換為null？
自測題13 前一個remove方法刪除數組bag中的最後一項。刪除其他項為什麼會更難完成？
刪除給定的項。從包中刪除項的第3個方法涉及刪除給定項（稱為anEntry）的方法。如果項在包中出現多次，則僅刪除它的一次出現。沒有指定刪除哪次出現。我們隻刪除查找時遇到的anEntry的首次出現。正如我們在1.2節中所討論的，方法將根據在包中是否找到這個項而返回真或假。
假定包不為空，則查找數組bag與方法contains所做的一樣。如果anEntry等於bag[index]，則記下index的值。圖2-4說明成功查找後的數組。
現在需要刪除bag[index]中的項。如果隻寫
則刪除bag[index]中指向的項的引用，但數組中會留下空隙。即包的內容不再占據連續的數組位置，如圖2-5a所示。我們可以移動隨後的項來去掉這個空隙，如圖2-5b所示，並將指向最後項的重複引用替換為null，如圖2-5c所示。但不一定用這個費時的方法。
記住，我們不需要維護包中項的具體次序。所以刪除項後，不是移動數組項，而是用數組中最後麵的項替換被刪除的項，如圖2-6所示。找到bag[index]中的anEntry後，如圖2-6a所示，將bag[numberOfEntries-1]中的項複製到bag[index]中（見圖2-6b）。然後將bag[numberOfEntries-1]中的項替換為null，如圖2-6c所示，最後numberOfEntries減1。
刪除給定項的偽代碼。現在將前麵的討論用偽代碼寫出來，對給定的項anEntry，從含有它的包中刪除：
這個偽代碼假定包中含有anEntry。
在偽代碼中添加一些細節，以適應anEntry不在包中的情形，偽代碼如下：
避免重複工作。很容易將這段偽代碼翻譯為Java方法remove。但是，如果我們這樣做了，就會發現新方法與刪除不確定項中寫過的remove方法有很多類似的地方。實際上，如果anEntry出現在bag[numberOfEntries-1]處，則這兩個remove方法將有完全相同的效果。為避免這樣的重複勞動，兩個remove方法可以調用一個私有方法來完成刪除操作。可以如下說明一個方法：
因為這是一個私有方法，所以類中的其他方法可以給它傳一個下標作為參數，仍能讓這個下標（實現細節）對類的客戶隱藏。
在實現這個私有方法之前，讓我們看看是否可以用它來修改“刪除不確定項”中的remove方法。因為該方法刪除並返回數組bag的最後一項，即bag[numberOfEntries-1]，所以它的定義中可以調用removeEntry(numberOfEntries-1)。繼續我們的工作，就如同removeEntry已經定義且測試過一樣，可以如下定義remove：
這個定義看上去不錯，我們來實現第二個remove方法。
第二個remove方法。第一個remove方法不查找要刪除的項，因為它刪除數組中的最後一項。但第二個remove方法必須執行查找。現在先不考慮在數組中查找一個項的細節，我們將這個任務委派給另一個私有方法來完成，它的規格說明如下所示。
假定這個私有方法已經定義且測試過，我們在第二個remove方法中調用它，如下所示。
注意，removeEntry返回它刪除的項或者null。這正是第一個remove方法所需要的，但第二個remove方法必須返回一個布爾值。所以，在第二個方法中，我們必須將想刪除的項與removeEntry的返回值進行比較，以便得到希望的布爾值。
自測題14 remove的前一個定義中的return語句能寫成下麵這樣嗎？
自測題15 ArrayBag中的數組bag含有包aBag中的項。如果數組含有字符串"A"，"A"，"B"，"A"，"C"，為什麼aBag.remove("B")將數組的內容改變為"A"，"A"，"C"，"A"，null，而不是"A"，"A"，"A"，"C"，null或"A"，"A"，null，"A"，"C"？
私有方法removeEntry的定義。現在回過頭來看在“刪除給定項的偽代碼”中為從包中刪除指定項而寫的偽代碼。私有方法removeEntry假定項的查找已經完成，所以可以忽略偽代碼的第一步。不管怎樣，偽代碼的其他部分給出了刪除一個項的基本邏輯。可以修改偽代碼，如下所示。
前一段給出的第二個remove方法的定義將getIndexOf返回的整數傳給removeEntry。因為getIndexOf可能返回-1，所以removeEntry必須對這樣一個參數值進行查找。因此，如果包不為空（即如果numberOfEntries大於0）且givenIndex大於或等於0，則removeEntry刪除位於givenIndex的數組項，將它用最後一項來替換，並讓numberOfEntries減1。然後該方法返回刪除的項。但是，如果包是空的，則該方法返回null。
該方法的代碼如下所示。
找到要刪除的項。現在需要考慮如何在包中找到要刪除的項，這樣才可以將它的下標傳給removeEntry。方法contains執行與remove的定義中查找anEntry相同的機製。不幸的是，contains返回真或假，它不返回項在數組中的下標。所以在定義這個方法時不能簡單調用那個方法。
設計決策：方法contains應該返回找到項的下標嗎？
我們應該修改contains的定義，讓它返回一個下標而不是一個布爾值嗎？不應該。作為一個公有方法，contains不應該給客戶提供這樣的實現細節。客戶不應該期望得到放在數組中的包的項，因為它們沒有具體的次序。不應改變contains的規格說明，而是應該遵循最初的規劃，定義一個私有方法來查找一個項並返回它的下標。
getIndexOf的定義。getIndexOf的定義與contains的定義很像，我們記得方法contains中它的循環是這樣的：
這個循環結構適合於方法getIndexOf，但當找到項時必須保存index的值。該方法將返回這個下標而不是一個布爾值。
為修改前麵這個循環以便將其用在getIndexOf中，我們定義一個整數變量where來記錄當anEntry等於bag[index]時index的值。所以getIndexOf是這樣的：
方法getIndexOf返回where的值。注意，我們將where初始化為-1，這是沒找到anEntry時返回的值。
自測題16 在方法getIndexOf的return語句之前，能添加什麼assert語句來表示方法能夠返回的可能值？
自測題17 修改方法getIndexOf的定義，讓它不使用布爾值。
旁白：正向思考
與方法contains不一樣，方法getIndexOf將布爾變量found僅用來控製循環，而不是作為返回值。所以我們可以修改邏輯，避免取反操作符!的使用。
我們使用變量stillLooking來替代found，並將它初始化為真。然後可以將布爾表達式!found替換為stillLooking，如你在下麵的方法getIndexOf的定義中所見：
如果在數組中找到anEntry，則將stillLooking設置為假來結束循環。有些程序員傾向於正向思考，如這個版本中所述，而另一些人覺得!found就已經非常清楚了。
方法contains定義的修改。完成remove和它們調用的私有方法的定義後，我們知道方法contains可以調用私有方法getIndexOf，得到比方法contains中更簡單的定義。我們記得，如果anEntry在包中，則表達式getIndexOf(anEntry)返回0～numberOfEntries-1的一個整數，否則返回-1。即如果anEntry在包中，則getIndexOf(anEntry)大於-1。所以可以定義contains如下：
因為已經修改了contains的定義，所以應該再次測試它。為此，我們還要測試私有方法getIndexOf。
注：方法contains和remove都必須執行類似的對項的查找。將查找功能單獨放在方法contains和remove都能調用的一個私有方法中，使得我們的代碼更易調試及維護。這個策略與在兩個remove方法都調用的私有方法removeEntry中定義刪除操作時用到的一樣。
設計決策：什麼方法應該調用checkInitialization？
類ArrayBag的關鍵點是數組bag的分配。你已經看到，像add這樣依賴於這個數組的方法，是從調用checkInitialization開始的，以確保構造方法已經完全初始化了ArrayBag對象，包括數組的分配。而我們可以堅持在直接涉及數組bag的每個方法中調用checkInitialization，不過我們選擇更加靈活的做法。例如，私有方法getIndexOf和removeEntry直接訪問bag，但它們不調用checkInitialization。為什麼？刪除給定項的remove方法調用getIndexOf和removeEntry。如果這兩個私有方法都調用checkInitialization，則它被公有方法調用兩次。所以，對於這個具體實現來說，我們在公有方法中調用checkInitialization，並為這兩個私有方法添加一個前置條件來說明checkInitialization必須要先調用。因為它們是私有方法，所以這樣的前置條件隻給我們這些實現者和維護者使用。一旦做了這個決策，其他的remove方法和contains方法都必須調用checkInitialization，因為它們都隻調用這兩個私有方法中的一個。
注意，私有方法getIndexOf和removeEntry都執行一個已定義的任務。它們不再為第二個任務（檢查初始化）負責。
程序設計技巧：即使可能已經有了方法的正確定義，但如果你想到了一個更好的實現，也不要猶豫地去修改它。肯定要再次測試方法！
測試。我們的ArrayBag類基本上完成了。可以使用前麵測試remove和clear的測試方法了——我們假定它們是正確的。從一個沒滿的包開始，在線程序ArrayBagDemo3刪除包中的項直到它為空時為止。它還包括了從滿包開始的類似的測試。最後，應該將前麵的測試整合起來再次運行它們。在本書在線網站的源代碼中，測試程序是ArrayBagDemo，完整的類是ArrayBag。
最後更新：2017-06-26 17:32:43