アルゴリズムとデータ構造 第2章 リスト構造 5月24日分 情報知能学科 白井英俊 リストの応用(1) 二重線形リスト構造 • 線形リスト構造：ポインタが一つ 次のようなセルをつなぐことで実現 data next データ部 ポインタ • 二重線形リスト構造：ポインタは二つ prec data next ポインタ データ部 ポインタ 二重線形リスト構造(続) 線形リスト構造 後続のセルだけ、たどることが可能 二重線形リスト構造 後続のセルだけではなく、その前のセルもたどることが可能 リストの応用(2) 木構造 根つき木、もしくは木構造 (1) 頂点と辺とから作られる 頂点： vertex, node, ノード、節点、… 辺： edge, arc, アーク、枝、… 木はグラフの一種。 頂点は 、辺は や で表す (2) 根(root) という特別な頂点がただ一つある 木構造(続) • パス(道):頂点と頂点を結ぶ辺の集合 • 根は特別な頂点 根から、他のどの頂点へも辺をたどっていくことができる • 木とグラフの違い 頂点から別な頂点へのサイクルがない（同じ頂点同士 を結ぶ複数のパスが存在しない） グラフ理論の用語 木とグラフの違い 木： v0 が根。根からはど の頂点へも枝をたどってい ける。同じ頂点への複数の パスはない。 グラフ： 『根』のような特殊な 頂点はない。v0 からv4へは、 v1を通っても、v2を通ってもい ける(複数のパスがある）。 v0 v1 v3 v2 v4 v5 v7 v1 v6 v8 v0 v2 v3 v4 v5 v6 木の用語 v0 • 親と子 (例： v1とv4) v1 2つの頂点が結ばれていると v2 き、上の頂点を親(parent)、 下の頂点を子(son)、という v4 v5 • 兄弟(例：v4とv5) 同じ親を持つ子頂点同士を 兄 弟(brother)、という v7 v3 v6 v8 •最も左の子を、第一子(first child)という ( 例： v1の第一子は v4、v5の第一子はv7 ) •右隣の兄弟を、次の兄弟(next brother)、という( 例： v1の次 の兄弟はv2、v2の次の兄弟はv3 ) •葉（leaf): 子を持たない頂点(例： v2, v3, v4, v7, …) 木の用語の確認 • 試験の頻出問題 v0 右の木の(1)根, (2)v5の兄弟の頂点 すべて、(3)v6の先祖の頂点すべて、 v1 v2 (4)v2の子孫の頂点すべて、(5)葉の v4 頂点すべて、を答えよ v5 v6 定義：頂点xの「先祖」とは、xの親頂 点すべて、およびxの親頂点の先 v9 祖すべて(再帰的な定義） 定義：頂点xの「子孫」とは、xの子頂 点すべて、およびxの子頂点の子 孫すべて(再帰的な定義） v3 v7 v8 v10 木の表現 • 線形リスト構造を、セル(の集まり）で表したよ うに、木構造を次のようなデータ構造（ノード と呼ぶ）で表す class Node def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end end @parent self @firstChild 木の表現(続) クラスNodeを図示すると、次のようになる 頂点 一個一個が以下の構造をもつ @parent 親頂点 label (ラベル） parent (親） self @nextBrother firstChild(第一子） nextBrother(次の兄弟） @firstChild 子頂点 兄弟頂点 練習：木の表現 右の木をNodeクラスを用いて表す それには、7つのNodeインスタ ンスが必要…一つの頂点が一 つのNodeインスタンスに対応 v1 v4 根の頂点 v0 の表現 ラベル v0 親頂点 nil 頂点 v1 第一子 次の兄弟 nil v0 v2 v5 v3 v6 練習：木の表現(続) 根の頂点 v0 の表現 ラベル v0 親頂点 nil v1 第一子 次の兄弟 nil v4 頂点 v1 ラベル v0 v1 親頂点 第一子 次の兄弟 頂点 v2 頂点 v4 v2 v5 v3 v6 練習：木の表現(続) ラベル v0 nil 親頂点 第一子 nil 次の兄弟 ラベル v1 v0 v1 v4 ラベル 親頂点 親頂点 第一子 第一子 次の兄弟 次の兄弟 ラベル v4 親頂点 親頂点 第一子 次の兄弟 ラベル nil 第一子 次の兄弟 v2 v3 v6 v5 v2 v5 練習：木の表現を完成させよう ラベル v0 v0 nil 親頂点 v1 第一子 nil 次の兄弟 ラベル v1 親頂点 第一子 次の兄弟 ラベル v4 親頂点 第一子 次の兄弟 nil v4 v2 v5 ラベル 親頂点 第一子 次の兄弟 v2 ラベル 親頂点 第一子 次の兄弟 v5 nil nil v3 v6 ラベル 親頂点 第一子 次の兄弟 ラベル 親頂点 第一子 次の兄弟 v3 v6
© Copyright 2024 ExpyDoc
