Java语法-基于proj1

课程资料：CS61B sp21, Project 1: Data Structures

接口与实现

在Project1中，我们需要完成两种双端队列：基于链表的和基于数组的．这两种双端队列的方法有许多重复：都要实现头插、尾插、头删、尾删、打印队列等；并且根据类的封装特点，这两种双端队列仅仅是实现方法不同，在用户使用过程中不应该有很大区别．因此，可以将这两种双端队列都视为一个共同接口的实现．

接口

接口（Interface） 内部一般而言只需要声明方法的返回类型、方法名及参数，而不需要提供方法的具体实现；这部分通常留给其实现类来完成．

当然，接口内部也可以直接把方法的具体实现补充完全，这样实现类如果没有重写该方法，就会调用接口内的默认实现．此时接口内部该函数前要加 default 关键字．

默认接口中的方法都是 public 的．当我们在方法前加 public 时，IDEA会告诉我们这个修饰是冗余的．

根据proj1对Deque接口方法的描述，其代码实现如下：

public interface Deque<T> {  
    void addFirst(T item);  
    void addLast(T item);  
    int size();  
    void printDeque();  
    T removeFirst();  
    T removeLast();  
    T get(int index);  
    
	// 由于已经有size()函数，因此这个方法可以在接口中实现
    default boolean isEmpty() {  
        return size() == 0;  
    }  
}

实现

当一个类要成为接口的实现时，需要添加 implements 关键字．这个类可以有接口以外的方法，但必须要把接口中所有的非 default 方法实现，否则无法编译．例如proj1中的两个实现：

public class LinkedListDeque<T> implements Deque<T>
public class ArrayDeque<T> implements Deque<T>

重写

类实现接口的方法，或者子类覆盖掉原来父类的方法，这叫做重写（Override）．当重写一个方法时，可以选择在方法前加上一行 @Override 签名．

@Override  
public void addFirst(T item) {  
	......
}

实际上，就算不包含这个签名，只要形式一样你就是在重写该方法．但是当你出现错误（比如函数名打错）编译器会认为你是在写一个新方法而非重写；如果加上签名编译器会提醒你程序错误．

继承与派生

在proj1中，并没有使用继承语法，但因其与接口相似且十分重要，在此一并记录．

继承

当A类的部分方法与B类完全一样时，可以用 extends 关键字，让A类继承B类的方法，此时B类称为父类，A类成为子类．

由于子类是在父类的基础上添加、重写方法，因此创建子类实例时一定要先初始化一个父类实例．子类的构造函数中会默认插入一个无参 super()，即先调用无参的父类构造函数创建一个父类实例；如果父类没有无参构造函数就会报错，需要我们手动在子类中补充完 super() 函数．

子类默认会继承父类所有 public 和 protected 成员，当子类需要调用父类成员时需要使用 super.methodname() 调用．

派生

子类可以重写父类的方法，也可以在父类的基础上添加新的方法．

对象

数据类型

在Java中，除了8种基本数据类（byte short int long float double char boolean）外，其他数据类型引用类型（类似C中的指针），本身不存有数据，存的是实例的地址．并且引用类型中所有的类、数组和枚举都可以认为是 Object 的子类．

对于引用类型，与C++不同的是：当我们声明一个变量时，系统并没有为这个变量的实例分配内存，而只是为这个变量本身分配内存，也就是只分配了个64位地址（此时地址为 null）．只有 new 的时候才会为实例本身分配内存．

泛型

我们不知道用户需要用双端队列存什么类型的数据，对此Java提供了泛型：在类声明中，类名后加上 <占位符>，在想用任意类型的地方，系统会自动使用那个占位符，也就是题意中 <T> 的来源．

需要注意的是，泛型只适用于引用类型，也就是说我们不能把 int 这类基本类型放入角括号中，而要将其对应的引用版本放去，如 Integer．

对象方法

之前提到所有类都是 Object 类的子类，因此所有类都继承了其方法：

• String toString()
• boolean equals(Object obj)
  等等．其中 equals 就是我们之后要实现的方法．

静/动态类型

一般来说，创建对象时，对象的类型一般用接口类型，而对象的实例用实现类．

例如 Deque<String> dq = new ArrayDeque<String>()，左边是静态类型用接口类，右边是动态类型用实例类．

