把玩算法 | 數組

coder-qi 2021-08-15 12:58:37 阅读数:931

本文一共[544]字,预计阅读时长:1分钟~
把玩 算法

基礎

數組是由相同類型的元素的集合所組成的數據結構,分配一塊連續的內存來存儲。數組是使用索引來訪問裏面的元素的。如果我們有n個值,那麼數組索引的範圍為0至n-1。對於0到n-1之間的任意的i,我們就能在Java代碼中用arr[i]來訪問第i個元素的值。

下面的代碼創建了一個人名的數組,然後打印數組中的第二個元素:

String[] names = {"張三", "李四", "王五"};
System.out.println(names[1]);

但是數組創建完成後,其大小也就不能改變了。如果我們想要動態的改變數組的大小,那麼就需要先創建足够大的同類型的數組,然後再將原始的數組中的數據拷貝到新創建的數組中。例如原先創建了一個長度為3的數組存放了3個人的名字,後來需要再存放"趙六"和"錢七"這兩個人名,那麼就需要重新創建長度為5的數組來存放這5個人名。相關的代碼如下(注:數組的拷貝可以使用System.arraycopy方法來進行拷貝):

String[] names = {"張三", "李四", "王五"}; // 原先的數組
// 現在需要存放"趙六"和"錢七"這兩個人名
String[] newNames = new String[5];
// 拷貝之前的數據
for (int i = 0; i < names.length; i++) {
newNames[i] = names[i];
}
// 存放"趙六"和"錢七"
newNames[3] = "趙六";
newNames[4] = "錢七";

每次都要自己手動的來對數組進行擴容確實挺麻煩的,我們可以將添加、删除、訪問數組中的元素的方法進行封裝,在需要用到時直接用就行了。

API

下面是我們為數組定義的相關API:


數組

pubic class Array<Element> implements Iterable<Element>
Array() 創建一個空數組
Array(int capacity) 創建一個初始化容量的數組
void add(Element e) 添加一個元素
Element get(int index) 獲取指定比特置的元素
void set(int index, Element e) 設置指定比特置的元素
Element remove(int index) 移除指定比特置的元素
int size() 獲取數組的大小

  • 泛型:一種特別的Java的機制,也叫參數化類型。在API中,類名後面的<Element>Element定義為一個類型參數,它是一個占比特符,錶示的是該類將會使用到的某個具體的數據類型。Array<Element>可以理解為某種元素的數組。我們這裏的數組是能存放任意類型的數據的,例如,可以編寫下面的代碼來存放String類型的對象:

    Array<String> arr = new Array<String>();
    arr.add("張三");
    ...
    
  • 可迭代的集合:在很多情况下,只需要用某種方式來處理集合中的每個元素,這種模式一般叫做迭代器模式。有了它,我們就能寫出很清晰的代碼而不必依賴於具體的集合類型的實現。只要實現了Iterable,就能使用for-each來遍曆集合中的每一個元素,例如下面的代碼打印出所有的人的姓名:

    Array<String> names = new Array<String>();
    ...
    for (String name : names) {
    System.out.println(name);
    }
    

    上面的for-each等同於下面的代碼(很明顯,使用for-each要簡介方便很多):

    for (Iterator<String> iterator = names.iterator(); iterator.hasNext();) {
    String name = iterator.next();
    System.out.println(name);
    }
    

有了上面的API後,就能將上面的代碼改為使用Array來編寫。在這裏只需要關注所需要實現的邏輯,而不必關注具體的內部實現細節:

public static void main(String[] args) {
Array<String> names = new Array<>(3);
names.add("張三");
names.add("李四");
names.add("王五");
System.out.println(names);
// 存放"趙六"和"錢七"
names.add("趙六");
names.add("錢七");
System.out.println(names);
}

實現

更加詳細的實現見github:Array.java

public class Array<Element> implements Iterable<Element> {
private Object[] elements; // 元素
private int size; // 元素的個數
public Array() { this(0); }
public Array(int capacity) { elements = new Object[capacity]; }
public void add(Element e) {
if (size == elements.length) {
resize(size * 2 + 1);
}
elements[size++] = e;
}
public Element get(int index) { return (Element) elements[index]; }
public void set(int index, Element e) { elements[index] = e; }
public int size() { return size; }
// 下面這幾個方法的實現,請看接下來的實現說明
private void resize(int capacity)
public void remove(int index)
public Iterator<Element> iterator()
}

默認的構造器創建了一個空白的數組(長度為0),也提供了一個能指定初始化容量的版本,這樣就可以根據自己的使用場景提供一個恰當的容量,避免在添加元素的過程中,數組內部頻繁的進行擴容,影響性能。內部維護了一個數組Object[]用來存放元素,使用實例變量size來記錄數組的大小。

為了能更加直觀的看到數組存放的元素,還需要重寫toString方法:

public String toString() {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++) {
if (i > 0) {
sb.append(",");
}
sb.append(elements[i]);
}
sb.append("]");
return sb.toString();
}

add, get, set這幾個方法的實現都比較簡單,都是直接操作存放元素的數組來實現,還提供了size()方法來獲取數組的大小。如果元素數組滿了,add方法會在添加元素之前會數組進行擴展,相關的實現如下:

數組擴容

elements的初始化長度是固定的,當elements滿了之後就沒有空餘的空間來存放後續添加的元素了,這時就需要進行擴容了。這裏的實現也比較簡單,創建一個新的數組,再將原先數組中的值複制過去,再將新的數組賦值給elements就可以了。

private void resize(int capacity) {
Object[] newElements = new Object[capacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
}

在add方法中,將元素數組的長度調整為原先的2倍再加1(size * 2 + 1

移除

移除數組中指定索引i處的元素時,需要將索引i之後的所有元素往前挪一格,並且還需要將數組中最後的一個元素設置為null,避免對失效比特置對元素的引用。

例如,數組中存放了5個元素:[張三,李四,王五,趙六,錢七],如果要删除第二個元素,調用remove(1)方法的示例圖如下:

移除過程(灰色方格錶示還未處理到的比特置):

實現如下:

public Element remove(int index) {
for (int i = index + 1; i < size; i++) {
elements[i - 1] = elements[i];
}
size--;
Element oldValue = (Element) elements[size];
elements[size] = null;
if (size > 0 && size < elements.length / 4) {
resize(elements.length / 2);
}
return oldValue;
}

當數組的大小為其容量的四分之一時,將數組的容量縮减為數組容量的二分之一。

迭代

iterator()方法的實現如下:

public Iterator<Element> iterator() {
return new Iterator<Element>() {
int cursor;
@Override
public boolean hasNext() {
return cursor < size;
}
@Override
public Element next() {
return (Element) elements[cursor++];
}
@Override
public void remove() {
throw new UnsupportedOperationException("remove");
}
};
}

內部維護了一個當前迭代器的指針cursor,相關方法的實現說明如下:

  • hasNext():錶示是否還有下一個元素,如果cursor指針未超過數組的大小,那麼說明還有下一個元素
  • next():獲取下一個元素,並將cursor指針指向下一個元素
  • remove():這裏不支持移除操作,直接拋出了UnsupportedOperationException异常

迭代示意圖如下:

版权声明:本文为[coder-qi]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815125809460q.html