线性表（用数组存储数据）

线性表是按顺序存储数据时常用的一种数据结构。例如，学生的列表、空房间的列表、城市的列表以及书籍的列表。使用数组存储线性表的元素是实现线性表的其中一种方式。

下面以袋集合为例，介绍数组线性表。袋可以定义为一种没有按照任何特定位置关系来组织其元素的组合。从概念上讲，它类似于放置物品的真实袋子。一旦将元素放入袋中，将不能确定袋中元素的相对位置。如果进入袋中盲目地取出一个元素，则元素的取出几率是相同的。袋是一种非线性集合。这种集合中的元素实质上根本就没有任何组织方式。袋中的元素相互间没有任何固有关系，而且元素也没有按照特定的次序添加到袋中。

UML描述

接口实现

 

import java.util.Itrator;
public interface BagADT
{
     // Adds one element to this bag
     public void add (Object element);

     // Removes and returns a random element from this bag
     public Object removeRandom ();

     // Removes and retruns the specified element from this bag
     public Object remove (Object element);

     // Returns the union of this bag and the parameter
     public BagADT union (BagADT set);

     // Returns true if this bag contains the parameter
     public boolean contains (Object target);

     // Returns true if this bag and the parametr contain exactly the 
     // same elements
     public boolean equals (BAgADT bag);

     // Returns true if this set contains no elements
     public boolean isEmpty ();

     // Returns the number of elements in this set
     public int size ();

     // Returns an iterator for the elements in this bag
     public Iterator iterator ();

     // Returns a string representation of this bag
     public String toString ();
}

注意某些方法的返回类型是BagADT，这表示它们返回一个袋集合。但是通过使用接口名作为返回类型，接口就没有将方法的调用委托给任何实现袋的类。对于接口的定义来说，这非常重要，因为接口并没有人为地绑定到某个特定的实现。接收袋集合作为参数的方法也是同样的道理。

 

ArrayBag类

ArrayBag类实现BagDAT接口，因而必须定义该接口中列出的方法。记住，实现某个接口的类还要定义其他的方法。

ArrayBag类的关键实例数据包括：一个数组（contents），用于存储袋中的对象；整形变量count，用于记录集合中元素的个数。还要定义一个Random对象，以支持袋中随机元素的绘制；一个定义默认容量的常量（DEFAULT_CAPACITY）；一个名为NOT_FOUND的常量，以有助于操作查找特定的元素。ArrayBag类的实例数据声明如下：

 

private static Random rand = new Random();
private final int DEFAULT_CAPACITY = 100;
private final int NOT_FOUND = -1;
private int count;
private Object [] contents;

注意，Random对象声明为一个静态变量，在其声明中（而不是在构造函数中）进行实例化。因为Random对象是静态变量，所以ArrayBag类的所有实例均共享该变量。这种做法将避免因创建两个袋，但它们的随机数产生器却使用相同的种子值(seed value)而带来的问题。

变量count的值实际上表示两个相关的信息。首先，它表示当前存储在袋集合中的元素个数；其次，因为Java数组的索引从0开始，所以它还表示数组中下一个可以存储新元素的空位置。一方面，变量count的值表示集合的抽象状态，另一方面它又有助于我们了解集合的内在实现。

下面定义了ArrayBag类的构造函数，它创建一个初始为空的袋。变量count的值设置为0，并且实例化用于存储袋中元素的数组。该构造函数将contents数组 的初始容量设置为一个默认值。

 

// Create an empty bag using the default capacity
public ArrayBag()
{
     count = 0;
     contents = new Object [DEFAULT_CAPACITY];
}

因为在特定的情况下，用户可能知道袋中将要存储元素的大致数目，因而在开始时可以指定该值。所以我们还可以提供另一个有参构造函数，它接收一个表示contents数组的初始容量的整形参数。这个有参构造函数定义如下：

 

// Creat an emptybag using the specified capacity
public ArrayBag (int initialCapacity)
{
     count = 0;
     contents = new Object [initialCapacity];
}

 

方法

size和isEmpty方法

 

size方法仅仅返回count变量的值：

 

// Returns the number of elements currently in this bag
public int size()
{
     retrurn count;
}

 

isEmpty方法在count变量的值为0时返回真：

 

// Returns true if this bag is empty and false otherwise
public boolean isEmpty()
{
     return (count == 0);
}

ArrayBag实现在多种情况中需要依赖count的值。它是集合表示的基础。因此，所有改变袋集合状态的操作都必须仔细地维护count值的一致性。

 

add方法

该方法 的目的是将其接收的Object参数添加到袋集合中。如果数据结构的容量是固定的，则add方法必须考虑数组填满的情况。其解决方案是在这种情况发生时自动地扩展数组的容量。

 

// Adds the specified element to the bag, expanding the capacity of the bag array if necessary.
public void add (Object element)
{
     if (size() == contents.length)
       expandCapacity();
     contents[count] = element;
     count ++;
}

expandCapacity方法创建一个新的数组，其容量是当前存储袋中元素的数组的2倍，并将当前数组中的所有引用复制到这个新数组中，然后将重新设置实例变量contents，使其指向larger数组。

 

// wtice the capacity of the old one.
private void expandCapacity()
{
     Object [] larger = new Object [contents.length*2];
     for (int index = 0; index < contents.length; index++)
       larger [index] = contents [index];
     contents = larger;
}

注意，expandCapacity方法的可见性声明为private。它设计为一个支持方法（support method)，而不是作为提供给袋集合用户的方法。

 

addAll方法

