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

アルゴリズムとデータ構造1
2009年6月29日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2009/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
•front, rearというポインタで管理
•キューの容量はmaxSizeで管理
int front;
int maxSize;
Object[] queueArray;
int rear;
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から配列終わりまでの表示
}
int count = 1;
•配列先頭からrearまでの表示
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();
}
パイプラインとFIFO
デ
ー
タ
ラ
ッ
チ
デ
ー
タ
ラ
ッ
チ
演算器
デ
ー
タ
ラ
ッ
チ
デ
ー
タ
ラ
ッ
チ
演算器
デ
ー
タ
ラ
ッ
チ
演算器
デ
ー
タ
ラ
ッ
チ
演算器
デ
ー
タ
ラ
ッ
チ
デ
ー
タ
ラ
ッ
チ
※演算器がなければＦＩＦＯ
ハードウェアによる実装
デ
ー
タ
ラ
ッ
チ
デ
ー
タ
ラ
ッ
チ
値型と参照型ふたたび…
• 現代の主流はノイマン型プロセッサによる計算
– 命令はメモリに蓄積し、逐次読み出し実行
みなさんは今、データ構造を勉強し、プログラムを勉強しています。
– データもメモリに置き、命令に従って処理される
それでは、プログラムが動作中のメモリのイメージはわかりますか？
• メモリからのロード・ストア、四則演算、論理演算
Ｊａｖａにおける基本型とオブジェクト（構造型）を説明できますか？
•そして値型と参照型について説明できますか？
機械語のレベルではデータはほぼすべて参照型
– データどおしの代入という操作すらないものが多い
– アドレスを指定してロード、アドレスを指定してストア
• つまりデータはアドレスにより参照される
– このあたりの区別がわかりやすいので実験２ではＨ８を使う
– 身近なＩＡ３２アーキテクチャとそのアセンブラはわかりにくい
// リストのデータ構造
// Java言語でアクセッサあり
public class Element1
{
public Element1(Object aData)
{
this.data = aData;
}
public Object getData()
{
return this.data;
}
public Element1 getNextElement()
{
return this.next;
}
public void setNextElement(Element1 anNextElement)
{
this.next = anNextElement;
}
private Object data; // 参照型
private Element1 next;
}
/* リストのデータ構造 */
/* C言語版その１ */
union Object {
int Integer;
double Double;
};
struct Element1 {
union Object data;
struct Element1 *next;
};
// リストのデータ構造
// Java言語でアクセッサなし
public class Element2
{
public Element2()
{
}
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にもポインタは存在する
• ただし、ポインタ演算はない。
– Javaと異なり、Ｃの構造型は値型である
• Javaのほうが参照を多用するけど、表立って見えない

Download Report