• 静态类型：在变量声名时决定，编译器根据静态类型判断能调用哪些方法．
• 动态类型：变量实际指向的对象的类型，即等号右边 new 出来的 ArrayDeque。它在运行期才被确定，它确定了方法被调用时具体执行哪一段代码．

静动态变量体现了OOP的封装思想，用户只需要知道可以使用什么方法而不需要知道方法如何实现．

链表双端队列

至此，我们已经可以实现除迭代器与比较器外的所有方法了．让我们再看看题目要求：

• public void addFirst(T item)：头插，且可以认为不会插入 null．
• public void addLast(T item)：尾插，且可以认为不会插入 null．
• public boolean isEmpty()：返回是否为空．
• public int size()：返回队列大小．
• public void printDeque()：打印元素，相邻元素用空格隔开，所有元素打完后打印一个新行．
• public T removeFirst()：头删并返回删除元素，若不存在返回 null．
• public T removeLast()：尾删并返回删除元素，若不存在返回 null．
• public T get(int index)：返回0-base的第index个元素，若不存在返回 null．
  以上是Deque接口的要求，而对链表Deque还有额外要求：
• 插入、删除、队列大小要实现 ．
• 其他操作不能慢于 ．
• get() 函数要使用迭代，同时再写一个 public T getRecursive(int index) 函数使用递归．
• 有构造函数 public LinkedListDeque() 创建一个空链表．

数据结构实现

根据之前的链表经验，加入一个哨兵结点可以减少很多特判情况．由于要求头尾操作均为 ，因此单哨兵结点的线性链表一定不行．提供了两种解决方案：

• 使用两个哨兵结点，分别在头和尾．
• 只使用一个哨兵结点，该结点后一个是第一个结点而前一个是最后一个结点．
  本人选择使用法二，即首尾相连方法．首先无论选择哪种，我们都有“找到一个结点的前驱结点与后继结点”操作，因此这一定是一个双向链表，结点要有指向前驱结点与后继结点的指针．

除了哨兵结点与嵌套结点类，由于我们需要在 时间返回大小，因此最好直接用一个 size 变量存储大小．因此，我们可以写出我们需要的成员变量：

public class LinkedListDeque<T> implements Deque<T> {  
  
    private class Node {  
        T item;  
        Node prev, next;  
  
        Node(T i, Node p, Node n) {  
            item = i;  
            prev = p;  
            next = n;  
        }  
    }  
    
    private int size;  
    private Node sentinel;
}

方法实现

我们按照创建-增-删-查的顺序进行方法实现．

创建空链表（构造函数）

由于链表为空，因此大小为0；哨兵结点的前驱结点与后继结点都是自身．

/** Creates an empty linked list deque. */  
public LinkedListDeque() {  
    size = 0;  
    sentinel = new Node(null, null, null);  
    sentinel.next = sentinel;  
    sentinel.prev = sentinel;  
}

我尝试写过 sentinel = new Node(null, sentinel, sentinel) 的写法，但是由于此时 sentinel 还未被创建，左脚踩右脚出现bug．

头插

当我们向链表的头插入新元素时，有五个地方需要被修改：

• 数组大小增加1
• 哨兵结点的后继结点变成新头
• 新头的前驱结点变成哨兵结点
• 新头的后继结点变成老头
• 老头的前驱结点变成新头

  /** Add an item of type T to the front of the deque in O(1). */ 
  @Override  
  public void addFirst(T item) {  
      size++;  
      Node temp = new Node(item, sentinel, sentinel.next);  
      sentinel.next = temp;  
      temp.next.prev = temp;  
  }

  尾插

  尾插与头插类似，也是五个地方，不再赘述．

  /** Adds an item of type T to the back of the deque in O(1). */ 
  @Override  
  public void addLast(T item) {  
      size++;  
      Node temp = new Node(item, sentinel.prev, sentinel);  
      sentinel.prev = temp;  
      temp.prev.next = temp;  
  }

  头删

  根据要求，先判断能不能删，即判断大小是否为0；若不为0，需要改变三个地方：
• 数组大小减少1
• 哨兵结点的后继结点变为原来的第二个结点
• 原来的第二个结点的前驱结点变为哨兵结点

当我们修改完这两个指针后，由于没人指向该结点，Java会帮我们自动回收内存．由于我们需要返回被删除的结点的值，因此要先存下来．

