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

データ構造とアルゴリズム論
第８章連結リスト
平成16年12月7日
森田彦
基礎課題提出状況(11/30)
平均提出数=35.7 (全課題数39)
基礎課題提出状況（11/30）　平均＝35.7
120
度数（人数）
100
80
60
40
20
0
6～20
21～25
26～30
31～35
提出課題数
80%が36題以上を提出
36～39
全
基
礎
課
題
提
出
62
%
応用課題提出状況（11/30）
平均提出課題数＝14.1
応用課題提出状況（11/30）　平均=14.1／27
50
45
40
度数（人数）
35
30
25
20
15
10
5
0
0～5
6～10
11～15
16～20
20～25
26～27
提出数
①27題：３名
②25題：1名
③24題：４名
第２回目テストのアナウンス
 日時：12/14 13:15～14:15 （13:10までに
着席しておいて下さい）
 実施形態：ペーパーテスト形式（テスト中
はＰＣを使用できません）
 参照等：テキスト、プリント、自作ノート参
照可
 出題範囲：第５章～第８章まで
 アドバイス：暗記ではなく、処理の流れを
“理解する”事に重点を置いて下さい。
テスト学習のポイント
 問題１ソートのアルゴリズム
バブルソート、選択ソート、挿入ソートの処理の
流れをトレースしておくこと→p.74～75、p.82～
83、p.86～87を（自分で手を動かして）良く確認
しておいて下さい。
 問題２探索のアルゴリズム
線形探索（番兵法）と２分探索のアルゴリズム
（流れ図）をよく理解しておくこと（p.93,p.95～
96,p.101）→具体的なデータを用いて、処理の
流れをトレースしておいて下さい。
テスト学習のポイント
 問題３再帰を応用したプログラム
メソッドの再帰的呼び出しを応用したプログラ
ムの問題。→p.112の処理の流れおよび基礎課
題をよく理解しておいて下さい。
 問題４連結リスト
連結リストの作成やセルの追加の仕方に関す
る理解度を問う問題。本日学習する第８章の
【基礎課題】をよく理解して下さい。→【応用課
題】を解くと、理解度は深まります。
本章（本日）の学習のねらい
① 変数の保管（記憶）場所である、参照（アドレ
ス）の概念を理解する。→8-1節
② 連結リストの概念を理解する。→8-2・3節
③ 連結リストに関する基本操作（挿入、削除）の
プログラミング（の仕方）を学習する。
→8-4・5節
参照とは？
→ コンピュータ・メモリ
変数の保管場所
１
２
変数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
連結リストの学習ポイント
参照によるセルのつなぎ方
※ 参照の動き（変化）を理解すること
がポイント
本章の学習の流れ
 8-1節 “参照”について
プリントをよく読み、“参照”の概念をよく理解する。次の２点がポイ
ント。
＊参照（値）とは、メモリ上の保管場所（アドレス）である。
＊オブジェクト名は参照型変数である
 8-2節連結リストとは？
p.128～129の流れをよく理解する
 8-3節連結リストの作成
p.134～136の流れをよく理解する
【基礎課題8-1・2】で実際のプログラミング（の仕方）を理解する。
 8-4節セルの挿入
【応用課題8-A・B】で理解度チェック
 8-5節セルの削除
p.146の流れをよく理解 →【応用課題8-C】さらに【応用課題8-D】
で理解度チェック
第２回目テストのアナウンス
 日時：12/14 13:15～14:15 （13:10までに
着席しておいて下さい）
 実施形態：ペーパーテスト形式（テスト中
はＰＣを使用できません）
 参照等：テキスト、プリント、自作ノート参
照可
 出題範囲：第５章～第８章まで
 アドバイス：暗記ではなく、処理の流れを
“理解する”事に重点を置いて下さい。

Download Report