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

Slides:



Advertisements
Similar presentations
アルゴリズムとデータ構造1 2009年6月8日
Advertisements

アルゴリズムとデータ構造 第2回 線形リスト(復習).
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
データ構造とアルゴリズム 第10回 mallocとfree
アルゴリズムとデータ構造1 2007年6月12日
基本情報技術概論(第4回) 埼玉大学 理工学研究科 堀山 貴史
2009/10/9 良いアルゴリズムとは 第2講: 平成21年10月9日 (金) 4限 E252教室 コンピュータアルゴリズム.
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
情報工学概論 (アルゴリズムとデータ構造)
オペレーティングシステムJ/K 2004年11月4日
アルゴリズムとデータ構造 2011年6月13日
条件式 (Conditional Expressions)
プログラミング論 II 電卓,逆ポーランド記法電卓
アルゴリズムとデータ構造1 2009年6月18日
アルゴリズムとデータ構造1 2009年6月25日
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2013年6月10日
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
アルゴリズムとデータ構造 2013年6月17日
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
アルゴリズムとデータ構造1 2005年7月26日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
プログラミング 4 記憶の割り付け.
アルゴリズムとデータ構造1 2005年7月15日
データ構造と アルゴリズム第4回 知能情報学メジャー 和田俊和.
コンパイラ 2012年11月15日
アルゴリズムとデータ構造 2010年6月28日
アルゴリズムとデータ構造1 2005年6月28日
第7回 プログラミングⅡ 第7回
オペレーティングシステムJ/K (仮想記憶管理)
アルゴリズムとデータ構造 2010年6月18日
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとデータ構造1 2005年6月10日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
情報処理Ⅱ 第2回:2003年10月14日(火).
コンパイラ 2011年10月20日
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
プログラミング言語論 第六回 理工学部 情報システム工学科 新田直也.
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
アルゴリズムとプログラミング (Algorithms and Programming)
コンパイラ 2012年10月1日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとプログラミング (Algorithms and Programming)
アルゴリズムとデータ構造1 2008年7月24日
オペレーティングシステムJ/K (管理のためのデータ構造)
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造1 2009年6月15日
コンパイラ 2012年10月11日
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造 2010年6月17日
ソフトウェア工学 知能情報学部 新田直也.
PROGRAMMING IN HASKELL
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
Presentation transcript:

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

テキスト    『アルゴリズムとデータ構造』, 石畑清 著(岩波書店) 参考書    『アルゴリズムとデータ構造』, 平田富夫 著(森北出版). 『アルゴリズムとデータ構造入門』, 東野勝治,臼田昭司 著(森北出版). 『ハッカーのたのしみ』, H.S.ウォーレン Jr 著,滝沢徹,鈴木貢, 赤池英夫,葛毅,藤波順久,玉井浩訳(星雲社) 『プログラミング言語C』, B.W.カーニハン,D.M.リッチー 著, 石田晴久 訳(共立出版).

講義計画 アルゴリズムと計算量 (6月9日5時限) 線形探索・2分探索 (6月13日5時限) 2分探索木 (6月14日2時限)※ アルゴリズムと計算量 (6月9日5時限) 線形探索・2分探索 (6月13日5時限) 2分探索木 (6月14日2時限)※ 平衡木・B木 (6月16日5時限) ハッシュ法 (6月20日5時限) シェルソート (6月23日5時限) クイックソート (6月27日5時限) ヒープソート (6月28日2時限)※ マージソート・ビンソート (6月30日5時限) グラフの表現法・探索 (7月4日5時限) 連結性の判定 (7月7日5時限) 最短路の問題 (7月11日5時限) 文字列のアルゴリズム (7月12日2時限)※ バックトラック・幅優先探索・ゲームの木の探索 (7月14日5時限) NP完全問題・近似アルゴリズム (7月21日5時限) [クォータ末試験] (7月25日5時限)

成績評価 クオータ末試験および演習を総合的に 評価する. 試験や演習で持ち込めるもの 教科書・ノート・配布資料 再試験はしない.

