苹果的成长日记

我还是个青苹果呀!

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  57 随笔 :: 0 文章 :: 74 评论 :: 0 Trackbacks
        容器(Container)在生活中处处可见。每种容器的类型都有各自定制、访问实体的一系列规则。
        区别容器对象本身和该容器包含的对象是很重要的。从某种意义上说,研究数据结构也就是研究容器。这里,将给出容器这种抽象数据类型的行为框架,并且创建实现这种抽象数据类型的基本原型。根据一下的特性可以区别不同类型的容器:
    (1)容器中的对象是否可排序。比如:按容器的一个继承属性排序,或按容器中的对象的一个属性排序。
    (2)是否允许对象的复制(是否允许重复)。
    (3)容器中的对象可被限制为一个特定的类型。
    (4)容器中的对象可基于索引来访问。
    (5)容器中的对象可基于相对位置来访问。
    (6)容器中的对象可基于值访问。
    (7)容器可根据其连通性(线性、非线性)来区别。

这里以Container接口为根接口来表示所有容器最一般的形式。

1.1 顶层的Container接口
      在开发新的java类时,我们应该先考虑是否需要可串行化。一个可串行化的对象可以很容易的从作为对象的文件流中来读/写的。最一般的容器具有一下特性:
    1)不考虑它所包含的对象的类型;
    2)所包含的对象没有排序的要求;
   3)接受复制的对象;
   4)支持可串行化;
   5)接受使本身为空的命令;
   6)接受一下查询:返回所包含的对象的个数、返回容器是否为空。
我们所定义的Container接口如下:
  /** Interface Container - top level container*/
 package foundations;
 import java.io.serializable;
 public interface Container extends Serializable {
// Commands - see subinferfaces
/** Remove all objects from the container if found
*/
public void makeEmpty ();
//Queries
/** Return true if the container is empty
*/
public boolean isEmpty();
/** Return the number of objects in the container
*/
public int size();
}

1.2 最简单的容器--堆栈和队列
    这里定义最简单的容器:堆栈(Stack)和队列(Queue)
    堆栈使一个容器,并具有以下特性:
 1) 堆栈是有次序的,这也是堆栈的一个属性,与堆栈所包含的对象无关。堆栈中对象的次序依赖于其插入、删除的顺序。后进先出。
 2)对堆栈的操作只能在一个名为top的位置上。用Push方法在堆栈顶部增加新的对象,用pop方法删除堆栈顶部的对象,用top方法查询堆栈顶部的对象。
 3)用MakeEmpty方法可以清除堆栈的对象,也可用isEmpty来查询该堆栈是否为空,以及查询堆栈的大小(size())。
    接口Stack是对Container的扩展,因此它继承了Container所有的方法,并增加了新的方法:push、pop、以及查询顶部对象的方法。
  /** Interface Stack - a first-in last-out container
 */
package foundations;
public interface Stack extends Container {
//Commands
/** Add an object onto the top of the stack
*/
public void push(object obj);

/** Remove an object form the top of the stack
* Throw NoSuchElementException if stack is empty
*/
public void pop();
//Queries

/** Return without removing, the top object on the stack
* Throw NoSuchElementException if stack is empty
*/
public object top();
}
队列也是一个容器,并具有以下特性:
1)队列有次序,这也是它的一个属性,与队列所包含的对象无关。队列中对象的次序依赖于其插入、删除的顺序。队列中的次序关系的主要特点是先进先出。
2)对队列的操作限制在两个位置上,即front(对头)、rear(队尾)。我们可以在尾部增加对象,在头部删除对象,或查询头部的对象。
3)可以用MakeEmpty方法可以清除队列的对象,也可用isEmpty来查询该队列是否为空,以及查询队列的大小(size())。
接口Queue是对Container的扩展,因此它继承了Container所有的方法,并增加了新的方法:add、remove、以及查询头部对象的方法。
/** Interface Queue
*/
public interface Queue extends Container {
//Commands
/** Add an object at the rear of the queue
*/
public void add(Object obj);

/** Remove an object from the front of the queue
* Throws NoSuchElementException if queue is empty
*/
public void remove();

//Queries
/** Return without removing, the front object in the queue
* Throws NoSuchElementException if queue is empty
*/
public object front();
}

1.3 辅助性接口和类--Comparable(可比性)和Association(关联性)
   有序容器包含了一些对象,这些对象在容器中的位置(或次序)是根据它的某个属性的重要性来决定的,更确切的说,有序容器中的对象是可比较的,这个属性可以通过要求对象类来实现Comparable接口来获得。Comparable接口包含唯一一个查询方法CompareTo。
  查询CompareTo返回一个整数值。
/** Interface Comparable
*/
public Interface Comparable {
//Queries

/** Return -1 if the receiver is less than obj,
* 0 if the receiver equals obj and
* 1 if the receiver is greater than obj
*/
public int compareTo (Object obj);
}

   类Association允许将值和键(Key)组合起来,即在键和其值之间有一个关联。类Association在研究一个需要键-值(key-value)对的容器数据结构时起到什么重要的作用。
   在字典类容器中就包含Association类的实例,字典是由键组成的,也就是说,我们查找字典中的对象时,只是查找它的键。如果字典按某种顺序(根据所包含的键的相对大小)排列的,那么我们必须保证任何输入到OrderdDictionary(有序字典)中的关联对的键也是可以比较的(Comparable)。同时,我们要求关联也必须是可串行化的,这样才能保证前面所提到的所有容器都要求是可串行化的。Association是一个类,而不是接口。
/** Class Assocation
* An instance must initialize a key on creation.
* If used as a comparable Assocation,keys must be comparable and comparions is based on keys only.
* Note that equals() does not enforce the comparable feature and requires equality of both key and value.
*/
package foundations;
import java.io.serializable;

public class Association extends Object implements Comparable,Serializable {
//Fields
private Object key;
private Object value;

/** Create an instance with specified key and null value
*/
public Assocation (Object key) {
 this(key,null);
}

/** Create an instance with specified key and value
*/
public Association(Object key,Object value) {
  this.key=key;
  this.value=value;
}

/** Set the value
*/
public void setValue(Object value) {
  this.value = value;
}

/** return key
*/
public Object key() {
  return key;
}

/** return value
*/
public Object value() {
return value;
}

/**Return a string representation.
* Return a String of the form <key:value>
*/
public String toString() {
 return "<"+key+":"+value+">";
}

/** Override inherited object method equals()
*/
public boolean   equals (Object obj) {
  if(obj instanceof Assocation)]
    return (key.equals((Assocation)obj).key) && value.equals((Assocation)obj).value));
  else return false;
}

/**Implement Comparable method compareTo
* Compare based only on key; key must be comparable
*/
public int compareTo (Object obj) {
 return ((Comparable)key).compareTo((Association)obj.key());
}

/** Override inherited Object method hashCode().
*Return a unique int representing this object
*/
public int hashCode () {
  int bits1 = key.hashCode();
  int bits2 = value.hashCode();
 return (bits1 <<8)^(bits2>>8);
 }
}

未完,待续....
posted on 2005-06-25 16:31 苹果 阅读(2107) 评论(0)  编辑  收藏 所属分类: J2EE/JAVA学习

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


网站导航: