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

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

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

2 復習：Rubyにおけるクラス定義 オブジェクト指向
プログラムが扱うデータ（オブジェクト）と、それをどのように扱うかという手続き（関数）とを「組」として表す クラスーオブジェクトの「種類」 クラス定義 1) どのようなパーツ（部品）があるかを宣言：インスタンス変数 　 2) 手続き（関数)の宣言：インスタンスメソッド 2

3 復習：クラスとインスタンス 複素数は、実部と虚部とからなる。 例題：複素数 例： 3+2i クラス名を Complex とする
　　部品(パーツ)は２つ： real (reと略す、実部) 　　　　　　　imaginary (im と略す、虚部) 　すると、 3+2i は Complex.new(3,2)　で生成 i は i2 = -1となる虚数 インスタンス生成

4 クラス定義とインスタンス生成（まとめ） クラス名は大文字
class Complex # 複素数のクラス def initialize(x,y) # = = y end # initialize attr_accessor :re, :im # インスタンス変数へのアクセス # def tasu(z) # 複素数同士の足し算 return + + z.im) end def hiku(z) # 複素数同士の引き算 return - - z.im) end # end # class インスタンスを作る時のメソッド 生成の例： Complex.new(1,2) インスタンス変数は＠つき attr_accessor につづけて インスタンス変数の前にコロン( : ) インスタンス固有のメソッドをクラス定義の中に書く。インスタンス変数を参照・書き換え可能

5 インスタンス・メソッドの使用 x = a.re ⇒ 3.0 a = Complex.new(3.0,2.0)
class Complex # 複素数のクラス def initialize(x,y)　 # インスタンス生成 @re = x @im = y end # initialize attr_accessor :re, :im 　# def tasu(z) # 複素数同士の足し算 return + + z.im) end end # class a = Complex.new(3.0,2.0) initializeメソッドが起動 Complexオブジェクトを生成 re 3.0 im 2.0 x = a.re ⇒ 3.0 b = Complex.new(1.0,-1.0) y = a.tasu(b)

6 インスタンス・メソッドの使用 a = Complex.new(3.0,2.0) b = Complex.new(1.0,-1.0)
re 3.0 im 2.0 class Complex # 複素数のクラス def initialize(x,y)　 # インスタンス生成 @re = x @im = y end # initialize attr_accessor :re, :im 　# def tasu(z) # 複素数同士の足し算 return + + z.im) end end # class a = Complex.new(3.0,2.0) b = Complex.new(1.0,-1.0) y = a.tasu(b) aのtasuメソッドが起動 Complex( ,　 ) の結果をyに代入 比較： b.tasu(a) 結果はほぼ同じだが、起動するメソッドが異なる

7 問題：「出欠レポート」に記入する 問１．以下のクラス定義において以下を答えよ (1) 定義されるクラスの名前
　(1) 定義されるクラスの名前 　(2)部品(インスタンス変数)の名称 すべて (3) これに対する適切なattr_accessor文 注：　femaleは「女性」を表す。「男性」はmaleとする。 class Person def initialize(x,y,u,v,w=“female”) @given_name = x @family_name = y @father = u @mother = v @sex = w end

8 問題：「出欠レポート」に記入する 問２．右図はサザエ一家の家系図の一部とする。
フグ田サザエ フグ田マスオ 磯野フネ 磯野波平 フグ田タラオ 問1のクラスを用いて、磯野波平、磯野フネ、フグ田マスオにそれぞれ対応するインスタンスが、変数namihei, hune, masuoの値になっているとする （１）　フグ田サザエに対応するインスタンスを作り、それを変数 　　sazaeの値とせよ。 （２）　同様に、フグ田タラオに対応するインスタンスを作り、それを 　　変数taraoの値とせよ。

9 Thinking time…

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

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

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

13 クラスCellにメソッドを追加する このままだと単にCellの構造(どんなパーツがあるか）を定義しただけ
クラス (Rubyのクラス） 概念図 Cell data データ部 next ポインタ class Cell def　initialize(x,y) @data = x = y end 　 attr_accessor :data, :next

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

15 クラスCellにgetメソッドを追加 “b” x “b” “c” get(n) :このメソッドが適用されたセルから数えてn番目のセルを返す
例：　x.get(1) => data next “b” 要するに　x.next と同じ このメソッドの書き方に注意！ 「インスタンス．メソッド」 data next data next data next x “a” “b” “c” それでは、x.get(0) は　何を返すべきか？

16 self --- 「自分自身」変数 x get(n) :このメソッドが適用されたセルから数えてn番目のセルを返す
data next 答え: 先頭のセル（0番目のセル） x “a” つまり、x.get(0) は x の値となっているセルを返す---getメソッドが呼び出されたインスタンス自身を返す selfは「インスタンス自身」を値とする変数！

17 クラス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)を返す n>0　かつ 後続のセルがある場合 再帰！次のセルから見て

18 クラス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

19 クラス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” となるようにできればよい

20 クラス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 既に定義済み ここにはちょっと問題がある 値のチェックをすることが必要。

21 クラスCellのinsertメソッドの検証
c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) 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” x “b” “c” ｂ

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”
元のリストの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 既に定義済み ここにはちょっと問題がある 値のチェックをすることが必要。

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 x “a” “b” “d” “c” ｂ d c

26 宿題（締め切りは５月20日正午） Cellクラスにlast, concat, reverseメソッドを加える
c = Cell.new(“c”, nil) ; d = Cell.new(“d”, c) b = Cell.new("b", c) ; x = Cell.new("a", b) Cellクラスにlast, concat, reverseメソッドを加える lastメソッド：　リストの最後のセルを返す。 　例：　x.last ⇒　cの値となっているセル concatメソッド: リストを接合する 　例: x.concat(Cell.new(“e”,nil)) ⇒　ｃのセルの後ろにdataとして”e”を持つセルがつながる （難）reverseメソッド：リストの順番を逆にする 　例：x.reverse ⇒ 先頭が”c”、最後が”a”をdata部にもつリストとなる

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

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

29 リストの実現のための別な方法(続) 先の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)

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

31 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

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

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

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

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

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

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

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

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

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

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

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

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

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