本講義の位置づけ プログラムの勉強(技術的な知識) アルゴリズムとデータ構造(抽象的な知識) 計算機のしくみの勉強(低水準の知識) 計算機言語、情報学群実験1 背景は、表現方法としてのプログラミング言語 アルゴリズムとデータ構造(抽象的な知識) 計算機システムの基礎 数学と計算法(計算機はΣや∫を知らない) 計算機のしくみの勉強(低水準の知識) 情報学群実験2 コーディング対象を知る システム設計の勉強(高水準の知識) ソフトウェア工学、オペレーティングシステム

アルゴリズム+データ構造=プログラム (このように書くのは簡単) アルゴリズムとデータ構造 具体化 抽象化 この間があまりにも遠いのが現実     間を埋めるもの→想像力       想像力を増やす→経験を積む         経験を積むには→楽しさが必要           楽しさって何?               書いたとおり動くのが救い プログラム(Java, C,…)

プログラムとは? アルゴリズムとデータ構造を表現したもの 計算機に仕事をさせる指示・手続き 表現方法にはいっぱいある プログラミング言語の数だけ 構造体やレコードといったデータ構造 連接や条件文や繰り返し文といった制御構造 計算機に仕事をさせる指示・手続き 計算機は指示通りに動くように作られている 動かない場合も稀にある… (教科書2ページ)

なぜ学習するか? すばやくコーディングするため 美しいコードを書くため わかりやすいコードにするため どのように表現するか、どのように処理し目的を達成するか、を理解する

すばやくコーディングする よく知られたものを使う 全体をよく考えて、既存のものが使えるようにする 探せばどこかに実装が存在する 既存のものを使えばデバグの手間が省ける 定番と呼ばれる書籍の存在 全体をよく考えて、既存のものが使えるようにする そのために勉強する!

美しいコード 洗練されたコードは美しい コーディング規則の外側に美しさがある 適切なアルゴリズム 適切なデータ構造 人間が読み書きするものであることを肝に銘じて きちゃないコードは読む気がするか?

わかりやすいコード 構造がわかりやすい 構造がプログラミング言語の自然なデータ型や制御文に合っている プログラムの共有ができる よくしられたデータ構造 よくしられたアルゴリズム これらの再帰的な組み合わせ 構造がプログラミング言語の自然なデータ型や制御文に合っている プログラムの共有ができる 3日後の自分は他人と同じ 記憶力のいい人は1ヶ月くらいは平気?

抽象的 vs. 具体的 ptrで指される領域からvalueを線形探索 for(i = n; i; i--, ptr++) if(*ptr == value) break; mov eax,value mov edx,ptr mov ecx,n 0: cmp eax,[edx] je 1f lea edx,[edx+4] loop 0b 1:

Euclidの互除法(2ページ 1.1) mをnで割って、余りをrとする。 r=0であれば、アルゴリズムは終了する。 このとき、nが最大公約数である。 m←nとする(nの値をmに代入する)。 次にn←rとして1に戻る。 ここでは、次の処理が使われている。 除算 0との比較・分岐処理 変数への代入 繰り返し(ループ)

