アルゴリズムとデータ構造1

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

Download Report