@Override  
public T removeFirst() {  
    if (size == 0) {  
        return null;  
    }  
    size--;  
    T item = sentinel.next.item;  
    sentinel.next = sentinel.next.next;  
    sentinel.next.prev = sentinel;  
    return item;  
}

尾删

与头删类似．

@Override  
public T removeLast() {  
    if (size == 0) {  
        return null;  
    }  
    size--;  
    T item = sentinel.prev.item;  
    sentinel.prev = sentinel.prev.prev;  
    sentinel.prev.next = sentinel;  
    return item;  
}

查找大小

由于专门创建了个成员变量 size 记录大小，直接返回即可．

@Override  
public int size() {  
    return size;  
}

打印

我们选择头结点为哨兵结点的后继结点，循环条件是当前结点不为哨兵结点．由于我们的链表中不存在空结点，因此当再一次到达哨兵结点的时候就是走到尾了．

@Override  
public void printDeque() {  
    for (Node p = sentinel.next; p != sentinel; p = p.next) {  
        System.out.print(p.item + " ");  
    }  
    System.out.println();  
}

查找元素（迭代版）

首先判断是否存在这个数：由于 index 是0-base的，因此只要 index >= size 都是不存在，直接返回 null；接着选择头结点为哨兵结点的后继结点，迭代 index 次，返回最后迭代到的结点即可．

/** Gets the item at the given index using iteration.  
 *  0 is the front, 1 is the next item, and so forth. *  If no such item exists, returns null. */
@Override  
public T get(int index) {  
    if (index >= size) {  
        return null;  
    }  
    Node p = sentinel.next;  
    for (int i = 0; i < index; i++) {  
        p = p.next;  
    }  
    return p.item;  
}

查找元素（递归版）

观察提供的接口 public T getRecursive(int index)，参数只有一个 index 而没有其他可以定位的，也就是说即使用 index - 1 也不知道从哪里开始．这时候需要用61B之前教过的方法：构造一个 private 的辅助函数．我们将两个参数传入辅助函数：当前结点 current 和剩余需要遍历的结点数 left．当 lfet == 0 时就将当前结点返回．

/** Helpful method of getRecursive. */
private T getRecursiveHelper(Node current, int left) {  
    if (left == 0) {  
        return current.item;  
    }  
    return getRecursiveHelper(current.next, left - 1);  
}

然后可以将判断的部分放在原函数中，index < size 就从头结点开始递归．

/** Same as get, but uses recursion */  
public T getRecursive(int index) {  
    if (index >= size) {  
        return null;  
    }  
    return getRecursiveHelper(sentinel.next, index);  
}

数组双端队列

我们再来看看题目对数组Deque的额外要求：

• 插入、删除、队列大小、查找要实现 （不含扩、缩容）．
• 数组起始大小要为 ．
• 当数组满时自动扩容；对于长度为 及以上的数组．使用率小于 时自动缩容．
• 有构造函数 public ArrayDeque() 来创建一个空数组．

  数据结构实现

  首先是由数组实现，因此创建一个 T 类型的数组 dq，再同链表Deque用一个 size 专门记录大小．

由于增删改查均要求 ，因此对于这些操作不能改变每一个元素对应的数组位置．例如不能将首元素固定在 dq[0] 位置，因为这样每次头插都要将每个元素后移一位．因此可以像链表Deque一样，通过一个变量记录从哪里开始哪里结束，并且将整个数组首尾相接循环使用：此处用 start 表示Deque的起始下标（含），用 end 表示Deque的结束下标（不含）．也就是说真正存有数据的下标范围是 ．

对于数组循环遍历，可以使用 i = (i + 1) % dq.length，当 i == length 时会自动变为0．

public class ArrayDeque<T> implements Deque<T>, Iterable<T> {  

    private T[] dq;  
    private int start, end;  
    private int size;
}

方法实现

创建空数组（构造函数）

由于数组为空，因此大小为0；根据 start 和 end 的定义，初始均为0；按照题目要求，new 一个大小为8的数组．

/** Creates an empty array deque.  
 *  From dq[start] to dq[end - 1], size = end - start.*/
public ArrayDeque() {  
    dq = (T[]) new Object[8];  
    start = size = end = 0;  
}

修改容量

由于增删都要用到扩容缩容，可以将其单独写成一个方法．

