アルゴリズム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