热门文章
阿标在线 动力3.62HTML生成3.62网站文件说明
动力3.62整合动网7.0 SP2插
MDAC2.8 下载！
动力3.62版 防止垃圾留言
动力3.6全方位改动方法
让3.62不同频道实现不同风
把3.62首页登陆为横向代码
动易3.6首页随机FLASH修改
362首页和文章频道页图文幻
个性化修改3.6宝典
3.62轻易实现网摘功能
如何正确统计中文字数？
弹出JAVASCRIPT语法错误对
后台使“网站顶部LOGO地址
最新图片文章横向移动的修
html 生成艺术字
3.6 Sp2 Logo和Banner及广
日期值的计算
汉字转拼音
首页“图片更新”图片滚动
简体中文转换为繁体中文的
如何在css中定义链接的下划
Java入门笔记3_Datastructure
[ 录入：阿标 | 点击数： | 更新时间：2005-3-2 14:44:00]
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);
}