アルゴリズムとデータ構造
1
アルゴリズムとデータ構造
アルゴリズムとデータ構造
1
1
2007
2007
年
年
6
6
月
月
26
26
日
日
酒居敬一
酒居敬一
(
(
sakai.keiichi@kochi
sakai.keiichi@kochi
-
-
tech.ac.jp
tech.ac.jp
)
)
http://www.info.kochi
待ち行列（
FIFO）
（４４ページ）
データ挿入
データ取得
待ち行列の配列による実現
データ挿入
データ取得
新しい要素を入れようとすると入らない
→右へコピーして移動
リングバッファ
(46ページ)
¾配列の最初と最後を接続して環にしたもの
¾２つのポインタでデータの出し入れを管理
¾データの先頭を指すポインタ
¾
head, front
¾データの最後尾を指すポインタ
¾
tail, rear
¾２つのポインタが重なったらデータは空
¾領域の大きさを
nとしたらポインタの位置はnとおり
¾データの数が
0からnまでn+1とおりある
¾ポインタが重なったら、空か満杯の状態が重なる…
リングバッファ
リア
フロント
挿入口
取り出し口
•環状のデータ格納領域
•データの存在を示すポインタ
フロント
リア
リア
満杯になったとき、
リアとフロントのポインタが
重なってしまって
空と区別が付かない
配列を使用したリングバッファ
9配列には始まりと終わりがある
9ポインタが終わりまで移動したら先頭へ戻る
9（フロント−リア）の演算でも境界を考慮
9ラップラウンド処理
9ラップラウンド処理
9条件文で判定
9配列の大きさを
2のべき乗にする
9配列のインデックスをビットごとの
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 int front;
private int maxSize;
private Object[] queueArray;
private 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;
}
return dequedObject;
}
public boolean isEmpty()
{
return (this.rear == this.front);
}
•
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;
}
return true;
}
public boolean isFull()
{
return ((this.rear + 1) == this.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;
while(position < limit){
System.out.println(count +"¥t" + this.queueArray[position]);
++count;
++position;
}
System.out.println();
}
•場合分けしてラップラウンド処理
•
frontから配列終わりまでの表示
•配列先頭から
rearまでの表示
パイプライン
データラッチ
演算器
データラッチ
データラッチ
演算器
データラッチ
演算器
データラッチ
演算器
データラッチ
データラッチ
データラッチ
データラッチ
データラッチ
※演算器がなければＦＩＦＯ
ハードウェアによる実装
値型と参照型
ふたたび…
• 現代の主流はノイマン型プロセッサによる計算
– 命令はメモリに蓄積し、逐次読み出し実行
– データもメモリに置き、命令に従って処理される
• メモリからのロード・ストア、四則演算、論理演算
• 機械語のレベルではデータはほぼすべて参照型
– データどおしの代入という操作すらないものが多い
– アドレスを指定してロード、アドレスを指定してストア
• つまりデータはアドレスにより参照される
– このあたりの区別がわかりやすいので実験２ではＨ８を使う
– 身近なＩＡ３２アーキテクチャとそのアセンブラはわかりにくい
みなさんは今、データ構造を勉強し、プログラムを勉強しています。
それでは、プログラムが動作中のメモリのイメージはわかりますか？
Ｊａｖａにおける基本型とオブジェクト（構造型）を説明できますか？
そして値型と参照型について説明できますか？
// リストのデータ構造
// 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);
/* リストのデータ構造 *//* 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;
/* リストのデータ構造 *//* 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;
// リストのデータ構造 // Java言語でアクセッサなし
// Element2 next_element2; // どこかで与えられている Element2 new_element2;
new_element2 = new Element2();
new_element2.data = new Integer(100); new_element2. next = next_element2;
Element1のインスタンス
getData() getNextElement() setNextElement() data nextElement2のインスタンス
data nextIntegerのインスタンス
100Element1のインスタンス
getData() getNextElement() setNextElement() data next new_element1 next_element1 new_element2 next_element2Element2のインスタンス
data next 100 data next next_element1 next 100 next_element1 next data data next// リストのデータ構造
// 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;
new_element1 = new Element1(100);
new_element1. setNextElement(next_element1);
/* リストのデータ構造 *//* 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;
/* リストのデータ構造 *//* 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;
// リストのデータ構造 // Java言語でアクセッサなし
// Element2 next_element2; // どこかで与えられている Element2 new_element2;
new_element2 = new Element2(); new_element2.data = 100;
new_element2. next = next_element2;
