Java入门笔记3_Datastructure

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);

}

本文地址：http://com.8s8s.com/it/it11291.htm