首先需要知道修改后容量的大小，因此接受一个参数 len．修改容量方法也比较暴力：直接创建一个新数组，将每个元素都复制一遍．

如果我们按照原来的 start 和 end 来复制数组，由于不确定是要缩容还是扩容，会产生很多特判；为了避免繁琐，修改容量时直接将首元素拉回下标0处（反正都是一样的复杂度），然后直接一路往后复制直到原数组遍历完即可（不用考虑新数组会不会越界，这是在增删方法中应该完成的特判）．

在本项目中，扩容采用2倍扩容，缩容采用1/2缩容；这样操作结果都是偶数，也不用担心取整问题．

/** Resize an array deque to larger or smaller. */  
private void resize(int len) {  
    T[] tmp = (T[]) new Object[len];  
    for (int i = start, k = 0; k < size; i = (i + 1) % dq.length, k++) {  
        tmp[k] = dq[i];  
    }  
    start = 0;  
    end = size;  
    dq = tmp;  
}

头插

有四个地方需要被修改：

• 数组大小增加1
• start 减小1
• 将新数据放在 dq[start] 处
• 判断数组是否满；如果满进行扩容．

需要注意的是 start-- 可能越界，如果 start == 0 要将其赋值为最后一个位置．

/** Add an item of type T to the front of the deque in O(1). */  
@Override  
public void addFirst(T item) {  
    size++;  
    if (start == 0) {  
        start = dq.length - 1;  
    } else {  
        start--;  
    }  
    dq[start] = item;  
    if (size == dq.length) {  
        resize(2 * dq.length);  
    }  
}

尾插

类似头插，只不过修改与判定点变为 end．

/** Adds an item of type T to the back of the deque in O(1). */  
@Override  
public void addLast(T item) {  
    size++;  
    dq[end] = item;  
    if (end == dq.length - 1) {  
        end = 0;  
    } else {  
        end++;  
    }  
    if (size == dq.length) {  
        resize(2 * dq.length);  
    }  
}

头删

先判断大小是否为0；若不为0，需要改变四个地方：

• 数组大小减少1
• 将 dq[start] 对应的数据删除
• start 增加1
• 判断是否需要缩容

  /** Removes and returns the item at the front of the deque in O(1).  
   *  Returns null if no item. */
  @Override  
  public T removeFirst() {  
      if (size == 0) {  
          return null;  
      }  
      size--;  
      T tmp = dq[start];  
      dq[start] = null;  
      start = (start + 1) % dq.length;  
      if ((double) size / dq.length < 0.25 && dq.length >= 16) {  
          resize(dq.length / 2);  
      }  
      return tmp;  
  }

  尾删

  与头删类似．

  /** Removes and returns the item at the back of the deque in O(1).  
   *  Returns null if no item. */@Override  
  public T removeLast() {  
      if (size == 0) {  
          return null;  
      }  
      size--;  
      if (end >= 1) {  
          end--;  
      } else {  
          end = dq.length - 1;  
      }  
      T tmp = dq[end];  
      dq[end] = null;  
      if ((double) size / dq.length < 0.25 && dq.length >= 16) {  
          resize(dq.length / 2);  
      }  
      return tmp;  
  }

  查找大小

  /** Returns the number of items in the deque in O(1). */  
  @Override  
  public int size() {  
      // System.out.println(size);  
      return size;  
  }

  打印

  直接从 i = start 开始遍历，直到 i == end 时结束．尽管我们是左闭右开的区间设置，但由于数组满时会自动扩容，因此数组永远不会满，start 与 end 永远不会相等．

  /** Prints the items in the deque from first to last, separated by a space.  
   *  Once all the items have been printed, print out a new line. */@Override  
  public void printDeque() {  
      for (int i = start; i != end; i = (i + 1) % dq.length) {  
          if (dq[i] != null) {  
              System.out.print(dq[i] + " ");  
          }  
      }  
      System.out.println("");  
  }

  查找元素

  数组直接用下标即可 查找．直接用 start + index 查找即可．

  /** Gets the item at the given index in O(1).  
   *  0 is the front, 1 is the next item, and so forth. *  If no such item exists, returns null. */@Override  
  public T get(int index) {  
      if (index >= size) {  
          return null;  
      }  
      return dq[(start + index) % dq.length];  
  }

  迭代器

  为了完成 public Iterator<T> iterator() 方法，我们需要先认识一下迭代器相关语法．

