アルゴリズムA 第6回


Cell

「セル」とは「リスト」の中で1個ずつのデータを保持しているデータ構造です。 「データを1個保持する場所」と、「次のセルへの参照」を含んでいます。

Cell.java
授業で配布するプリントを参照して下さい。

LinkedList

セルがつながった構造を「リスト」(list)または「連結リスト」(Linked List) と呼びます。


教科書の MyLinkedList.java は、整数(int を Integerに変えて)を 小さい順にリストに保持するプログラムです。 授業では別の機能を持つクラスをMyLinkedListクラスとして作成しますので、 ここではその名前を IntegerList.java と変更して掲載しています。

IntegerList.java
授業で配布するプリントを参照して下さい。
RunIntegerList.java
授業で配布するプリントを参照して下さい。
RunIntegerList.javaの実行例
授業で配布するプリントを参照して下さい。

イテレータ

教科書 p.129-p.135

イテレータ(iterator)は「繰り返し」を抽象化するための道具です。 特定のクラスの実装を外部に見せないようにするのに役立ちます。

メソッドの概要
 boolean hasNext()
          繰り返し処理でさらに要素がある場合に true を返します。
 Object next()
          繰り返し処理で次の要素を返します。
 void remove()
          基になるコレクションから、反復子によって最後に返された要素を削除します (任意のオペレーション)。
IntegerListIterator.java
授業で配布するプリントを参照して下さい。
RunIntegerListIterator.java
授業で配布するプリントを参照して下さい。
RunIntegerListIterator.javaの実行例
授業で配布するプリントを参照して下さい。


アルゴリズムA 演習


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

課題6a: 連結リスト

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai6a
提出ファイルMyLinkedList.java
コメント欄なし

「連結リスト」のクラスである MyLinkedList.java を作成しなさい。

MyLinkedList.java
授業で配布するプリントを参照して下さい。

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

課題6b: Stackをリストで実装してみよう

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai6b
提出ファイルCellStack.java
コメント欄なし

一方向の連結リストを内部表現として用いて、スタックを表現する Java のプログラムを作成してみましょう。

Cellクラスをつかってスタックを実現したのが CellStackクラスです。 CellStack.java のメソッド定義のうち

の定義の一部が省略されています。 これらの定義を自分で書いて下さい。

CellStack.java
授業で配布するプリントを参照して下さい。
RunCellStack.java
授業で配布するプリントを参照して下さい。
RunCellStack.javaの実行例
授業で配布するプリントを参照して下さい。

課題6c: Queueをリストで実装してみよう

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai6c
提出ファイルCellQueue.java
コメント欄なし

一方向の連結リストを内部表現として用いて、キューを表現する Java のプログラムを作成してみましょう。

CellQueue.java
授業で配布するプリントを参照して下さい。
RunCellQueue.java
授業で配布するプリントを参照して下さい。
RunCellQueue.javaの実行例
授業で配布するプリントを参照して下さい。