アルゴリズムとデータ構造 第2章 リスト構造 5月17日分 情報知能学科 白井英俊 復習:Rubyにおけるクラス定義 • オブジェクト指向 プログラムが扱うデータ(オブジェクト)と、それをど のように扱うかという手続き(関数)とを「組」として表 す • クラスーオブジェクトの「種類」 • クラス定義 1) どのようなパーツ(部品)があるかを宣言:インス タンス変数 2) 手続き(関数)の宣言:インスタンスメソッド 復習:クラスとインスタンス 例題:複素数 複素数は、実部と虚部とからなる。 i は i2 = -1となる虚数 例: 3+2i クラス名を Complex とする 部品(パーツ)は2つ: real (reと略す、実部) imaginary (im と略す、虚部) すると、 3+2i は Complex.new(3,2) で生成 インスタンス生成 クラス定義とインスタンス生成(まとめ) クラス名は大文字 class Complex # 複素数のクラス def initialize(x,y) # インスタンス生成メソッド インスタンスを作る時のメソッド @re = x 生成の例: Complex.new(1,2) インスタンス変 @im = y 数は@つき end # initialize attr_accessor :re, :im # インスタンス変数へのアクセス # attr_accessor につづけて def tasu(z) # 複素数同士の足し算 インスタンス変数の前にコロン( : ) return Complex.new(@re + z.re, @im + z.im) end インスタンス固有のメソッ def hiku(z) # 複素数同士の引き算 ドをクラス定義の中に書 く。インスタンス変数を参 return Complex.new(@re - z.re, @im - z.im) 照・書き換え可能 end # end # class インスタンス・メソッドの使用 class Complex # 複素数のクラス a = Complex.new(3.0,2.0) def initialize(x,y) # インスタンス生成 initializeメソッドが起動 @re = x Complexオブジェクトを生成 @im = y end # initialize re 3.0 attr_accessor :re, :im im 2.0 # def tasu(z) # 複素数同士の足し算 x = a.re return ⇒ 3.0 Complex.new(@re + z.re, @im + z.im) b = Complex.new(1.0,-1.0) end end # class y = a.tasu(b) re im インスタンス・メソッドの使用 3.0 2.0 a = Complex.new(3.0,2.0) class Complex # 複素数のクラス def initialize(x,y) # インスタンス生成 @re = x b = Complex.new(1.0,-1.0) @im = y end # initialize y = a.tasu(b) attr_accessor :re, :im # aのtasuメソッドが起動 def tasu(z) # 複素数同士の足し算 @reと@imはaの実部/虚部の値 return Complex(3.0+1.0, 2.0-1.0) Complex.new(@re + z.re, @im + z.im) の結果をyに代入 end end # class 比較: b.tasu(a) 結果はほぼ同じだが、起動するメソッドが異なる 問題:「出欠レポート」に記入する 問1.以下のクラス定義において以下を答えよ (1) 定義されるクラスの名前 注: femaleは「女性」 (2)部品(インスタンス変数)の名称 すべて を表す。「男性」は maleとする。 (3) これに対する適切なattr_accessor文 class Person def initialize(x,y,u,v,w=“female”) @given_name = x @family_name = y @father = u @mother = v @sex = w end end 問題:「出欠レポート」に記入する 問2.右図はサザエ一 家の家系図の一部と する。 磯野フネ 問1のクラスを用いて、磯野波平、 磯野フネ、フグ田マスオにそれぞ れ対応するインスタンスが、変数 namihei, hune, masuoの値に なっているとする 磯野波平 フグ田サザエ フグ田マスオ フグ田タラオ (1) フグ田サザエに対応するインスタンスを作り、それを変数 sazaeの値とせよ。 (2) 同様に、フグ田タラオに対応するインスタンスを作り、それを 変数taraoの値とせよ。 Thinking time… リスト構造 • リスト(線形リスト)構造 データ部とポインタを持つデータ構造 ポインタが1つの場合、このデータ構造が「直 線」的に並ぶので、「線形リスト」という • リスト(線形リスト)構造の基本単位:セル(Cell) データ部: データの記憶用 データ部 ポインタ ポインタ部:別なセルのアドレス リスト構造(教科書p.16) • リスト構造 ポインタを持つデータ構造 以下のような Cell (セル)クラスを考え、線形リスト構造を 作る: Cell 概念図 data next データ部 ポインタ クラス (Rubyのクラス) class Cell def initialize(x,y) @data = x @next = y end end 線形リストの例 data next 青木 data 石川 ここには、隣のセルへのポイン タ(アドレス)が入っている b = Cell.new(石川, nil ) a = Cell.new(青木, b) next この印は、このセルに続く セルがないことを意味 nil は、このセルに続くセ ルがないことを意味 これは次のように書いてよい: a = Cell.new(青木, Cell.new(石川, nil )) クラスCellにメソッドを追加する • このままだと単にCellの構造(どんなパーツがある か)を定義しただけ • Cellをつないだり、後続のCellにアクセスしたり、書 き替えたりできるよう、メソッドを追加する Cell 概念図 data next データ部 ポインタ クラス (Rubyのクラス) class Cell def initialize(x,y) @data = x @next = y end attr_accessor :data, :next end クラスCellにメソッドを追加する(続) 「このメソッドが適用されたセル」とは、例えば、x.get(2)の場合、 xの値のセルのこと Cellに3つのインスタンスメソッドを付け加える: (1)get(n) : このメソッドが適用されたセルから数 えてn番目のセルを返す(get) (2)insert(n, content) :このメソッドが適用された セルから数えて n 番目のセルの前に、 contentをデータ部にもつセルを挿入(insert) (3)delete(n) :このメソッドが適用されたセルから 数えてn番目のセルを削除する(delete) クラスCellにgetメソッドを追加 • get(n) :このメソッドが適用されたセルから数 えてn番目のセルを返す data next 例: x.get(1) => “b” 要するに x.next と同じ このメソッドの書き方に注意! 「インスタンス.メソッド」 data x “a” next data next “b” それでは、x.get(0) は 何を返すべきか? data “c” next self --- 「自分自身」変数 • get(n) :このメソッドが適用されたセルから数 えてn番目のセルを返す • x.get(0) は 何を返すべきか? data next 答え: 先頭のセル(0番 x “a” 目のセル) つまり、x.get(0) は x の値となっているセルを返 す---getメソッドが呼び出されたインスタンス自 身を返す selfは「インスタンス自身」を値とする変数! クラス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 (@next != nil) return @next.get(n-1) else return nil end # if end #def end # class 既に定義済み n=0なら呼ばれたセ ル自身(self)を返す n>0 かつ 後続のセ ルがある場合 再帰!次のセルから見て n-1番目のセルを返す。 @next が次のセルを与 える。 クラスCellのgetメソッドの検証 c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) # getの検証 p x.get(0) =x (= self) p x.get(1) =b.get(0) =b p x.get(2) = b.get(1) = c.get(0) = c x class Cell def get(n) n=0 return self if (n <= 0) if (@next next != nil) n=1 return @next.get(n-1) else return nil n=2 end # if end #def end data next data next data next “a” “b” b “c” c クラスCellにinsertメソッドを追加 • insert(n, content) : 先頭のセルから数えて n 番目のセルの前に、contentをデータ部にもつ セルを挿入(insert)する data x next “a” この時、x.insert(2,”d”)を実行すると data next “b” “c” data “d” となるようにできればよい data next next クラス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 = Cell.new(cont, @next) else # n > 1 と仮定 ここにはちょっと問題がある @next.insert(n - 1, cont) 値のチェックをすることが必要。 end # if end #def end # class クラスCellのinsertメソッドの検証 c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) x.insert(2, “d”) n =2 n =1 b.insert(1,”d”) “d” data next x 0 data next 1 “a” “b” b def insert(n, cont) if (n == 1) “d” @next) next = Cell.new(cont, @next next else # n > 1 と仮定 @next.insert(n - 1, cont) next end # if end #def data next 3 “c” data next 2 クラスCellにdeleteメソッドを追加 • delete(n) : 先頭のセルから数えてn番目 のセルを削除する(delete) 変数aの値が以下のような連結リストへのポ インタとする: x data “a” next data next “b” data “d” next data next “c” x.delete(2) を実行すると となるようにできればよい deleteメソッドの動き 先の結果を書き直すと x.delete(2)の結果は: x “a” “b” “c” “d” 元のリストの3番目が2番目のセルになる。 元の2番目の要素は消えたわけではない。 が、リストの先頭からはアクセス(接近)不能=削除! クラス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 = @next.next else # n > 1 と仮定 @next.delete(n - 1) end # if end #def end # class ここにはちょっと問題がある 値のチェックをすることが必要。 クラスCellのdeleteメソッドの検証 c = Cell.new(“c”, nil) ; d = Cell.new(“d”, c) b = Cell.new("b", c) ; x = Cell.new("a", b) def delete(n) if (n == 1) @next = @next.next else # n > 1 と仮定 @next.delete(n - 1) end # if end #def x.delete(2) n =2 n =1 b.delete(1) data x next “a” data next “b” b data next “d” d data “c” c next 宿題(締め切りは5月20日正午) 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)) ⇒ cのセルの後ろにdata として”e”を持つセルがつながる • (難)reverseメソッド:リストの順番を逆にする 例:x.reverse ⇒ 先頭が”c”、最後が”a”をdata部にもつリス トとなる リストの実現のための別な方法 • 今見てきた方法だと、1番目の要素の削除や、 1番目に要素を挿入するのは、難しい • それに対し、次の方法は、分かりやすい方法 先頭にいつもダミー(データ記憶には使わな いセル)を置く方法 ⇒ 今までのリスト: 新方法 のリスト: x x “a” “b” “a” “b” contents リストの実現のための別な方法(続) • ダミーセルの値を書き換えることで、 次を実現するプログラムが容易に書ける (1) xの1番目のセルとして新たな要素を挿入 x.contents = Cell.new(新たな要素,x.contents) (2) 1番目のセルを削除 x.contents =x.contents.next リストの実現のための別な方法(続) • 先のCellクラスに加えて、新たにリスト構造を 表すためのデータ構造(クラス)をNCellとする class NCell ここでダミーセルを作っている def initialize(lst) @contents = lst end attr_accessor :contents end 使用例: c = Cell.new(“c”, nil) ;b = Cell.new("b", c) a = Cell.new("a", b) ; x = NCell.new(a) 練習問題 このように定義したNCellクラスに、4つのインス タンスメソッドを付け加える: [注] 必要ならCellの定義も書き変えよ (1) get(n) : リストにおけるn番目のセルを返す。ただし、リストの 先頭のセルを0番目、その次のセルは1番目、等とする。 (2) insert(n, content) : リストの先頭のセルから数えて n 番目 のセルの前に、contentをデータ部にもつセルを挿入する。 n=0の時は先頭のセルの「前に」挿入する。 (3) delete(n) :リストの先頭のセルから数えてn番目のセルを削 除する。n=0の時は先頭のセルを削除する。 (4) size : 引数なし。リストにおけるセルの数(ダミーセルは無 視する)を返す。 参考:NCellを用いたリスト構造 w = Cell.new(“c”, nil) ; y = Cell.new("b", w) z = Cell.new("a", y) ; x = NCell.new(z) contents x x.get(0) = z 3 “a” 1 “b” “c” x.get(1) = y x.get(2) = w x.insert(0, “d”) “d” x.insert(2, “e”) x.delete(2) x.delete(0) x.size = 3 2 “e” ちょっとbreak • ここまでで質問はありますか? リストの応用(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 木の用語 • 親と子 (例: v1とv4) v1 2つの頂点が結ばれていると き、上の頂点を親(parent)、 下の頂点を子(son)、という v4 • 兄弟(例:v4とv5) 同じ親を持つ子頂点同士を 兄 弟(brother)、という v0 v3 v2 v5 v7 v6 v8 •最も左の子を、第一子(first child)という ( 例: v1の第一子は v4、v5の第一子はv7 ) •右隣の兄弟を、次の兄弟(next brother)、という( 例: v1の次 の兄弟はv2、v2の第一子はv3 ) •葉(leaf): 子を持たない頂点(例: v2, v3, v4, v7, …) 木の表現 • 線形リスト構造を、セル(の集まり)で表したよ うに、木構造を次のようなデータ構造(ノード と呼ぶ)で表す 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 2025 ExpyDoc