Java实现具有迭代器的线性表(顺序表)
Java实现具有迭代器的线性表(顺序表)
1，先了解下JAVA类库中的迭代器：JAVA提供了两种基本类型的迭代器，分别用两个接口来表示：Iterator<T>，ListIterator<T>。其中，Iterator<T>接口中只定义了三个方法：hasNext()、iterator()、next()，而ListIterator<T>中，除了拥有前面所述的三种方法外，而另外拥有hasPrevious()、previous()、remove()、set()等其他方法（具体参考JDK文档）。
这说明：实现了Iterator<T>接口的迭代器只能往一个方向遍历(正向)，而实现了ListIterator<T>接口的迭代器即可以正向遍历又可以反向遍历（由hasPrevious()、previous()实现反向遍历），同时，它还可以对遍历的元素进行修改（由set()方法实现）、删除当前遍历的元素（由remove()实现）。
2，当前，在写程序时，最好能够使用JAVA类库中已经为我们定义好的迭代器，它为JAVA的集合类都定义了返回上述两种迭代器的方法。
如：ArrayList<T>类的 iterator() 方法返回一个Iterator<T>类型的只能对单一方向进行迭代的迭代器，而listIterator()方法返回一个ListIterator<T>类型的迭代器，它不仅能双向迭代，而且修改、删除迭代的元素。
3，下面实例代码实现了一种ADT之顺序表（实质为数组），并且该数组拥有遍历器。该遍历器能对当前遍历的数组进行修改和删除。个人感觉要想同时保证迭代器具有修改和删除的功能，同时又要保证ADT基本操作的正确，对数组下标的合适定义真的很难。
4，首先定义了一个接口ListWithListIteratorInterface，该接口只有一个方法getIterator()，该方法负责生成一个迭代器并返回给调用者。然后，再让实现了数组的类SequenceListWithIterator<T> implements ListWithListIteratorInterface<T>.
为什么要这样做呢？为什么不用SequenceListWithIterator直接 implements ListIterator<T> ?
因为，如果用SequenceListWithIterator直接 implements ListIterator<T>，那么SequenceListWithIterator类的对象不仅是一个迭代器（因为它implements ListIterator<T>）而且是一个顺序表（因为它实现了线性表中的各种基本操作，相当于implments ListInterface<T>了）。这意味着，在我们的代码中，当创建了一个SequenceListWithIterator对象时，该对象不能在同一时刻对线性表进行多次迭代，因为它本身就是迭代器，只能对"自身"元素进行迭代了。
而采用SequenceListWithIterator<T> implements ListWithListIteratorInterface<T>，这样SequenceListWithIterator对象只是线性表，它不是迭代器。但是，由于它实现了ListWithListIteratorInterface<T>，它(顺序表对象)就可以调用getIterator()方法获得一个迭代对象，让该迭代器对象对自己进行遍历，当然了，它就可以多次调用getIterator()方法获得多个迭代器对象，从而可以让多个迭代器同时对自己进行遍历。
接口ListWithListIteratorInterface具体代码如下：
import java.util.ListIterator;
public interface ListWithListIteratorInterface<T> {
public ListIterator<T> getIterator();
}
实现了线性表的基本操作（说明它是一个顺序表）及拥有一个实现了ListIterator<T>接口内部类（说明它拥有一个迭代器）的具体代码如下：
import java.util.Arrays;
import java.util.ListIterator;
import java.util.NoSuchElementException;
public class SequenceListWithIterator<T> implements
ListWithListIteratorInterface<T> {
private final int DEFAULT_SIZE = 16;// final实例变量显示指定初始值，且不再变化。
private Object[] elementData;// 该数组用来保存顺序表中的元素
private int capacity;// 保存数组的长度
private int size;// 保存顺序表中当前元素的个数
private enum Move {
NEXT, PREVIOUS
};
private class IteratorForSequenceList implements ListIterator<T> {
private int nextIndex;// 标记迭代器指针的位置
private boolean isRemoveOrSetLegal;// 标记 remove() 或 set() 操作是否合法
private Move lastMove;// 当进行了一次移动操作后，lastMove指示这是前移而是后移
private IteratorForSequenceList() {
nextIndex = 0;
isRemoveOrSetLegal = false;//初始值为false，当调用了next()或previous()时被设置为true
lastMove = null;
}
public boolean hasNext() {
return nextIndex < size - 1;
}
public T next() {
if (hasNext()) {
lastMove = Move.NEXT;// 进行的是后移操作
isRemoveOrSetLegal = true;// 当next()调用了之后，才可以调用remove()或set()
return (T) elementData[nextIndex++];// 注意nextIndex的自增顺序
} else
throw new NoSuchElementException("Illegal call to next(),"
+ "迭代器位于表的最后端");
}
public boolean hasPrevious() {
return (nextIndex > 0) && (nextIndex <= size);
}
public T previous() {
if (hasPrevious()) {
lastMove = Move.PREVIOUS;// 进行的是前移操作
isRemoveOrSetLegal = true;
return (T) elementData[--nextIndex];// 注意nextIndex的自减顺序
} else
throw new NoSuchElementException("Illegal call to previous()"
+ "iterator is before beginning of list");
}
// 返回当前元素的索引
public int nextIndex() {
int result;
if (hasNext())
result = nextIndex + 1;
else
result = size;// 迭代超出顺序表的最后一个元素时返回顺序表中元素的个数
return result;
}
// 返回当前元素的前一个元素的索引
public int previousIndex() {
int result;
if (hasPrevious())
result = nextIndex - 1;
else
result = -1;// 迭代在顺序表的第一个元素时，返回-1
return result;
}
// 删除当前迭代的元素
public void remove() {
if (isRemoveOrSetLegal) {
isRemoveOrSetLegal = false;
if (lastMove.equals(Move.NEXT)) {
// next()被调用，但add() remove()没有被调用
SequenceListWithIterator.this.delete(nextIndex - 1);
nextIndex--;
} else if (lastMove.equals(Move.PREVIOUS)) {
SequenceListWithIterator.this.delete(nextIndex);
}
} else
throw new IllegalStateException(
"Illegal call to remove();"
+ "next() or previous() was not called, OR add() or remove() called since then");
}
// 更改当前迭代的元素
public void set(T e) {
if (isRemoveOrSetLegal) {
if (lastMove.equals(Move.NEXT))
// 使用内部类机制,内部类里面可以可以直接访问它外部类的底层数据
elementData[nextIndex - 1] = e;
else {
assert lastMove.equals(Move.PREVIOUS);
elementData[nextIndex] = e;
}
} else {
throw new IllegalStateException(
"Illegal call to set();"
+ "next() or previous() was not called, OR add() or remove() called since then");
}
}
// 在迭代器的当前元素之前添加一个元素,注意是之前
public void add(T e) {
// set 和 remove 操作只能是在迭代器访问过(跳跃过)某元素之后才能进行
isRemoveOrSetLegal = false; // 进行add操作之后，不能立即进行set() 或者 remove()
SequenceListWithIterator.this.insert(e, nextIndex++);
}
}
// 以默认的大小创建顺序表
public SequenceListWithIterator() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
// 以指定的大小创建顺序表
public SequenceListWithIterator(int initSize) {
capacity = 1;
while (capacity < initSize)
capacity <<= 1;// 将capacity设置成大于initSize的最小2次方
elementData = new Object[capacity];
}
public ListIterator<T> getIterator() {
return new IteratorForSequenceList();
}
// 获取顺序表中当前元素的个数
public int length() {
return size;
}
// 获取顺序表中索引为 i 处的元素，i表示索引，即以 0 开始
public T get(int i) {
if (i < 0 || i > size - 1)
throw new IndexOutOfBoundsException("顺序表索引越界");
return (T) elementData[i];
}
// 查看顺序表中指定元素的索引，若未找到，返回-1
public int locate(T element) {
for (int i = 0; i < size; i++)
if (elementData[i].equals(element))
return i;
return -1;
}
// 在顺序表的指定索引处插入一个元素
public void insert(T element, int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("顺序表索引越界");
ensureCapacity(size + 1);// 确保顺序表满时进行扩容，从而能插入元素
// 将指定索引后的所有元素向后移动一个位置
// System.arraycopy(elementData, index, elementData, index + 1, size -
// index);
for (int i = size; i > index; i--)
elementData[i] = elementData[i - 1];
elementData[index] = element;
size++;// 顺序表中的元素个数增1
}
private void ensureCapacity(int minCapacity) {
// 当数组容量已满时，对数组进行扩容。将容量扩展到大于minCapacity的最小2的次方
if (minCapacity > capacity) {
while (capacity < minCapacity)
capacity <<= 1;
elementData = Arrays.copyOf(elementData, capacity);
}
}
// 在顺序表的末尾添加一个元素
public void add(T element) {
insert(element, size);
}
// 删除顺序表中指定索引处的元素
public T delete(int index) {
if (index < 0 || index > size - 1)
throw new IndexOutOfBoundsException("顺序表索引越界");
T oldValue = (T) elementData[index];
int numMoved = size - index - 1;// 计算需要移动的元素个数
if (numMoved > 0) {
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
}
elementData[--size] = null;// 让垃圾回收器及时回收，避免内存泄露
return oldValue;
}
// 删除顺序表中的最后一个元素
public T remove() {
return delete(size - 1);
}
// 判断顺序表是否为空表
public boolean empty() {
return size == 0;
}
// 清空顺序表
public void clear() {
Arrays.fill(elementData, null);// 将数组elementData中的每个元素都赋值null
size = 0;
}
public String toString() {
if (size == 0)
return "[]";
else {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++)
sb.append(elementData[i].toString() + ", ");
int len = sb.length();
// 删除由于上面for循环中最后添加的多余的两个字符 (一个是逗号，一个是空格符号)
return sb.delete(len - 2, len).append("]").toString();
}
}
}
本文永久更新链接地址：
评论暂时关闭