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

Slides:



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

アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
データ構造とアルゴリズム 第10回 mallocとfree
アルゴリズムとデータ構造1 2007年6月12日
アルゴリズムとプログラミング (Algorithms and Programming)
問題提起その 1 一文字ずつ文字(数字)を読み込み、それぞれの文字が何回入力されたかを数えて出力するプログラム。
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
オペレーティングシステムJ/K 2004年11月4日
アルゴリズムとデータ構造 2011年6月13日
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
アルゴリズムとデータ構造 2013年6月10日
第13回 ハッシュテーブルを使ったプログラム ~高速に検索するには?~.
プログラミング言語入門 手続き型言語としてのJava
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
アルゴリズムとデータ構造 2013年6月17日
独習JAVA 6.8 コンストラクタの修飾子 6.9 メソッドの修飾子 6.10 ObjectクラスとClassクラス 11月28日(金)
暗黙的に型付けされる構造体の Java言語への導入
アルゴリズムとデータ構造1 2006年7月4日
精密工学科プログラミング基礎 第10回資料 (12/18実施)
プログラミング 4 記憶の割り付け.
アルゴリズムとデータ構造1 2005年7月15日
2005年度 データ構造とアルゴリズム 第3回 「C言語の復習:再帰的データ構造」
コンパイラ 2012年11月15日
第7回 プログラミングⅡ 第7回
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
もっと詳しくArrayクラスについて調べるには → キーワード検索
一時的な型 長谷川啓
プログラムの制御構造 配列・繰り返し.
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
コンパイラ 2011年10月20日
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
プログラミング言語論 第六回 理工学部 情報システム工学科 新田直也.
精密工学科プログラミング基礎Ⅱ 第5回資料 今回の授業で習得してほしいこと: 構造体 (教科書 91 ページ)
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング言語論 第十一回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年7月2日
C#プログラミング実習 第3回.
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
オペレーティングシステムJ/K (管理のためのデータ構造)
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造1 2009年6月15日
ネットワーク・プログラミング Cプログラミングの基礎.
オブジェクト指向言語論 第九回 知能情報学部 新田直也.
コンパイラ 2012年10月11日
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造 2010年6月17日
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
情報処理Ⅱ 2005年11月25日(金).
オブジェクト指向言語論 第九回 知能情報学部 新田直也.
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
Presentation transcript:

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

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

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

「配列オブジェクト」と「オブジェクトの配列」は違う オブジェクトと配列 Object certainObject = new Object(); // オブジェクト生成 int[] intarray = new int[100]; // 基本型intの配列の定義 Object[] objects = new Object[100]; // 配列オブジェクトの定義 objects[i-1] = new Object(); // オブジェクトを定義→配列要素 objects[i-1].method_name(arguments,…); // メソッド 「配列オブジェクト」と「オブジェクトの配列」は違う

オブジェクトと参照 1. オブジェクト変数の宣言 オブジェクト変数 メモリ領域 オブジェクト変数 オブジェクト 参照情報 メモリ領域 2. オブジェクトの生成(new) オブジェクト領域 3. オブジェクトの初期化 オブジェクト変数 オブジェクト 参照情報 メモリ領域 オブジェクト領域 初期化

この段階ではオブジェクトの配列ができてない 配列オブジェクト 配列要素となるオブジェクトの定義 配列オブジェクトの宣言 メモリ領域 配列オブジェクト変数 オブジェクト領域 オブジェクト 参照情報 初期化 オブジェクト 参照情報 初期化 オブジェクト 参照情報 初期化 オブジェクト 参照情報 初期化 この段階ではオブジェクトの配列ができてない

Javaにおける多次元配列 Javaにおける多次元配列は、 配列オブジェクトの配列である // 2次元配列 Object[][] array2D = new Object[3][2]; // 3次元配列 Object[][][] array3D = new Object[4][3][2]; // 1次元配列の配列として表される Object[][] array2D = new Object[3][]; array2D[0] = new Object[2]; array2D[1] = new Object[2]; array2D[2] = new Object[2]; // 2次元配列の配列として表される Object[][][] array3D = new Object[4][][]; array3D[0] = new Object[3][2]; array3D[1] = new Object[3][2]; array3D[2] = new Object[3][2]; array3D[3] = new Object[3][2]; Javaにおける多次元配列は、 配列オブジェクトの配列である /* 参考: 1次元配列の配列としてC言語で定義(Javaの2次元配列に近い) */ Object *array2D[3] ; array2D[0] = malloc(2*sizeof(Object)); array2D[1] = malloc(2*sizeof(Object)); array2D[2] = malloc(2*sizeof(Object)); /* 参考: C言語での2次元配列の定義(Javaと全く違う!) */ Object array2D[3][2] ;

2次元配列 メモリ領域 配列オブジェクト変数 配列オブジェクト達… オブジェクト 参照情報 オブジェクト 参照情報 オブジェクト 参照情報

シンタックスシュガー 本来必要ではないがコーディングの効率化のために設けられている特別な文法 array[1][3]; ((Object[])(array[1]))[3]; String[] string = new String[]{“a”, “b”, “c”}; String[] string = new String[3]; string[0] = “a”; string[1] = “b”; string[2] = “c”;

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

配列上の探索 添え字を用いて 直接アクセス 先頭から 順に調べる

配列上の探索 半分ずつ調べます 1)半分に分ける 2)前半に存在するか調べる 前半にあれば前半について探索 後半にあれば後半について探索 ※探索のためにデータの整列が必要

配列上の探索 添え字を用いて 直接アクセス 先頭から 順に調べる 直接探索            線形探索

配列の要素が尽きたかどうかの判定 目的のデータであるかどうかの判定 1つのデータを探すのに2回も判定 public class Array { public Array(int aMaxSize) this.array = new String[aMaxSize]; this.number = 0; } public int search(String aTarget) for(int count = 0; count < this.number; count++){ if(aTarget.equals(this.array[count])){ return count + 1; return -1; private String[] array; private int number; 配列の要素が尽きたかどうかの判定 目的のデータであるかどうかの判定 1つのデータを探すのに2回も判定

番兵 計算量は減らないが、実行時間は減る アルゴリズムではなくテクニックのひとつ 線形探索では番兵を最後尾に置く 線形探索における番兵では、探索したいデータと等しい値のデータを用いることが多い 探索は目的のデータか番兵いずれかの発見で終了 探索対象が無くなったかどうかの判定が不要になる 番兵は最も後に探索され、そして必ず一致する

これが番兵 配列の要素が尽きたかどうかの判定 目的のデータであるかどうかの判定 を最後に1回だけにした public class Array { public Array(int aMaxSize) this.array = new String[aMaxSize+1]; this.number = 0; } public int search(String aTarget) int count=0; this.array[this.number] = aTarget; while( !aTarget.equals(this.array[count]) ){ count++; if(count != this.number){ return count + 1; return -1; private String[] array; private int number; これが番兵 配列の要素が尽きたかどうかの判定 目的のデータであるかどうかの判定 を最後に1回だけにした

自己再構成リスト LRUの実装などに使える 先頭 前 次 データ 次 データ 次 データ 次 データ 次 データ 探索対象 先頭 前 次 探索対象を先頭に寄せる