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

アルゴリズムとデータ構造
2010年7月1日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2010/index.html
待ち行列（FIFO）（４４ページ）
データ挿入
データ取得
待ち行列（データの挿入・取得）
待ち行列の配列による実現
データ挿入
データ取得
新しい要素を入れようとすると入らない
→右へコピーして移動
→隙間を空ける
リングバッファ(46ページ)
配列の最初と最後を接続して環にしたもの
２つのポインタでデータの出し入れを管理
データの先頭を指すポインタ
head, front
データの最後尾を指すポインタ
tail, rear
２つのポインタが重なったらデータは空
領域の大きさをnとしたらポインタの位置はnとおり
データの数が0からnまでn+1とおりある
ポインタが重なったら、空か満杯の状態が重なる…
リングバッファ
挿入口
•環状のデータ格納領域
•データの存在を示すポインタ
取り出し口
フロント
リア
リア
フロント
リア
満杯になったとき、
リアとフロントのポインタが
重なってしまって
空と区別が付かない
配列を使用したリングバッファ
配列には始まりと終わりがある
ポインタが終わりまで移動したら先頭へ戻る
（フロント－リア）の演算でも境界を考慮
ラップラウンド処理
ラップラウンド処理
条件文で判定
配列の大きさを2のべき乗にする
配列のインデックスをビットごとのAND処理
public class Queue {
private Queue() {
}
public Queue(int aMaxSize) {
int realSize = aMaxSize + 1;
this.maxSize = realSize;
this.queueArray = new Object[realSize];
this.front = 0;
this.rear = 0;
}
}
private
private
private
private
int front;
int maxSize;
Object[] queueArray;
int rear;
•データのおき場所は配列
•front, rearというポインタで管理
•キューの容量はmaxSizeで管理
public Object dequeue() {
if(this.isEmpty()){
System.err.println("待ち行列は空です");
return null;
}
Object dequedObject = this.queueArray[this.front];
this.queueArray[this.front] = null;
++this.front;
if(this.maxSize == this.front){
this.front = 0;
•frontの指すところがキューの先頭
}
return dequedObject; •先頭と最後尾が同じ場合は空
}
•条件文でラップラウンド処理
public boolean isEmpty() {
return (this.rear == this.front);
}
public boolean enqueue(Object aTarget) {
if(this.isFull()){
System.err.println("待ち行列はいっぱいです");
return false;
}
this.queueArray[this.rear] = aTarget;
++this.rear;
if(this.maxSize == this.rear){
this.rear = 0;
•rearの指すところがキューの最後尾
}
return true;
•先頭と最後尾が同じ場合は空
}
•そうならないようにする判定が必須
•条件文でラップラウンド処理
public boolean isFull() {
return ((this.rear + 1) == this.front);
}
public void printAll() {
System.out.println("待ち行列の内容");
if(this.isEmpty()){
System.out.println();
•場合分けしてラップラウンド処理
return;
•frontから配列終わりまでの表示
}
•配列先頭からrearまでの表示
int count = 1;
int position = this.front;
int limit = (this.front > this.rear)? this.maxSize: this.rear;
while(position < limit){
System.out.println(count +"\t" + this.queueArray[position]);
++count;
++position;
}
position = 0;
limit = (this.front > this.rear)? this.rear: 0;
while(position < limit){
System.out.println(count +"\t" + this.queueArray[position]);
++count;
++position;
}
System.out.println();
}
値型と参照型ふたたび…
• 現代の主流はノイマン型プロセッサによる計算
– 命令はメモリに蓄積し、逐次読み出し実行
みなさんは今、データ構造を勉強し、プログラムを勉強しています。
– データもメモリに置き、命令に従って処理される
それでは、プログラムが動作中のメモリのイメージはわかりますか？
• メモリからのロード・ストア、四則演算、論理演算
Ｊａｖａにおける基本型とオブジェクト（構造型）を説明できますか？
•そして値型と参照型について説明できますか？
機械語のレベルではデータはほぼすべて参照型
– データどおしの代入という操作すらないものが多い
– アドレスを指定してロード、アドレスを指定してストア
• つまりデータはアドレスにより参照される
– このあたりの区別がわかりやすいので実験２ではＨ８を使う
– 身近なＩＡ３２アーキテクチャとそのアセンブラはわかりにくい
// リストのデータ構造
/* リストのデータ構造 */
// Javaでアクセッサあり
/* C言語版その１ */
public class Element1 {
union Object {
public Element1(Object aData) {
int Integer;
this.data = aData;
double Double;
}
};
public Object getData() {
struct Element1 {
return this.data;
union Object data;
}
struct Element1 *next;
public Element1 getNextElement() {
};
return this.next;
}
// リストのデータ構造
public void setNextElement(Element1 anNextElement) {
// Javaでアクセッサなし
this.next = anNextElement;
public class Element2 {
}
public Element2() {
private Object data; // 参照型
}
private Element1 next;
public Object data;
}
public Element2 next;
}
/* リストのデータ構造 */
/* C言語版その２ */
struct Element2 {
void *data;
struct Element2 *next;
};
// リストのデータ構造 // Javaでアクセッサあり
//
Element1 next_element1; // どこかで与えられている
Element1 new_element1;
new_element1 = new Element1(new Integer(100));
new_element1. setNextElement(next_element1);
100
Integerのインスタンス
/* リストのデータ構造 *//* C言語版その１ */
100 */
/*
struct Element1 *next_element1: /* どこかで与えられている
new_element1
structElement1のインスタンス
Element1 *new_element1;
data
new_element1getData()
= malloc(sizeof (struct Element1));
next
data
new_element1->data.Integer
getNextElement() = 100;
new_element1->next
= next_element1;
next
setNextElement()
// リストのデータ構造 // Javaでアクセッサなし
data
next_element1
100
//
Element2 next_element2; // どこかで与えられている
next
Element2 new_element2;
new_element2 = new Element2();
next_element1
next
new_element2.data = new Integer(100);
new_element2. next = next_element2;
Element1のインスタンス
getData()
getNextElement()
next_element1
data
/*
リストのデータ構造
*//*
C言語版その２
*/
new_element2
setNextElement()
Element2のインスタンス
/*
struct
Element2 *next_element2: /* どこかで与えられている */
data
struct Element2 *new_element2;
data
next
next
Element2のインスタンス
new_element2 =next
malloc(sizeof (struct Element2));
new_element2->data = malloc(sizeof (int));
data
*((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い
*/
next
new_element2->next = next_element2;
next_element2
// リストのデータ構造
// Javaでアクセッサあり
public class Element1 {
public Element1(int aData) {
this.data = aData;
}
public int getData() {
return this.data;
}
public Element1 getNextElement() {
return this.next;
}
public void setNextElement(Element1 anNextElement) {
this.next = anNextElement;
}
}
private int data; // 値型
private Element1 next;
/* リストのデータ構造 */
/* C言語版その１ */
struct Element1 {
int data;
struct Element1 *next;
};
// リストのデータ構造
// Javaでアクセッサなし
public class Element2 {
public Element2() {
}
public int data;
public Element2 next;
}
/* リストのデータ構造 */
/* C言語版その２ */
struct Element2 {
int *data;
struct Element2 *next;
};
// リストのデータ構造 // Javaでアクセッサあり
//
Element1 next_element1; // どこかで与えられている
Element1 new_element1;
100
new_element1 = new Element1(100);
new_element1. setNextElement(next_element1);
/* リストのデータ構造 *//* C言語版その１ */
/*
struct Element1 *next_element1: /* どこかで与えられている */
new_element1
structElement1のインスタンス
Element1 *new_element1;
data
new_element1getData()
= malloc(sizeof (struct Element1));
next
data
new_element1->data.Integer
getNextElement() = 100;
new_element1->next
= next_element1;
next
setNextElement()
// リストのデータ構造 // Javaでアクセッサなし
１００
//
Element2 next_element2; // どこかで与えられている
next
Element2 new_element2;
100
Element1のインスタンス
new_element2 = new Element2();
next_element1
next
new_element2.data = 100;
getData()
new_element2. next = next_element2;
data
getNextElement()
new_element2 /* リストのデータ構造 *//* C言語版その２ */
next
setNextElement()
Element2のインスタンス
/*
struct
Element2 *next_element2: /* どこかで与えられている */
data
struct Element2 *new_element2;
１００
next
Element2のインスタンス
new_element2 =next
malloc(sizeof (struct Element2));
new_element2->data = malloc(sizeof (int));
data
*((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い
*/
next
new_element2->next = next_element2;
next_element2
Javaのfinal
• クラスへのfinal
– 継承ができなくなる
• メソッドへのfinal
– オーバーライドできなくなる
• フィールドへのfinal
– 変更できなくなる
• 値型では定数としてふるまう
• 参照型では、定数として振舞わない
– 参照先の値を変更できなくするというものでもない
まとめ
• データ構造
– 配列・リスト・スタック・待ち行列・木
• プログラムへの変換
– 参照型と値型の違い・利害得失
• メモリのイメージ
– 抽象的なデータ構造との対応
• プログラミング言語による違い
– Javaにもポインタは存在する
• ただし、ポインタ演算はない。
– Javaと異なり、Ｃの構造型は値型である
• Javaのほうが参照を多用するけど、表立って見えない

Download Report