EC科データ構造とアルゴリズム I 要点

第0回

Oracle の Java 7 SE の JDK をインストールすること
Eclipse をインストールすること
予習復習でプログラムを作って動かすこと

第1回

プログラムの意味のある部分を切り出して、関数にしましょう。その時、関数名は何をするかが分かるように付けてください。
public static void main メソッドから関数を切り出すときは、 private static を頭に付けてください。

第2回

変数の取扱い

C言語の変数は原則として、データを入れる箱に名前がついているものだと思って下さい。特に構造体は複数のデータを入れられる箱です。構造体で代入や比較をすると、各メンバーすべてに対してデータのコピーや比較が行われます。但し、ポインター型にはデータが入りません。ポインター型の変数は他の変数の箱の位置情報のみが入ります。配列型はポインター型の変形です。宣言すると、指定した量のデータを入れる箱を連続領域で確保した後、配列変数にはその位置情報が入ります。

Javaは型により変数の取扱いが異なります。

基本型(プリミティヴ型)はC言語と同様にデータを入れる箱に名前をつけます。
一方、オブジェクト型はC言語のポインタ型に対応します。つまり、オブジェクト型の変数宣言ではオブジェクトの位置情報のみしか扱えません。オブジェクト型のデータを格納するには、コンストラクタを起動するなどして、オブジェクトを生成する必要があります。
配列はオブジェクトに近い動きになります。変数宣言では領域は確保されません。 new double[3] などにより配列を作成し、位置情報を配列に入れます。配列の長さは length フィールドにより取り出せます。 foreach 構文が使用できます。

オブジェクト指向プログラミングの基礎

いくつかのメソッドで共通の引数が複数ある場合、その引数をフィールドにしたクラスを作成する
コンストラクタと toString を作成する
メソッドをそのクラスに移動する

第3回

クラスの中に入るもの

フィールド
コンストラクタ
toString
Setter
Getter
一般のメソッド
static なメソッド
static なフィールド

継承

既存のクラス A に対して、新たなクラス B がクラス宣言で extends A を指定するとクラス A 内の private メンバーとコンストラクタ以外は全て引き継げる。
親クラスで定義されているメソッドを子クラスで再定義できる(Override)
親クラスの変数で子クラスのオブジェクトを参照できる。 Override されているメソッドは、子クラスのものが実行される。
親クラスにおいて、継承してオーバライドして使うためのメソッドを abstract 宣言することで、実装を省略でき、子クラスに実装を強要できる。 abstract 宣言されたメソッドがあるクラスは abstract 宣言が必要。 abstract クラスのオブジェクトは作れないが、変数は作れる。
abstract クラス内の全てのメソッドが abstract である場合、 interface 宣言ができる。 interface は定義のみを継承し、実装は全く引き継がれない。そのため、extends ではなく implements で指定する。

Generics

型を引数としたクラスやメソッドを作る方法がある。

その他小技

protected 指定は継承はさせるけど、外部からは見せない指定
super は親クラスを表す。super.メソッド名などとして使う。
super() は親クラスのコンストラクタを表す。各コンストラクタで super を省略すると super() が暗黙で挿入される
オーバーライドするメソッドには@Override を指定すると、オーバーライドを失敗したときコンパイラが教えてくれる

第4回

計算量

プログラムの実行速度を比較するには、任意の入力の長さ n に対する実行時間の関数を考え、オーダーを比較する。

例外

プログラムの通常処理と異常処理

異常処理が必ず起きる（ファイルが終了するなど）: 必ずチェックして、起きたときの対処も通常処理の範囲内として行う
想定内の異常処理が起きる(ファイルがないなど): 主たる処理から分岐して、専用の異常への対処
対処不能な異常の発生(メモリーフルなど): 対処せずにプログラムを異常終了させる(検知した異常を知らせる程度はしても良い)

Exception

Java では通知可能な異常情報として例外Exceptionという概念がある。 java.lang.Exception のサブクラスのオブジェクトで例外情報を取り扱う。

throw new SomeException();

SomeException(Exception のサブクラス)を発生。通常の処理を中断し、例外処理に移行する

try catch

次の構文で使う


try{
    例外が発生する可能性のある処理
}catch(例外1の型 e){
  例外1が発生したときの処理
}catch(例外2の型 e){
  例外2が発生したときの処理
}

int foo(int baz) throws SomeException { ... }