/* C言語によるgcdの例1 */ int gcd(int m, int n) { int r; 1: r = m % n; if (r == 0) goto 2; m = n; n = r; goto 1; 2: return n; } /* C言語によるgcdの例2 */ int gcd(int m, int n) { int r; while((r = m % n) != 0){ m = n; n = r; } return n; /* Java とほとんど同じ */ プログラムは、連接(文の並び順による評価)・条件分岐(たとえばif文)・繰り返し(例えばwhile文)だけで構成できるとされている。そもそも、gotoを使わないで書いたほうがわかりやすいことも多い。 そのような背景で、Javaのようにgotoを使えないプログラミング言語がある。

スタックフレーム sp+4 sp+2 sp ; アセンブリ言語によるgcd関数の例 引数n .text  スタックフレーム sp+4 sp+2    sp ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r1 ; 引数 m mov.w @(4,sp),r0 ; 引数 n 1: divxu.b r0l,r1 xor.b r2h,r2h mov.b r1h,r2l ; r = m % n beq 2f ; if(r == 0) goto 2 mov.w r0,r1 ; m = n mov.w r2,r0 ; n = r bra 1b ; goto 1 2: rts ; return n .end 戻りアドレス 引数n 引数m 簡単なアルゴリズムであればアセンブリ言語でも記述できる。ただし、アルゴリズムが必要とする処理をプロセッサが知っていれば… ちなみに、スタックというデータ構造は、C言語では例のように、さりげなく使われている。

スタックフレーム sp+4 sp+2 sp bsr直後のスタック ; アセンブリ言語によるgcd関数の例 .text  スタックフレーム sp+4 sp+2    sp ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r0 ; m mov.w @(4,sp),r1 ; n beq 1f ; if (n == 0) divxu.b r1l,r0 mov.b r0h,r0l xor r0h,r0h ; m % n push r0 push r1 bsr gcd adds.w #2,sp 1: rts ; return m .end 戻りアドレス 引数n 引数m  bsr直後のスタック sp+10  sp+8  sp+6  sp+4  sp+2     sp 戻りアドレス 引数n 引数m 戻りアドレス 引数n 引数m レジスタ変数r2(変数r)が、不要になっている。 再帰呼び出しでは、引数は新しい領域に確保される。新しい領域としては、スタックが使われる。

アルゴリズム アルゴリズムは必ず問題を解決するもの ひとつまたは複数のデータを操作し目的の結果を得るための一連の処理手順 いつかは停止しないといけない ひとつまたは複数のデータを操作し目的の結果を得るための一連の処理手順 ループ不変条件 繰り返し開始直前にこの条件が成立。 この条件が成立しているときに、 繰り返しを1回すすめると、再びこの条件が成立。

計算量の概念(7ページ 1.2節) アルゴリズムの性能を示す指標 大きな問題が少ない計算量で解ければ優秀 時間計算量 計算量の概念(7ページ 1.2節) アルゴリズムの性能を示す指標 時間計算量 (文字通り)計算に要する時間 最悪時間計算量・平均時間計算量 空間計算量(領域計算量) どれくらいの作業領域を必要とするかを表す 大きな問題が少ない計算量で解ければ優秀 漸近的に表現したものがO記法 計算量を定式化したとき、計算量に最も大きな影響を及ぼす項をとりだしたもの。

O記法 漸近的な振る舞いを表す 項の形で大きく2つに分けられる(問題:n) 定数項は無視 係数は1 一般には最も影響力の強い項のみで表す 指数関数   kn

10 O(n) O(n log n) 25 10 10 100 O(n2) 2500 O(en) 10 10

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

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

配列(27ページ) 添え字とデータが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) 添え字を 用いて データに アクセス

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

先頭 前 次 データ 次 データ 次 データ 次 データ 次 データ 挿入対象 前 先頭 次 データ 次 データ 次 データ 次 データ 次 データ 削除対象

例:メモリ割り当て(37ページ) 最も簡単なメモリ割り当てアルゴリズム ・リストで管理 ・データ領域を分断し、あらたなリスト要素として、挿入 ・リストのヘッダには空きか使用中かのフラグがある ・割当てるデータ領域はリストのヘッダとヘッダの間 使用状況を示すフラグ 次のヘッダを指すポインタ ヘッダは左のような構造 要素としては、フラグとポインタしかない 空きの領域 使用中 空き 空き 使用中

空き 使用中 空き 空き 空き 空き 使用中 メモリの割り付け・開放を繰り返していくとメモリが分断するようになる ・フラグメンテーションといい、大きな領域を割り当てできなくなる ・そこで、ときおり、空き領域にはさまれたヘッダを削除する メモリ割付け技法 連続割付け 単一連続割付け 分割割付け(ゾーン割り付け) 固定区画割付け 可変区画割付け 非連続割付け ページング セグメンテーション 管理手法 線形リスト ハッシュ表

スタック(LIFO) プッシュ ポップ スタックポインタ スタックポインタ スタックポインタ

連結リスト操作(挿入) リストを使ったスタック(push) 先頭 次 データ 次 データ データをそれぞれの要素に格納 要素どおし、つながってリストを形成 単純な連結リスト(線形リスト)データ挿入

