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

アルゴリズムとデータ構造1
2005年6月24日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2005/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();
}
二次元配列
• 行と列それぞれをインデックスで指し示す
１
３
・
・
・
・
・・・
・・・・・・・
２
４
３
・・・・・・・
１
（３，２）
添え字を
用いて
データに
アクセス
２
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・・・・・・・・・・・・・・・・・
ｍ
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”;
演習課題
1.
次の数値列から二分探索木を作成せよ
39, 10, 6, 81, 91, 28, 29, 97, 43, 40, 15, 1, 61, 7, 88
2. 二分探索木を中間順（通りかけ順）で走査せよ
3. 次の数値列をバブルソートせよ（過程も書くこと）
36, 1, 26, 7, 99, 69, 95, 63
4. 次の数値列をクイックソートせよ（過程も書くこと）
51, 23, 10, 71, 36, 1, 26, 7, 39, 99, 82, 69, 74, 95, 57, 48
※ このとき、学生番号が奇数の人は右端、偶数の人は左端を
基準値として、左から小さい数値が並ぶように書くこと
5. 一般的な「オブジェクトの配列」とJavaの
「配列オブジェクト」、これらの違いを説明せよ

Download Report