小狐狸事務所: Java 複習筆記 : 陣列

陣列是程式員最常用的資料結構, Java 的陣列屬於傳統的固定式陣列, 亦即陣列元素資料類型必需相同, 而且元素個數必須先宣告才能使用, 不像 Javascript 等動態語言之陣列允許異質性資料, 且長度不需先宣告即可使用. 當然, Java 陣列也不支援關聯性陣列, Java 是利用 Map 來處理此種資料型態. 以下整理了 Java 陣列的使用方法.

# http://docs.oracle.com/javase/7/docs/api/

一. 陣列的宣告與賦值 :

Java 陣列的主要特性如下 :

宣告一個變數名稱即可儲存大量相同資料型態之資料
陣列元素存放在記憶體中的連續空間, 其值可以重複.
以變數名稱與索引 (0 起始), 配合迴圈可方便存取元素
Java 陣列是物件型態, 其元素可以是原始資料型態, 字串, 或物件 (必須全部一致)
Java 陣列之元素個數宣告之後即固定, 即陣列長度不可變更.
Java 陣列長度可由 length 屬性取得, 而同樣是物件的字串, 卻用方法 length()

陣列變數的宣告有兩種方式 :

int a[];
int[] a;

亦即中括號可以在資料型別後面, 也可以在變數名稱後面. 宣告陣列變數後, 編譯器是在程式的 stack 記憶體區中配置一個儲存陣列參考的記憶體位址, 其預設值為 null, 表示沒有指向任何陣列實體. 這時如果去讀取陣列長度屬性, 編譯時將出現 "error: variable a might not have been initialized" 錯誤訊息 (還沒有實體化) :

int a[];
//System.out.println(a.length); //無法通過編譯

接下來需用 new 指令要求編譯器配置連續的記憶體以儲存陣列實體 (即元素) :

a=new int[3];

編譯器看到 new 就會在 heap 記憶體區配置連續 3 個記憶體位址來存放陣列元素, 然後把第一個位址 (陣列頭) 填入 stack 記憶體區中, 儲存陣列變數參考的位址, 這就是陣列的參考位址. 5k4

這個 new 就是陣列實體化 (也就是建立陣列物件), 陣列實體是放在 heap 區, 而其參考是放在 stack 區. 陣列實體化後就可以讀取到物件的 length 屬性了 :

int a[];
a=new int[3];
System.out.println(a.length); //輸出 3

上面這兩個分解動作也可以合而為一, 可以用 for 迴圈拜訪陣列元素 :

int a[]=new int[3];
for (int i=0; i<a.length; i++) {
System.out.print(a[i]); //輸出 000
}

但是要注意, 存取陣列元素時不可超過索引上限, 雖然可以通過編譯, 但是會出現執行時期錯誤 : "java.lang.ArrayIndexOutOfBoundsException".

上面配置完記憶體後, 陣列元素都已有值 0, 這是因為 int 的預設值為 0 之故. 因為存放在 heap 區的變數都會有預設值, 因此雖然陣列元素都還沒有初始化 (賦值), 但編譯器會先給予預設值, 如果元素是物件, 其預設值為 null, 如果是原始資料, 預設值如下所示 :

最後是將陣列元素初始化 (賦值), 亦即將元素值填入 heap 記憶體中 :

a[0]=100;
a[1]=101;
a[2]=103;

這上面三個分解動作 (宣告, 實體化, 初始化) 也可以一氣呵成 :

int a[]=new int[]{100,101,103};

亦即, 陣列元素是用大括號列舉. 特別注意, 這裏大括號前的那個中括號裡面不可再填入元素個數, 否則編譯會出現 "; expected", "{ not a statement" 等錯誤 :

//int a[]=new int[3]{100,101,103}; //編譯失敗 :

因為 JDK 看到 int[3] 後就準備在 heap 配置記憶體, 預期後面應該要有一個分號, 但是卻出現大括號之故. 編譯器會根據大括弧裡面的元素個數來配置記憶體數目.

或者可以乾脆省略 new int[] :

int a[]={100,101,103};
for (int i=0; i<a.length; i++) {
System.out.print(a[i]); //輸出 100101103
}

也可以使用 for each 方式拜訪 :

int a[]={100,101,103};
for (int i : a) { //i in a 之意
System.out.print(i); //輸出 100101103
}

二維陣列的宣告則是用兩個中括號表示, 同樣有兩種方式 :

int a[][];
int[][] a;

同樣地, 它也是告訴編譯器, 在 stack 記憶體區配置一個存放陣列參考的記憶體 :

