アルゴリズムa 第7回

循環リスト

先週は、「先頭から最後まで順にセルが次のセルを指す」『連結リスト』 図5.8(a) について説明しました。

『循環リスト』では「先頭から最後まで順にセルが次のセルを指す」のは 同じですが、さらに「最後のセルが先頭のセルを指して」います。

リストの頭を用意しておく方法は、headがnullを指す場合の特別の処理 をする心配がないので、プログラムが単純に書けるのが利点。 (最初の要素を挿入、最後の要素を削除、データが1個もない場合の探索、など)。

循環リストをたどる(ヘッダがない場合)
Cell ptr;
if (ptr != null) {
    Cell p = ptr;
    do {
        // 処理
        p = p.next;
    } while (p != ptr)
}

Cell ptr;
if (ptr != null) {
    Cell p = ptr;
    // 処理
    p = p.next;
    while (p != ptr) {
        // 処理
        p = p.next;
    }
}




循環リストをたどる(ヘッダがある場合)
Cell head;  // headがnullである場合を考慮しなくていいので記述が楽
for (Cell p = head.next; p!=head; p=p.next) {
    // 処理
}







アルゴリズムa 演習






課題提出〆切は次回の講義の開始時刻です。




課題7a





提出先

http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai7a

提出ファイルCircularLinkedList.java


コメント欄なし






「循環リスト」のクラスである CircularLinkedList.java を作成しなさい。






CircularLinkedList.java














いくつかのメソッドの本体の記述が省略されています。
自分で考えて、クラス定義を完成させて下さい。




課題7b





提出先

http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai7b

提出ファイルCircularLinkedListIterator.java


コメント欄: TestCLList.javaにTestCLList02.txtを入力として
与えたときの出力










CircularLinkedListIterator.java












testcllist.java












TestCLList01.txt
removeFirst
removeLast
length
addFirst a
addLast b
addFirst c
addLast d
show
length
addFirst e
addFirst f
addFirst g
addFirst h
addLast i
addLast j
length
addLast k
addLast l
addLast m
show
exit






TestCLList.javaの実行例
$ javac TestCLList.java CircularLinkedList.java CircularLinkedListIterator.java  
$ java TestCLList < TestCLList01.txt  
removeFirst null
removeLast null
0
[c a b d ]
4
10
[h g f e c a b d i j k l m ]






TestCLList02.txt
removeFirst
addLast a
show
removeLast
show
addFirst b
addFirst c
removeLast
removeFirst
addLast d
removeFirst
addLast e
addFirst f
addLast g
addLast h
removeFirst
removeFirst
addFirst i
removeLast
show
length
exit