addAll方法的目的是将一个袋中的所有对象添加到袋集合中。对于我们的数组实现，这意味着可以使用iterator方法遍历一个袋中的所有元素，然后使用add方法将它们添加到当前的袋中。以这种方式使用add方法的一个优点是，该方法将检查容量，并在必要时扩展数组。

 

// Adds the contents of the parameter to this bag.
public void addAll (BagADT bag)
{
     Iterator scan = bag.iterator();
     while (scan.hasNext())
        add (scan.next());
}

 

removeRandom方法

removeRandom方法从集合中随机地选择一个元素，并从集合中删除该元素，然后将其返回给调用方法。如果袋集合为空，则该方法将抛出EmptyBagException异常。

 

// Removes a random elelment from the bag and returns it .Throws an EmptyBagException if the bag is empty.
public Object removeRandom () throws EmptyBagException
{
     if (isEmpty())
       throw new EmptyBagException();
     int choice = rand.nextInt(count);
     Object result = contents [choice];
     contents [choice] = contents [count - 1];
     contents [count - 1] = null;
     count --;
}

袋集合的这种实现方法将袋中的所有元素从一端开始连续地存储在contents数组中。因为该方法删除某个元素，所以必须以某种方式填补空缺。可以使用一个循环将所有的元素向低位移动一个位置，但是这样做是不必要的。因为数组中不存在次序，所以可以简单地将最后一个数组元素放置在存储删除元素的单元中，这样就不需要循环了。

 

remove方法

remove方法从袋中删除指定的元素，并返回该元素。但袋允许出现重复的元素。这意味着如果袋中存在相同的两个元素，则删除其中一个，而保留另一个。如果为空袋，则该方法将抛出EmptyBagException异常，如果袋中并不存在目标元素，则抛出NoSuchElementException异常。

 

// Removes one occurance of the specificed element from the bag and rerurn it. Throws an EmptyBagExceptionif the bag is empty and a NosuchElementException if the taget is not in the bag.
public Object remove (Object target) throws EmptyBagException,NoSuchElementException
{
     int search = NOT_FOUND;
     if (isEmpty())
       throw new EmptyBagException();
     for (int index = 0; index < count && search == NOT_FOUND; index ++)
       if (contents [index].equals (target))
         search = index;
       if (search == NOT_FOUND)
         throw new NoSuchElementException();
     Object result = contents[search];
     contents[search] = contents[count - 1];
     contents[count - 1] = null;
     count --;
     return result;
}

 

 

union方法

union方法返回一个新袋，新袋包含原来两个袋中的所有元素。使用构造函数创建一个新袋，然后遍历数组，并使用add方法将当前袋中的元素添加到这个新袋中。接下来，我们为任务参数的袋创建一个迭代器，然后该袋中的每个元素，并将它们添加到新袋中。因为袋中的元素没有固有的次序，所以首先添加哪个袋中的内容无关紧要。

 

// Returns a new bag that is the union of this bag and the parameter.
public BagADT union (BagADT bag)
{
     ArrayBag both = new ArrayBag();
     for (int index = 0; index < count; index++)
       both.add (contents [index]);
     Iterator scan = bag.iterator();
     while (scan = bag.hasNext())
       both.add(scan.next());
     return both;
}

 

 

contains方法

在袋包含指定的目标元素时，contains方法返回真。

 

// Returns true if this bag contains the specified target element.
public boolean contains (Objct target)
{
     int search = NOT_FOUND;
     for(int index = 0; index < count && search == NOT_FOUND; index ++)
       if(contents[index].equals(target))
         search = index;
     return (search != NOT_FOUND);
}

 

 

equals方法

在当前的袋所包含的元素确实与传递为参数的袋的元素相同时，equals方法返回真。

 

// Returns true if this bag contains exactly the same elements as the parameter.
public boolean equals (BagADT bag)
{
     boolean result = false;
     ArrayBag temp1 = new ArrayBag();
     ArrayBag temp2 = new ArrayBag();
     Object obj;
     if(size() == bag.size())
       {
          temp1.addAll(this);
          temp2.addAll(bag);
          Iterator scan = bag.iterator();
          while(scan.hasNext())
            {
               obj = scan.next();
               if(temp2.contains(obj))
                 {
                    temp1.remove(obj);
                    temp2.remove(obj);
                 }
             }
            result = (temp1.isEmpty() && temp2.isEmpty());
         }
     return result;
}

 

 

toString方法

toString方法将袋中每个球的字母和数字构成一个字符串，然后返回它。

 

// Returns a string representation of thisbag.
public String toString()
{
     String result = "";
     for (int index = 0; index < count; index ++)
       result = result + contents[index].toString() + "\n";
     return result;
}

 

iterator方法

iterator方法通过ArrayIterator类实现。

 

// Returns an iterator for the elements currently in this bag
public Iterator iterator()
{
     rerurn new ArrayIterator(contents, count);
}

ArryIterator类：

 

import java.util.*;
public class ArrayIterator implements Iterator
{
     private int count;
     private int current;
     private Object[] items;

     // Set up this iterator using the specified items.
     public ArrayIter(Object[] collection, int size)
       {
          items = collection;
          count = size;
          current = 0;
       }

     // Returns true if this iterator has at least one more element to deliver in the iteraion.
     public boolean hasNext()
       {
           return (current < count);
       }
     // Returns the next element in the iteration. If therer are no more elements in this itertion,a NoSuchElementException is thrown.
     public Object next()
       {
           if(! hasNext())
               throw new NoSuchElementException();
           current ++;
           return items[current - 1];
       }