アルゴリズムA 第6回


Cell

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

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

LinkedList

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


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

IntegerList.java
授業で配布するプリントを参照して下さい。
RunIntegerList.java
授業で配布するプリントを参照して下さい。
RunIntegerList.javaの実行例
sp204: ~/pro 4> javac RunIntegerList.java 
sp204: ~/pro 5> java RunIntegerist 
[]
[5 ]
[5 7 ]
[2 5 7 ]
[2 5 7 12 ]
[2 4 5 7 12 ]
sp204: ~/pro 6> 

イテレータ

教科書 p.129-p.135

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

メソッドの概要
 boolean hasNext()
          繰り返し処理でさらに要素がある場合に true を返します。
 Object next()
          繰り返し処理で次の要素を返します。
 void remove()
          基になるコレクションから、反復子によって最後に返された要素を削除します (任意のオペレーション)。
IntegerListIterator.java
授業で配布するプリントを参照して下さい。
RunIntegerListIterator.java
授業で配布するプリントを参照して下さい。
RunIntegerListIterator.javaの実行例
sp204: ~/pro 4> javac RunIntegerListIterator.java 
sp204: ~/pro 5> java RunIntegerListIterator 
[3 15 18 20 37 ]
---------------
1番目の要素:3
2番目の要素:15
3番目の要素:18
4番目の要素:20
5番目の要素:37
sp204: ~/pro 6> 


アルゴリズム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の実行例
% javac CellStack.java RunCellStack.java 
% java RunCellStack 
CellStack=[c b a ]
pop: c
CellStack=[b a ]
CellStack=[f e d b a ]
pop: f
pop: e
pop: d
pop: b
pop: a
CellStack=[]
% 

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

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

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

CellQueue.java
public class CellQueue {
    MyLinkedList list;
    public CellQueue() { list = new MyLinkedList(); }	// コンストラクタ
    public void enqueue(Object x) {
	// 自分で考えて書きましょう
    }
    public Object dequeue() {
	if (isEmpty()) throw new RuntimeException("queue underflow");
	// 自分で考えて書きましょう
    }
    public boolean isEmpty() { return list.isEmpyt(); } // 空かどうか?
    public String toString() {	// 文字列変換
	return "CellQueue=" + list;
    }
}
RunCellQueue.java
授業で配布するプリントを参照して下さい。
RunCellQueue.javaの実行例
% javac CellQueue.java RunCellQueue.java 
% java RunCellQueue 
CellQueue=[c b a ]
dequeue: a
CellQueue=[f e d c b ]
dequeue: b
dequeue: c
dequeue: d
dequeue: e
dequeue: f
CellQueue=[]
%