アルゴリズムとデータ構造 第2章 リスト構造 5月24日分

Presentation on theme: "アルゴリズムとデータ構造 第2章 リスト構造 5月24日分"— Presentation transcript:

1 アルゴリズムとデータ構造 第2章 リスト構造 5月24日分
アルゴリズムとデータ構造 第2章　リスト構造 5月24日分 情報知能学科 白井英俊

2 リストの応用(1) 二重線形リスト構造 線形リスト構造：ポインタが一つ 次のようなセルをつなぐことで実現 二重線形リスト構造：ポインタは二つ
　　次のようなセルをつなぐことで実現 二重線形リスト構造：ポインタは二つ data データ部 next ポインタ prec ポインタ data データ部 next ポインタ

3 二重線形リスト構造(続) 線形リスト構造 二重線形リスト構造 後続のセルだけ、たどることが可能
後続のセルだけではなく、その前のセルもたどることが可能

4 リストの応用(2) 木構造 根つき木、もしくは木構造 (1) 頂点と辺とから作られる 頂点： vertex, node, ノード、節点、…
　(1) 頂点と辺とから作られる 　　頂点： vertex, node, ノード、節点、… 辺： edge, arc, アーク、枝、… 　木はグラフの一種。 頂点は　　、辺は 　や　　　　　　で表す (2) 根(root) という特別な頂点がただ一つある

5 木構造(続) パス(道):頂点と頂点を結ぶ辺の集合 根は特別な頂点 根から、他のどの頂点へも辺をたどっていくことができる 木とグラフの違い
　根から、他のどの頂点へも辺をたどっていくことができる 木とグラフの違い 　　頂点から別な頂点へのサイクルがない（同じ頂点同士を結ぶ複数のパスが存在しない） グラフ理論の用語

6 木とグラフの違い グラフ： 『根』のような特殊な頂点はない。v0 からv4へは、v1を通っても、v2を通ってもいける(複数のパスがある）。

7 木の用語 v0 v1 v3 v2 v4 v6 v5 v8 v7 親と子 (例： v1とv4)
　2つの頂点が結ばれているとき、上の頂点を親(parent)、下の頂点を子(son)、という v1 v3 v2 v4 v6 v5 　兄弟(例：v4とv5) 　同じ親を持つ子頂点同士を兄　弟(brother)、という v8 v7 最も左の子を、第一子(first child)という ( 例： v1の第一子はv4、v5の第一子はv7 ) 右隣の兄弟を、次の兄弟(next brother)、という( 例： v1の次の兄弟はv2、v2の次の兄弟はv3 ) 葉（leaf): 子を持たない頂点(例： v2, v3, v4, v7, …)

8 木の用語の確認 試験の頻出問題 v0 v1 v3 v2 v4 v5 v8 v7 v6 v9 v10
定義：頂点xの「先祖」とは、xの親頂点すべて、およびxの親頂点の先祖すべて(再帰的な定義） 定義：頂点xの「子孫」とは、xの子頂点すべて、およびxの子頂点の子孫すべて(再帰的な定義） v0 v1 v3 v2 v4 v5 v8 v7 v6 v9 v10

9 木の表現 線形リスト構造を、セル(の集まり）で表したように、木構造を次のようなデータ構造（ノードと呼ぶ）で表す class Node
def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end @parent @firstChild self

10 木の表現(続) クラスNodeを図示すると、次のようになる 頂点 親頂点 兄弟頂点 子頂点 label (ラベル） parent (親）
一個一個が以下の構造をもつ 親頂点 label (ラベル） parent (親） firstChild(第一子） nextBrother(次の兄弟） @parent @firstChild self @nextBrother 兄弟頂点 子頂点

11 練習：木の表現 右の木をNodeクラスを用いて表す v0 v1 v3 v2 v4 v6 v5
それには、7つのNodeインスタンスが必要…一つの頂点が一つのNodeインスタンスに対応 v1 v3 v2 v4 v6 v5 根の頂点 v0 の表現 ラベル v0 nil 親頂点 頂点 v1 第一子 nil 次の兄弟

12 練習：木の表現(続) v0 v1 v3 v2 v4 v6 v5 根の頂点 v0 の表現 v0 nil nil 頂点 v1 v1 頂点 v2
ラベル nil 親頂点 v1 v3 第一子 v2 nil 次の兄弟 v4 v6 v5 頂点 v1 ラベル v1 親頂点 第一子 次の兄弟 頂点 v2 頂点 v4

13 練習：木の表現(続) v0 v3 v1 v2 v6 v4 v5 v0 nil nil v1 v2 v4 v5 nil ラベル 親頂点 第一子
次の兄弟 ラベル v1 ラベル v2 親頂点 親頂点 第一子 第一子 次の兄弟 次の兄弟 v4 ラベル v5 ラベル 親頂点 親頂点 nil 第一子 第一子 次の兄弟 次の兄弟

14 練習：木の表現を完成させよう v0 v3 v1 v2 v6 v4 v5 v0 nil nil v1 v2 v3 nil v5 v6 v4
ラベル nil 親頂点 第一子 nil 次の兄弟 ラベル v1 v2 ラベル 親頂点 第一子 次の兄弟 v3 ラベル 親頂点 第一子 次の兄弟 親頂点 nil 第一子 次の兄弟 v5 ラベル 親頂点 第一子 次の兄弟 v6 ラベル 親頂点 第一子 次の兄弟 v4 ラベル nil 親頂点 nil 第一子 次の兄弟