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

データ構造とアルゴリズム論
第９章連結リスト
平成15年12月16日
森田彦
第２回目テスト結果
平均点＝65.3 最高点＝100（２名）最低点＝32（１名）
受験生＝１４6名
第２回目テスト結果（平均点=65.3）
40
35
30
度数
25
20
15
10
5
0
30～39
40～49
50～59
60～69
70～79
80～89
90～100
総合成績（テスト平均点＋応用課題数）
最高点＝123 最低点＝34
受験生＝１４6名
総合成績分布（平均＝73.2）
（２回のテストの平均点＋応用課題数）
45
40
35
度数
30
25
20
15
10
5
0
0～49
50～59
60～69
70～79
80～89
応用課題で挽回を！
90～99
100～123
基礎課題提出状況(12/9)
平均提出数=42.8 (全課題数44)
基礎課題提出状況（12/9）
平均提出数=42.8
140
120
度数（人数）
100
80
60
40
20
0
0～20
21～25
26～30
31～35
提出数範囲
87%が41題以上を提出
36～40
41～44
応用課題提出状況（12/9）
平均提出課題数＝9.6
応用課題提出状況（12/9）
平均提出数＝9.6
45
40
35
度数（人数）
30
25
20
15
10
5
0
0
1～5
6～10
11～15
16～20
21～25
提出数範囲
①26題：１名
②25題：1名
③24題：３名
26～30
本章（本日）の学習のねらい
① 変数の保管（記憶）場所である、参照（アドレ
ス）の概念を理解する。
② 連結リストの概念を理解する。
③ 連結リストに関する基本操作（挿入、削除）の
プログラミング（の仕方）を学習する。
参照とは？
→ コンピュータ・メモリ
変数の保管場所
１
２
変数A
変数B
３
４
メモリ上の
記憶位置
↓
変数C
５
６
７
８
９
１０
１１
１２
アドレス
↓
１３
１４
１５
１６
アドレスを保管する変数 →
参照
参照型変数
オブジェクト名や配列名など
連結リストとは？
クラス
フィールドの一つが“参照（型変数）”である場合を
考える。
データ
参照
参照は変数のアドレスを指定できる。
データ１
データ３
データ２
参照によってつながれたリスト
連結リスト
要素（セル）の挿入・削除が容易
配列要素の挿入
（１）
（２）
（３）
（４）
（５）
Ａデータ１データ２データ３データ４データ５
A(4)にデータXを挿入する。
４．「データX」をA(４)へ代入。
２．「データ５」をA(6)へ移動。
１．A(6)を用意する。
３．「データ４」をA(５)へ移動。
（１）
（２）
（３）
（４）
（５）
（６）
Ａデータ１データ２データ３データX
データ４データ５
データ４データ５
挿入位置以降の要素をずらす必要がある！
連結リストの場合
D1
D2
D3
D4
D5
※「データ１」はD1と略記
D3の入ったセルの次にDXの入ったセルを挿入。
３．D3セルの参照がDXセルを指すようにする。
２．DXセルの参照がD4セルを指すようにする。
１．「データX」の入ったセルを生成する。
D1
D2
D3
D4
DX
D3セルの参照以外は変更していない！
D5
連結リストの学習ポイント
 以下の方法を学習する。
① データ（セル）を（メモリ上）に生成する方法
② 参照によるセルのつなぎ方
 参照の動き（変化）を理解することがポイ
ント
本章の学習の流れ
 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：今後の学習のガイダンス＋これまでの応用課題
チェック

Download Report