データ構造とアルゴリズム論

データ構造とアルゴリズム論
第８章連結リスト
平成27年7月3日
森田彦
理解度チェック1（問題１）
空欄①に入る適切な式は次のいずれですか？
１．n＜2
４．n＞=2
２． n＜=2
５． n＞2
３． n==2
理解度チェック1 解答
空欄①に入るのは次のいずれですか？適切なもの
を選択して下さい。
１．n＜2
２． n＜=2
３． n==2
４．n＞=2
５． n＞2
 プログラムより、条件①が満たされたとき、フィボ
ナッチ数列Fnの値が１となっている。
 フィボナッチ数列の定義より、値が１となるのは
F1とF2の場合。
 したがって、n≦2がその条件。
理解度チェック2（問題2）
空欄②に入る適切な式は次のいずれですか？
１．n<2
４．n>=2
２． n<=2
５． n>2
３． n==2
理解度チェック2 解答
空欄①に入るのは次のいずれですか？適切なもの
を選択して下さい。
１．n＜2
２． N<=2
３． n==2
４．N<=2
５． n＞2
 プログラムより、条件①が満たされたとき、フィボ
ナッチ数列Fnが次の式で求められてる。
Fn=Fn-2+Fn-1
 （フィボナッチ数列の定義により）これは、n≧3の時
に可能。
 したがって、上の選択肢の中では、n>2が該当。
本章（本日）の学習のねらい
① 変数の保管（記憶）場所である、参照（アドレ
ス）の概念を理解する。→8-1節
② 連結リストの概念を理解する。→8-2・3節
③ 連結リストに関する基本操作（挿入、削除）の
プログラミング（の仕方）を学習する。
→8-4・5節
参照とは？
→ コンピュータ・メモリ
変数の保管場所
１
25
２ 15.5
変数A
変数B
３
true
４
メモリ上の
記憶位置
↓
変数C
５
６
７
８
９
１０
１１
１２
アドレス
オブジェクトAの記憶領域
１３
オブジェク１４
１５
１６
参照
トA
参照を保管する変数 →
↓
参照型変数
オブジェクト名や配列名など
変数「オブジェクトA」の
中身→9番地
連結リストとは？
クラス
フィールドの一つが“参照（型変数）”である場合を
考える。
データ
参照
参照は他の変数のアドレスを指定できる。
データ１
データ３
データ２
参照によってつながれたリスト
連結リスト
要素（セル）の挿入・削除が容易
配列要素の挿入
[１]
[２]
[３]
[４]
[５]
Ａデータ１データ２データ３データ４データ５
A[4]にデータXを挿入する。
１．A[6]を用意する。
２．「データ５」をA[6]へ移動。
３．「データ４」をA[５]へ移動。
４．「データX」をA[４]へ代入。
[１]
[２]
[３]
[４]
[５]
[６]
Ａデータ１データ２データ３データX
データ４データ４
データ５データ５
挿入位置以降の要素をずらす必要がある！
連結リストの場合
D1
D2
D3
D4
D5
※「データ１」はD1と略記
D3の入ったセルの次にDXの入ったセルを挿入。
３．D3セルの参照がDXセルを指すようにする。
２．DXセルの参照がD4セルを指すようにする。
１．「データX」の入ったセルを生成する。
D1
D2
D3
D4
DX
D3セルの参照以外は変更していない！
D5
連結リストの学習ポイント
参照によるセルのつなぎ方
※ 参照の動き（変化）を理解すること
がポイント
本章の学習の流れ
 8-1節 “参照”について
プリントをよく読み、“参照”の概念をよく理解する。次の２点がポイ
ント。
＊参照（値）とは、メモリ上の保管場所（アドレス）である。
＊オブジェクト名は参照型変数である
 8-2節連結リストとは？
＊p.135の説明を良く読む。
＊p.136～137の処理の流れを追って、挿入の容易さを理解する。
 8-3節連結リストの作成
＊p.141～142の連結リスト作成の流れをよく理解する。
＊【基礎課題8-1・2】で実際のプログラミング（の仕方）を理解する。
 8-4節セルの挿入
＊【基礎課題8-3】で挿入操作のプログラミングを行う。
＊【応用課題8-A】が分かれば、理解度OK!
 8-5節セルの削除
p.154の流れをよく理解 →【応用課題8-B】さらに【応用課題8-C】
で理解度チェック
今後の予定
 7/ 3 第８章連結リスト
 7/10 第９章木構造
 7/17 第１０章スタックとキュー
 7/24 第２回テスト&課題最終チェック
プリントをどれだけじっくり読んで理解しているか
がポイント→理解度確認テストでチェック
学習に当たって
 第8章までの基礎課題を全て終了した学
生は、第８章の応用課題を全て提出すれ
ば演習を終えても結構です。
 上の条件を満たしていないのに無断退出
した学生は欠席と見なしますので注意し
て下さい。

Download Report