アルゴリズムとデータ構造

アルゴリズムとデータ構造
第2章リスト構造
5月17日分
情報知能学科
白井英俊
復習：Rubyにおけるクラス定義
• オブジェクト指向
プログラムが扱うデータ（オブジェクト）と、それをど
のように扱うかという手続き（関数）とを「組」として表
す
• クラスーオブジェクトの「種類」
• クラス定義
1) どのようなパーツ（部品）があるかを宣言：インス
タンス変数
2) 手続き（関数)の宣言：インスタンスメソッド
復習：クラスとインスタンス
例題：複素数
複素数は、実部と虚部とからなる。
i は i2 = -1となる虚数
例： 3+2i
クラス名を Complex とする
部品(パーツ)は２つ： 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) 定義されるクラスの名前
注： 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
問題：「出欠レポート」に記入する
問２．右図はサザエ一
家の家系図の一部と
する。
磯野フネ
問1のクラスを用いて、磯野波平、
磯野フネ、フグ田マスオにそれぞ
れ対応するインスタンスが、変数
namihei, hune, masuoの値に
なっているとする
磯野波平
フグ田サザエ
フグ田マスオ
フグ田タラオ
（１）フグ田サザエに対応するインスタンスを作り、それを変数
sazaeの値とせよ。
（２）同様に、フグ田タラオに対応するインスタンスを作り、それを
変数taraoの値とせよ。
Thinking time…
リスト構造
• リスト（線形リスト）構造
データ部とポインタを持つデータ構造
ポインタが１つの場合、このデータ構造が「直
線」的に並ぶので、「線形リスト」という
• リスト(線形リスト）構造の基本単位：セル(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
概念図
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に３つのインスタンスメソッドを付け加える:
(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”
ｂ
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”
ｂ
data
next
“d”
d
data
“c”
c
next
宿題（締め切りは５月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)) ⇒ ｃのセルの後ろにdata
として”e”を持つセルがつながる
• （難）reverseメソッド：リストの順番を逆にする
例：x.reverse ⇒ 先頭が”c”、最後が”a”をdata部にもつリス
トとなる
リストの実現のための別な方法
• 今見てきた方法だと、1番目の要素の削除や、
1番目に要素を挿入するのは、難しい
• それに対し、次の方法は、分かりやすい方法
先頭にいつもダミー（データ記憶には使わな
いセル）を置く方法
⇒
今までのリスト：
新方法
のリスト：
x
x
“a”
“b”
“a”
“b”
contents
リストの実現のための別な方法(続)
• ダミーセルの値を書き換えることで、
次を実現するプログラムが容易に書ける
(1) xの1番目のセルとして新たな要素を挿入
ｘ.contents =
Cell.new(新たな要素,ｘ.contents)
(2) 1番目のセルを削除
ｘ.contents =ｘ.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クラスに、４つのインス
タンスメソッドを付け加える:
［注] 必要なら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

Download Report