酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2010年6月17日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2010/index.html

メモリとデータ構造（18ページ　(g)） 配列，スタック，待ち行列，連結リストといったデータ構造と，それを取り扱うアルゴリズムについての理解を助けるため，計算機に実装されたメモリとデータ構造について述べる． メモリをいかにうまく使うか？ 多彩なデータ構造をどうやって表現するか？

データ型 基本型, primitive type 構造型, structured type byte, word, dword, qword, tbyte void, char, int, float, double boolean, byte, int, double 構造型, structured type section(?) struct, union class

データ スカラ ベクトル グラフ 集合 基本型として限定的に記述可能 １次元の配列として表現可能なことがある 実は、普通の計算機では演算できない グラフ 実は、普通の計算機では簡単に表現できない 集合 もちろん、集合演算はできない

メモリと配列 計算機のメモリは一種の１次元配列である プログラミング言語による多彩なデータ構造 プロセッサが扱える最小単位を要素としている 普通の計算機ではbyteを最小の単位としている 有限の大きさを持つ ただし、仮想記憶管理機構により伸長できる場合もある 配列のインデックスに相当するものがアドレス メモリへのアクセスはアドレッシングと呼ばれる 普通の計算機では、プロセスにはこの配列が1個 プログラミング言語による多彩なデータ構造 プログラミング言語のコンパイラが変換します 実はほとんどの型はbyteの配列になっている

例: Lego MindstormsのRCX内蔵のマイコン メモリ空間は 64KB(65536バイト) メモリマップドI/O アドレスは1 word (2 bytes, １６ビット)で表せる データは、bit, byte, wordを基本とする アドレッシング レジスタ メモリ ビット レジスタ間接指定メモリ メモリ間接指定メモリ レジスタ間接指定ビット ※パソコンのＣＰＵはもっともっと難しい

基本型 プロセッサが定義 メモリは１次元配列 整合の制約もある 驚くほど少ない型 すべてのデータ構造は これらの組み合わせ

例: RCX内蔵マイコンのレジスタ 演算はレジスタ対レジスタ。 演算対象は、bit, byte, word。 データもコードもメモリに置く。 ポインタは必要不可欠。 スタックがサポートされている。 高級言語のスタックフレームに使う。

レジスタ上の表現 レジスタは演算専用の変数 制約はレジスタに由来 ごく限られた数しかない ロードストアアーキテクチャなど コードとデータはメモリに置く

配列 添え字とデータが1対1で対応 添え字は連続 データの挿入や削除は面倒 添え字が１から始まるとは限らない 1 2 3 4 … n … 添え字とデータが1対1で対応 添え字は連続 添え字が１から始まるとは限らない データの挿入や削除は面倒 添え字を用いてアクセスする（例では３）

二次元配列 行と列それぞれをインデックスで指し示す ・・・・・・・ ・・・・・・・ （３，２） 添え字を 用いて ・・・・・・・・・・・・ １　　　　　　２　　　　　　３　　　　　・・・　　　　　ｍ １　 ２　　３　　４　 ・・・・　 ｎ ・・・・・・・ ・・・・・・・ （３，２） 添え字を 用いて データに アクセス ・・・・・・・・・・・・ ・・・・・ ・・・・・・・・・・・・・・・・

三次元配列 １ ２ ３ ・・・・ ｍ １ ２ ３ ・・・ ｎ ・・・・・ ・・・・・・ ・・・・ ・・・・・・・・・ １ ２ ３ ・・・ ｋ １　２　３ ・・・ ｎ １ ２ ３ ・・・ ｋ １　　　 ２　　　 ３ ・・・・　　ｍ （３，１，１） 添え字を 用いて データに アクセス

Javaの配列 Javaにはポインタが陽に説明されていない… 「～への参照」という形でポインタの存在が見える 配列オブジェクト 配列オブジェクト変数 length: 配列の大きさ 配列本体へのポインタ Javaの配列 Javaにはポインタが陽に説明されていない… 「～への参照」という形でポインタの存在が見える NullPointerExceptionでも存在がわかる 配列オブジェクト変数 [実はポインタ変数] 配列オブジェクト 配列オブジェクト 配列オブジェクト変数 [実はポインタ変数] 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ 配列オブジェクト 配列オブジェクト変数 [実はポインタ変数] 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ length: 配列の大きさ 配列オブジェクト 配列オブジェクト変数 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ 配列本体へのポインタ 配列本体 [メモリ上の領域]

(n-1)*m+(m-1)は、展開してn*m-m+m-1、簡単にしてn*m-1 Cの配列 行と列それぞれをインデックスで指し示す Ｃコンパイラはそれをオフセットに変換する １　　　　　　２　　　　　　３　　　　　・・・　　　　　ｍ 配列名 １　 ２　　３　　４　 ・・・・　 ｎ 1 2 ・・・・・・・ m-1 m m+1 m+2 ・・・・・・・ 2*m-1 （３，２） 添え字を 用いて データに アクセス 2*m 2*m+1 ・・・・・・・・・・・・ 3*m ・・・・・ n*m-1 (n-1)*m (n-1)*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; struct Element *firstElement; /* リストの先頭を指す */ int main(void) { firstElement = malloc(sizeof (struct Element) ); if(firstElement == NULL){ return 1; } firstElement->data = NULL; firstElement->next = NULL; ※ＮＵＬＬはＣ言語のキーワード（予約語）ではありません。

値型と参照型 値型 参照型 値が定義したところに存在する 値が別に存在し、それへの参照が定義される JavaやＣ言語の基本型の変数 Ｃ言語では構造型変数(構造体)も値型 参照型 値が別に存在し、それへの参照が定義される Javaのオブジェクトはすべて参照型 newで得られる値は、実体への参照 Ｃ言語では参照型を明示的に定義できる これがいわゆるポインタで、参照する演算子が単項の＊ 値型の参照を得る演算子が単項の＆ Ｃ言語の関数や配列は参照型 名前はそれへの参照を表す