CS61B資料結構及演算法筆記:(八)迭代

Evan
Apr 3, 2022

--

集(set)是繼列表(list)之後要介紹的資料結構,不一樣的是,集這個抽象的資料結構有兩個與列表不同的特性

  1. 每個在集內存放的資料沒有順序之分
  2. 每個在集內存放的資料唯一

集可以直接使用 Java 內建各種實現集的類別,常見如 HashSet 等,或是和前幾章實現 List61B 一樣,自行建立一個類別,實作所有方法,接下來以陣列為基底的 ArraySet 實現三個操作集常用的方法:contains()、add()、size() 如下

其中在方法 add 中可以發現我們加入了一項錯誤判斷式

throw new IllegalArgumentException();

這是當想要對集加入 null 時,Java 會彈出例外錯誤的語法,原因是加入 null 的集在呼叫 contains() 時,會出現 null 無法使用方法 equal() 而出現錯誤,為了這項例外錯誤的預防措施。

foreach 語法

在實作方法 contains() 中可以發現在 for 迴圈使用變數 i 紀錄陣列中的位置,確認每一個陣列內的資料是否與輸入的參數相等,不過 Java 支援另一種不需要紀錄陣列位置的語法:foreach,能直接列舉該陣列,或是任一繼承接口 Iterable 的類別。

foreach(T item : items){}

當對繼承接口 Iterable 的實例物件 items 使用 foreach 的語法時,Java 編譯器實際上會代為執行如下程式碼

Iterator<T> seer = items.iterator();
while(seet.hasNext()){
seer.next()
}

任何繼承接口 Iterable 的類別都必須完成一個可以回傳迭代器(itertaor)的方法 iterator()。

Iterator<T> iterator();

而該迭代器又必須擁有兩個可以被呼叫的方法

  1. hasNext()
    檢查目前位置是否有值,並回傳布林值
  2. next()
    回傳目前位置之值,並指向下一個位置
boolean hasNext();
E next();

因此,為了強制任一迭代器都必須要實現這兩個方法,同樣利用接口的特性以控制每一個繼承接口 Iterator 的類別,都要完成 hasNext() 和 next()。

總了言之,要對一個類別使用 foreach 的語法,該類別必須先繼承 Iterable 接口,清楚地告訴 Java,所有子類別都將實現方法 iterator(),該方法會回傳一個迭代器,其擁有兩個方法 hasNext() 及 next() 以迭代整個類別。

舉例來說,如果想要對 ArraySet 使用 foreach 語法以迭代所有的內容,繼承 Java 內建的兩個接口 Iterable 及 Iterator 如下所示:

從上述程式碼可以發現

  1. 繼承接口 iterator 的類別 ArraySetIterator 為 ArraySet 的巢狀類別。
  2. 類別 ArraySetIterator 內存在一個私有變數 wizPosition 以紀錄迭代器在迭代陣列 items 時,方法 next() 及 hasNext()追蹤在陣列中的位置。
    如圖一所示,當 wisPosition = 0 時,藉由和 size 比較大小確認該陣列位置是否有值,如果回傳 true 則回傳 item[0] 並將 wisPostion 移動到下一個陣列中的位置,直到迭代完整個陣列為止。
圖一

--

--