アルゴリズムとデータ構造
2012
年6
月11
日酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2012/index.html
1
値型と参照型
•
値型–
値が定義したところに存在する• Java
やＣ言語の基本型の変数•
Ｃ言語では構造型変数(
構造体)
も値型•
参照型–
値が別に存在し、それへの参照が定義される• Java
のオブジェクトはすべて参照型– newで得られる値は、実体への参照
•
Ｃ言語では参照型を明示的に定義できる– これがいわゆるポインタで、参照する演算子が単項の＊
– 値型の参照を得る演算子が単項の＆
•
Ｃ言語の関数や配列は参照型データ型
•
基本型, primitive type
– byte, word, dword, qword, tbyte – void, char, int, float, double
– boolean, byte, int, double
•
構造型, structured type
– section(?)
– struct, union – class
3
オブジェクトと配列
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.
オブジェクトの初期化5
配列オブジェクト
配列オブジェクト変数 オブジェクト
参照情報
メモリ領域
初期化
オブジェクト領域
オブジェクト 参照情報 オブジェクト
参照情報 オブジェクト
参照情報
配列オブジェクトの宣言
配列要素となるオブジェクトの定義
この段階ではオブジェクトの配列ができてない 初期化
初期化 初期化
Java
における多次元配列• Java
における多次元配列は、配列オブジェクトの配列である
// 2次元配列
Object[][] array2D = new Object[3][2];
// 1次元配列の配列として表される
Object[][] array2D = new Object[3][];
array2D[0] = new Object[2];
array2D[1] = new Object[2];
array2D[2] = new Object[2];
// 3次元配列
Object[][][] array3D = new Object[4][3][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];
/* 参考: 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] ; 7
2
次元配列配列オブジェクト変数 オブジェクト
参照情報
メモリ領域
オブジェクト 参照情報 オブジェクト
参照情報 オブジェクト
参照情報
配列オブジェクト達
…
シンタックスシュガー
•
本来必要ではないがコーディングの効率 化のために設けられている特別な文法array[1][3]; ((Object[])(array[1]))[3];
String[] string = new String[3];
string[0] = “a”; string[1] = “b”; string[2] = “c”; String[] string = new String[]{“a”, “b”, “c”};
9
Java
の配列• Java
にはポインタが陽に説明されていない…
–
「〜への参照」という形でポインタの存在が見える– NullPointerException
でも存在がわかる配列オブジェクト 配列オブジェクト変数
[実はポインタ変数]
配列本体
[メモリ上の領域] length: 配列の大きさ
配列本体へのポインタ
配列オブジェクト 配列オブジェクト変数
[実はポインタ変数]
配列本体
[メモリ上の領域] length: 配列の大きさ
配列本体へのポインタ
配列オブジェクト 配列オブジェクト変数
[実はポインタ変数]
配列本体
[メモリ上の領域] length: 配列の大きさ
配列本体へのポインタ
配列オブジェクト変数
配列本体
length: 配列の大きさ
配列本体へのポインタ
配列オブジェクト 配列オブジェクト変数
length: 配列の大きさ
配列本体へのポインタ
10
１ ２ ３ ・・・ ｍ
0 1 2 m-1
m 2*m 3*m
(n-1)*m
m+1 m+2 2*m+1
2*m-1
(n-1)*m+1 n*m-1
・・・・・・・・・・・・・・・・
・・・・・・・
・・・・・・・
C
の配列•
行と列それぞれをインデックスで指し示す•
Ｃコンパイラはそれをオフセットに変換する（３，２）
添え字を 用いて データに アクセス
(n-1)*m+(m-1)は、展開してn*m-m+m-1、簡単にしてn*m-1 配列名
11
配列上の探索
添え字を用いて 直接アクセス
先頭から 順に調べる
配列上の探索
半分ずつ調べます
1)
半分に分ける2)
前半に存在するか調べる前半にあれば前半について探索 後半にあれば後半について探索
※探索のためにデータの整列が必要
13
配列上の探索
添え字を用いて 直接アクセス
先頭から 順に調べる
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回も判定
15
番兵
•
計算量は減らないが、実行時間は減る•
アルゴリズムではなくテクニックのひとつ•
線形探索では番兵を最後尾に置く–
線形探索における番兵では、探索したいデータと等 しい値のデータを用いることが多い–
探索は目的のデータか番兵いずれかの発見で終了–
探索対象が無くなったかどうかの判定が不要になる•
番兵は最も後に探索され、そして必ず一致する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回だけにした
これが番兵
17
自己再構成リスト
• LRU
の実装などに使える次
データ データ 次 データ 次 データ 次 データ 次
先頭 前
探索対象 次
データ データ 次 データ 次 データ 次 データ 次
先頭 前
探索対象
探索対象を先頭に寄せる
