Presentation is loading. Please wait.

Presentation is loading. Please wait.

酒居敬一(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.

Similar presentations


Presentation on theme: "酒居敬一(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."— Presentation transcript:

1 酒居敬一(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造 2010年6月17日

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

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

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

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

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

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

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

11 二次元配列 行と列それぞれをインデックスで指し示す ・・・・・・・ ・・・・・・・ (3,2) 添え字を 用いて ・・・・・・・・・・・・
1      2      3     ・・・     m 1  2  3  4  ・・・・  n ・・・・・・・ ・・・・・・・ (3,2) 添え字を 用いて データに アクセス ・・・・・・・・・・・・ ・・・・・ ・・・・・・・・・・・・・・・・

12 三次元配列 1 2 3 ・・・・ m 1 2 3 ・・・ n ・・・・・ ・・・・・・ ・・・・ ・・・・・・・・・ 1 2 3 ・・・ k
1 2 3 ・・・ n 1 2 3 ・・・ k 1    2    3 ・・・・  m (3,1,1) 添え字を 用いて データに アクセス

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の配列 行と列それぞれをインデックスで指し示す Cコンパイラはそれをオフセットに変換する 1      2      3     ・・・     m 配列名 1  2  3  4  ・・・・  n 1 2 ・・・・・・・ m-1 m m+1 m+2 ・・・・・・・ 2*m-1 (3,2) 添え字を 用いて データに アクセス 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; ※NULLはC言語のキーワード(予約語)ではありません。

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


Download ppt "酒居敬一(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."

Similar presentations


Ads by Google