アルゴリズムとデータ構造
2013年6月17日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2013/index.html
連結リスト(29ページ)
• データをそれぞれの要素に格納
• 要素どおし、つながってリストを形成
メモリ上に置かれた構造型データをアドレスで指す
先頭
データ 次
データ 次
データ 次 データ 次
データ 次
構造型データ
2
先頭
データ 次
前
データ 次
データ 次
データ 次
データ 次
前
先頭
データ 次
データ 次
データ 次
挿入対象
データ 次
削除対象
データ 次
3
例:メモリ割り当て(37ページ)
最も簡単なメモリ割り当てアルゴリズム
・リストで管理
・データ領域を分断し、あらたなリスト要素として、挿入
・リストのヘッダには空きか使用中かのフラグがある
・割当てるデータ領域はリストのヘッダとヘッダの間
使用状況を示すフラグ
次のヘッダを指すポインタ
空き
空き使用中
ヘッダは左のような構造
要素としては、フラグとポインタしかない
空きの領域
使用中
4
空き
空き使用中
空き
空き
空き 空き
使用中
メモリの割り付け・開放を繰り返していくとメモリが分断するようになる
・フラグメンテーションといい、大きな領域を割り当てできなくなる
・そこで、ときおり、空き領域にはさまれたヘッダを削除する
メモリ割付け技法
•連続割付け
•単一連続割付け
•分割割付け(ゾーン割り付け)
•固定区画割付け
•可変区画割付け
•非連続割付け
•ページング
•セグメンテーション
管理手法
•線形リスト
•ハッシュ表
5
スタック(LIFO)
プッシュ
ポップ
スタックポインタ
スタックポインタ
6
連結リスト操作(挿入)
リストを使ったスタック(push)
先頭
データ
次
データ
データ
データ
次
次
次
• データをそれぞれの要素に格納
• 要素どおし、つながってリストを形成
単純な連結リスト(線形リスト)データ挿入
7
連結リスト操作(削除)
リストを使ったスタック(pop)
先頭
データ
データ
データ
次
次
次
単純な連結リスト(線形リスト)データ削除
8
Postscript
•
•
•
•
プログラミング言語ではなくて、ページ記述言語
オペランドスタック、辞書スタックを持つ
オブジェクトはリテラル、エグゼキュータブル
A-WSでgsというコマンドで実行できる
• push/pop以外のスタック処理がある
• index
指定位置の内容をコピーしてpush
• rotate
指定位置までのスタックを配列とみて回転
• [] , {}, () スタックから配列オブジェクトを切り出せる
9
RPN(逆ポーランド記法)
普通は 1 + 2 と入力して 3 という答えを得ます
同じ答えを得るために、RPNで書くと 1 2 + となります。
普通の書き方の(1 + 2) × (3 + 4) をRPNにすると 1 2 + 3 4 + × となります。
ありがちなプログラミング言語では規則をもとに構文解析を行っている
演算子には優先順位がある
括弧は優先度を変える
変わった言語、変わったプロセッサというものがありまして
Forth, PostScriptといった言語、インテル x87 数値演算プロセッサ
これらはスタックを基本的なデータ構造としている
10
(1 + 2) × (3 + 4)
RPNでは 1 2 + 3 4 +
(1 + 2) × (3 + 4) ÷(5×6 – 7×8)
RPNでは 1 2 + 3 4 + × 5 6 × 7 8 × - ÷
PostScriptでは、三角関数まで定義されている。
GS>1 2 add 3 4 add mul =
21
GS>1 2 add 3 4 add mul 5 6 mul 7 8 mul sub div =
-0.807692
GS>30 sin =
0.5
GS>45 cos =
0.707107
RPNで記述するとき、日本語で数式の動作を
読み上げることにかなり近い順序になる
11
/* 可変長引数を持つ関数 */
int printf(const char *fmt,…);
/* それの呼び出し */
printf(“%d %f \n”, int_number, dbl_number);
C言語では引数はスタックに積まれて、
関数に渡される。呼び出し側の責任で
引数を積んだり降ろしたりする。
呼ばれた関数にわかっていること
1. 呼ばれた関数のスタックフレームの大きさ
2. 関数の戻り先(呼び出し元PC)
3. 第1引数がconst char *fmtであること
つまりfmtが読める→以降の引数がわかる
呼ばれた関数の
スタックフレーム
← TOS
PC
fmt
int_number
dbl_number
呼んだ関数の
スタックフレーム
12
/* 可変長引数を持つ関数 */
int execl(const char *path, const char *arg, ...);
/* それの呼び出し */
execl(“/bin/ls”, “ls”, “-l”, “/home/sakai”, NULL);
呼ばれた関数にわかっていること
1. 呼ばれた関数のスタックフレームの大きさ
2. 関数の戻り先(呼び出し元PC)
3. 第1引数が“/bin/ls”であること
4. 第2引数が”ls”であること
5. 最後の引数は必ずNULLであること
スタックに何らかのマークをpushし、
TOSからマークまでをリストとして渡す
呼ばれた関数の
スタックフレーム
← TOS
PC
“/bin/ls”
“ls”
“-l”
“/home/sakai”
NULL
呼んだ関数の
スタックフレーム
13
% PostScriptにおける配列の切り出し
% [1 2 3 4 5 6 7 8 9 10] という配列を定義
GS>[
GS<1>1
GS<2>2
GS<3>3
GS<4>4
GS<5>5
GS<6>6
GS<7>7
GS<8>8
GS<9>9
GS<10>10
GS<11>]
GS<1>==
[1 2 3 4 5 6 7 8 9 10]
GS>
PostScriptでは、配列が定義できる。
スタック上の「マーク」と「マークまでを配列とする」
オペレータを組み合わせて使う。
このオペレータはマークまでをすべてpopし、
配列オブジェクトとしてふたたびpushする
[ オブジェクトの並び ] は通常の配列
{ オブジェクトの並び } は実行可能な配列(手続き)
(文字の並び) は文字の配列(文字列)
いずれも配列の基本的な性質は継承している
14
待ち行列(FIFO)(44ページ)
データ挿入
データ取得
待ち行列(データの挿入・取得)
15
待ち行列の配列による実現
データ挿入
データ取得
新しい要素を入れようとすると入らない
→右へコピーして移動
→隙間を空ける
16
リングバッファ(46ページ)
配列の最初と最後を接続して環にしたもの
2つのポインタでデータの出し入れを管理
データの先頭を指すポインタ
head, front
データの最後尾を指すポインタ
tail, rear
2つのポインタが重なったらデータは空
領域の大きさをnとしたらポインタの位置はnとおり
データの数が0からnまでn+1とおりある
ポインタが重なったら、空か満杯の状態が重なる…17
リングバッファ
挿入口
リア
•環状のデータ格納領域
•データの存在を示すポインタ
取り出し口
フロント
18
リア
フロント
リア
満杯になったとき、
リアとフロントのポインタが
重なってしまって
空と区別が付かない
19
配列を使用したリングバッファ
配列には始まりと終わりがある
ポインタが終わりまで移動したら先頭へ戻る
(フロント-リア)の演算でも境界を考慮
ラップラウンド処理
ラップラウンド処理
条件文で判定
配列の大きさを2のべき乗にする
配列のインデックスをビットごとのAND処理
20
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;
21
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);
}
22
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);
}
23
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();
24
}
// リストのデータ構造
// 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言語版その1 */
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言語版その2 */
struct Element2 {
void *data;
struct Element2 *next;
25
};
// リストのデータ構造 // Java言語でアクセッサあり
//
Element1 next_element1; // どこかで与えられている
Element1 new_element1;
new_element1 = new Element1(new Integer(100));
new_element1. setNextElement(next_element1);
100
Integerのインスタンス
/* リストのデータ構造 *//* C言語版その1 */
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言語版その2
*/
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 で行儀が悪い
*/
26
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言語版その1 */
struct Element1 {
int data;
struct Element1 *next;
};
// リストのデータ構造
// Java言語でアクセッサなし
public class Element2
{
public Element2()
{
}
public int data;
public Element2 next;
}
/* リストのデータ構造 */
/* C言語版その2 */
struct Element2 {
int *data;
struct Element2 *next;
};
27
// リストのデータ構造 // Java言語でアクセッサあり
//
Element1 next_element1; // どこかで与えられている
Element1 new_element1;
100
new_element1 = new Element1(100);
new_element1. setNextElement(next_element1);
/* リストのデータ構造 *//* C言語版その1 */
/*
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言語でアクセッサなし
100
//
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言語版その2 */
next
setNextElement()
Element2のインスタンス
/*
struct
Element2 *next_element2: /* どこかで与えられている */
data
struct Element2 *new_element2;
100
next
Element2のインスタンス
new_element2 =next
malloc(sizeof (struct Element2));
new_element2->data = malloc(sizeof (int));
data
*((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い
*/
28
next
new_element2->next = next_element2;
next_element2
自己再構成リスト
• LRUの実装などに使える
前
先頭
データ 次
データ 次
データ 次
データ 次
データ 次
探索対象
前
先頭
データ 次
データ 次
探索対象
データ 次
データ 次
データ 次
探索対象を先頭に寄せる
29
配列上の探索
添え字を用いて
直接アクセス
先頭から
順に調べる
直接探索
線形探索
30
public class Array
{
public Array(int aMaxSize)
{
this.array = new String[aMaxSize];
this.number = 0;
}
}
public int search(String aTarget)
{
for(int count = 0; count < this.number; count++){
if(aTarget.equals(this.array[count])){
return count + 1;
}
}
return -1;
}
private String[] array;
配列の要素が尽きたかどうかの判定
private int number;
目的のデータであるかどうかの判定
1つのデータを探すのに2回も判定
31
番兵
• 計算量は減らないが、実行時間は減る
• アルゴリズムではなくテクニックのひとつ
• 線形探索では番兵を最後尾に置く
– 線形探索における番兵では、探索したいデータと等
しい値のデータを用いることが多い
– 探索は目的のデータか番兵いずれかの発見で終了
– 探索対象が無くなったかどうかの判定が不要になる
• 番兵は最も後に探索され、そして必ず一致する
32
public class Array
{
public Array(int aMaxSize)
{
this.array = new String[aMaxSize+1];
this.number = 0;
}
}
public int search(String aTarget)
{
int count=0;
これが番兵
this.array[this.number] = aTarget;
while( !aTarget.equals(this.array[count]) ){
count++;
}
if(count != this.number){
return count + 1;
}
配列の要素が尽きたかどうかの判定
return -1;
目的のデータであるかどうかの判定
}
private String[] array;
配列の要素が尽きたかどうかの判定
private int number;
を最後に1回だけにした
33
配列上の探索
半分ずつ調べます
1)半分に分ける
2)前半に存在するか調べる
前半にあれば前半について探索
後半にあれば後半について探索
※探索のためにデータの整列が必要
二分探索
34
木構造
ルートとそれ以外の
ノードにちょうど1つだけ
の経路しか存在しない
ルートノード
エッジ
ノード
末端ノード
35
まとめ
• データ構造
– 配列・リスト・スタック・待ち行列・木
• プログラムへの変換
– 参照型と値型の違い・利害得失
• メモリのイメージ
– 抽象的なデータ構造との対応
• プログラミング言語による違い
– Javaにもポインタは存在する
• ただし、ポインタ演算はない。
– Javaと異なり、Cの構造型は値型である
36
• Javaのほうが参照を多用するけど、表立って見えない
ダウンロード

PPT