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

第0回

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

第1回

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

第2回

変数の取扱い

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

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

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

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

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

第3回

クラスの中に入るもの

  1. フィールド
  2. コンストラクタ
  3. toString
  4. Setter
  5. Getter
  6. 一般のメソッド
  7. static なメソッド
  8. static なフィールド

継承

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

Generics

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

その他小技

  1. protected 指定は継承はさせるけど、外部からは見せない指定
  2. super は親クラスを表す。super.メソッド名などとして使う。
  3. super() は親クラスのコンストラクタを表す。 各コンストラクタで super を省略すると super() が暗黙で挿入される
  4. オーバーライドするメソッドには@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 以降に列挙する。

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

  1. 例外に対処しない場合はその使用するメソッドも同じ throws 宣言をする。 例外が発生したら、そこで処理が中断され、メソッドを使用しているメソッド に例外が伝えられる
  2. 例外に対処する場合は 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 クラス 分析法がある。 他に、デザインパターンと呼ばれる特定の状況で使用する定石がある。

定石の例

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

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

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

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

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

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科