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

データ構造とアルゴリズム論
第８章連結リスト
平成17年12月13日
森田彦
基礎課題提出状況(12/6)
基礎課題提出状況（12/6）　平均=36.5（昨年35.7）　［全課題39題］
全
基
礎
課
'04年度
題
'05年度
提
出
67.6
%
120
100
度数（人数）
80
60
5章以前の課題未提
出 19名
40
20
0
0～19
20～24
25～31
提出数
昨年を上回るペース
32～37
38～39
応用課題提出状況（12/6）
応用課題提出状況（12/6）　平均14.9（昨年14.1）
全課題27題
度数（人数）
昨年を上回るペース
50
45
40
35
30
25
20
15
10
5
0
'04年度
'05年度
0～5
6～10 11～15 16～20 21～25 26～27
提出数
①27題：8名
②26題：5名
③25題：7名
本章（本日）の学習のねらい
① 変数の保管（記憶）場所である、参照（アドレ
ス）の概念を理解する。→8-1節
② 連結リストの概念を理解する。→8-2・3節
③ 連結リストに関する基本操作（挿入、削除）の
プログラミング（の仕方）を学習する。
→8-4・5節
参照とは？
→ コンピュータ・メモリ
変数の保管場所
１
２
変数A
変数B
３
４
メモリ上の
記憶位置
↓
変数C
５
６
７
８
９
１０
１１
１２
アドレス
↓
１３
１４
１５
１６
アドレスを保管する変数 →
参照
参照型変数
オブジェクト名や配列名など
連結リストとは？
クラス
フィールドの一つが“参照（型変数）”である場合を
考える。
データ
参照
参照は変数のアドレスを指定できる。
データ１
データ３
データ２
参照によってつながれたリスト
連結リスト
要素（セル）の挿入・削除が容易
配列要素の挿入
（１）
（２）
（３）
（４）
（５）
Ａデータ１データ２データ３データ４データ５
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.127、130の説明を良く読む。
＊p.128～129の処理の流れを追って、挿入の容易さを理解する。
 8-3節連結リストの作成
＊p.133～134の連結リスト作成の流れをよく理解する。
＊【基礎課題8-1・2】で実際のプログラミング（の仕方）を理解する。
 8-4節セルの挿入
＊【基礎課題8-3】で挿入操作のプログラミングを行う。
＊【応用課題8-A】が分かれば、理解度OK!
 8-5節セルの削除
p.146の流れをよく理解 →【応用課題8-B】さらに【応用課題8-C】
で理解度チェック
第２回目テストのアナウンス
 日時：12/27 13:15～14:15
 実施形態：ペーパーテスト形式（テスト中
はＰＣを使用できません）
 参照等：テキスト、プリント、自作ノート参
照可
 出題範囲：第５章～第９章まで
 アドバイス：暗記ではなく、処理の流れを
“理解する”事に重点を置いて下さい。

Download Report