4. Data Structure
4.1 Array
4.1.1 基本概念
數(shù)組在Java中是對象，因此使用它之前需要實(shí)例化。數(shù)組中的元素可以是基本元素，也可以是對象，但是同一數(shù)組中元素的類型必須是相同的。

數(shù)組中存放的對象不是對象本身，而是對象的引用。

4.1.2 數(shù)組申明與實(shí)例化
（1） String difWords[]; Point hits[];

（2） String[] difWords[]; Point[] hits; 常用于方法的返回類型；

（3） String[] names = new String[10]; int[] temps = new int[10];

（4） String[] names = {"jalapeno", "anaheim", "serrano"}

（5） int coords[][] = new int[12][12];

4.1.3 數(shù)組的屬性與方法
數(shù)組是對象，因些它有屬性與方法，如length屬性等。

4.2 Enumeration
Enumeration是個(gè)接口，它提供了一些標(biāo)準(zhǔn)的方法用于訪問其中的元素，這些方法有：

（1） hasMoreElement()：判斷是否有其它元素

（2） nextElement()：返回下來元素，如果沒有下來元素，使用該方法會拋出NoSuchElementException異常；

4.3 BitSet
BitSet在表示一組布爾值標(biāo)志時(shí)比較方便，它可以對bit進(jìn)行訪問，而不需要使用位操作符：

BitSet bits = new BitSet(4);

定義了長度為4個(gè)bit的bit set，我們至少可以使用以下幾個(gè)方法對這些bit位進(jìn)行操作：

（1） bits.set(index)：將第index個(gè)bit設(shè)為1；

（2） bits.clear(index)：將第index個(gè)bit設(shè)為0；

（3） bits.get(index)：返回第index個(gè)bit的值；

（4） bits.size()：用于返回bit set的長度；

（5） xor(BitSet set)：與指定bit set進(jìn)行Xor操作；

（6） 還有其它一些操作見java.util包

4.4 Vector
Vector與Array的概念類似，但是Array的長度不能自動(dòng)增長，但Vector的長度可以自動(dòng)增加，當(dāng)Vector長度不夠時(shí)，它就會自動(dòng)增長，而且可以指定每次自動(dòng)增長的長度，如：

Vector v = new Vector(20,5)；

表示新建一個(gè)Vector對象，它的初始長度為20，即可以容納20個(gè)元素，如果元素個(gè)數(shù)超過20個(gè)時(shí)，每次增加5個(gè)元素的容量，即第一次增長時(shí)變?yōu)?5，第二次增長時(shí)變以30。

Vector中的方法詳見java.util包

4.5 Stack
Stack是一個(gè)典型的數(shù)據(jù)結(jié)構(gòu)，采用先進(jìn)后出的原則。它有幾個(gè)重要的方法：

（1） pop；

（2） push(Object)；

（3） empty()：清空

（4） peek()：查看棧頂元素，但并不將該元素出棧；

（5） search(object)：查找指定元素的位置；

4.6 Dictionary
Dictionary是個(gè)抽象類，它定義了基本的key-mapped數(shù)據(jù)結(jié)構(gòu)。Hashtable等都是從這個(gè)抽象類中繼承的。Vector也可以通過key（index）來訪問元素，但Vector中的key的類型是特殊的，默認(rèn)的。而Dictionary中的key可以自定義。Dictionary類中的所有方法都是抽象的，這就說明這些方法都需要派生類來實(shí)現(xiàn)，這些抽象的方法如下：

（1） put(Object, Object)：如put(“small”,new Rectangle(0,0,5,5))；

（2） get(Object)：如get(“small”)；

（3） remove(Object)：如remove(“small”)；

（4） size()；

（5） isEmpty()；

（6） keys()：如Enumeration keys = dict.keys()

（7） elements()：如Enumeration elements = dict.elements()

4.7 Hashtable
HashTable是從Dictionary繼承下來，它實(shí)現(xiàn)了父類的所有方法，并且實(shí)現(xiàn)了Serializable這個(gè)接口，所以它常被用于客戶機(jī)與服務(wù)器之間數(shù)據(jù)遞，即在傳遞之前先序列化，接收后重新對象化。

Hashtable有以下幾個(gè)構(gòu)造函數(shù)：

（1） Hashtable()：執(zhí)行Hashtable(11,0.75f)；

（2） Hashtable(int)：執(zhí)行Hashtable(int,0.75f)；

（3） Hashtable(int capicility,float factor)；

（4） Hashtable(Map t)：執(zhí)行Hashtable(Math.max(2*t.size(),11),0.75f); putAll(t)