連結リスト操作(削除) リストを使ったスタック(pop) 先頭 次 データ 単純な連結リスト(線形リスト)データ削除

Postscript プログラミング言語ではなくて、ページ記述言語 オペランドスタック、辞書スタックを持つ オブジェクトはリテラル、エグゼキュータブル A-WSでgsというコマンドで実行できる push/pop以外のスタック処理がある index 指定位置の内容をコピーしてpush rotate 指定位置までのスタックを配列とみて回転 [] , {}, () スタックから配列オブジェクトを切り出せる

ありがちなプログラミング言語では規則をもとに構文解析を行っている RPN(逆ポーランド記法) 普通は 1 + 2 と入力して 3 という答えを得ます 同じ答えを得るために、RPNで書くと 1 2 + となります。 普通の書き方の(1 + 2) × (3 + 4) をRPNにすると 1 2 + 3 4 + × となります。 ありがちなプログラミング言語では規則をもとに構文解析を行っている 演算子には優先順位がある 括弧は優先度を変える 変わった言語、変わったプロセッサというものがありまして Forth, PostScriptといった言語、インテル x87 数値演算プロセッサ これらはスタックを基本的なデータ構造としている

RPNで記述するとき、日本語で数式の動作を (1 + 2) × (3 + 4) RPNでは 1 2 + 3 4 + (1 + 2) × (3 + 4) ÷(5×6 – 7×8) RPNでは 1 2 + 3 4 + × 5 6 × 7 8 × - ÷ PostScriptでは、三角関数まで定義されている。 GS>1 2 add 3 4 add mul = 21 GS>1 2 add 3 4 add mul 5 6 mul 7 8 mul sub div = -0.807692 GS>30 sin = 0.5 GS>45 cos = 0.707107 RPNで記述するとき、日本語で数式の動作を 読み上げることにかなり近い順序になる

呼ばれた関数の スタックフレーム PC fmt int_number dbl_number 呼んだ関数の スタックフレーム /* 可変長引数を持つ関数 */ int printf(const char *fmt,…); /* それの呼び出し */ printf(“%d %f \n”, int_number, dbl_number); C言語では引数はスタックに積まれて、 関数に渡される。呼び出し側の責任で 引数を積んだり降ろしたりする。 ← TOS 呼ばれた関数の スタックフレーム PC 呼ばれた関数にわかっていること 呼ばれた関数のスタックフレームの大きさ 関数の戻り先(呼び出し元PC) 第1引数がconst char *fmtであること つまりfmtが読める→以降の引数がわかる fmt int_number dbl_number 呼んだ関数の スタックフレーム

呼ばれた関数の スタックフレーム PC “/bin/ls” “ls” “-l” “/home/sakai” NULL 呼んだ関数の /* 可変長引数を持つ関数 */ int execl(const char *path, const char *arg, ...); /* それの呼び出し */ execl(“/bin/ls”, “ls”, “-l”, “/home/sakai”, NULL); ← TOS 呼ばれた関数の スタックフレーム 呼ばれた関数にわかっていること 呼ばれた関数のスタックフレームの大きさ 関数の戻り先(呼び出し元PC) 第1引数が“/bin/ls”であること 第2引数が”ls”であること 最後の引数は必ずNULLであること PC “/bin/ls” “ls” スタックに何らかのマークをpushし、 TOSからマークまでをリストとして渡す “-l” “/home/sakai” NULL 呼んだ関数の スタックフレーム

% PostScriptにおける配列の切り出し % [1 2 3 4 5 6 7 8 9 10] という配列を定義 GS>[ GS<1>1 GS<2>2 GS<3>3 GS<4>4 GS<5>5 GS<6>6 GS<7>7 GS<8>8 GS<9>9 GS<10>10 GS<11>] GS<1>== [1 2 3 4 5 6 7 8 9 10] GS> PostScriptでは、配列が定義できる。 スタック上の「マーク」と「マークまでを配列とする」 オペレータを組み合わせて使う。 このオペレータはマークまでをすべてpopし、 配列オブジェクトとしてふたたびpushする [ オブジェクトの並び ] は通常の配列 { オブジェクトの並び } は実行可能な配列(手続き) (文字の並び) は文字の配列(文字列) いずれも配列の基本的な性質は継承している

