アルゴリズムA 第4回


基本的なデータ構造

リスト

「リスト(list)」というデータ構造は、通常、次のような構造を表します。


しかし、教科書では、上記の構造を「連結リスト」と呼び、 「リスト」という語を「データを線形に並べたもの」とか「一覧表」 などという意味で使用しているようです。混乱しないように注意して下さい。

リストに対する操作

項番操作
1k番目の要素の前に要素を挿入する
2k番目の要素を削除する
3k番目の要素の内容を読む/書く
4特定のキーを持つ要素を探索する
5複数のリストを1つにまとめる
61つのリストを複数のリストに分割する
7リストの複製を作る
8リストに含まれる要素の個数を求める

配列による実現

リストを配列で実現した場合を考えます。
    int[] x = new int[データの最大個数];

k番目に要素を挿入するには、それよりも後ろの要素を全て 1ずつずらしてコピーする必要があります。 要素の個数がn個だとすると、ずらすべき要素の個数は平均で n/2 となるので、要素を1個挿入するための計算量はO(n) です。

k番目の要素を削除するための計算量も、同様にO(n)と なります。

k番目の要素を読み書き(アクセス)するには k[i] でいいので、計算量はO(1)となります。

結論として、リストへの要素の挿入や削除が多く発生する場合、 配列は適切な実現方法ではないことになります。


スタック

「挿入と削除がリストの先頭のみで行われるもの」が「スタック (stack)」です。

スタックでは、リストの先頭をtop, 最後をbottomと呼びます。 「topにデータを挿入すること」を push, 「topからデータを取り出すこと」を popと呼びます。

「最初に挿入されたデータが最後に取り出される」ために "First In, Last Out" と呼ぶことがあります。 もちろん、逆の見方をすれば 「最後に挿入されたデータが最初に取り出される」ことになるので "Last In, First Out" とも言います。

MyStack.java
授業で配布するプリントを参照して下さい。
RunMyStack.java
授業で配布するプリントを参照して下さい。
RunMyStack.javaの実行例
sp204: ~/pro 4> javac RunMyStack.java 
sp204: ~/pro 5> java RunMyStack 
[a b c ]
pop: c
[a b ]
[a b d e f ]
pop: f
pop: e
pop: d
pop: b
pop: a
[]

逆ポーランド記法

式 (ab) ×(cd) を括弧を使わずに読み上げてみましょう。 もし、「a 足すb かける c 引く d」 と読み上げると ab×cd との区別がつかなくなってしまいます。 このような場合は、「演算子をデータの後から読み上げる」 方法を取るとうまくいきます。 つまり 「abを足したもの に cからdを引いたものを掛けたもの」 と表現すると括弧を使わずにうまく表現できます。

このような、「データを先に書いて、演算子を後に書く方法」を、 『後置記法 (postfix notation)』とか『逆ポーランド記法 (reverse polish notation)』などと呼びます。 逆ポーランド記法を用いると、上記の例は 「a bc d − ×」 と表現されます。 式を表すのに括弧が不要なので「演算式の処理が簡単である」 という利点が逆ポーランド記法にはあります。

ちなみに、 式 (ab) ×(cd) のような通常の記法を挿入記法 (infix notation)と呼びます。

逆ポーランド記法で表現された式を処理するときは

という動作を行います。

例として (3 + 5) * (7 - 1) という式が逆ポーランド記法で 表されたときに、スタックを使ってどのように処理できるか 見てみましょう。

挿入記法:              (3 + 5) * (7 - 1)
逆ポーランド記法:      3 5 + 7 1 - *
スタックの様子
bottom ... top
入力備考
初期状態
33データをスタックにpush
3 55データをスタックにpush
8+2個popして演算し結果をスタックにpush
8 77データをスタックにpush
8 7 11データをスタックにpush
8 6-2個popして演算し結果をスタックにpush
48*2個popして演算し結果をスタックにpush
48最後にスタック上に1個残ったデータが演算結果
Calculator.java
授業で配布するプリントを参照して下さい。
Calculator.javaの実行例
sp204: ~/pro 4> javac Calculator.java 
sp204: ~/pro 5> java Calculator 
3 5 + 7 1 - * 
答は48です。
6 3 - 2 5 + 8 4 - - * 
答は9です。
Ctl-D   ←入力行の先頭でコントロールキーとDを同時に押すと入力終了。
sp204: ~/pro 6> java Calculator 
2 3 5 + 
入力された式が不正です。
2 3 + 5 - * 
Exception in thread "main" java.lang.RuntimeException: stack underflow
	at MyStack.pop(MyStack.java:17)
	at Calculator.pop(Calculator.java:8)
	at Calculator.main(Calculator.java:30)


アルゴリズムA 演習


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

課題4a

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai4a
提出ファイルCalculator.java
コメント欄以下の3種類データに対する出力結果

Calculator.java を次のデータに対して動作させて下さい (注意: Calculator.javaの実行にはMyStack.javaも必要です)。

[データ1]
73  26  *  5  10  +  27  103  19  -  *  -  -
[データ2]
21  17  5  203  32  -  2  3  5  *  *  +  -  -  108  9  /  +
[データ3]
21  17  5  203  32  -  2  3  5  *  *  +  -  -  108  9  /  -  +

課題4b

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai4b
提出ファイルCalculator2.java
コメント欄実行したときの出力結果

課題4aで作成した Calculator.java を参考にして、 実数を扱えるようにしたCalculator2.javaを作成しなさい。 すべての計算は実数で行えばよいものとします。

コメント欄には実行結果を貼り付けておいて下さい。

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