Download presentation
Presentation is loading. Please wait.
1
酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造1 2009年6月29日
2
待ち行列（FIFO）（４４ページ） データ挿入 データ取得 待ち行列（データの挿入・取得）
3
待ち行列の配列による実現 データ挿入 データ取得 新しい要素を入れようとすると入らない →右へコピーして移動 →隙間を空ける
4
リングバッファ(46ページ) 配列の最初と最後を接続して環にしたもの ２つのポインタでデータの出し入れを管理 データの先頭を指すポインタ
head, front データの最後尾を指すポインタ tail, rear ２つのポインタが重なったらデータは空 領域の大きさをnとしたらポインタの位置はnとおり データの数が0からnまでn+1とおりある ポインタが重なったら、空か満杯の状態が重なる…
5
リングバッファ 挿入口 リア 環状のデータ格納領域 データの存在を示すポインタ 取り出し口 フロント
6
満杯になったとき、 リアとフロントのポインタが 重なってしまって 空と区別が付かない リア リア フロント
7
配列を使用したリングバッファ 配列には始まりと終わりがある ポインタが終わりまで移動したら先頭へ戻る （フロント－リア）の演算でも境界を考慮
ラップラウンド処理 条件文で判定 配列の大きさを2のべき乗にする 配列のインデックスをビットごとのAND処理
8
データのおき場所は配列 front, rearというポインタで管理 キューの容量はmaxSizeで管理 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 int front; private int maxSize; private Object[] queueArray; private int rear; データのおき場所は配列 front, rearというポインタで管理 キューの容量はmaxSizeで管理
9
frontの指すところがキューの先頭 先頭と最後尾が同じ場合は空 条件文でラップラウンド処理 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; return dequedObject; public boolean isEmpty() return (this.rear == this.front); frontの指すところがキューの先頭 先頭と最後尾が同じ場合は空 条件文でラップラウンド処理
10
rearの指すところがキューの最後尾 先頭と最後尾が同じ場合は空 そうならないようにする判定が必須 条件文でラップラウンド処理
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; return true; public boolean isFull() return ((this.rear + 1) == this.front); rearの指すところがキューの最後尾 先頭と最後尾が同じ場合は空 そうならないようにする判定が必須 条件文でラップラウンド処理
11
場合分けしてラップラウンド処理 frontから配列終わりまでの表示 配列先頭からrearまでの表示
public void printAll() { System.out.println("待ち行列の内容"); if(this.isEmpty()){ System.out.println(); return; } 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; 場合分けしてラップラウンド処理 frontから配列終わりまでの表示 配列先頭からrearまでの表示
12
パイプラインとFIFO データラッチ 演算器 データラッチ 演算器 データラッチ 演算器 データラッチ 演算器 データラッチ データラッチ
※演算器がなければＦＩＦＯ ハードウェアによる実装
13
値型と参照型ふたたび… 現代の主流はノイマン型プロセッサによる計算 機械語のレベルではデータはほぼすべて参照型
命令はメモリに蓄積し、逐次読み出し実行 データもメモリに置き、命令に従って処理される メモリからのロード・ストア、四則演算、論理演算 機械語のレベルではデータはほぼすべて参照型 データどおしの代入という操作すらないものが多い アドレスを指定してロード、アドレスを指定してストア つまりデータはアドレスにより参照される このあたりの区別がわかりやすいので実験２ではＨ８を使う 身近なＩＡ３２アーキテクチャとそのアセンブラはわかりにくい みなさんは今、データ構造を勉強し、プログラムを勉強しています。 それでは、プログラムが動作中のメモリのイメージはわかりますか？ Ｊａｖａにおける基本型とオブジェクト（構造型）を説明できますか？ そして値型と参照型について説明できますか？
14
// リストのデータ構造 // 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; };
15
Integerのインスタンス Element1のインスタンス Element1のインスタンス Element2のインスタンス
// リストのデータ構造 // Java言語でアクセッサあり // Element1 next_element1; // どこかで与えられている Element1 new_element1; new_element1 = new Element1(new Integer(100)); new_element1. setNextElement(next_element1); 100 Integerのインスタンス 100 /* リストのデータ構造 *//* C言語版その１ */ /* struct Element1 *next_element1: /* どこかで与えられている */ struct Element1 *new_element1; new_element1 = malloc(sizeof (struct Element1)); new_element1->data.Integer = 100; new_element1->next = next_element1; Element1のインスタンス getData() getNextElement() setNextElement() data next new_element1 data next data next // リストのデータ構造 // Java言語でアクセッサなし // Element2 next_element2; // どこかで与えられている Element2 new_element2; new_element2 = new Element2(); new_element2.data = new Integer(100); new_element2. next = next_element2; next_element1 next 100 Element1のインスタンス getData() getNextElement() setNextElement() data next next_element1 next_element1 next data /* リストのデータ構造 *//* C言語版その２ */ /* struct Element2 *next_element2: /* どこかで与えられている */ struct Element2 *new_element2; new_element2 = malloc(sizeof (struct Element2)); new_element2->data = malloc(sizeof (int)); *((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い */ new_element2->next = next_element2; Element2のインスタンス data next new_element2 Element2のインスタンス data next next_element2
16
// リストのデータ構造 // 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; };
17
Element1のインスタンス Element1のインスタンス Element2のインスタンス Element2のインスタンス
// リストのデータ構造 // Java言語でアクセッサあり // Element1 next_element1; // どこかで与えられている Element1 new_element1; new_element1 = new Element1(100); new_element1. setNextElement(next_element1); 100 /* リストのデータ構造 *//* C言語版その１ */ /* struct Element1 *next_element1: /* どこかで与えられている */ struct Element1 *new_element1; new_element1 = malloc(sizeof (struct Element1)); new_element1->data.Integer = 100; new_element1->next = next_element1; Element1のインスタンス getData() getNextElement() setNextElement() １００ next new_element1 data next data next // リストのデータ構造 // Java言語でアクセッサなし // Element2 next_element2; // どこかで与えられている Element2 new_element2; new_element2 = new Element2(); new_element2.data = 100; new_element2. next = next_element2; Element1のインスタンス getData() getNextElement() setNextElement() data next next 100 next_element1 next data /* リストのデータ構造 *//* C言語版その２ */ /* struct Element2 *next_element2: /* どこかで与えられている */ struct Element2 *new_element2; new_element2 = malloc(sizeof (struct Element2)); new_element2->data = malloc(sizeof (int)); *((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い */ new_element2->next = next_element2; Element2のインスタンス １００ next new_element2 Element2のインスタンス data next next_element2
18
まとめ データ構造 プログラムへの変換 メモリのイメージ プログラミング言語による違い 配列・リスト・スタック・待ち行列・木
参照型と値型の違い・利害得失 メモリのイメージ 抽象的なデータ構造との対応 プログラミング言語による違い Javaにもポインタは存在する ただし、ポインタ演算はない。 Javaと異なり、Ｃの構造型は値型である Javaのほうが参照を多用するけど、表立って見えない
Similar presentations
