2. 线性表 ADT 的替代设计¶

线性表 ADT 规定，一个线性表不仅包含按线性顺序排列的对象集合，还包含"当前位置"。虽然这是呈现线性表所体现的主要概念的一种简单方式，但它会使任何依赖在同一线性表中拥有两个或更多不同"当前位置"的算法变得复杂，例如任何从两端向中间逐步推进的算法。

另一种设计是把"当前位置"分离为一个单独的对象。在下面的 ADT 中，我们把它称为 ListIndex 。这是一种有时被称为迭代器的概念的简单形式。 ListIndex 接口抽象了线性表中位置的概念。

public interface ListIndex {
  public void prev();
  public void next();
}

public interface List {
  public void clear();
  public void insert(Object it, ListIndex where);
  public void append(Object it);
  public Object remove(ListIndex where);
  public ListIndex getStart();
  public ListIndex getEnd();
  public ListIndex pointToPos(int where);
  public int length();
  public Object getValue(ListIndex where);
}

在实现中有一个问题：这两个类将如何通信。对于基于数组的线性表， ListIndex 只需存储一个表示位置的整数。对于链表类， ListIndex 将存储一个指向链表结点的指针。这意味着 List 类需要能够设置和获取这个指针，但外部任何人都不应当需要知道它。有些语言（如 Java 和 C++）有机制允许特定类访问另一个类的非公开成员。其他语言（如 Processing）则没有这样的概念。

一种通用的解决办法是，把 ListIndex 的接口设为公开，但把实现作为 List 实现的一个私有内部类。下面针对基于数组的线性表的实现就采用了这种方法。

// Array-based list implementation
class AList implements List {
  private class AListIndex implements ListIndex {
    int pos;

    AListIndex(int posit) { pos = posit; }
    public void prev() { if (pos != 0) { pos--; } }
    public void next() { if (pos < listSize) { pos++; } }
  }

  private static final int defaultSize = 10; // Default size
  private int maxSize;                    // Maximum size of list
  private int listSize;                   // Current # of list items
  private Object listArray[];             // Array holding list elements

  // Constructors
  // Create a new list object with maximum size "size"
  AList(int size) { 
    maxSize = size;
    listSize = 0;
    listArray = new Object[size];         // Create listArray
  }
  // Create a list with the default capacity
  AList() { this(defaultSize); }          // Just call the other constructor

  public void clear()                     // Reinitialize the list
    { listSize = 0; }              // Simply reinitialize values

  // Insert "it" at current position
  public void insert(Object it, ListIndex where) {
    if (listSize >= maxSize) {
      System.out.println("List capacity exceeded, nothing inserted");
      return;
    }
    int pos = ((AListIndex)where).pos;
    for (int i=listSize; i>pos; i--) {     // Shift elements up
      listArray[i] = listArray[i-1];      //   to make room
    }
    listArray[pos] = it;
    listSize++;                           // Increment list size
  }

  // Append "it" to list
  public void append(Object it) {
    if (listSize >= maxSize) {
      System.out.println("List capacity exceeded, nothing inserted");
      return;
    }
    listArray[listSize++] = it;
  }

  // Remove and return the current element
  public Object remove(ListIndex where) {
    int pos = ((AListIndex)where).pos;
    if ((pos<0) || (pos>=listSize)) {     // No current element
      return null;
    }
    Object it = listArray[pos];          // Copy the element
    for(int i=pos; i<listSize-1; i++) {    // Shift them down
      listArray[i] = listArray[i+1];
    }
    listSize--;                           // Decrement size
    return it;
  }

  // Return list size
  public int length() { return listSize; }

  // Return a ListIndex to the beginning of the list
  public ListIndex getStart() {
    return new AListIndex(0);
  }
  
  // Return a ListIndex past the end of the list
  public ListIndex getEnd() {
    return new AListIndex(listSize);
  }
  
  public ListIndex pointToPos(int pos) {
    return new AListIndex(pos);
  }

  // Return the current element
  public Object getValue(ListIndex where) {
    int pos = ((AListIndex)where).pos;
    if ((pos < 0) || (pos >= listSize)) { // No current element
      return null;
    }
    return listArray[pos];
  }
}

CS5040 中级数据结构与算法

Chapter 9 Design

2. 线性表 ADT 的替代设计¶