Download presentation
Presentation is loading. Please wait.
1
酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造1 2009年6月15日
2
メモリとデータ構造（18ページ (g)） 配列，スタック，待ち行列，連結リストといったデータ構造と，それを取り扱うアルゴリズムについての理解を助けるため，計算機に実装されたメモリとデータ構造について述べる． メモリをいかにうまく使うか？ 多彩なデータ構造をどうやって表現するか？
3
データ型 基本型, primitive type 構造型, structured type
byte, word, dword, qword, tbyte void, char, int, float, double boolean, byte, int, double 構造型, structured type section(?) struct, union class
4
データ スカラ ベクトル グラフ 集合 基本型として限定的に記述可能 １次元の配列として表現可能なことがある
実は、普通の計算機では演算できない グラフ 実は、普通の計算機では簡単に表現できない 集合 もちろん、集合演算はできない
5
メモリと配列 計算機のメモリは一種の１次元配列である プログラミング言語による多彩なデータ構造 プロセッサが扱える最小単位を要素としている
普通の計算機ではbyteを最小の単位としている 有限の大きさを持つ ただし、仮想記憶管理機構により伸長できる場合もある 配列のインデックスに相当するものがアドレス メモリへのアクセスはアドレッシングと呼ばれる 普通の計算機では、プロセスにはこの配列が1個 プログラミング言語による多彩なデータ構造 プログラミング言語のコンパイラが変換します 実はほとんどの型はbyteの配列になっている
6
例: Lego MindstormsのRCX内蔵のマイコン メモリ空間は 64KB(65536バイト) メモリマップドI/O
アドレスは1 word (2 bytes, １６ビット)で表せる データは、bit, byte, wordを基本とする アドレッシング レジスタ メモリ ビット レジスタ間接指定メモリ メモリ間接指定メモリ レジスタ間接指定ビット ※パソコンのＣＰＵはもっともっと難しい
7
基本型 プロセッサが定義 メモリは１次元配列 整合の制約もある 驚くほど少ない型 すべてのデータ構造は これらの組み合わせ
8
例: RCX内蔵マイコンのレジスタ 演算はレジスタ対レジスタ。 演算対象は、bit, byte, word。 データもコードもメモリに置く。 ポインタは必要不可欠。 スタックがサポートされている。 高級言語のスタックフレームに使う。
9
レジスタ上の表現 レジスタは演算専用の変数 制約はレジスタに由来 ごく限られた数しかない ロードストアアーキテクチャなど
コードとデータはメモリに置く
10
配列 添え字とデータが1対1で対応 添え字は連続 データの挿入や削除は面倒 添え字が１から始まるとは限らない 1 2 3 4 …
n … 添え字とデータが1対1で対応 添え字は連続 添え字が１から始まるとは限らない データの挿入や削除は面倒 添え字を用いてアクセスする（例では３）
11
二次元配列 行と列それぞれをインデックスで指し示す ・・・・・・・ ・・・・・・・ （３，２） 添え字を 用いて ・・・・・・・・・・・・
１ ２ ３ ・・・ ｍ １ ２ ３ ４ ・・・・ ｎ ・・・・・・・ ・・・・・・・ （３，２） 添え字を 用いて データに アクセス ・・・・・・・・・・・・ ・・・・・ ・・・・・・・・・・・・・・・・
12
三次元配列 １ ２ ３ ・・・・ ｍ １ ２ ３ ・・・ ｎ ・・・・・ ・・・・・・ ・・・・ ・・・・・・・・・ １ ２ ３ ・・・ ｋ
１ ２ ３ ・・・ ｎ １ ２ ３ ・・・ ｋ １ ２ ３ ・・・・ ｍ （３，１，１） 添え字を 用いて データに アクセス
13
Javaの配列 Javaにはポインタが陽に説明されていない… 「～への参照」という形でポインタの存在が見える
配列オブジェクト 配列オブジェクト変数 length: 配列の大きさ 配列本体へのポインタ Javaの配列 Javaにはポインタが陽に説明されていない… 「～への参照」という形でポインタの存在が見える NullPointerExceptionでも存在がわかる 配列オブジェクト変数 [実はポインタ変数] 配列オブジェクト 配列オブジェクト 配列オブジェクト変数 [実はポインタ変数] 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ 配列オブジェクト 配列オブジェクト変数 [実はポインタ変数] 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ length: 配列の大きさ 配列オブジェクト 配列オブジェクト変数 配列本体 [メモリ上の領域] length: 配列の大きさ 配列本体へのポインタ 配列本体へのポインタ 配列本体 [メモリ上の領域]
14
(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
15
メモリ上に置かれた構造型データをアドレスで指す
連結リスト 先頭 データ 次 データ 次 データ 次 データをそれぞれの要素に格納 要素どおし、つながってリストを形成 データ 次 データ 次 メモリ上に置かれた構造型データをアドレスで指す 先頭 次 データ 構造型
16
// リストを形成するためのデータ構造 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;
17
/* リストを形成するためのデータ構造 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; ※ＮＵＬＬはＣ言語のキーワード（予約語）ではありません。
18
値型と参照型 値型 参照型 値が定義したところに存在する 値が別に存在し、それへの参照が定義される JavaやＣ言語の基本型の変数
Ｃ言語では構造型変数(構造体)も値型 参照型 値が別に存在し、それへの参照が定義される Javaのオブジェクトはすべて参照型 newで得られる値は、実体への参照 Ｃ言語では参照型を明示的に定義できる これがいわゆるポインタで、参照する演算子が単項の＊ 値型の参照を得る演算子が単項の＆ Ｃ言語の関数や配列は参照型 名前はそれへの参照を表す
Similar presentations