這里要說明的是Hashtable(int capicility,float factor)中的參數(shù)，capicility用于初化Hashtable的大小，t=capicility*factor決定于Hashtable何值reHash，在Hashtable中如果Hashtable中的條目超過t的值，就要reHash，reHash就是重建一個(gè)2* capicility的Hashtable。因此factor的取值為0.0<factor<=1。默認(rèn)的factor值為0.75。

當(dāng)一個(gè)條目被放到Hashtable中值，即put(obj1,obj2)時(shí)，會為這些obj建立hascode，hascode是int型的，并且是唯一的。

4.8 Double Link
以上是Java中一些內(nèi)置的數(shù)據(jù)結(jié)構(gòu)，如果內(nèi)置的數(shù)據(jù)結(jié)構(gòu)不能滿足我們的需要，可以自定義數(shù)據(jù)結(jié)構(gòu)，這里介紹雙向鏈的實(shí)現(xiàn)。要實(shí)現(xiàn)雙向鏈，這里用到了三個(gè)類：

（1） LinkedListEntry：鏈中的條目；

（2） LinkedList：鏈的主類；

（3） LinkedListEnumerator：實(shí)現(xiàn)了Enumeration接口；

4.8.1 LinkedListEntry類
class LinkedListEntry {

protected Object val = null;

protected LinkedListEntry next = null;

protected LinkedListEntry prev = null;



public LinkedListEntry(Object obj) {

if (obj == null)

throw new NullPointerException();

val = obj;

}

}

4.8.2 LinkedListEnumerator
1: class LinkedListEnumerator implements Enumeration {

2: protected LinkedListEntry pos;

3:

4: public LinkedListEnumerator(LinkedList list) {

5: pos = list.start;

6: }

7:

8: public boolean hasMoreElements() {

9: return (pos != null);

10: }

11:

12: public Object nextElement() {

14: if (pos == null)

15: throw new NoSuchElementException();

18: LinkedListEntry tmp = pos;

19: pos = pos.next;

20: return tmp.val;

21: }

22: }

4.8.3 LinkedList
LinkedList中的變量成員：

protected LinkedListEntry start = null;

protected LinkedListEntry end = null;

protected int numElements;

LinkedList主要就是對LinkedListEntry進(jìn)行管理，它有以下一些功能：

（1） 增加指定條目；

（2） 插入指定條目；

（3） 刪除指定條目；

（4） 根據(jù)對象查找指定條目；

（5） 根據(jù)位置查找；

（6） 返回Enumeration對象；

（7） 判斷是否包含某個(gè)條目；

（8） 判斷鏈?zhǔn)欠駷榭眨龋?br />
要完全實(shí)現(xiàn)以上功能，需要很多代碼，當(dāng)然這些代碼都比較簡單，所以這些只給出部份代碼，作為引子。

（1） 增加指定條目addElement：

1: public void addElement(Object obj) {

3: if (obj == null)

4: throw new NullPointerException();

5:

7: LinkedListEntry newElement = new LinkedListEntry(obj);

8: numElements++;

9:

11: if (start == null) {

12: start = newElement;

13: end = newElement;

14: }

15: else {

16: end.next = newElement;

17: newElement.prev = end;

18: end = newElement;

19: }

20: }

（2） 插入指定條目insertElementAt

1: public void insertElementAt(Object obj, Object pos) {

3: if (obj == null || pos == null)

4: throw new NullPointerException();

5:

7: LinkedListEntry posEntry = find(pos);

8: if (posEntry == null)

9: throw new NullPointerException();

10:

12: LinkedListEntry newElement = new LinkedListEntry(obj);

13: numElements++;

14:

16: newElement.next = posEntry;

17: newElement.prev = posEntry.prev;

18: if (posEntry == start)

19: start = newElement;

20: else

21: posEntry.prev.next = newElement;

22: posEntry.prev = newElement;

23: }

（3） 根據(jù)對象查找指定條目

private LinkedListEntry find(Object obj) {

if (isEmpty() || obj == null)

return null;



LinkedListEntry tmp = start;

while (tmp != null) {

if (tmp.val == obj)

return tmp;

tmp = tmp.next;

}

return null;

}

（4） 判斷是否包含某個(gè)條目

public boolean contains(Object obj) {

return (find(obj) != null);

}

（5） 判斷鏈?zhǔn)欠駷榭?br />
public boolean isEmpty() {

return (start == null);

}

（6） 返回Enumeration對象

public Enumeration elements() {

return new LinkedListEnumerator(this);

}