待ち行列(FIFO)(44ページ) データ挿入 データ取得 待ち行列(データの挿入・取得)

待ち行列の配列による実現 データ挿入 データ取得 新しい要素を入れようとすると入らない →右へコピーして移動 →隙間を空ける

リングバッファ(46ページ) 配列の最初と最後を接続して環にしたもの 2つのポインタでデータの出し入れを管理 データの先頭を指すポインタ head, front データの最後尾を指すポインタ tail, rear 2つのポインタが重なったらデータは空 領域の大きさをnとしたらポインタの位置はnとおり データの数が0からnまでn+1とおりある ポインタが重なったら、空か満杯の状態が重なる…

リングバッファ 挿入口 リア 環状のデータ格納領域 データの存在を示すポインタ 取り出し口 フロント

満杯になったとき、 リアとフロントのポインタが 重なってしまって 空と区別が付かない リア リア フロント

配列を使用したリングバッファ 配列には始まりと終わりがある ポインタが終わりまで移動したら先頭へ戻る (フロント-リア)の演算でも境界を考慮 ラップラウンド処理 条件文で判定 配列の大きさを2のべき乗にする 配列のインデックスをビットごとのAND処理

データのおき場所は配列 front, rearというポインタで管理 キューの容量はmaxSizeで管理 public class Queue { private Queue() } public Queue(int aMaxSize) int realSize = aMaxSize + 1; this.maxSize = realSize; this.queueArray = new Object[realSize]; this.front = 0; this.rear = 0; private int front; private int maxSize; private Object[] queueArray; private int rear; データのおき場所は配列 front, rearというポインタで管理 キューの容量はmaxSizeで管理

