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

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

1 酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造 2012年6月11日

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

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

4 「配列オブジェクト」と「オブジェクトの配列」は違う
オブジェクトと配列 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,…); // メソッド 「配列オブジェクト」と「オブジェクトの配列」は違う

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

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

7 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] ;

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

9 シンタックスシュガー 本来必要ではないがコーディングの効率化のために設けられている特別な文法 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”;

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

11 (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

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

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

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

15 配列の要素が尽きたかどうかの判定 目的のデータであるかどうかの判定 １つのデータを探すのに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回も判定

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

17 これが番兵 配列の要素が尽きたかどうかの判定 目的のデータであるかどうかの判定 を最後に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回だけにした

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