对于线性的数据结构，其迭代方式一般都是从前往后迭代，如数组、链表；而对于非线性数据结构，如树、图，我们要自己实现内置的迭代方式，java为此提供了可迭代接口和迭代器．

可迭代接口

对于一个数据结构，其可以成为一个可迭代接口（Iterable）的实现类．

Iterable 的完整定义：

public interface Iterable<T> {
    Iterator<T> iterator();

    // Java 8+ 引入的默认方法（61B 初期不要求，了解即可）
    default void forEach(Consumer<? super T> action) { ... }
    default Spliterator<T> spliterator() { ... }
}

此处唯一的要求就是要实现一个获取迭代器的 public 方法．而这个迭代器需要我们使用嵌套类定义．

迭代器

根据上述，我们要用嵌套类在数据结构内部实现一个迭代器的类．

Iterator 的完整定义：

public interface Iterator<T> {
    // 如果仍有元素可以迭代，则返回 true．
    boolean hasNext();

    // 返回迭代中的下一个元素．
    T next();

    //从底层集合中移除迭代器最后返回的元素（可选操作）．在61B的作业中，通常不需要实现它．
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    // Java 8 引入，61B不做要求
    default void forEachRemaining(Consumer<? super T> action) { ... }
}

需要实现两个方法：hasNext 和 next．我们可以这么设计：不妨设迭代下标为 pos，而数据结构当前总大小为 size．

• hasNext 检查当前位置是否还有元素，如果有返回true；也就是判断 pos < size 即可．
• next 返回当前位置的元素，并且将 pos 后移一位．

方法实现

迭代器

有了上述知识，我们就可以根据设计的结构写出两种Deque的迭代器：

// 链表双端队列的迭代器
private class LinkedListDequeIterator implements Iterator<T> {  
    Node p = sentinel.next;  
  
    @Override  
    public boolean hasNext() {  
        return p != sentinel;  
    }  
  
    @Override  
    public T next() {  
        T returnItem = p.item;  
        p = p.next;  
        return returnItem;  
    }  
}

/** The Deque objects we’ll make are iterable  
 *  so we must provide this method to return an iterator. */
public Iterator<T> iterator() {  
    return new LinkedListDequeIterator();  
}

// 数组双端队列的迭代器
private class ArrayDequeIterator implements Iterator<T> {  
    int pos = start;  
  
    @Override  
    public boolean hasNext() {  
        return pos != end;  
    }  
  
    @Override  
    public T next() {  
        T returnItem = dq[pos];  
        pos = (pos + 1) % dq.length;  
        return returnItem;  
    }  
}

/** The Deque objects we’ll make are iterable  
 *  so we must provide this method to return an iterator. */
public Iterator<T> iterator() {  
	return new ArrayDequeIterator();  
}

判断数据结构相等

除了迭代器之外，我们还需要实现一个 public boolean equals(Object o) 方法：如果 o 是Deque且里面的元素均相等，则判断两个Deque是相等的．由于不用实现 compareTo，因此这并不算是比较器内容而是迭代器内容．

如果二者指向的是同一个容器，也就是地址完全相等，此时可以用 this == o 即可直接判等，如果相等就直接返回 true．

if (this == o) {  
    return true;  
}

接着需要判断 o 是否是 Deque．Java里的 instanceof 可以判断一个元素是否是一个类的实例．如果不是的话直接返回 false．

if (!(o instanceof Deque)) {  
    return false;  
}

还需要判断元素是否相等．由于我们知道 o 是一个 Deque 了，但是编译器并不知道，它还认为 o 是一个 Object，因此不让我们用迭代器；我们需要将其强制转换为 Deque 类型．由于我们并不知道它内部装了什么数据类型，因此需要用 ? 来占位（这个语法有点玄学）．

Deque<?> other = (Deque<?>) o;

现在 o 是一个 Deque，我们还可以进行简化：如果两个容器内元素个数不相等，也可以直接返回 false．

if (this.size() != other.size()) {  
    return false;  
}

最后用迭代器进行迭代；由于编译器现在只知道 o 是 Deque 而不知道其是否可迭代（尽管我们写的 Deque 都实现了迭代器），因此还需要将其转化为 Iterable<?>，迭代器也需要使用 Iterator<?> 类型（最难绷的语法），然后用 .equals() 方法依次判断是否相等．