メソッド定義において、メソッドが例外を発生する可能性がある場合には、メソッドの定義に必ず発生する例外を throws 以降に列挙する。

例外が発生する可能性があるメソッドを使用する場合、次のどちらかの対処をする必要がある。

例外に対処しない場合はその使用するメソッドも同じ throws 宣言をする。例外が発生したら、そこで処理が中断され、メソッドを使用しているメソッドに例外が伝えられる
例外に対処する場合は try catch で適切な処理を行う

よく使うクラスライブラリ

文字列: 不変: java.lang.String, 可変: java.lang.StringBuilder
ラッパークラス: java.lang.Integer, java.lang.Double など
ファイル: ファイルそのもの java.io.File, 入力バイト列 java.io.InputStream, 入力文字列 java.io.Reader, 一行ずつ読める形式 java.io.BufferedReader
コレクション: 配列の代替となるデータ構造: java.util.ArrayList, ランダムアクセスをせずに挿入、削除を多用する場合は java.util.LinkedList, 唯一性を保つ集まり java.util.HashSet, 唯一性を持ち、整列している java.util.TreeSet
マップ: キーバリュー形式(鍵と値)のデータ構造を持ち、鍵で値を検索できるもの。高速性 java.util.HashMap, 鍵順に整列できる java.util.TreeMap

第5回

JUnit

JUnitは、Java のプログラムを自動テストするツール。 Eclipse に標準装備されている。 assertEquals(期待値, 式) と言う構文で式の値をチェックするプログラムを作成する。アジャイル開発では、テストプログラムを先に作成してからプログラムを作成する。

クラスの作成法

クラスの作成法は出来上がったプログラムを手直ししながらクラスを作るリファクタリングの他に、自然言語で作成された仕様書を分析して作る CRC クラス分析法がある。他に、デザインパターンと呼ばれる特定の状況で使用する定石がある。

定石の例

オブジェクトの集まりをクラスとする
イテレータ

第6回

クラス間の関係が is-a 関係なら継承し、 has-a 関係ならコンポジションを行う。

他のオブジェクトを参照しているオブジェクトを単純にコピーすると、参照のみがコピーされて、参照されているオブジェクトまでコピーされない。これをシャローコピーと呼ぶ。すべてをコピーするのをディープコピーと呼ぶ。

オブジェクトをコピーするにはコピーコンストラクタを使うか、 clone メソッドを使用する。

プロトタイプデザインパターンは、作成が複雑なオブジェクトは毎回生成せずにコピーして使用するデザインパターンである。

比較

equals はオブジェクトが等価であるかどうかを調べるメソッドで、 java.lang.Object に既に実装されている。

hashCode はオブジェクトに対して 32bit の整数を割り当てるもので、equals が成り立つオブジェクト同士は同じ値を出す必要がある。

java.lang.Comparable インターフェイスは compareTo という順序関係を与えるメソッド持つ。 compareTo が 0 になるのと equals が true になるのが必要十分である時に一貫性があると言う。

第7回

ポリモーフィズム

オブジェクトを親クラスの変数で参照できる。親クラスのメソッドが子クラスで実装されているとき、親クラスの変数から参照されていても子クラスのメソッドが起動される。これをポリモーフィズムと言う。

ポリモーフィズムして使用するメソッドは親クラスで実装する必要はない。そのため、親クラスで abstract 宣言すると親クラスで実装を省略でき、子クラスでの実装を強制できる。

テンプレートデザインパターン

親クラスで abstract 宣言したメソッドの値をするメソッドを作ると、子クラスでabstract宣言されたメソッドをオーバライドすることにより親クラスのメソッドの動作を変えることができる。これをテンプレートデザインパターンという。子クラスで文字列の差し替えなどを行うのに便利である。

ストラテジデザインパターン

メソッドを一つだけ宣言したインタフェースに対して、その変数のフィールドを持たせ、外部からオブジェクトを与える。そして、そのフィールドからメソッドを呼び出すようなメソッドを作成する。すると、そのメソッド自体をインタフェースを実装したオブジェクトを与えることでコントロールできる。これをストラテジデザインパターンという。

並べ替えアルゴリズムを実装しておき、比較のメソッドだけをインタフェースのフィールド変数から呼び出すようにしておくと、任意のオブジェクトの比較方法を後から与えることができるようになる。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科