歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

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();
        }
    }

}

Copyright © Linux教程網 All Rights Reserved