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

アルゴリズムとデータ構造
2010年6月21日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2010/index.html
オブジェクトと配列
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. オブジェクトの初期化
オブジェクト変数
オブジェクト
参照情報
メモリ領域
メモリ領域
オブジェクト領域
メモリ領域
オブジェクト領域
初期化
配列（２７ページ）
• 添え字とデータが1対1で対応
• 添え字は連続
1
2
– 添え字が１から始まるとは限らない
3
4
…
…
n
•
•
•
•
データの挿入や削除は面倒
同じ大きさの要素が並ぶ
配列は固定長
オブジェクトの配列もありうる…
添え字を用いてアクセスする（例では３）
配列オブジェクト
配列オブジェクトの宣言
配列要素となるオブジェクトの定義
メモリ領域
配列オブジェクト変数
オブジェクト領域
オブジェクト
初期化
参照情報
オブジェクト
参照情報
オブジェクト
参照情報
オブジェクト
参照情報
初期化
初期化
初期化
この段階ではオブジェクトの配列ができてない
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;
配列へデータの挿入
P-1
P-1
p
p
P+1
ｐ番目にデータを挿入 P+1
P+2
P+2
P+3
P+3
・
・
・
・
隙間を空けて
突っ込みます
・
・
・
・
n
n
n+1
n+1
public boolean insert(int aPosition, String aString)
{
if((1 > aPosition) || (aPosition > this.number + 1)){
return false;
}
if(this.array.length == this.number){
return false;
}
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];
}
配列上の探索
添え字を用いて
直接アクセス
先頭から
順に調べる
public int search(String aTarget)
{
for(int count = 0; count < this.number; count++){
if(aTarget.equals(this.array[count])){
return count + 1;
}
}
public int binarySearch(String aTarget)
return -1;
{
}
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;
}
}
配列上の探索
半分ずつ調べます
1)半分に分ける
2)前半に存在するか調べる
前半にあれば前半について探索
後半にあれば後半について探索
※探索のためにデータの整列が必要
配列からデータの削除
P-1
P-1
p
p
ｐ番目の
データを削除
P+1
P+1
P+2
P+2
P+3
P+3
・
・
・
・
n
n+1
・
・
・
・
削除してできた
隙間を詰めます
n
n+1
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 + 1 + "\t" + this.array[count]);
}
System.out.println();
}
二次元配列
• 行と列それぞれをインデックスで指し示す
１
３
・
・
・
・
・・・
・・・・・・・
２
４
３
・・・・・・・
１
（３，２）
添え字を
用いて
データに
アクセス
２
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・・・・・・・・・・・・・・・・・
ｍ
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
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];
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”;

Download Report