由於還沒有實體化, 故其值 (參考) 為 null.

二維陣列宣告中的第一個中括弧代表列, 第二個中括弧代表行, 當以 new 實體化時, 我們必須指定列數與行數, 例如 :

a=new int[3][2];

編譯器會在 heap 記憶體區配置 "列x行" 個記憶體以存放全部元素, 這些元素會分成 "列" 組, 每一組都是連續空間, 用來存放各列元素. 然後會在 heap 區再配置 "列" 個連續空間, 以儲存每一列第一個元素的參考位址, 最後再把這個列陣列的第一個元素參考填入陣列變數 a 中即完成全部記憶體配置. 因此二維陣列的第一維 (列陣列) 存放的其實是個一維的參考陣列, 第二維 (行陣列) 才是存放元素的陣列, 如下列範例所示 :

int[][] a=new int[3][2];
for (int i=0; i<a.length; i++) {
System.out.println(a[i]);
}

輸出結果 :

[I@175d6ab
[I@160a26f
[I@1484a05

此即第一維所存放的列陣列參考. 若此時去拜訪陣列元素, 如下例所示 :

int[][] a=new int[3][2];
for (int i=0; i<a.length; i++) {
for (int j=0; j<a[i].length; j++) {
    System.out.print(a[i][j]);
    }
System.out.println("");
}

輸出結果 :

00
00
00

可見由於 heap 中的變數都有預設值, 而 int 的預設值為 0, 因此全部元素值均為 0. 注意 a.length 表示陣列的列數, 而 a[i].length 則為其行數.

二維陣列的初始化可以一個元素一個元素賦值 :

int a[0][0]=100;
int a[0][1]=101;
.....

也可以用雙重大括弧比較簡潔 :

int a[][]=new int[][]{{100,101},{99,103},{78,117}};

同樣要注意, 這裡中括號裡不可填列數與行數, 或者乾脆省略 new int[][] :

int a[][]={{100,101},{99,103},{78,117}};

如下列範例所示 :

int[][] a={{100,101},{99,103},{78,117}};
for (int i=0; i<a.length; i++) {
for (int j=0; j<a[i].length; j++) {
    System.out.print(a[i][j] + " ");
    }
System.out.println("");
}
輸出結果 :

100 101
99 103
78 117

二. 一維陣列的排序與搜尋 :

# http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html

Java 的 java.util.Arrays 類別提供幾個靜態方法來處理一維陣列 (不能用於二維陣列). 其中最常用的是 sort() 與 binarySearch(), 可對一維陣列進行排序與搜尋. 要使用此功能可以先匯入此類別 :

import java.util.Arrays;

然後就可以使用 Arrays 了, 使用 sort() 方法只要傳入待排序陣列即可 :

Arrays.sort(a);

也可以不先匯入, 直接使用 java.util.Arrays :

java.util.Arrays(a);

如下範例所示 :

int a[]={103,101,102};
java.util.Arrays.sort(a);
for (int i : a) { //i in a 之意
System.out.print(i + " ");   //輸出 101 102 103
}

可見 sort() 方法會對陣列元素進行升階排序. 降階排序該怎麼做呢? 可以利用 sort() 另一個多載方法, 傳入一個 Comparator 物件 ;

sort(T[] a, Comparator c)

降序的 Comparator 物件可以利用 java.util.Collections 類別的靜態方法 reverseOrder() 來取得, 因此我們需要再匯入 Collections 類別或者乾脆指定整個 java.util 路徑即可 :

import java.util.*;

關於 Comparator 與 Collections 類別可參考 :

# http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html
# http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html

但是要注意, 這個降序用的 sort() 方法只能傳入物件型別的陣列, 不能用於原始型別陣列, 因此下列用法是錯的, 無法編譯成功 :

int a[]={103,101,102}; //原始型別陣列
//java.util.Arrays.sort(a, java.util.Collections.reverseOrder()); //編譯失敗

必須先將原始型別陣列利用包裹類別把原始型態陣列轉成物件陣列才行 :

Integer[] aInt=new Integer[a.length]; //宣告 a 陣列的包裹陣列
for (int i : a) {
aInt[i]=new Integer(a[i]); //建立與原始陣列內容相同之包裹陣列
}

參考 :

# Sorting Arrays

這樣就可以呼叫降序的 sort() 方法了, 如下列範例所示 :

import java.util.*;
public class test {
public static void main(String argv[]) {
    int a[]={103,101,102};
    Integer[] aInt=new Integer[a.length];
    for (int i=0; i<a.length; i++) {
      aInt[i]=new Integer(a[i]);
      }
    Arrays.sort(aInt, Collections.reverseOrder());
    for (Integer i : aInt) {
      System.out.print(i.intValue() + " ");   //輸出 103 102 101
      }
    }
}

如果是字串陣列那就不需要如此麻煩了, 因為字串本身就是物件型態, 可以直接使用, 例如 :

import java.util.*;
public class test {
public static void main(String argv[]) {
    String str[]={"one","two","three"};
    Arrays.sort(str, Collections.reverseOrder());
    for (String s : str) {
      System.out.print(s + " ");   //輸出 two three one
      }
    }
}

可見英文字串的排序是依照字母一個一個比較來定先後的. 排序在英文與數字不成問題, 但在中文就頭大了, 例如下列升序排列 :

String str[]={"渡邊淳二","渡邊淳三","渡邊淳一"};
Arrays.sort(str);
for (String s : str) {
   System.out.print(s + " ");   //輸出渡邊淳一渡邊淳三渡邊淳二
   }

而降序排列卻是 :

String str[]={"渡邊淳二","渡邊淳三","渡邊淳一"};
Arrays.sort(str, Collections.reverseOrder());
for (String s : str) {
   System.out.print(s + " ");   //輸出渡邊淳二渡邊淳三渡邊淳一
   }

原以為會照筆畫順序, 看起來不是, 也無法理解其排序的邏輯. 關於中文排序, 參見 :

# java 中文排序

此文實作了一個 Comparator 介面的類別來替中文做升序排序 :

public class Asc implements Comparator {
public int compare(Object arg0, Object arg1) {
     VLG_ItemMaster m1=(VLG_ItemMaster)arg0;
     VLG_ItemMaster m2=(VLG_ItemMaster)arg1;
     Collator collator=Collator.getInstance(Locale.TRADITIONAL_CHINESE);
     return collator.compare(m1.getItemDesc(),m2.getItemDesc());
     }
}

其次來看搜尋, 也就是找看看陣列中是否有指定之元素, java.util.Arrays 的 binarySearch() 方法採用二元搜尋法, 它有兩個參數, 第一個是目標陣列, 第二個參數是要搜尋的標的, 它會傳回一個整數, 如果有找到, 會傳回該元素的索引, 否則傳回一個負數, 其值為標的在此陣列內的排序索引取負數再減 1. 為了提高搜尋效能, 呼叫 binarySearch() 之前最好先呼叫 sort() 進行排序.

static int binarySearch(array, key)

如下列範例所示 :

int a[]={105,101,103};
java.util.Arrays.sort(a);     //排序後是 {101,103,105}
System.out.print(java.util.Arrays.binarySearch(a, 101));   //輸出 0
System.out.print(java.util.Arrays.binarySearch(a, 102));   //輸出 -2
System.out.print(java.util.Arrays.binarySearch(a, 100));   //輸出 -1
System.out.print(java.util.Arrays.binarySearch(a, 104));   //輸出 -4

上例中, 100 找不到, 它在排序後的陣列中會排在索引 0, 因此回傳 -1; 104 也找不到, 若將其排入目標陣列, 其索引將會是 3, 故傳回 -4. 所以有沒有找到可以簡單地以傳回值的正負數判斷.

如果沒有先呼叫 sort(), 如下所示, 傳回的索引將會不同 :

int a[]={105,101,103};
System.out.print(java.util.Arrays.binarySearch(a, 101));   //輸出 1
System.out.print(java.util.Arrays.binarySearch(a, 102));   //輸出 -3
System.out.print(java.util.Arrays.binarySearch(a, 100));   //輸出 -1
System.out.print(java.util.Arrays.binarySearch(a, 104));   //輸出 -4

可見蒐尋 101 傳回其索引 1 沒錯, 但 102 傳回 -3, 搜尋 100 傳回 -1, 搜尋 104 傳回 -4 就不容易理解了. 總之, 如果需要用到其傳回值, 搜尋前請先排序; 如果只是要判斷陣列是否含有某元素, 則不需要先排序, 直接搜尋即可.

三. 可變長度陣列 ArrayList :

# http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html

Java 陣列的長度是固定的, 一旦宣告之後就不能改變. 但很多時候我們無法預期陣列可能的元素個數, 例如陣列就不適合用來儲存文字檔內的每一列字串, 因為檔案會有幾列無法預期的, 這時就要改用 java.util.ArrayList 類別, 這是 Java 集合的一種 (List 串列), 此類別實做了 List 介面, 其特性與陣列大致相同, 可視為可變長度的陣列 :

有序 (以索引存取)
元素可以重複
一個變數名稱可以存取大量同性質資料

但是有兩點不同 :

ArrayList 長度可以增減
ArrayList 的元素全部是物件, 即使存入原始資料, 也會 Autoboxing 為物件.

ArrayList 預設配置 10 個元素的記憶體空間, 當空間不足時會自動擴充容量, 也可以隨時呼叫 trimToSize() 方法來去除多餘的容量, 使其剛好符合元素數量, 以釋放多餘之記憶體. 為了方便, 使用 ArrayList 最好先匯入 java.util 類別庫 :

import java.util.*;

ArrayList 類別支援泛型設計, 因此宣告一個 ArrayList 物件時要指定其型別 :

ArrayList<String> list=new ArrayList<String>();

例如下列為一個元素均為字串的 ArrayList :

ArrayList<String> list=new ArrayList<String>();

其常用方法如下表所示 :

方法	說明
add(E element)	將元素加到串列尾端
add(int index, E element)	將元素加到指定索引位置, 該位置後面的元素全部往後移
get(int index)	傳回指定索引位置之元素值
set(int index, E element)	以新值取代指定索引位置之元素
remove(int index)	移除指定索引位置之元素
remove(Object o)	移除指定元素
size()	傳回 ArrayList 元素個數 (與容量無關)
indexOf(Object o)	從前端搜尋串列中是否有指定元素, 有傳回其索引, 否則傳回 -1
lastIndexOf(Object o)	從尾端搜尋串列中是否有指定元素, 有傳回其索引, 否則傳回 -1
contains(Object o)	搜尋串列是否有指定之元素, 有傳回 true, 否則 false
isEmpty()	串列無元素傳回 true, 否則 false
toArray()	將全部元素以陣列傳回
trimToSize()	去除串列預留空間, 使其剛好裝得下全部元素

拜訪 ArrayList 的元素跟拜訪陣列一樣, 用 for 迴圈或 for each 迴圈 :

for (String e : list) {
System.out.println(e);
}

如下面範例所示 :

import java.util.*;
public class test {
public static void main(String[] args) {
    ArrayList list=new ArrayList();
    System.out.println(list.size());    //輸出 0 (空的, 尚無元素)
    System.out.println(list.isEmpty()); //輸出 true (空的)
    list.add("楊過");                   //加入第一個元素
    System.out.println(list.size());    //輸出 1
    //list.add(2,"小龍女");             //編譯錯誤, 超出索引上限
    list.add(1,"小龍女");               //加入第二個元素
    System.out.println(list.size());    //輸出 2
    list.add(1,"郭襄");                 //加入第三個元素於索引 1
    System.out.println(list.get(1));    //輸出郭襄
    System.out.println(list.get(2));    //輸出小龍女
    list.set(1,"完顏萍");               //更改索引 1 之值
    System.out.println(list.get(1));    //輸出完顏萍
    System.out.println(list.indexOf("小龍女"));   //輸出 2
    System.out.println(list.lastIndexOf("楊過")); //輸出 0
    System.out.println(list.contains("完顏萍")); //輸出 true
    System.out.println(list.contains("黃蓉"));    //輸出 false
    List sList=list.subList(1,3);         //傳回子串列
    String[] a=sList.toArray(new String[sList.size()]); //串列轉字串
    for (String e : a) {System.out.print(e + " ");}    //輸出完顏萍小龍女
    System.out.println("");
    list.remove("完顏萍");                             //刪除元素
    for (String e : list) {System.out.print(e + " ");} //輸出楊過小龍女
    System.out.println("");
    list.remove(1);                                    //刪除索引 1 之元素
    for (String e : list) {System.out.print(e + " ");} //輸出小龍女
    }
}

# String array to arraylist

下面這個 readLines() 靜態方法用來讀取文字檔, 然後拆成列字串陣列傳回 :

public static String[] readLines(String file) {
    ArrayList<String> list=new ArrayList<String>();
    try {
      BufferedReader br=new BufferedReader(new FileReader(file));
      String line=null;
      while ((line=br.readLine()) != null) {list.add(line);}
      br.close();
      }
    catch (IOException e) {System.out.println(e);}
    list.trimToSize();
    return list.toArray(new String[list.size()]);
    }

參考資料 :

# stack vs heap：執行時期儲存兩大要角

小狐狸事務所

2014年3月26日星期三

Java 複習筆記 : 陣列

1 則留言:

2014年3月26日 星期三

Java 複習筆記 : 陣列

1 則留言:

2014年3月26日星期三