情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ
0. プログラム書ける? 講義を聴いているだけで OK? 言語の要素技術を覚えれば OK? 目的のプログラム? 要素技術 データ型 配列 文字列 関数 オブジェクト クラス ポインタ 2
0. プログラム書ける? 講義を聴いているだけで OK? 言語の要素技術を覚えれば OK? 目的のプログラム データ構造? アルゴリズム 要素技術 データ型 配列 文字列 関数 オブジェクト クラス ポインタ 3
0. プログラム書ける? よく使われるデータ構造やアルゴリズムをパターンとして習得し, 目的に応じて使い分ける. どんなプログラムを書けばよいかを考える... プログラムを構成する3 要素を意識する. 入力 ( 内部 ) 処理 出力 プログラム 入力データ 出力データ 4
0. プログラム書ける? プログラムが苦手 と感じる人は... 教科書 ( 入門書 ) やチュートリアルに書かれているサンプルプログラムを書き写す ( 写経 ). コピー & ペーストは駄目! 本 1 冊分のサンプルプログラムを打ち込んでみるべし. いろいろなコンパイルエラーに遭遇しよう. リファレンスの引き方を覚える. その場その場で必要な関数やクラスを調べる能力. 標準関数やライブラリを必ずしも全て覚える必要はない. 5
0. プログラム書ける? 簡単なプログラムが書けるようになったら... 目的に応じたデータ構造を考え, 処理の手順 ( アルゴリズム ) を考える. このデータを扱うならリストで, この問題は要素間に親子関係があるから木構造で デバッガやプロファイラなどのツールを積極的に使う. 統合開発環境は開発者の必携ツール 外部ライブラリ等を調べて使う. 典型的なソースは自分で書かない方がよいこともある. 性能, 信頼性, 汎用性,etc. 6
本日の実験で作るプログラム Federer 11255 Nadal 8845 Murray 8390 Djokovic 7330 ルート Federer 11255 Nadal Murray Djokovic =null 8845 8390 7330 ノードノードノードノード 7
情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ
1. アドレスとポインタ アドレス : メモリ空間内の住所 00 12 0a 7f aa 30 00 17 90 23 90 : 1 byte = = 10010000 8 bits 9
1. アドレスとポインタ アドレス : メモリ空間内の住所 00 00 00 7b (123(10 進数 )) 整数型 a のメモリ領域が確保され, 123 が格納される. : 1 byte int 型 : 4byte のメモリを使用 10
1. アドレスとポインタ 実際に確認してみよう. 11
1. アドレスとポインタ ポインタ : アドレスを格納する 変数 メモリのアドレス メモリに格納された値 int a = 0, b = 0 a 12ff60 0 b 12ff61 0 p( ポインタ ) int *p ( ポインタ p を int 型ポインタとして宣言 ) 12ff60 0 12ff61 0 12ff62??? p = &a ( ポインタ p に変数 a のアドレスを代入 ) 12ff60 0 12ff61 0 12ff62 12ff60 *p = 100 ( ポインタ p が指すアドレスに 100 を格納 ) 12ff60 100 12ff61 0 12ff62 12ff60 b = *p + 1 ( ポインタ p が指すアドレスに格納されている 12ff60 100 12ff61 101 12ff62 12ff60 値に 1 を足した値を変数 b に格納 ) +1 12
1. アドレスとポインタ ポインタ : アドレスを格納する 変数 変数 a, b に格納されている値は? 13
1. アドレスとポインタ int 型のメモリ領域を確保し, その先頭のアドレスをポインタ i に記憶させる. void *malloc( size_t size ): 指定されたバイト分のメモリ領域を確保する. 確保した領域の先頭のアドレスを返す. sizeof 演算子 : 指定されたデータ型のメモリ領域サイズを返す. 14
1. アドレスとポインタ ポインタ : アドレスを格納する変数... データ型毎に区別しなくてもよいのでは? データ型毎にメモリ量が異なる 15
情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ
2. 構造体 構造体 : 様々なデータ ( メンバ ) をまとめて扱うデータ型 12ff58 Member (member 型変数 ) 12ff5c age 12ff60????????? 構造体変数 Memberを宣言すると同時に データ型 memberとして定義 以降 memberをintやcharと同様に使えるようになる 17
2. 構造体 構造体の宣言および利用方法 メンバはピリオド (.) を用いて指定 bob age 12ff58 12ff5c 12ff60??? 100?????? 21 malloc で確保 Bob??? strcpy で格納 18
情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ
3. 構造体とポインタ 構造体を参照するポインタ メンバはアロー演算子 (->) を用いて指定 malloc で確保 john 12ff60 member 394674 age 394678 構造体の最初のアドレスを記憶??? 3946a8??? 50?????? 19 malloc で確保 3946a8 John??? strcpy で格納 20
情報工学実験 II 実験 2 アルゴリズム ( リスト構造とハッシュ ) 実験を始める前に... C 言語を復習しよう 0. プログラム書ける? 1. アドレスとポインタ 2. 構造体 3. 構造体とポインタ
リスト構造 : ノード内に, データ部と次のノードへの参照 ( ポインタ ) を持つデータ構造 Bob 102 Linda Mike John =null 294 105 44 Member (member 型変数 ) 394678 394682 394684 Member (member 型変数 ) 394688 3946a2 abff60 3946a8 102 394684 3946c8 102 abff60 1266fa 3946a8 Bob 3946c8 Linda 22 12 M
リスト構造 : 構造体を宣言 typedef struct Member{ char *; int ; struct Member *; } member;?????????????????? member 型変数 23
リスト構造 : 最初のノード (= ルート ) を作成 member 型ポインタ root: 先頭ノードのアドレスを記憶 ( 始めは ) root??? 24
リスト構造 : 最初のノード (= ルート ) を作成 関数 addmember を実行 ( リスト先頭の と を引数とする ) root リスト先頭の リスト先頭の 関数 addmember (Bob, 102) 25
リスト構造 : 最初のノード (= ルート ) を作成 member 型ポインタ curmember を宣言 root の内容 () をコピー root リスト先頭の リスト先頭の 関数 addmember (Bob, 102) curmember abff60??? 26
リスト構造 : 最初のノード (= ルート ) を作成 member 型ポインタ を宣言 root 関数 addmember (Bob, 102) curmember abff60??? abff61??? 27
リスト構造 : 最初のノード (= ルート ) を作成 関数 createmember を実行 ( リスト先頭の と を引数とする ) root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? abff61??? 28
リスト構造 : 最初のノード (= ルート ) を作成 member 型ポインタ を宣言 メモリ領域を確保 root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? abff61??? 12ff6a?????? 13af62??? 13af63??? 29
リスト構造 : 最初のノード (= ルート ) を作成 と に引数, に をコピー root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? abff61??? 12ff6a??? 13af62 13af63 Bob??? 102?????? 30
リスト構造 : 最初のノード (= ルート ) を作成 関数 createmember の の内容を 関数 addmember の にコピー ( 関数 createmember の処理終了 ) root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? create! abff61??? 12ff6a Bob 13af62 102 13af63 31
リスト構造 : 最初のノード (= ルート ) を作成 curmember が の場合 root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60 abff61 12ff6a??? Bob 13af62 102 13af63 32
root リスト構造 : 最初のノード (= ルート ) を作成 curmember curmemberがの場合 rootにの内容をコピー関数 addmemberの処理終了 = 最初のノード作成完了 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) abff60??? abff61 12ff6a??? Bob 13af62 102 13af63 33
リスト構造 : 最初のノード (= ルート ) を作成 つまり root に関数 createmember で作った構造体の情報が格納 root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? abff61 12ff6a??? Bob 13af62 102 13af63 34
リスト構造 : 最初のノード (= ルート ) を作成 つまり root に関数 createmember で作った構造体の情報が格納 root 関数 addmember (Bob, 102) 関数 createmember (Bob, 102) curmember abff60??? add! Bob abff61 13af62 102 13af63 12ff6a??? Bob 13af62 102 13af63 35
リスト構造 :2 番目のノードを作成 member 型ポインタ curmember を宣言 root の内容 () をコピー root Bob 13af62 102 13af63 関数 addmember (Linda, 294) 関数 createmember (Linda, 294) curmember abff60??? ea9130 733578??? Linda 43f702 294 43f703 36
リスト構造 :2 番目のノードを作成 curmember の (=root の ) が? root Bob 13af62 102 13af63 関数 addmember (Linda, 294) 関数 createmember (Linda, 294) curmember abff60??? ea9130 733578??? Linda 43f702 294 43f703 37
root リスト構造 :2 番目のノードを作成 curmember もし curmemberの(=rootの) がなら curmemberのにの内容をコピー 関数 addmember (Linda, 294) 関数 createmember (Linda, 294) abff60 13af63??? Bob ea9130 13af62 102 13af63 733578??? Linda 43f702 294 43f703 38
リスト構造 :2 番目のノードを作成 つまり 関数 createmember で作った新しい構造体が root に接続 root Bob 13af62 102 13af63 関数 addmember (Linda, 294) 関数 createmember (Linda, 294) curmember abff60??? ea9130 733578??? Linda 43f702 294 43f703 39
リスト構造 :2 番目のノードを作成 つまり 関数 createmember で作った新しい構造体が root に接続 root Bob 13af62 102 13af63 add! Linda 43f702 294 43f703 関数 addmember (Linda, 294) 関数 createmember (Linda, 294) curmember abff60??? ea9130 733578??? Linda 43f702 294 43f703 40
root リスト構造 :3 番目以降のノードを作成 curmember curmemberの(=rootの) が? がになるまでcurMembeを更新 関数 addmember (Mike, 105) 関数 createmember (Mike, 105) abff60??? Bob が じゃない! 13af62 102 create! 132910 3dfd00 13af63 453578 3dfd00??? Linda 3dfd00 Mike 43f702 294 43f703 3dfd01 105 3dfd02 41
root リスト構造 :3 番目以降のノードを作成 curmember curmemberの(=rootの) が? がになるまでcurMembeを更新 関数 addmember の内容 (Mike, 105) をコピー関数 createmember (Mike, 105) abff60??? Bob 13af62 102 132910 3dfd00 13af63 453578 3dfd00??? Linda 3dfd00 Mike 43f702 294 43f703 3dfd01 105 3dfd02 42
root リスト構造 :3 番目以降のノードを作成 curmember curmemberの(=rootの) が? がになるまでcurMembeを更新 関数 addmember の内容が (Mike, 105)!! 関数 createmember (Mike, 105) abff60 Bob 132910 3dfd00 13af62 102 13af63 453578 3dfd00??? Linda 3dfd00 Mike 43f702 294 3dfd01 105 43f703 3dfd02 43
リスト構造 :3 番目以降のノードを作成 curmember の に の内容をコピー root Bob 13af62 102 13af63 Linda 43f702 294 43f703 3dfd00 関数 addmember (Mike, 105) 関数 createmember (Mike, 105) curmember abff60 132910 3dfd00 453578 3dfd00??? 3dfd00 Mike 3dfd01 105 3dfd02 44
リスト構造 :3 番目以降のノードを作成 つまり 関数 createmember で作った新しい構造体がリストの最後に接続 root Bob 13af62 102 13af63 Linda 43f702 294 43f703 3dfd00 関数 addmember (Mike, 105) 関数 createmember (Mike, 105) curmember abff60??? 132910 3dfd00 453578 3dfd00??? 3dfd00 Mike 3dfd01 105 3dfd02 45
root リスト構造 :3 番目以降のノードを作成 curmember つまり 関数 createmember で作った新しい構造体がリストの最後に接続 関数 addmember (Mike, 105) 関数 createmember (Mike, 105) abff60??? Bob 132910 3dfd00 13af62 102 13af63 453578 3dfd00??? Linda 3dfd00 Mike 43f702 294 3dfd01 105 43f703 3dfd00 add! 3dfd02 nam (char 型ポ 3dfd 46 Mik
リスト構造 : ノードを消すとき prevmember-> = curmember-> prevmember ノード 1 のアドレス curmember ノード 2 のアドレス ノード1 ノード2 ノード3 :Bob :102 : ノード23 のアドレス :Linda :294 : ノード3の : アドレス :Mike :105 : 47