数据结构(八) -- 迭代器

一，迭代器

在对向量、列表和序列进行处理（比如，查找某一特定的元素）时，一种典型的操作就是依次访问或修改其中的各个元素。迭代器是软件设计的一种模式，它是对** “逐一访问所有元素” **这类操作的抽象。

迭代器本身也是一个序列S，在任何时候，迭代器中都有唯一的当前元素。迭代器还必须提供某种机制，使得我们可以不断转向S中的下一元素，并将其置为新的当前元素。与前面所介绍的** 位置ADT 相比，迭代器是对前者的扩展与推广。 实际上，一个位置本身已经可以被看作是一个迭代器了，只不过它还不能不断更新。 ** 总之，所谓迭代器，就是对一组对象之间的位置、直接后继等关系的集成。

---

二，迭代器ADT(AbstractDataType)

操作方法	功能描述
hasNext()	检查迭代器中是否还有剩余的元素 输入：无 输出：布尔标志
getNext()	返回迭代器中的下一元素 输入：无 输出：对象

---

三，基于列表实现的迭代器

接口：

package dsa.Iterator;

/*
 * 迭代器ADT接口
 */
public interface Iterator {
    boolean hasNext();// 检查迭代器中是否还有剩余的元素

    Object getNext();// 返回迭代器中的下一元素
}

异常：

package dsa.Iterator;

public class ExceptionNoSuchElement extends RuntimeException {

    public ExceptionNoSuchElement(String err) {
        super(err);
    }

}

• 基于列表实现的位置迭代器：

package dsa.Iterator;

import dsa.List.List;
import other.Position;

/*
 * 基于列表实现的位置迭代器
 */
public class IteratorPosition implements Iterator {
    private List list;// 列表
    private Position nextPosition;// 当前（下一个）位置
    // 默认构造方法

    public IteratorPosition() {
        list = null;
    }

    // 构造方法
    public IteratorPosition(List L) {
        list = L;
        if (list.isEmpty())// 若列表为空，则
            nextPosition = null;// 当前位置置空
        else
            // 否则
            nextPosition = list.first();// 从第一个位置开始
    }

    // 检查迭代器中是否还有剩余的位置
    public boolean hasNext() {
        return (nextPosition != null);
    }

    // 返回迭代器中的下一位置
    public Object getNext() throws ExceptionNoSuchElement {
        if (!hasNext())
            throw new ExceptionNoSuchElement("意外：没有下一位置");
        Position currentPosition = nextPosition;
        if (currentPosition == list.last())// 若已到达尾位置，则
            nextPosition = null;// 不再有下一个位置
        else
            // 否则
            nextPosition = list.getNext(currentPosition);// 转向下一位置
        return currentPosition;
    }
}

• 基于列表实现的元素迭代器：

package dsa.Iterator;

import other.Position;
import dsa.List.List;

/*
 * 基于列表实现的元素迭代器
 */
public class IteratorElement implements Iterator {
    private List list;// 列表
    private Position nextPosition;// 当前（下一个）元素的位置

    // 默认构造方法

    public IteratorElement() {
        list = null;
    }

    // 构造方法
    public IteratorElement(List L) {
        list = L;
        if (list.isEmpty())// 若列表为空，则
            nextPosition = null;// 当前元素置空
        else
            // 否则
            nextPosition = list.first();// 从第一个元素开始
    }

    // 检查迭代器中是否还有剩余的元素
    public boolean hasNext() {
        return (null != nextPosition);
    }

    // 返回迭代器中的下一元素
    public Object getNext() throws ExceptionNoSuchElement {
        if (!hasNext())
            throw new ExceptionNoSuchElement("意外：没有下一元素");
        Position currentPosition = nextPosition;
        if (currentPosition == list.last())// 若已到达尾元素，则
            nextPosition = null;// 不再有下一元素
        else
            // 否则
            nextPosition = list.getNext(currentPosition);// 转向下一元素
        return currentPosition.getElem();
    }

}