データ構造とアルゴリズム論 第９章 連結リスト

Presentation on theme: "データ構造とアルゴリズム論 第９章 連結リスト"— Presentation transcript:

1 データ構造とアルゴリズム論 第９章 連結リスト
データ構造とアルゴリズム論 第９章　連結リスト 平成15年12月16日 森田　彦

2 第２回目テスト結果 平均点＝65.3　最高点＝100（２名）　最低点＝32（１名）　　受験生＝１４6名

3 総合成績（テスト平均点＋応用課題数） 最高点＝123　最低点＝34　　受験生＝１４6名 応用課題で挽回を！

4 基礎課題提出状況(12/9) 平均提出数=42.8　(全課題数44) 87%が41題以上を提出

5 応用課題提出状況（12/9） 平均提出課題数＝9.6 ①26題：１名　　②25題：1名　　③24題：３名

6 本章（本日）の学習のねらい 変数の保管（記憶）場所である、参照（アドレス）の概念を理解する。 連結リストの概念を理解する。
連結リストに関する基本操作（挿入、削除）のプログラミング（の仕方）を学習する。

7 参照とは？ アドレス 参照 変数の保管場所 → コンピュータ・メモリ メモリ上の記憶位置 ↓ 変数A 変数B 変数C ↓
→　コンピュータ・メモリ メモリ上の記憶位置 ↓ アドレス １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ １５ １６ 変数A 変数B 変数C 　　　↓ 　参照 アドレスを保管する変数　→　参照型変数 オブジェクト名や配列名など

8 連結リストとは？ 連結リスト クラス フィールドの一つが“参照（型変数）”である場合を考える。 データ 参照
参照は変数のアドレスを指定できる。 データ１ データ３ データ２ 参照によってつながれたリスト 連結リスト 要素（セル）の挿入・削除が容易

9 配列要素の挿入 Ａ A(4)にデータXを挿入する。 ４．「データX」をA(４)へ代入。 １．A(6)を用意する。
（１） （２） （３） （４） （５） Ａ データ１ データ２ データ３ データ４ データ５ A(4)にデータXを挿入する。 ４．「データX」をA(４)へ代入。 １．A(6)を用意する。 ２．「データ５」をA(6)へ移動。 ３．「データ４」をA(５)へ移動。 データ１ データ２ データ３ データ４ データ５ （１） （２） （３） （４） （５） （４） データ４ （５） （５） データ５ （６） （６） Ａ データX 挿入位置以降の要素をずらす必要がある！

10 連結リストの場合 D3の入ったセルの次にDXの入ったセルを挿入。 １．「データX」の入ったセルを生成する。
２．DXセルの参照がD4セルを指すようにする。 ３．D3セルの参照がDXセルを指すようにする。 D1 D2 D3 D4 D5 DX D3セルの参照以外は変更していない！

11 連結リストの学習ポイント 以下の方法を学習する。 ① データ（セル）を（メモリ上）に生成する方法 参照の動き（変化）を理解することがポイント
　①　データ（セル）を（メモリ上）に生成する方法 　②　参照によるセルのつなぎ方 参照の動き（変化）を理解することがポイント

12 本章の学習の流れ 9-1節 “参照”について 9-2節 連結リストとは？ 9-3節 連結リストの作成 9-4節 セルの挿入
9-1節　“参照”について 　　プリントをよく読み、“参照”の概念をよく理解する。次の２点がポイント。 　　参照（値）とは、メモリ上の保管場所（アドレス）　である。 　　オブジェクト名は参照型変数である 9-2節　連結リストとは？ 　　p.142～143の流れをよく理解する 9-3節　連結リストの作成 　　p.148～150の流れをよく理解する 　　【応用課題9-A・B】で実際のプログラミング（の仕方）を理解する。 9-4節　セルの挿入 　　【応用課題9-C・D】で理解度チェック 9-5節　セルの削除 　　p.160の流れをよく理解　【応用課題9-E】で理解度チェック　 【自由課題】にもチャレンジしてみて下さい。 1/13：今後の学習のガイダンス＋これまでの応用課題チェック