天天看點

《資料結構與抽象:Java語言描述(原書第4版)》一2.2.1 可變大小數組

本節書摘來華章計算機《資料結構與抽象:java語言描述(原書第4版)》一書中的第2章 ,第2.2.1節,[美]弗蘭克m.卡拉諾(frank m. carrano) 蒂莫西m.亨利(timothy m. henry) 著 羅得島大學  新英格蘭理工學院 辛運帏 饒一梅 譯 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

政策。當教室滿了時,能容納更多學生的一種辦法是移到一間更大的教室。用類似的方式,當數組滿了時,可以将它的内容移到一個更大的數組中。這個過程稱為調整(resizing)數組大小。圖2-7顯示兩個數組:一個是有5個連續記憶體單元的原始數組,另一個數組(兩倍于原始數組大小)在計算機的另一塊記憶體中。如果将資料從原始的小數組中複制到新的大數組的開頭部分,得到的結果像是擴充了原來的數組一樣。這種機制的唯一不足是新數組的名字:你想讓它與原始數組同名。馬上就會看到如何完成這個工作。

《資料結構與抽象:Java語言描述(原書第4版)》一2.2.1 可變大小數組

細節。假定已有myarray指向的數組,如圖2-8a所示。我們先定義一個别名oldarray,它也指向這個數組,如圖2-8b所示。下一步是建立一個比原始數組更大的新數組,讓myarray指向這個新數組。如圖2-8c所示,一般地新數組要兩倍于原始數組的大小。最後一步是将原始數組的内容複制到新數組中(見圖2-8d),然後丢棄原始數組(見圖2-8e)。下列僞代碼概括了這些步驟:

《資料結構與抽象:Java語言描述(原書第4版)》一2.2.1 可變大小數組

圖2-8 a)一個數組;b)指向同一數組的兩個引用;c)原始數組變量現在指向新的更大的數組;d)原始數組中的項複制到新數組中;e)丢棄原始數組

注:當數組不再被引用時,它的記憶體在垃圾回收時被收回,就像是對其他對象發生的那樣。 代碼。将前面的僞代碼轉換為java時,可以使用java類庫中的方法arrays.copyof (sourcearray, newlength)來做很多事情。例如,對如下的簡單整數數組進行操作:
《資料結構與抽象:Java語言描述(原書第4版)》一2.2.1 可變大小數組

此時,myarray指向一個數組,如圖2-9a所示。接下來,調用arrays.copyof。将變量myarray中的引用賦給這個方法的第一個參數sourcearray,如圖2-9b所示。接下來,方法建立一個新的更大的數組,并将參數數組中的項複制給它(見圖2-9c)。最後,方法傳回指向新數組的一個引用(見圖2-9d),我們将這個引用賦給myarray(見圖2-9e)。下面的語句執行這些步驟:

《資料結構與抽象:Java語言描述(原書第4版)》一2.2.1 可變大小數組

圖2-9 語句myarray = arrays.copyof(myarray, 2 * myarray.length);的效果。a)參數數組;

b)指向參數數組的參數;c)獲得參數數組内容的新的更大的數組;d)指向新數組的傳回值;

e)将傳回值賦給參數變量

注:圖2-9中的數組含有整數。這些整數是基本類型值,且像這樣占據數組中的位置。與之相對,例如圖2-6中的數組,含有指向對象的引用而不是對象本身。

調整數組的大小或許沒有第一眼看上去這樣有吸引力。每次擴充數組的大小時,必須複制它的内容。如果每次需要數組外的一個額外空間而讓數組增大一個元素,則這個過程将耗時過大。例如,如果含50個元素的數組滿了,為了容納另一個項,需要将數組複制到有51個元素的數組中。再添加一項時又會要求你将含有51個元素的數組複制到含有52個元素的數組中,以此類推。每次添加都會導緻複制數組。如果在原含有50個項的數組中添加100項,則要複制100次數組。

另一種做法是将數組擴充m個元素,将複制開銷分攤在m次添加上而不是集中在一次上。每次當數組滿時倍增它的大小,這是一種典型的方法。

例如,當在含有50個項的滿數組中添加一項時,在進行添加前先将50個元素的數組複制到100個元素的數組中。那麼接下來的49次添加都可以快速完成而不需要複制數組。是以數組複制隻需一次。

程式設計技巧:當增大數組時,将它的項複制到更大的數組中。應該充分地擴充數組,以減少複制代價的影響。常用的辦法是倍增數組大小。 注:說“調整數組的大小”實際上是用詞不當,因為數組的長度不會改變。調整數組大小的過程是建立了一個含有原始數組項的全新數組。給新數組與原始數組一樣的名字——換句話說,指向新數組的引用賦給指向原始數組引用的變量。然後丢棄原始數組。 注:引入一個類

若一個類使用了java類庫中的類,則它的定義前必須有import語句。例如,要使用類arrays,應該将下面的語句寫在你的類定義和描述性注釋之前:

《資料結構與抽象:Java語言描述(原書第4版)》一2.2.1 可變大小數組

有些程式員将這條語句中的arrays替換為星号,目的是在程式中可以使用包java.util中的所有類。

自測題18 考慮下列語句定義的字元串數組:
《資料結構與抽象:Java語言描述(原書第4版)》一2.2.1 可變大小數組
為數組text增大5個元素的容量且不改變目前内容的java語句是什麼?

自測題19 考慮字元串數組text。如果放到這個數組中的字元串的個數小于它的長度(容量),你如何減少數組的長度而不改變它的目前内容?假定字元串的個數儲存在變量size中。