酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年6月13日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html

値型と参照型 値型 参照型 値が定義したところに存在する 値が別に存在し、それへの参照が定義される JavaやＣ言語の基本型の変数 Ｃ言語では構造型変数(構造体)も値型 参照型 値が別に存在し、それへの参照が定義される Javaのオブジェクトはすべて参照型 newで得られる値は、実体への参照 Ｃ言語では参照型を明示的に定義できる これがいわゆるポインタで、参照する演算子が単項の＊ 値型の参照を得る演算子が単項の＆ Ｃ言語の関数や配列は参照型 名前はそれへの参照を表す

データ型 基本型, primitive type 構造型, structured type byte, word, dword, qword, tbyte void, char, int, float, double boolean, byte, int, double 構造型, structured type section(?) struct, union class

「配列オブジェクト」と「オブジェクトの配列」は違う オブジェクトと配列 Object certainObject = new Object(); // オブジェクト生成 int[] intarray = new int[100]; // 基本型intの配列の定義 Object[] objects = new Object[100]; // 配列オブジェクトの定義 objects[i-1] = new Object(); // オブジェクトを定義→配列要素 objects[i-1].method_name(arguments,…); // メソッド 「配列オブジェクト」と「オブジェクトの配列」は違う

オブジェクトと参照 1. オブジェクト変数の宣言 オブジェクト変数 メモリ領域 オブジェクト変数 オブジェクト 参照情報 メモリ領域 2. オブジェクトの生成（new） オブジェクト領域 3. オブジェクトの初期化 オブジェクト変数 オブジェクト 参照情報 メモリ領域 オブジェクト領域 初期化

この段階ではオブジェクトの配列ができてない 配列オブジェクト 配列要素となるオブジェクトの定義 配列オブジェクトの宣言 メモリ領域 配列オブジェクト変数 オブジェクト領域 オブジェクト 参照情報 初期化 オブジェクト 参照情報 初期化 オブジェクト 参照情報 初期化 オブジェクト 参照情報 初期化 この段階ではオブジェクトの配列ができてない

Javaにおける多次元配列 Javaにおける多次元配列は、 配列オブジェクトの配列である // 2次元配列 Object[][] array2D = new Object[3][2]; // 3次元配列 Object[][][] array3D = new Object[4][3][2]; // 1次元配列の配列として表される Object[][] array2D = new Object[3][]; array2D[0] = new Object[2]; array2D[1] = new Object[2]; array2D[2] = new Object[2]; // 2次元配列の配列として表される Object[][][] array3D = new Object[4][][]; array3D[0] = new Object[3][2]; array3D[1] = new Object[3][2]; array3D[2] = new Object[3][2]; array3D[3] = new Object[3][2]; Javaにおける多次元配列は、 配列オブジェクトの配列である /* 参考: 1次元配列の配列としてC言語で定義(Javaの2次元配列に近い) */ Object *array2D[3] ; array2D[0] = malloc(2*sizeof(Object)); array2D[1] = malloc(2*sizeof(Object)); array2D[2] = malloc(2*sizeof(Object)); /* 参考: C言語での2次元配列の定義(Javaと全く違う!) */ Object array2D[3][2] ;

2次元配列 メモリ領域 配列オブジェクト変数 配列オブジェクト達… オブジェクト 参照情報 オブジェクト 参照情報 オブジェクト 参照情報

シンタックスシュガー 本来必要ではないがコーディングの効率化のために設けられている特別な文法 array[1][3]; ((Object[])(array[1]))[3]; String[] string = new String[]{“a”, “b”, “c”}; String[] string = new String[3]; string[0] = “a”; string[1] = “b”; string[2] = “c”;

Javaの配列 Javaにはポインタが陽に説明されていない… 「～への参照」という形でポインタの存在が見える 配列オブジェクト 配列オブジェクト変数 length: 配列の大きさ 配列本体へのポインタ Javaの配列 Javaにはポインタが陽に説明されていない… 「～への参照」という形でポインタの存在が見える NullPointerExceptionでも存在がわかる 配列オブジェクト変数 [実はポインタ変数] 配列オブジェクト 配列オブジェクト 配列オブジェクト変数 [実はポインタ変数] 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ 配列オブジェクト 配列オブジェクト変数 [実はポインタ変数] 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ length: 配列の大きさ 配列オブジェクト 配列オブジェクト変数 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ 配列本体へのポインタ 配列本体 [メモリ上の領域]

(n-1)*m+(m-1)は、展開してn*m-m+m-1、簡単にしてn*m-1 Cの配列 行と列それぞれをインデックスで指し示す Ｃコンパイラはそれをオフセットに変換する １　　　　　　２　　　　　　３　　　　　・・・　　　　　ｍ 配列名 １　 ２　　３　　４　 ・・・・　 ｎ 1 2 ・・・・・・・ m-1 m m+1 m+2 ・・・・・・・ 2*m-1 （３，２） 添え字を 用いて データに アクセス 2*m 2*m+1 ・・・・・・・・・・・・ 3*m ・・・・・ n*m-1 (n-1)*m (n-1)*m+1 ・・・・・・・・・・・・・・・・ (n-1)*m+(m-1)は、展開してn*m-m+m-1、簡単にしてn*m-1

配列上の探索 添え字を用いて 直接アクセス 先頭から 順に調べる

配列上の探索 半分ずつ調べます 1)半分に分ける 2)前半に存在するか調べる 前半にあれば前半について探索 後半にあれば後半について探索 ※探索のためにデータの整列が必要

配列上の探索 添え字を用いて 直接アクセス 先頭から 順に調べる 直接探索　　　　　　　　　　　　線形探索

配列の要素が尽きたかどうかの判定 目的のデータであるかどうかの判定 １つのデータを探すのに2回も判定 public class Array { public Array(int aMaxSize) this.array = new String[aMaxSize]; this.number = 0; } public int search(String aTarget) for(int count = 0; count < this.number; count++){ if(aTarget.equals(this.array[count])){ return count + 1; return -1; private String[] array; private int number; 配列の要素が尽きたかどうかの判定 目的のデータであるかどうかの判定 １つのデータを探すのに2回も判定

番兵 計算量は減らないが、実行時間は減る アルゴリズムではなくテクニックのひとつ 線形探索では番兵を最後尾に置く 線形探索における番兵では、探索したいデータと等しい値のデータを用いることが多い 探索は目的のデータか番兵いずれかの発見で終了 探索対象が無くなったかどうかの判定が不要になる 番兵は最も後に探索され、そして必ず一致する

これが番兵 配列の要素が尽きたかどうかの判定 目的のデータであるかどうかの判定 を最後に1回だけにした public class Array { public Array(int aMaxSize) this.array = new String[aMaxSize+1]; this.number = 0; } public int search(String aTarget) int count=0; this.array[this.number] = aTarget; while( !aTarget.equals(this.array[count]) ){ count++; if(count != this.number){ return count + 1; return -1; private String[] array; private int number; これが番兵 配列の要素が尽きたかどうかの判定 目的のデータであるかどうかの判定 を最後に1回だけにした

自己再構成リスト LRUの実装などに使える 先頭 前 次 データ 次 データ 次 データ 次 データ 次 データ 探索対象 先頭 前 次 探索対象を先頭に寄せる