frontの指すところがキューの先頭 先頭と最後尾が同じ場合は空 条件文でラップラウンド処理 public Object dequeue() { if(this.isEmpty()){ System.err.println("待ち行列は空です"); return null; } Object dequedObject = this.queueArray[this.front]; this.queueArray[this.front] = null; ++this.front; if(this.maxSize == this.front){ this.front = 0; return dequedObject; public boolean isEmpty() return (this.rear == this.front); frontの指すところがキューの先頭 先頭と最後尾が同じ場合は空 条件文でラップラウンド処理

rearの指すところがキューの最後尾 先頭と最後尾が同じ場合は空 そうならないようにする判定が必須 条件文でラップラウンド処理 public boolean enqueue(Object aTarget) { if(this.isFull()){ System.err.println("待ち行列はいっぱいです"); return false; } this.queueArray[this.rear] = aTarget; ++this.rear; if(this.maxSize == this.rear){ this.rear = 0; return true; public boolean isFull() return ((this.rear + 1) == this.front); rearの指すところがキューの最後尾 先頭と最後尾が同じ場合は空 そうならないようにする判定が必須 条件文でラップラウンド処理

場合分けしてラップラウンド処理 frontから配列終わりまでの表示 配列先頭からrearまでの表示 public void printAll() { System.out.println("待ち行列の内容"); if(this.isEmpty()){ System.out.println(); return; } int count = 1; int position = this.front; int limit = (this.front > this.rear)? this.maxSize: this.rear; while(position < limit){ System.out.println(count +"\t" + this.queueArray[position]); ++count; ++position; position = 0; limit = (this.front > this.rear)? this.rear: 0; 場合分けしてラップラウンド処理 frontから配列終わりまでの表示 配列先頭からrearまでの表示

// リストのデータ構造 // Java言語でアクセッサあり public class Element1 { public Element1(Object aData) this.data = aData; } public Object getData() return this.data; public Element1 getNextElement() return this.next; public void setNextElement(Element1 anNextElement) this.next = anNextElement; private Object data; // 参照型 private Element1 next; /* リストのデータ構造 */ /* C言語版その1 */ union Object { int Integer; double Double; }; struct Element1 { union Object data; struct Element1 *next; // リストのデータ構造 // Java言語でアクセッサなし public class Element2 { public Element2() } public Object data; public Element2 next; /* リストのデータ構造 */ /* C言語版その2 */ struct Element2 { void *data; struct Element2 *next; };

Integerのインスタンス Element1のインスタンス Element1のインスタンス Element2のインスタンス // リストのデータ構造 // Java言語でアクセッサあり // Element1 next_element1; // どこかで与えられている Element1 new_element1; new_element1 = new Element1(new Integer(100)); new_element1. setNextElement(next_element1); 100 Integerのインスタンス 100 /* リストのデータ構造 *//* C言語版その1 */ /* struct Element1 *next_element1: /* どこかで与えられている */ struct Element1 *new_element1; new_element1 = malloc(sizeof (struct Element1)); new_element1->data.Integer = 100; new_element1->next = next_element1; Element1のインスタンス getData() getNextElement() setNextElement() data next new_element1 data next data next // リストのデータ構造 // Java言語でアクセッサなし // Element2 next_element2; // どこかで与えられている Element2 new_element2; new_element2 = new Element2(); new_element2.data = new Integer(100); new_element2. next = next_element2; next_element1 next 100 Element1のインスタンス getData() getNextElement() setNextElement() data next next_element1 next_element1 next data /* リストのデータ構造 *//* C言語版その2 */ /* struct Element2 *next_element2: /* どこかで与えられている */ struct Element2 *new_element2; new_element2 = malloc(sizeof (struct Element2)); new_element2->data = malloc(sizeof (int)); *((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い */ new_element2->next = next_element2; Element2のインスタンス data next new_element2 Element2のインスタンス data next next_element2

// リストのデータ構造 // Java言語でアクセッサあり public class Element1 { public Element1(int aData) this.data = aData; } public int getData() return this.data; public Element1 getNextElement() return this.next; public void setNextElement(Element1 anNextElement) this.next = anNextElement; private int data; // 値型 private Element1 next; /* リストのデータ構造 */ /* C言語版その1 */ struct Element1 { int data; struct Element1 *next; }; // リストのデータ構造 // Java言語でアクセッサなし public class Element2 { public Element2() } public int data; public Element2 next; /* リストのデータ構造 */ /* C言語版その2 */ struct Element2 { int *data; struct Element2 *next; };

Element1のインスタンス Element1のインスタンス Element2のインスタンス Element2のインスタンス // リストのデータ構造 // Java言語でアクセッサあり // Element1 next_element1; // どこかで与えられている Element1 new_element1; new_element1 = new Element1(100); new_element1. setNextElement(next_element1); 100 /* リストのデータ構造 *//* C言語版その1 */ /* struct Element1 *next_element1: /* どこかで与えられている */ struct Element1 *new_element1; new_element1 = malloc(sizeof (struct Element1)); new_element1->data.Integer = 100; new_element1->next = next_element1; Element1のインスタンス getData() getNextElement() setNextElement() 100 next new_element1 data next data next // リストのデータ構造 // Java言語でアクセッサなし // Element2 next_element2; // どこかで与えられている Element2 new_element2; new_element2 = new Element2(); new_element2.data = 100; new_element2. next = next_element2; Element1のインスタンス getData() getNextElement() setNextElement() data next next 100 next_element1 next data /* リストのデータ構造 *//* C言語版その2 */ /* struct Element2 *next_element2: /* どこかで与えられている */ struct Element2 *new_element2; new_element2 = malloc(sizeof (struct Element2)); new_element2->data = malloc(sizeof (int)); *((int *)new_element2->data) = 100; /* cast as lvalue で行儀が悪い */ new_element2->next = next_element2; Element2のインスタンス 100 next new_element2 Element2のインスタンス data next next_element2

木構造 ルートとそれ以外の ノードにちょうど1つだけ の経路しか存在しない ルートノード 末端ノード エッジ ノード

まとめ データ構造 プログラムへの変換 メモリのイメージ プログラミング言語による違い 配列・リスト・スタック・待ち行列・木 参照型と値型の違い・利害得失 メモリのイメージ 抽象的なデータ構造との対応 プログラミング言語による違い Javaにもポインタは存在する ただし、ポインタ演算はない。 Javaと異なり、Cの構造型は値型である Javaのほうが参照を多用するけど、表立って見えない