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

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

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

2 リスト構造 リスト（線形リスト）構造 リスト(線形リスト）構造の基本単位：セル(Cell) データ部とポインタを持つデータ構造
時にはセルのことを 箱と呼ぶかもしれないが御免！ リスト（線形リスト）構造 データ部とポインタを持つデータ構造 ポインタが１つの場合、このデータ構造が「直線」的に並ぶので、「線形リスト」という リスト(線形リスト）構造の基本単位：セル(Cell) ポインタ データ部：　データの記憶用 ポインタ部：別なセルのアドレス データ部 2

3 リスト構造（教科書p.16) リスト構造 ポインタを持つデータ構造 以下のような Cell (セル)クラスを考え、線形リスト構造を作る：
クラス (Rubyのクラス） 概念図 Cell data データ部 next ポインタ class Cell def　initialize(x,y) @data = x = y end

4 ここには、隣のセルへのポインタ（アドレス）が入っている
線形リストの例 data next data next 青木 石川 ここには、隣のセルへのポインタ（アドレス）が入っている この印は、このセルに続くセルがないことを意味 b = Cell.new(石川, nil ) a = Cell.new(青木, b) nil は、このセルに続くセルがないことを意味 これは次のように書いてよい： a = Cell.new(青木, Cell.new(石川, nil ))

5 リストとセル 例えて言えば、 セルは電車の車両一両 (線形)リストは、車両(セル）が複数個連なった「列車」 他の車両を連結する「連結部」
　　セルは電車の車両一両 他の車両を連結する「連結部」 　　ポインタ データを記憶する場所 (線形)リストは、車両(セル）が複数個連なった「列車」

6 線形リストの特徴 data データ部 next ポインタ 後ろのセルの ポインタ
リストは「セル」が「つながって」できている この「つながり」は、次によって実現： 　　　前のセルの「ポインタ部」に「後ろのセルへのポインタ（アドレス）」が入っている このセルの後にどんなセルがあるかは分かるが、このセルの前にどんなセルがあるかは分からない Cell data データ部 next ポインタ 後ろのセルの ポインタ

7 クラスCellにメソッドを追加する Ｃｅｌｌをつないだり、後続のCellにアクセスしたり、書き替えたりできるよう、Cellのクラス定義に、インスタンスメソッドを追加する アクセス(access)＝(主に)値をとりだす ここではCellのメソッドが『リストに対する関数(メソッド）」を兼ねる ものとして考えていく クラス (Rubyのクラス） 概念図 Cell data データ部 next ポインタ class Cell def　initialize(x,y) @data = x = y end 　 attr_accessor :data, :next

8 クラスCellにメソッドを追加する（続)
「このメソッドが適用されたセル」とは、例えば、x.get(2)の場合、 xの値のセルのこと Cellに３つのインスタンスメソッドを付け加える: get(n) : このメソッドが適用されたセルから数えてn番目のセルを返す(get) insert(n, content) :このメソッドが適用されたセルから数えて n 番目のセルの前に、contentをデータ部にもつセルを挿入(insert) delete(n) :このメソッドが適用されたセルから数えてn番目のセルを削除する(delete)

9 １ ２ クラスCellにgetメソッドを追加 “b” x “a” “b” “c”
get(n) :このメソッドが適用されたセルから数えてn番目のセル（へのポインタ）を返す 例：　x.get(1) => data next “b” 要するに　x.next と同じ １ ２ data next data next data next x “a” “b” “c” 解説：　たとえて言えば、この例においてｘは3両編成の電車を指している。 先頭の車両を「０」号車、2番目の車両を「１」号車、などとする。 ここでは　x.get(n)　により　「ｎ」号車（へのポインタ）を返したい。

10 １ ２ クラスCellのgetメソッド x x “a” “b” “c” 下の例では、 x.get(0) ⇒ x.get(1) ⇒
「“a”をdataにもつセル 」、つまりxそれ自体 (self) 「“b”をdataにもつセル 」、つまり　x.next 「“c”をdataにもつセル 」、　x.next.next (後ろのセルがない） nil １ ２ data next data next data next x x “a” “b” “c”

11 クラスCellにgetメソッドを追加 class Cell def initialize(x,y) @data = x @next = y
end # def attr_accessor :data, :next def get(n) return self if (n <= 0) if != nil) return @next.get(n-1) else return nil end # if end #def end # class 既に定義済み n=0なら呼ばれたセル自身（self)を返す follower 　# 後ろのセル if (follower != nil) return follower.get(n-1) else return nil end # if n>0　かつ 後続のセルがある場合 再帰！次のセルから見て 今見ているセルからn番目に あるセルは、「その後ろのセル」 からみれば、n-1番目のセル

12 クラスCellのgetメソッドの検証 “b” “c” “a” x c b
c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) # getの検証 p x.get(0) p x.get(1) p x.get(2) class Cell def get(n) return self if (n <= 0) if != nil) return @next.get(n-1) else return nil end # if end #def end n = 0 =x (= self) next n = 1 =b.get(0) =b n = 2 = b.get(1) “a” “b” “c” data next = c.get(0) = c x c b

13 クラスCellにinsertメソッドを追加
insert(n, content) :このメソッドが適用されたセルから数えて n 番目のセルの前に、contentをデータ部にもつセルを挿入(insert)する １ ２ data next data next data next “a” “b” “c” x この時、x.insert(2,”d”)を実行すると data next “d” となるようにできればよい それには、　(1) n-1番目のセルを見つける、 (2)新しいセルを作る、(3)ポインタを正しく設定する、ことができればよい

14 クラスCellにinsertメソッドを追加
class Cell def initialize(x,y) @data = x @next = y end # def attr_accessor :data, :next def get(n) …. end def insert(n, cont) if (n == 1) @next = else # n > 1 と仮定 @next.insert(n - 1, cont) end # if end #def end # class 既に定義済み follower 　# 後ろのセル if (n == 1) return @next = Cell.new(cont, follower) else # n>1 を仮定 return follower.insert(n-1, cont) end # if ここにはちょっと問題がある 本当は値のチェックをすることが必要。 今見ているセルからn番目に あるセルは、「その後ろのセル」 からみれば、n-1番目のセル

15 クラスCellのinsertメソッドの検証
c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) xからみて2番目のセルの前に“ｄ”をデータ部にもつセルを作って挿入する x.insert(2, “d”) def insert(n, cont) if (n == 1) @next = else # n > 1 と仮定 @next.insert(n - 1, cont) end # if end #def n =2 “d” next next n =1 ｂからみて１番目のセルの前に挿入 b.insert(1,”d”) “d” next data next data next data next data next 2 1 3 “a” 1 2 x “b” “c” ｂ c

16 １ ２ 0番目のセルの前にinsert? “b” “c” “d”
insert(n, content) :このメソッドが適用されたセルから数えて n 番目のセルの前に、contentをデータ部にもつセルを挿入(insert)する １ ２ data next data next data next “a” “b” “c” x この時、x.insert(0,”d”)を実行すると data next “d” となるようにしなければならない それには、セルの値を書き変えのではなく、 変数ｘの値を書き変える必要がある⇒これはインスタンスメソッドではできない！

17 リスト構造とポインタの話… b リスト構造は基本的なデータ構造 Rubyの配列は、リスト構造で作られている Prologの配列もリスト構造
　 例: [a, b] は2つのセルがつながっている 　[a, b] = [a | [b] ] = [a | [b | [] ] ] 応用は広い：　これから述べる木構造やネットワークも、リスト構造が基本 この話は「人工知能プログラミング」を履修している人向けのもの ｜はセルの間の仕切り nil に相当するのがPrologでは[ ] a b

18 リスト構造とポインタ(続) x “a” ポインタとは、それが指しているオブジェクトが計算機のメモリ中に置かれているアドレス(場所）
Rubyでは、ポインタは、それが指しているオブジェクトと同一視される だから、x.data は ”a”を、x.next はそのポインタが指しているオブジェクトとみなせる。 x data next “a”

19 リスト構造とポインタ(続) 変数(インスタンス変数も含む)の使われ方は二通り：代入と参照
= 代入：変数の値の 書き換えー別なポインタで書き変わる 参照：変数の値 が取り出される 練習問題(どこがポインタの参照と代入か？） (1) x.next = x.next.next (2) y[3] = y[1]

20 リスト構造とポインタ(問題解答) x “b” 練習問題(どこがポインタの参照と代入か？） (1) x.next = x.next.next
(2) y[3] = y[1] えっ、と思ったかもしれない。(1)は次のような状況を想定していた： 左辺でも右辺でもx は参照。ただし、左辺のx.next は代入。右辺はすべて参照 x “a” “b” data next そして(2)は次のような状況を想定していた： y = [1,2,3,4,5] 左辺でも右辺でも y は参照。ただし、 y[3] は代入、y[1]は参照

21 リスト構造とポインタ（補足) 変数（例えば var）の値がポインタの場合、 var . メソッド もしくは var . メソッド(引数…)
　によって、ポインタが指しているオブジェクトに対しメソッドが呼び出される だから、 var = [1, 2, 3] の場合 var.size も　　[1, 2, 3].size も同じ結果を返す これが、insert メソッドの定義で　 @next.insert(n - 1, cont) が行っていること

22 クラスCellにdeleteメソッドを追加
delete(n) :このメソッドが適用されたセルから数えてn番目のセルを削除する(delete) 変数aの値が以下のような連結リストへのポインタとする： x ２ ３ １ data next data next data next data next “a” “b” “d” “c” x.delete(2)　を実行すると となるようにできればよい

23 deleteメソッドの動き ３ ２ １ ２ x “b” “c” “d” 先の結果を書き直すと x.delete(2)の結果は： “a”
２ １ x “a” “b” “c” ２ “d” 元のリストの3番目が2番目のセルになる。 元の2番目の要素は消えたわけではない。 が、リストの先頭からはアクセス(接近)不能＝削除！

24 クラスCellにdeleteメソッドを追加
class Cell def initialize(x,y) @data = x　　 @next = y end # def attr_accessor :data, :next def get(n) …. end 　　def insert(n,cont) … end def delete(n) if (n == 1) @next else # n > 1 と仮定 @next.delete(n - 1) end # if end #def end # class 既に定義済み follower 　# 後ろのセル if (n == 1) return @next = follower.next else # n>1 を仮定 return follower.delete(n-1) end # if ここにはちょっと問題がある 値のチェックをすることが必要。 今見ているセルからn番目に あるセルは、「その後ろのセル」 からみれば、n-1番目のセル

25 クラスCellのdeleteメソッドの検証
c = Cell.new(“c”, nil) ; d = Cell.new(“d”, c) b = Cell.new("b", c) ; x = Cell.new("a", b) x.delete(2) def delete(n) if (n == 1) @next else # n > 1 と仮定 @next.delete(n - 1) end # if end #def n =2 ｂからみて１番目のセルを削除 n =1 b.delete(1) data next data next data next data next 1 2 x “a” “b” 1 “d” “c” 2 ｂ d c

26 リスト構造の練習問題 リストがCellによって表わされているとする。 問題1. リストの最後のCellを返すメソッド last をCellに付け加えよ。 使用例: x.last data next data next data next x “a” “b” “c” 要するに、リストxの最後のCell へのポインタを返す

27 クラスCellのlastメソッド x “b” “c” “a” c b
考え方： 　c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) によって下図のリスト構造が作られたとする。 　x.last の結果は c （の値であるポインタが指しているセル)である。ポインタを順々にたどっていって(x, b, c)、それがリストの最後かどうかは がnilかどうかで判断 最後でなければ、「次のセルから始まるリストの最後」を返せばよい (x.last = b.last ) data next data next data next x “a” “b” “c” c b

28 リスト構造の練習問題 x “b” “c” y “d” “e”
リストがCellによって表わされているとする。 問題2．二つのリストをつなぎ合わせるメソッド concatをCellに付け加えよ。 使用例： x.concat(y) data next data next data next x “a” “b” “c” 要するに、リストxの最後のCell のポインタの値をnilからｙの値に 変える y “d” “e”

29 concatメソッド x “b” “c” y “d” “e”
二つのリストをつなぎ合わせるメソッド concat 使用例： x.concat(y) やりたいのは、 ここの値をyの値（ポインタ） にすること x.last 問題１の結果から data next data next data next x “a” “b” “c” y “d” “e”

30 リスト構造の練習問題 リストがCellによって表わされているとする。 問題3．リストのデータ部を要素に持つ配列を返すメソッド elements をCellに付け加えよ。 使用例: x.elements ⇒ [“a”, “b”, “c”] data next data next data next x “a” “b” “c” ヒント：x.elementsは、xのセルの「後ろのセル」のelementsの結果 に、xのセルのデータ部をつけ加えたもの ただし、xの値がnilの場合は空配列 [ ] を返す

31 リスト構造の練習問題 リストがCellによって表わされているとする。 問題4(やや難)．リストの順番が逆順になるようにポインタをつなぎかえるメソッドreverseをCellに付け加えよ。 使用例: z=x.reverese data next data next data next x “a” “b” “c” z

32 宿題（締め切りは５月１７日） c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) Cellクラスにlast, concat, elements,reverseメソッドを加える lastメソッド：　(引数なし）リストの最後のセルを返す。 　例：　x.last ⇒　cの値となっているセル concatメソッド: (引数は一つ）リストを接合する 　例: xとyがセルのインスタンスとする。x.concat(ｙ) ⇒　ｘのセルの後ろにセルｙ（から始まるリスト）がつながる elemetsメソッド： (引数なし）このメソッドが適用されたセルから始まるリストのデータ部を要素とする配列を返す。 　例：x.elements ⇒ [“a”, ”b”, ”c”] （難）reverseメソッド： (引数なし）リストの順番を逆にする 　例：x.reverse ⇒ 先頭が”c”、最後が”a”をdata部にもつリストとなる

33 リストの実現のための別な方法 “b” x “b” 今見てきた方法だと、1番目の要素の削除や、1番目に要素を挿入するのは、難しい
それに対し、次の方法は、分かりやすい方法 　⇒　先頭にいつもダミー（データ記憶には使わな いセル）を置く方法 今までのリスト： x “a” “b” 新方法のリスト： contents x “a” “b”

34 リストの実現のための別な方法(続) ダミーセルの値を書き換えることで、 次を実現するプログラムが容易に書ける
　(1) xの1番目のセルとして新たな要素を挿入 　　 ｘ.contents = Cell.new(新たな要素,ｘ.contents) 　(2) 1番目のセルを削除 　　　　ｘ.contents =ｘ.contents.next

35 リストの実現のための別な方法(続) 先のCellクラスに加えて、新たにリスト構造を表すためのデータ構造（クラス）をNCellとする
class NCell def initialize(lst) @contents = lst end attr_accessor :contents 　使用例： ここでダミーセルを作っている c = Cell.new(“c”, nil) ;b = Cell.new("b", c) a = Cell.new("a", b) ; x = NCell.new(a)

36 練習問題 このように定義したNCellクラスに、４つのインスタンスメソッドを付け加える: ［注] 必要ならCellの定義も書き変えよ
get(n) :リストのn番目のセルを返す。ただし、先頭のセルを0番目、その次は1番目、等とする。 insert(n, content) :リストのn 番目のセルの前に、contentをデータ部にもつセルを挿入する。n=0の時は先頭のセルの「前に」挿入する。 delete(n) :リストのn番目のセルを削除する。n=0の時は先頭のセルを削除する。 size ：　引数なし。リストを構成している（リストにつながっている）セルの個数（ただしダミーセルは無視する）を返す。

37 3 1 2 参考：NCellを用いたリスト構造 x “c” “b” “d” “e”
w = Cell.new(“c”, nil) ; y = Cell.new("b", w) z = Cell.new("a", y) ; x = NCell.new(z) contents 3 1 x “c” “a” “b” = z = w x.get(0) x.get(1) = y x.get(2) 2 x.insert(0, “d”) “d” “e” x.insert(2, “e”) x.delete(0) x.delete(2) x.size = 3

38 ちょっとbreak ここまでで質問はありますか？

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

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

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

42 木構造(続) 根は特別な頂点 根から、他のどの頂点へも辺をたどっていくことができる。これを『パス(道)』という。 木とグラフの違い
　根から、他のどの頂点へも辺をたどっていくことができる。これを『パス(道)』という。 木とグラフの違い 　　頂点から別な頂点へのサイクルがない（頂点へ至る複数のパスが存在しない）

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

44 木の用語 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, …)

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

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

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

48 練習：木の表現(続) 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

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

50 練習：木の表現を完成させよう 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 第一子 次の兄弟