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

アルゴリズムとデータ構造1
2006年6月12日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2006/index.html
メモリとデータ構造(18ページ
(g))
• 配列,スタック,待ち行列,連結リストといった
データ構造と,それを取り扱うアルゴリズムに
ついての理解を助けるため,計算機に実装さ
れたメモリとデータ構造について述べる.
• メモリをいかにうまく使うか?
• 多彩なデータ構造をどうやって表現するか?
データ型
• 基本型, primitive type
– byte, word, dword, qword, tbyte
– void, char, int, float, double
– boolean, byte, int, double
• 構造型, structured type
– section(?)
– struct, union
– class
データ
• スカラ
– 基本型として限定的に記述可能
• ベクトル
– 1次元の配列として表現可能なことがある
– 実は、普通の計算機では演算できない
• グラフ
– 実は、普通の計算機では簡単に表現できない
• 集合
– 実は、普通の計算機では簡単に表現できない
– もちろん、集合演算はできない
メモリと配列
• 計算機のメモリは一種の1次元配列である
– プロセッサが扱える最小単位を要素としている
• 普通の計算機ではbyteを最小の単位としている
– 有限の大きさを持つ
• ただし、仮想記憶管理機構により伸長できる場合もある
– 配列のインデックスに相当するものがアドレス
• メモリへのアクセスはアドレッシングと呼ばれる
– 普通の計算機では、プロセスにはこの配列が1個
• プログラミング言語による多彩なデータ構造
• プログラミング言語のコンパイラが変換します
• 実はほとんどの型はbyteの配列になっている
例: Lego MindstormsのRCX内蔵のマイコン
•メモリ空間は 64KB(65536バイト)
•メモリマップドI/O
•アドレスは1 word (2 bytes, 16ビット)で表せる
•データは、bit, byte, wordを基本とする
•アドレッシング
•レジスタ
•メモリ
•ビット
•レジスタ間接指定メモリ
•メモリ間接指定メモリ
•レジスタ間接指定ビット
※パソコンのCPUはもっともっと難しい
基本型
•プロセッサが定義
•メモリは1次元配列
•整合の制約もある
•驚くほど少ない型
•すべてのデータ構造は
これらの組み合わせ
例: RCX内蔵マイコンのレジスタ
•演算はレジスタ対レジスタ。
•演算対象は、bit, byte, word。
•データもコードもメモリに置く。
•ポインタは必要不可欠。
•スタックがサポートされている。
•高級言語のスタックフレームに使う。
レジスタ上の表現
•レジスタは演算専用の変数
•制約はレジスタに由来
•ロードストアアーキテクチャなど
•ごく限られた数しかない
•コードとデータはメモリに置く
配列
• 添え字とデータが1対1で対応
• 添え字は連続
1
2
– 添え字が1から始まるとは限らない
3
• データの挿入や削除は面倒
4
…
…
n
添え字を用いてアクセスする(例では3)
二次元配列
• 行と列それぞれをインデックスで指し示す
1
2
1
(3,2)
添え字を
用いて
データに
アクセス
・・・・・・・
3
・
・
・
・
n
・・・
・・・・・・・
2
4
3
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・・・・・・・・・・・・・・・・・
m
三次元配列
1
2
3
・・・・
・・・・・
・
・
・
・
・
・
・
・
・
・・・・・・・・・
1
2
3
・
・
・
k
・
・
・
・
・
・
・
・
・
m
・
・
・
・
・
・
・
・
・
(3,1,1)
添え字を
用いて
データに
アクセス
配列オブジェクト変数
Javaの配列
length: 配列の大きさ
• Javaにはポインタが陽に説明されていない…
配列本体へのポインタ
– 「~への参照」という形でポインタの存在が見える
– NullPointerExceptionでも存在がわかる
配列オブジェクト
配列オブジェクト変数
[実はポインタ変数]
配列オブジェクト変数
[実はポインタ変数]
配列オブジェクト変数
[実はポインタ変数]
配列オブジェクト変数
length: 配列の大きさ
length: 配列の大きさ
配列本体へのポインタ
length: 配列の大きさ
配列本体へのポインタ
length: 配列の大きさ
配列オブジェクト
配列本体へのポインタ
配列本体へのポインタ
配列オブジェクト
配列オブジェクト
配列本体
[メモリ上の領域]
配列本体
[メモリ上の領域]
配列本体
[メモリ上の領域]
配列本体
Cの配列
• 行と列それぞれをインデックスで指し示す
• Cコンパイラはそれをオフセットに変換する
1
配列名
1
(3,2)
添え字を
用いて
データに
アクセス
2
3
4
・
・
・
・
n
2
3
・・・
m
0
1
2
・・・・・・・
m-1
m
m+1
m+2
・・・・・・・
2*m-1
2*m
2*m+1
3*m
・
・
・
・
・
(n-1)*m
(n-1)*m+1
・・・・・・・・・・・・・・・・
・
・
・
・
・
・
・
・
・
・
・
・
n*m-1
(n-1)*m+(m-1)は、展開してn*m-m+m-1、簡単にしてn*m-1
連結リスト
先頭
データ 次
データ 次 データ 次
データ 次
• データをそれぞれの要素に格納
データ 次
• 要素どおし、つながってリストを形成
メモリ上に置かれた構造型データをアドレスで指す
先頭
データ
データ
データ
次
次
次
構造型
// リストを形成するためのデータ構造 in Java
public class Element {
public Element(Object aData) {
this.data = aData;
}
public Object getData() {
return this.data;
}
public Element getNextElement() {
return this.next;
}
public void setNextElement(Element anNextElement) {
this.next = anNextElement;
}
private Object data;
private Element next; // クラスの自己参照
}
// リストの先頭
public class MyLinkedList {
public MyLinkedList() {
this.firstElement = new Element(null);
}
private Element firstElement;
}
/* リストを形成するためのデータ構造 in C language */
struct Element {
void *data;
struct Element *next;
/* 構造体型の自己参照 */
};
struct Element *firstElement;
/* リストの先頭を指す */
int main(void)
{
firstElement = malloc(sizeof (struct Element) );
if(firstElement == NULL){
return 1;
}
firstElement->data = NULL;
firstElement->next = NULL;
}
※NULLはC言語のキーワード(予約語)ではありません。
値型と参照型
• 値型
– 値が定義したところに存在する
• JavaやC言語の基本型の変数
• C言語では構造型変数(構造体)も値型
• 参照型
– 値が別に存在し、それへの参照が定義される
• Javaのオブジェクトはすべて参照型
– newで得られる値は、実体への参照
• C言語では参照型を明示的に定義できる
– これがいわゆるポインタで、参照する演算子が単項の*
– 値型の参照を得る演算子が単項の&
• C言語の関数や配列は参照型
– 名前はそれへの参照を表す