IDC资讯中心
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);
}
