随笔-71  评论-4  文章-0  trackbacks-0

4. Data Structure
4.1 Array
4.1.1 基本概念
数组在Java中是对象,因此使用它之前需要实例化。数组中的元素可以是基本元素,也可以是对象,但是同一数组中元素的类型必须是相同的。

数组中存放的对象不是对象本身,而是对象的引用。

4.1.2 数组申明与实例化
(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 数组的属性与方法
数组是对象,因些它有属性与方法,如length属性等。

4.2 Enumeration
Enumeration是个接口,它提供了一些标准的方法用于访问其中的元素,这些方法有:

(1) hasMoreElement():判断是否有其它元素

(2) nextElement():返回下来元素,如果没有下来元素,使用该方法会抛出NoSuchElementException异常;

4.3 BitSet
BitSet在表示一组布尔值标志时比较方便,它可以对bit进行访问,而不需要使用位操作符:

BitSet bits = new BitSet(4);

定义了长度为4个bit的bit set,我们至少可以使用以下几个方法对这些bit位进行操作:

(1) bits.set(index):将第index个bit设为1;

(2) bits.clear(index):将第index个bit设为0;

(3) bits.get(index):返回第index个bit的值;

(4) bits.size():用于返回bit set的长度;

(5) xor(BitSet set):与指定bit set进行Xor操作;

(6) 还有其它一些操作见java.util包

4.4 Vector
Vector与Array的概念类似,但是Array的长度不能自动增长,但Vector的长度可以自动增加,当Vector长度不够时,它就会自动增长,而且可以指定每次自动增长的长度,如:

Vector v = new Vector(20,5);

表示新建一个Vector对象,它的初始长度为20,即可以容纳20个元素,如果元素个数超过20个时,每次增加5个元素的容量,即第一次增长时变为25,第二次增长时变以30。

Vector中的方法详见java.util包

4.5 Stack
Stack是一个典型的数据结构,采用先进后出的原则。它有几个重要的方法:

(1) pop;

(2) push(Object);

(3) empty():清空

(4) peek():查看栈顶元素,但并不将该元素出栈;

(5) search(object):查找指定元素的位置;

4.6 Dictionary
Dictionary是个抽象类,它定义了基本的key-mapped数据结构。Hashtable等都是从这个抽象类中继承的。Vector也可以通过key(index)来访问元素,但Vector中的key的类型是特殊的,默认的。而Dictionary中的key可以自定义。Dictionary类中的所有方法都是抽象的,这就说明这些方法都需要派生类来实现,这些抽象的方法如下:

(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继承下来,它实现了父类的所有方法,并且实现了Serializable这个接口,所以它常被用于客户机与服务器之间数据递,即在传递之前先序列化,接收后重新对象化。

Hashtable有以下几个构造函数:

(1) Hashtable():执行Hashtable(11,0.75f);

(2) Hashtable(int):执行Hashtable(int,0.75f);

(3) Hashtable(int capicility,float factor);

(4) Hashtable(Map t):执行Hashtable(Math.max(2*t.size(),11),0.75f); putAll(t)

这里要说明的是Hashtable(int capicility,float factor)中的参数,capicility用于初化Hashtable的大小,t=capicility*factor决定于Hashtable何值reHash,在Hashtable中如果Hashtable中的条目超过t的值,就要reHash,reHash就是重建一个2* capicility的Hashtable。因此factor的取值为0.0<factor<=1。默认的factor值为0.75。

当一个条目被放到Hashtable中值,即put(obj1,obj2)时,会为这些obj建立hascode,hascode是int型的,并且是唯一的。

4.8 Double Link
以上是Java中一些内置的数据结构,如果内置的数据结构不能满足我们的需要,可以自定义数据结构,这里介绍双向链的实现。要实现双向链,这里用到了三个类:

(1) LinkedListEntry:链中的条目;

(2) LinkedList:链的主类;

(3) LinkedListEnumerator:实现了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进行管理,它有以下一些功能:

(1) 增加指定条目;

(2) 插入指定条目;

(3) 删除指定条目;

(4) 根据对象查找指定条目;

(5) 根据位置查找;

(6) 返回Enumeration对象;

(7) 判断是否包含某个条目;

(8) 判断链是否为空,等;

要完全实现以上功能,需要很多代码,当然这些代码都比较简单,所以这些只给出部份代码,作为引子。

(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) 根据对象查找指定条目

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) 判断是否包含某个条目

public boolean contains(Object obj) {

return (find(obj) != null);

}

(5) 判断链是否为空

public boolean isEmpty() {

return (start == null);

}

(6) 返回Enumeration对象

public Enumeration elements() {

return new LinkedListEnumerator(this);

}

posted on 2006-03-20 12:16 zjw_albert 阅读(161) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: