アルゴリズムa 第6回

Cell

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

Cell.java

LinkedList

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

• シーケンシャルアクセスしかできない。 データのアクセスにO(n/2)の手間が必要。
• 次のデータを指すためのメモリを必要とする。
• データの挿入・削除が簡単。

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

IntegerList.java

RunIntegerList.java

$ javac RunIntegerList.java 
$ java RunIntegerist 
[]
[5 ]
[5 7 ]
[2 5 7 ]
[2 5 7 12 ]
[2 4 5 7 12 ]
$ 

イテレータ

教科書 p.129-p.135

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

• JavaのIteratorインターフェイスを実装する

  
      public class クラス名  implements Iterator { ... }
  

• 次の3種類のメソッドを実装する。

IntegerListIterator.java

RunIntegerListIterator.java

$ javac RunIntegerListIterator.java 
$ java RunIntegerListIterator 
[3 15 18 20 37 ]
---------------
1番目の要素:3
2番目の要素:15
3番目の要素:18
4番目の要素:20
5番目の要素:37
$ 

アルゴリズムA 演習

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

課題6a: 連結リスト

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

MyLinkedList.java

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

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

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

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

• void push(Object)
• Object pop()

CellStack.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をリストで実装してみよう

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

CellQueue.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=[]
$