アルゴリズムとデータ構造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 データ • スカラ – 基本型として限定的に記述可能 • ベクトル – １次元の配列として表現可能なことがある – 実は、普通の計算機では演算できない • グラフ – 実は、普通の計算機では簡単に表現できない • 集合 – 実は、普通の計算機では簡単に表現できない – もちろん、集合演算はできない メモリと配列 • 計算機のメモリは一種の１次元配列である – プロセッサが扱える最小単位を要素としている • 普通の計算機では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 添え字を用いてアクセスする（例では３） 二次元配列 • 行と列それぞれをインデックスで指し示す １ ２ １ （３，２） 添え字を 用いて データに アクセス ・・・・・・・ ３ ・ ・ ・ ・ ｎ ・・・ ・・・・・・・ ２ ４ ３ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・・・・・・・・・・・・・・・・・ ｍ 三次元配列 １ ２ ３ ・・・・ ・・・・・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・・・・・・・・・ １ ２ ３ ・ ・ ・ ｋ ・ ・ ・ ・ ・ ・ ・ ・ ・ ｍ ・ ・ ・ ・ ・ ・ ・ ・ ・ （３，１，１） 添え字を 用いて データに アクセス 配列オブジェクト変数 Javaの配列 length: 配列の大きさ • Javaにはポインタが陽に説明されていない… 配列本体へのポインタ – 「～への参照」という形でポインタの存在が見える – NullPointerExceptionでも存在がわかる 配列オブジェクト 配列オブジェクト変数 [実はポインタ変数] 配列オブジェクト変数 [実はポインタ変数] 配列オブジェクト変数 [実はポインタ変数] 配列オブジェクト変数 length: 配列の大きさ length: 配列の大きさ 配列本体へのポインタ length: 配列の大きさ 配列本体へのポインタ length: 配列の大きさ 配列オブジェクト 配列本体へのポインタ 配列本体へのポインタ 配列オブジェクト 配列オブジェクト 配列本体 [メモリ上の領域] 配列本体 [メモリ上の領域] 配列本体 [メモリ上の領域] 配列本体 Cの配列 • 行と列それぞれをインデックスで指し示す • Ｃコンパイラはそれをオフセットに変換する １ 配列名 １ （３，２） 添え字を 用いて データに アクセス ２ ３ ４ ・ ・ ・ ・ ｎ ２ ３ ・・・ ｍ 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; } ※ＮＵＬＬはＣ言語のキーワード（予約語）ではありません。 値型と参照型 • 値型 – 値が定義したところに存在する • JavaやＣ言語の基本型の変数 • Ｃ言語では構造型変数(構造体)も値型 • 参照型 – 値が別に存在し、それへの参照が定義される • Javaのオブジェクトはすべて参照型 – newで得られる値は、実体への参照 • Ｃ言語では参照型を明示的に定義できる – これがいわゆるポインタで、参照する演算子が単項の＊ – 値型の参照を得る演算子が単項の＆ • Ｃ言語の関数や配列は参照型 – 名前はそれへの参照を表す
© Copyright 2024 ExpyDoc
