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

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

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

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

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

4 配列（２７ページ） 添え字とデータが1対1で対応 添え字は連続 データの挿入や削除は面倒 同じ大きさの要素が並ぶ 配列は固定長
2 3 4 n … 添え字とデータが1対1で対応 添え字は連続 添え字が１から始まるとは限らない データの挿入や削除は面倒 同じ大きさの要素が並ぶ 配列は固定長 オブジェクトの配列もありうる… 添え字を用いてアクセスする（例では３）

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

6 public class Array { private Array() } public Array(int aMaxSize) this.array = new String[aMaxSize]; this.number = 0; public boolean add(String aString) if(this.array.length <= this.number){ return false; this.array[this.number] = aString; ++this.number; return true; private String[] array; private int number;

7 配列へデータの挿入 P-1 p P+1 P+2 P+3 n n+1 ・・・・ ｐ番目にデータを挿入 隙間を空けて 突っ込みます

8 public boolean insert(int aPosition, String aString)
{ if((1 > aPosition) || (aPosition > this.number + 1)){ return false; } if(this.array.length == this.number){ for(int count = this.number - 1; count >= aPosition - 1; count--){ this.array[count + 1] = this.array[count]; this.number++; this.array[aPosition - 1] = aString; return true; public String get(int aPosition) return this.array[aPosition - 1];

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

10 public int search(String aTarget)
{ for(int count = 0; count < this.number; count++){ if(aTarget.equals(this.array[count])){ return count + 1; } return -1; public int binarySearch(String aTarget) { int low = 0; int high = this.number - 1; int center; while(true){ center = (low + high)/2; if(aTarget.equals(this.array[center])){ return center + 1; } if(low > high){ return -1; if(0 > this.array[center].compareTo(aTarget)){ low = center + 1; }else{ high = center - 1;

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

12 配列からデータの削除 P-1 p P+1 P+2 P+3 n n+1 ・・・・ 削除してできた 隙間を詰めます ｐ番目の データを削除

13 public boolean remove(String aTarget)
{ int position = this.search(aTarget); if(position < 0){ return false; } for(int count = position - 1; count < this.number; count++){ this.array[count] = this.array[count + 1]; --this.number; this.array[this.number] = null; return true; public void printAll() for(int count = 0; count < this.number; count++){ System.out.println(count "\t" + this.array[count]); System.out.println();

14 二次元配列 行と列それぞれをインデックスで指し示す １ ２ ３ ・・・ ｍ ・・・・・・・ １ ２ ３ ４ ・・・・ ｎ （３，２）
１　　　　　　２　　　　　　３　　　　　・・・　　　　　ｍ １　 ２　　３　　４　 ・・・・　 ｎ ・・・・・・・・・・・・ ・・・・・ ・・・・・・・・・・・・・・・・ ・・・・・・・ （３，２） 添え字を 用いて データに アクセス

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

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

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

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