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

Slides:



Advertisements
Similar presentations
アルゴリズムとプログラミン グ (Algorithms and Programming) 第6回:クラスとインスタンス クラスの宣言 アクセス修飾子 インスタンスの生成 (new キーワード) this キーワード フィールドとメソッドの実際の定義と使い 方 クラスの宣言 アクセス修飾子 インスタンスの生成.
Advertisements

2.5 プログラムの構成要素 (1)文字セット ① ASCII ( American Standard Code for Interchange ) JIS コードと同じ ② EBCDIC ( Extended Binary Coded Decimal for Information Code ) 1.
アルゴリズムとデータ構造 第2回 線形リスト(復習).
5.データ構造入門 5-1.連結リスト(Linked List) 5-2.スタック(Stack) 5-3.キュー(Queue)
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造 2010年7月5日
データ構造とアルゴリズム 第10回 mallocとfree
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
オペレーティングシステムJ/K 2004年11月4日
アルゴリズムとデータ構造 2011年6月13日
構造体.
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
アルゴリズムとデータ構造 2011年6月9日
アルゴリズムとデータ構造1 2009年6月25日
メソッド名とその周辺の識別子の 相関ルールに基づくメソッド名変更支援手法
アルゴリズムとデータ構造 2011年6月14日
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
第3回 配列,構造体,ポインタ ~ データ構造について学ぶための基礎~
アルゴリズムとデータ構造 2013年6月10日
プログラミング言語入門 手続き型言語としてのJava
アルゴリズムとデータ構造 2013年6月17日
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
精密工学科プログラミング基礎 第10回資料 (12/18実施)
プログラミング 4 記憶の割り付け.
2005年度 データ構造とアルゴリズム 第3回 「C言語の復習:再帰的データ構造」
コンパイラ 2012年11月15日
アルゴリズムとデータ構造 2010年6月28日
第7回 プログラミングⅡ 第7回
アルゴリズムとデータ構造 補足資料5-1 「メモリとポインタ」
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
データ構造と アルゴリズム 第五回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
プログラミング言語論 第六回 理工学部 情報システム工学科 新田直也.
精密工学科プログラミング基礎Ⅱ 第5回資料 今回の授業で習得してほしいこと: 構造体 (教科書 91 ページ)
構造体と共用体.
6.データ構造入門 6-1.連結リスト(Linked List) 6-2.スタック(Stack) 6-3.キュー(Queue)
データ構造とアルゴリズム 第11回 リスト構造(1)
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング 3 2 次元配列.
プログラミング言語論 第十一回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造1 2006年7月4日
C#プログラミング実習 第3回.
ポインタとポインタを用いた関数定義.
アルゴリズムとデータ構造 2012年6月11日
オペレーティングシステムJ/K (管理のためのデータ構造)
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造1 2009年7月2日
ネットワーク・プログラミング Cプログラミングの基礎.
オブジェクト指向言語論 第九回 知能情報学部 新田直也.
オブジェクト指向言語論 第二回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2010年6月17日
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
情報処理Ⅱ 2005年11月25日(金).
プログラミング基礎a 第5回 C言語によるプログラミング入門 配列と文字列
マスク合成(のような処理) 出力画像 Out 入力画像1 In1 In1 In2 Out 入力画像2 In
左右反転と180度回転 [0][xsize – 1] [0][0] → i ↓ j [ysize – 1][xsize – 1]
TList リスト構造とは? 複数のデータを扱うために、 データの内容と、次のデータへのポインタを持つ構造体を使う。
オブジェクト指向言語論 第九回 知能情報学部 新田直也.
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
Presentation transcript:

酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2009年6月15日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2009/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

データ スカラ ベクトル グラフ 集合 基本型として限定的に記述可能 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から始まるとは限らない 1 2 3 4 … n … 添え字とデータが1対1で対応 添え字は連続 添え字が1から始まるとは限らない データの挿入や削除は面倒 添え字を用いてアクセスする(例では3)

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

三次元配列 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) 添え字を 用いて データに アクセス

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

(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

メモリ上に置かれた構造型データをアドレスで指す 連結リスト 先頭 データ 次 データ 次 データ 次 データをそれぞれの要素に格納 要素どおし、つながってリストを形成 データ 次 データ 次 メモリ上に置かれた構造型データをアドレスで指す 先頭 次 データ 構造型

// リストを形成するためのデータ構造 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; ※NULLはC言語のキーワード(予約語)ではありません。

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