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

Presentation on theme: "担当：酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造 2011年6月9日 担当：酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html."— Presentation transcript:

1 担当：酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp)
アルゴリズムとデータ構造 2011年6月9日

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

3 講義計画 アルゴリズムと計算量 （６月９日５時限） 線形探索・２分探索 （６月１３日５時限） ２分探索木 （６月１４日２時限）※
アルゴリズムと計算量 （６月９日５時限） 線形探索・２分探索 （６月１３日５時限） ２分探索木 （６月１４日２時限）※ 平衡木・B木 （６月１６日５時限） ハッシュ法 （６月２０日５時限） シェルソート （６月２３日５時限） クイックソート （６月２７日５時限） ヒープソート （６月２８日２時限）※ マージソート・ビンソート （６月３０日５時限） グラフの表現法・探索 （７月４日５時限） 連結性の判定 （７月７日５時限） 最短路の問題 （７月１１日５時限） 文字列のアルゴリズム （７月１２日２時限）※ バックトラック・幅優先探索・ゲームの木の探索 （７月１４日５時限） NP完全問題・近似アルゴリズム （７月２１日５時限） ［クォータ末試験］ （７月２５日５時限）

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

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

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

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

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

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

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

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

12 抽象的 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:

13 Ｅｕｃｌｉｄの互除法（２ページ 1.1） ｍをｎで割って、余りをｒとする。
ｒ＝０であれば、アルゴリズムは終了する。 このとき、ｎが最大公約数である。 ｍ←ｎとする（ｎの値をｍに代入する）。 次にｎ←ｒとして１に戻る。 ここでは、次の処理が使われている。 除算 ０との比較・分岐処理 変数への代入 繰り返し（ループ）

14 /* 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を使えないプログラミング言語がある。

15 スタックフレーム ｓｐ＋４ ｓｐ＋２ ｓｐ ; アセンブリ言語によるgcd関数の例 引数ｎ .text
　スタックフレーム ｓｐ＋４ ｓｐ＋２ 　　　ｓｐ ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r ; 引数 m mov.w @(4,sp),r ; 引数 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,r ; m = n mov.w r2,r ; n = r bra 1b ; goto 1 2: rts ; return n .end 戻りアドレス 引数ｎ 引数ｍ 簡単なアルゴリズムであればアセンブリ言語でも記述できる。ただし、アルゴリズムが必要とする処理をプロセッサが知っていれば… ちなみに、スタックというデータ構造は、Ｃ言語では例のように、さりげなく使われている。

16 スタックフレーム ｓｐ＋４ ｓｐ＋２ ｓｐ ｂｓｒ直後のスタック ; アセンブリ言語によるgcd関数の例 .text
　スタックフレーム ｓｐ＋４ ｓｐ＋２ 　　　ｓｐ ; アセンブリ言語によるgcd関数の例 .text gcd: mov.w @(2,sp),r ; m mov.w @(4,sp),r ; 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 戻りアドレス 引数ｎ 引数ｍ 　ｂｓｒ直後のスタック ｓｐ＋１０ 　ｓｐ＋８ 　ｓｐ＋６ 　ｓｐ＋４ 　ｓｐ＋２ 　　　　ｓｐ 戻りアドレス 引数ｎ 引数ｍ 戻りアドレス 引数ｎ 引数ｍ レジスタ変数r2(変数r)が、不要になっている。 再帰呼び出しでは、引数は新しい領域に確保される。新しい領域としては、スタックが使われる。

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

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

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

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

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

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

23 配列（２７ページ） 添え字とデータが1対1で対応 添え字は連続 データの挿入や削除は面倒 添え字が１から始まるとは限らない 1 2 3 4
n … 添え字とデータが1対1で対応 添え字は連続 添え字が１から始まるとは限らない データの挿入や削除は面倒 添え字を用いてアクセスする（例では３）

24 二次元配列 行と列それぞれをインデックスで指し示す ・・・・・・・ ・・・・・・・ （３，２） 添え字を 用いて ・・・・・・・・・・・・
１　　　　　　２　　　　　　３　　　　　・・・　　　　　ｍ １　 ２　　３　　４　 ・・・・　 ｎ ・・・・・・・ ・・・・・・・ （３，２） 添え字を 用いて データに アクセス ・・・・・・・・・・・・ ・・・・・ ・・・・・・・・・・・・・・・・

25 三次元配列 １ ２ ３ ・・・・ ｍ １ ２ ３ ・・・ ｎ ・・・・・ ・・・・・・ ・・・・ ・・・・・・・・・ １ ２ ３ ・・・ ｋ
１　２　３ ・・・ ｎ １ ２ ３ ・・・ ｋ １　　　 ２　　　 ３ ・・・・　　ｍ （３，１，１） 添え字を 用いて データに アクセス

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

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

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

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

30 スタック（LIFO） プッシュ ポップ スタックポインタ スタックポインタ スタックポインタ

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

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

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

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

35 RPNで記述するとき、日本語で数式の動作を
(1 + 2) × (3 + 4) RPNでは (1 + 2) × (3 + 4) ÷(5×6 – 7×8) RPNでは × 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 = GS>30 sin = 0.5 GS>45 cos = RPNで記述するとき、日本語で数式の動作を 読み上げることにかなり近い順序になる

36 呼ばれた関数の スタックフレーム 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 呼んだ関数の スタックフレーム

37 呼ばれた関数の スタックフレーム 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 呼んだ関数の スタックフレーム

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

39 待ち行列（FIFO）（４４ページ） データ挿入 データ取得 待ち行列（データの挿入・取得）

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

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

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

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

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

45 データのおき場所は配列 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で管理

46 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の指すところがキューの先頭 先頭と最後尾が同じ場合は空 条件文でラップラウンド処理

47 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の指すところがキューの最後尾 先頭と最後尾が同じ場合は空 そうならないようにする判定が必須 条件文でラップラウンド処理

48 場合分けしてラップラウンド処理 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までの表示

49 // リストのデータ構造 // 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言語版その１ */ 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言語版その２ */ struct Element2 { void *data; struct Element2 *next; };

50 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言語版その１ */ /* 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言語版その２ */ /* 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

51 // リストのデータ構造 // 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言語版その１ */ struct Element1 { int data; struct Element1 *next; }; // リストのデータ構造 // Java言語でアクセッサなし public class Element2 { public Element2() } public int data; public Element2 next; /* リストのデータ構造 */ /* C言語版その２ */ struct Element2 { int *data; struct Element2 *next; };

52 Element1のインスタンス Element1のインスタンス Element2のインスタンス Element2のインスタンス
// リストのデータ構造 // Java言語でアクセッサあり // Element1 next_element1; // どこかで与えられている Element1 new_element1; new_element1 = new Element1(100); new_element1. setNextElement(next_element1); 100 /* リストのデータ構造 *//* C言語版その１ */ /* 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() １００ 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言語版その２ */ /* 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のインスタンス １００ next new_element2 Element2のインスタンス data next next_element2

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

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