Microsoft PowerPoint - exp2-02_intro.ppt [互換モード]

Transcription

1 情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ

2 0. プログラム書ける? 講義を聴いているだけで OK? 言語の要素技術を覚えれば OK? 目的のプログラム? 要素技術 データ型 配列 文字列 関数 オブジェクト クラス ポインタ 2

3 0. プログラム書ける? 講義を聴いているだけで OK? 言語の要素技術を覚えれば OK? 目的のプログラム データ構造? アルゴリズム 要素技術 データ型 配列 文字列 関数 オブジェクト クラス ポインタ 3

4 0. プログラム書ける? よく使われるデータ構造やアルゴリズムをパターンとして習得し, 目的に応じて使い分ける. どんなプログラムを書けばよいかを考える... プログラムを構成する3 要素を意識する. 入力 ( 内部 ) 処理 出力 プログラム 入力データ 出力データ 4

5 0. プログラム書ける? プログラムが苦手 と感じる人は... 教科書 ( 入門書 ) やチュートリアルに書かれているサンプルプログラムを書き写す ( 写経 ). コピー & ペーストは駄目! 本 1 冊分のサンプルプログラムを打ち込んでみるべし. いろいろなコンパイルエラーに遭遇しよう. リファレンスの引き方を覚える. その場その場で必要な関数やクラスを調べる能力. 標準関数やライブラリを必ずしも全て覚える必要はない. 5

6 0. プログラム書ける? 簡単なプログラムが書けるようになったら... 目的に応じたデータ構造を考え, 処理の手順 ( アルゴリズム ) を考える. このデータを扱うならリストで, この問題は要素間に親子関係があるから木構造で デバッガやプロファイラなどのツールを積極的に使う. 統合開発環境は開発者の必携ツール 外部ライブラリ等を調べて使う. 典型的なソースは自分で書かない方がよいこともある. 性能, 信頼性, 汎用性,etc. 6

7 本日の実験で作るプログラム Federer Nadal 8845 Murray 8390 Djokovic 7330 ルート Federer Nadal Murray Djokovic =null ノードノードノードノード 7

8 情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ

9 1. アドレスとポインタ アドレス : メモリ空間内の住所 a 7f aa : 1 byte = = bits 9

10 1. アドレスとポインタ アドレス : メモリ空間内の住所 b (123(10 進数 )) 整数型 a のメモリ領域が確保され, 123 が格納される. : 1 byte int 型 : 4byte のメモリを使用 10

11 1. アドレスとポインタ 実際に確認してみよう. 11

12 1. アドレスとポインタ ポインタ : アドレスを格納する 変数 メモリのアドレス メモリに格納された値 int a = 0, b = 0 a 12ff60 0 b 12ff61 0 p( ポインタ ) int *p ( ポインタ p を int 型ポインタとして宣言 ) 12ff ff ff62??? p = &a ( ポインタ p に変数 a のアドレスを代入 ) 12ff ff ff62 12ff60 *p = 100 ( ポインタ p が指すアドレスに 100 を格納 ) 12ff ff ff62 12ff60 b = *p + 1 ( ポインタ p が指すアドレスに格納されている 12ff ff ff62 12ff60 値に 1 を足した値を変数 b に格納 ) +1 12

13 1. アドレスとポインタ ポインタ : アドレスを格納する 変数 変数 a, b に格納されている値は? 13

14 1. アドレスとポインタ int 型のメモリ領域を確保し, その先頭のアドレスをポインタ i に記憶させる. void *malloc( size_t size ): 指定されたバイト分のメモリ領域を確保する. 確保した領域の先頭のアドレスを返す. sizeof 演算子 : 指定されたデータ型のメモリ領域サイズを返す. 14

15 1. アドレスとポインタ ポインタ : アドレスを格納する変数... データ型毎に区別しなくてもよいのでは? データ型毎にメモリ量が異なる 15

16 情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ

17 2. 構造体 構造体 : 様々なデータ ( メンバ ) をまとめて扱うデータ型 12ff58 Member (member 型変数 ) 12ff5c age 12ff60????????? 構造体変数 Memberを宣言すると同時に データ型 memberとして定義 以降 memberをintやcharと同様に使えるようになる 17

18 2. 構造体 構造体の宣言および利用方法 メンバはピリオド (.) を用いて指定 bob age 12ff58 12ff5c 12ff60??? 100?????? 21 malloc で確保 Bob??? strcpy で格納 18

19 情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ

20 3. 構造体とポインタ 構造体を参照するポインタ メンバはアロー演算子 (->) を用いて指定 malloc で確保 john 12ff60 member age 構造体の最初のアドレスを記憶??? 3946a8??? 50?????? 19 malloc で確保 3946a8 John??? strcpy で格納 20

21 情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ

22 リスト構造 : ノード内に, データ部と次のノードへの参照 ( ポインタ ) を持つデータ構造 Bob 102 Linda Mike John =null Member (member 型変数 ) Member (member 型変数 ) a2 abff a c8 102 abff fa 3946a8 Bob 3946c8 Linda M

23 リスト構造 : 構造体を宣言 typedef struct Member{ char *; int ; struct Member *; } member;?????????????????? member 型変数 23

24 リスト構造 : 最初のノード (= ルート ) を作成 member 型ポインタ root: 先頭ノードのアドレスを記憶 ( 始めは ) root??? 24

25 リスト構造 : 最初のノード (= ルート ) を作成 関数 addmember を実行 ( リスト先頭の と を引数とする ) root リスト先頭の リスト先頭の 関数 addmember (Bob, 102) 25

26 リスト構造 : 最初のノード (= ルート ) を作成 member 型ポインタ curmember を宣言 root の内容 () をコピー root リスト先頭の リスト先頭の 関数 addmember (Bob, 102) curmember abff60??? 26