Iterator<T> iter1 = this.iterator();  
Iterator<?> iter2 = ((Iterable<?>) other).iterator();  
while (iter1.hasNext() && iter2.hasNext()) {  
    if (!(iter1.next().equals(iter2.next()))) {  
        return false;  
    }  
}  
return true;

最终效果（两个Deque代码相同）：

/** Returns whether the parameter o is equal to the Deque. */  
public boolean equals(Object o) {  
    if (this == o) {  
        return true;  
    }  
    if (!(o instanceof Deque)) {  
        return false;  
    }  
    Deque<?> other = (Deque<?>) o;  
    if (this.size() != other.size()) {  
        return false;  
    }  
    Iterator<T> iter1 = this.iterator();  
    Iterator<?> iter2 = ((Iterable<?>) other).iterator();  
    while (iter1.hasNext() && iter2.hasNext()) {  
        if (!(iter1.next().equals(iter2.next()))) {  
            return false;  
        }  
    }  
    return true;  
}

比较器

Proj1还有一个任务：在 ArrayDeque 的基础上创建 MaxArrayDeque，其拥有前者的所有方法，但还拥有一个新的构造函数和两个新的方法：

• public MaxArrayDeque(Comparator<T> c)：对给定的比较器创建一个 MaxArrayDeque．
• public T max()：返回由默认（即构造函数带有的）比较器决定的最大值，若为空返回 null．
• public T max(Comparator<T> c)：返回由传入的比较器 c 决定的最大值，若为空返回 null．

在完成这个任务前，先认识一下比较器相关语法．

可比较接口

由于 > < 符号只能比较基本数据类型而不能比较对象类型，且Java也没有C++中的重载运算符，因此提供了一个 Comparable 接口．

Comparable 接口的完整定义：

public interface Comparable<T> {
	// this > o返回正数，this == o返回0，this < o返回负数
	public int compareTo(T o);
}

比较器

由于一个类只能拥有一个 compareTo 函数，当需要不同关键字排序时会比较麻烦，而比较器（Comparator）就可以解决这个问题．

比较器的完整接口：

public interface Comparator<T> {
	// 返回值同上
    int compare(T o1, T o2);
}

对于自己写一个比较器而言，由于比较的两个对象都是该类的，因此这个比较器也应该放在该类中，成为一个嵌套类．并且由于比较器没有使用任何外部变量、不依赖任何实例，因此应该是静态嵌套类．

由于该任务要求直接用现成的比较器返回大小，因此不需要自己写比较器，只需要用给定比较器实现比较功能即可．

方法实现

根据题目要求，MaxArrayDeque 是 ArrayDeque 的子类．

构造函数

由于我们的要求是传入一个比较器然后将其设置为默认比较器，因此我们需要在成员变量中先创建一个比较器 defaultComparator；同时可以创建一个默认比较器下的最大值 defaultMax（非必须）．

public class MaxArrayDeque<T> extends ArrayDeque<T> {  
  
    private Comparator<T> defaultComparator;  
    private T defaultMax;  
  
    public MaxArrayDeque(Comparator<T> c) {  
        super();  
        defaultComparator = c;  
    }
}

默认最大值

先判断数组大小是否为0；若不为0，则通过 super 调用父类的迭代器，通过迭代器迭代、比较找到最值．

public T max() {  
    if (super.size() == 0) {  
        return null;  
    }  
    Iterator<T> iter = super.iterator();  
    defaultMax = iter.next();  
    while (iter.hasNext()) {  
        T current = iter.next();  
        if (defaultComparator.compare(current, defaultMax) > 0) {  
            defaultMax = current;  
        }  
    }  
    return defaultMax;  
}

给定比较器最大值

给定比较器最大值，与默认最大值类似．

public T max(Comparator<T> c) {  
    if (super.size() == 0) {  
        return null;  
    }  
    Iterator<T> iter = super.iterator();  
    T currentMax = iter.next();  
    while (iter.hasNext()) {  
        T current = iter.next();  
        if (c.compare(current, currentMax) > 0) {  
            currentMax = current;  
        }  
    }  
    return currentMax;  
}

至此，已完成proj1在数据结构方面的全部内容．