27 リスト構造 : 最初のノード (= ルート ) を作成 member 型ポインタ を宣言 root 関数 addmember (Bob, 102) curmember abff60??? abff61??? 27

28 リスト構造 : 最初のノード (= ルート ) を作成 関数 createmember を実行 ( リスト先頭の と を引数とする ) root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? abff61??? 28

29 リスト構造 : 最初のノード (= ルート ) を作成 member 型ポインタ を宣言 メモリ領域を確保 root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? abff61??? 12ff6a?????? 13af62??? 13af63??? 29

30 リスト構造 : 最初のノード (= ルート ) を作成 と に引数, に をコピー root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? abff61??? 12ff6a??? 13af62 13af63 Bob??? 102?????? 30

31 リスト構造 : 最初のノード (= ルート ) を作成 関数 createmember の の内容を 関数 addmember の にコピー ( 関数 createmember の処理終了 ) root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? create! abff61??? 12ff6a Bob 13af af63 31

32 リスト構造 : 最初のノード (= ルート ) を作成 curmember が の場合 root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60 abff61 12ff6a??? Bob 13af af63 32

33 root リスト構造 : 最初のノード (= ルート ) を作成 curmember curmemberがの場合 rootにの内容をコピー関数 addmemberの処理終了 = 最初のノード作成完了 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) abff60??? abff61 12ff6a??? Bob 13af af63 33

34 リスト構造 : 最初のノード (= ルート ) を作成 つまり root に関数 createmember で作った構造体の情報が格納 root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? abff61 12ff6a??? Bob 13af af63 34

35 リスト構造 : 最初のノード (= ルート ) を作成 つまり root に関数 createmember で作った構造体の情報が格納 root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? add! Bob abff61 13af af63 12ff6a??? Bob 13af af63 35

36 リスト構造 :2 番目のノードを作成 member 型ポインタ curmember を宣言 root の内容 () をコピー root Bob 13af af63 関数 addmember (Linda, 294) 関数 createmember (Linda, 294) curmember abff60??? ea ??? Linda 43f f703 36

37 リスト構造 :2 番目のノードを作成 curmember の (=root の ) が? root Bob 13af af63 関数 addmember (Linda, 294) 関数 createmember (Linda, 294) curmember abff60??? ea ??? Linda 43f f703 37

38 root リスト構造 :2 番目のノードを作成 curmember もし curmemberの(=rootの) がなら curmemberのにの内容をコピー 関数 addmember (Linda, 294) 関数 createmember (Linda, 294) abff60 13af63??? Bob ea af af ??? Linda 43f f703 38

39 リスト構造 :2 番目のノードを作成 つまり 関数 createmember で作った新しい構造体が root に接続 root Bob 13af af63 関数 addmember (Linda, 294) 関数 createmember (Linda, 294) curmember abff60??? ea ??? Linda 43f f703 39

40 リスト構造 :2 番目のノードを作成 つまり 関数 createmember で作った新しい構造体が root に接続 root Bob 13af af63 add! Linda 43f f703 関数 addmember (Linda, 294) 関数 createmember (Linda, 294) curmember abff60??? ea ??? Linda 43f f703 40

41 root リスト構造 :3 番目以降のノードを作成 curmember curmemberの(=rootの) が? がになるまでcurMembeを更新 関数 addmember (Mike, 105) 関数 createmember (Mike, 105) abff60??? Bob が じゃない! 13af create! dfd00 13af dfd00??? Linda 3dfd00 Mike 43f f703 3dfd dfd02 41

42 root リスト構造 :3 番目以降のノードを作成 curmember curmemberの(=rootの) が? がになるまでcurMembeを更新 関数 addmember の内容 (Mike, 105) をコピー関数 createmember (Mike, 105) abff60??? Bob 13af dfd00 13af dfd00??? Linda 3dfd00 Mike 43f f703 3dfd dfd02 42

43 root リスト構造 :3 番目以降のノードを作成 curmember curmemberの(=rootの) が? がになるまでcurMembeを更新 関数 addmember の内容が (Mike, 105)!! 関数 createmember (Mike, 105) abff60 Bob dfd00 13af af dfd00??? Linda 3dfd00 Mike 43f dfd f703 3dfd02 43

44 リスト構造 :3 番目以降のノードを作成 curmember の に の内容をコピー root Bob 13af af63 Linda 43f f703 3dfd00 関数 addmember (Mike, 105) 関数 createmember (Mike, 105) curmember abff dfd dfd00??? 3dfd00 Mike 3dfd dfd02 44

45 リスト構造 :3 番目以降のノードを作成 つまり 関数 createmember で作った新しい構造体がリストの最後に接続 root Bob 13af af63 Linda 43f f703 3dfd00 関数 addmember (Mike, 105) 関数 createmember (Mike, 105) curmember abff60??? dfd dfd00??? 3dfd00 Mike 3dfd dfd02 45

46 root リスト構造 :3 番目以降のノードを作成 curmember つまり 関数 createmember で作った新しい構造体がリストの最後に接続 関数 addmember (Mike, 105) 関数 createmember (Mike, 105) abff60??? Bob dfd00 13af af dfd00??? Linda 3dfd00 Mike 43f dfd f703 3dfd00 add! 3dfd02 nam (char 型ポ 3dfd 46 Mik

47 リスト構造 : ノードを消すとき prevmember-> = curmember-> prevmember ノード 1 のアドレス curmember ノード 2 のアドレス ノード1 ノード2 ノード3 :Bob :102 : ノード23 のアドレス :Linda :294 : ノード3の : アドレス :Mike :105 : 47