アルゴリズムとデータ構造
第2章 リスト構造
5月20日分
情報知能学科
白井英俊
リスト構造
• リスト（線形リスト）構造
時にはセルのことを
箱と呼ぶかもしれないが御免！
データ部とポインタを持つデータ構造
ポインタが１つの場合、このデータ構造が「直
線」的に並ぶので、「線形リスト」という
• リスト(線形リスト）構造の基本単位：セル(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
data
next
データ部
ポインタ
後ろのセルの
ポインタ
クラスCellにメソッドを追加する
• Ｃｅｌｌをつないだり、後続のCellにアクセスしたり、書
き替えたりできるよう、Cellのクラス定義に、インスタ
アクセス(access)＝(主に)値をとりだす
ンスメソッドを追加する
ここでは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”
0
x
data
“a”
next
１ data
“b”
next
２
x.next と同じ
data
next
“c”
解説： たとえて言えば、この例においてｘは3両編成の電車を指している。
先頭の車両を「０」号車、2番目の車両を「１」号車、などとする。
ここでは x.get(n) により 「ｎ」号車（へのポインタ）を返したい。
クラスCellのgetメソッド
下の例では、
x.get(0)
x.get(1)
x.get(2)
x.get(3)
0
x
⇒ 「“a”をdataにもつセル 」、つまりxそれ自体 (self)
⇒ 「“b”をdataにもつセル 」、つまり x.next
⇒ 「“c”をdataにもつセル 」、 x.next.next
⇒ (後ろのセルがない） nil
data
“a”
next
１ data
“b”
next
２
data
“c”
next
クラスCellにgetメソッドを追加
class Cell
def initialize(x,y)
@data = x
既に定義済み
@next = y
end # def
n=0なら呼ばれたセ
attr_accessor :data, :next
ル自身（self)を返す
def get(n)
return self if (n <= 0)
follower
@next
if (@next= !=
nil) # 後ろのセル
n>0 かつ 後続のセ
if (follower != nil)
ルがある場合
return
@next.get(n-1)
return
follower.get(n-1)
else
else
再帰！次のセルから見て
return
nil nil
return
end
n-1番目のセルを返す。
end# #ifif
今見ているセルからn番目に@next が次のセルを与え
end #def
る。
あるセルは、「その後ろのセル」
end # class
からみれば、n-1番目のセル
クラス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
n=0
n=1
n=2
data
class Cell
def get(n)
return self if (n <= 0)
if (@next
next != nil)
return @next.get(n-1)
else
return nil
end # if
end #def
end
next
data
next
data next
“a”
b
“b
”
“c”
c
クラスCellにinsertメソッドを追加
• insert(n, content) :このメソッドが適用されたセ
ルから数えて n 番目のセルの前に、contentを
データ部にもつセルを挿入(insert)する
0
x
data
next
１ data
“a”
この時、x.insert(2,”d”)を実行すると
となるようにできればよい
next
“b”
２
data
“c”
data
next
“d”
それには、 (1) n-1番目のセルを見つける、
(2)新しいセルを作る、(3)ポインタを正しく設定する、ことができればよい
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)
follower
= @next # 後ろのセル
if (n@next
== 1) = Cell.new(cont, @next)
return @next = Cell.new(cont, follower)
else
# n# n>1
> 1を仮定
と仮定
else
ここにはちょっと問題がある
@next.insert(n
- 1, cont) cont)
return
follower.insert(n-1,
本当は値のチェックをするこ
end# #ifif
end
とが必要。
end #def
今見ているセルからn番目に
end # class
あるセルは、「その後ろのセル」
からみれば、n-1番目のセル
クラスCellのinsertメソッドの検証
c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b)
xからみて2番目のセルの前に“ｄ”をデータ部にもつセルを作って挿入する
x.insert(2, “d”)
n =2
n =1
ｂからみて１番目のセルの前に挿入
b.insert(1,”d”)
“d”
data next
x
“a”
00
ｂ
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
11
“b”
data next
3
2
“c”
c
data next
2
0番目のセルの前にinsert?
• insert(n, content) :このメソッドが適用されたセ
ルから数えて n 番目のセルの前に、contentを
データ部にもつセルを挿入(insert)する
0
x
data
next
１ data
“a”
この時、x.insert(0,”d”)を実行すると
となるようにしなければならない
next
“b”
２
data
next
“c”
data
next
“d”
それには、セルの値を書き変えのではなく、
変数ｘの値を書き変える必要がある⇒これはインスタンスメソッドではできない！
リスト構造とポインタの話…
• リスト構造は基本的なデータ構造
この話は「人工知能プログラミング」を履修している人向けのもの
• Rubyの配列は、リスト構造で作られている
｜はセルの間の仕切り
Prologの配列もリスト構造
例: [a, b] は2つのセルがつながっている
nil に相当するのが
[a, b] = [a | [b] ] = [a | [b | [] ] ]
Prologでは[ ]
a
b
• 応用は広い： これから述べる木構造やネットワーク
も、リスト構造が基本
リスト構造とポインタ(続)
• ポインタとは、それが指しているオブジェクトが計算
機のメモリ中に置かれているアドレス(場所）
data
x
next
“a”
• 上の図では、変数 x の値はセル（オブジェクト）を指
している「ポインタ」
• Rubyでは、ポインタは、それが指しているオブジェク
トと同一視される
• だから、x.data は ”a”を、x.next はそのポインタが指
しているオブジェクトとみなせる。
リスト構造とポインタ(続)
• 変数(インスタンス変数も含む)の使われ方は二通
り：代入と参照
• 例： @next = Cell.new(cont, @next)
代入：変数の値の
書き換えー別なポイ
ンタで書き変わる
参照：変数の値
が取り出される
• 練習問題(どこがポインタの参照と代入か？）
(1) x.next = x.next.next
(2) y[3] = y[1]
リスト構造とポインタ(問題解答)
• 練習問題(どこがポインタの参照と代入か？）
(1) x.next = x.next.next
(2) y[3] = y[1]
えっ、と思ったかもしれない。(1)は次のような状況を想
定していた：
左辺でも右辺でもx は
data
x
“a”
next
data
“b”
next
参照。ただし、左辺の
x.next は代入。右辺は
すべて参照
そして(2)は次のような状況を想定していた：
左辺でも右辺でも y は
y = [1,2,3,4,5]
参照。ただし、 y[3] は
代入、y[1]は参照
リスト構造とポインタ（補足)
• 変数（例えば var）の値がポインタの場合、
var . メソッド もしくは var . メソッド(引数…)
によって、ポインタが指しているオブジェクトに
対しメソッドが呼び出される
だから、 var = [1, 2, 3] の場合
var.size も [1, 2, 3].size も同じ結果を返す
これが、insert メソッドの定義で
@next.insert(n - 1, cont)
が行っていること
クラスCellにdeleteメソッドを追加
• delete(n) :このメソッドが適用されたセルか
ら数えてn番目のセルを削除する(delete)
変数aの値が以下のような連結リストへのポイ
ンタとする：
x
0
data
“a”
next
１
data
next
“b”
２
data
“d”
next
３
data
next
“c”
x.delete(2) を実行すると
となるようにできればよい
deleteメソッドの動き
先の結果を書き直すと x.delete(2)の結果は：
0
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)
follower
= @next # 後ろのセル
if (n@next
== 1) = @next.next
return @next = follower.next
else
# n > #1 n>1
と仮定
else
を仮定
ここにはちょっと問題がある
@next.delete(n
- 1)
return
follower.delete(n-1)
値のチェックをすることが必要。
end
end# #ifif
end #def
今見ているセルからn番目に
あるセルは、「その後ろのセル」
end # class
からみれば、n-1番目のセル
クラス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
“a”
next
00
ｂ
data
11
next
“b”
data
next
“d”
d
2
data
“c”
c
2
next
リスト構造の練習問題
リストがCellによって表わされているとする。
問題1. リストの最後のCellを返すメソッド last をCellに
付け加えよ。
使用例: x.last
data
x
“a”
next
data
“b”
next
data
“c”
要するに、リストxの最後のCell
へのポインタを返す
next
クラスCellのlastメソッド
•
考え方：
c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b)
によって下図のリスト構造が作られたとする。
x.last の結果は c （の値であるポインタが指しているセル)で
ある。ポインタを順々にたどっていって(x, b, c)、それがリスト
の最後かどうかは
@next がnilかどうかで判断
最後でなければ、「次のセルから始まるリストの最後」を返
せばよい (x.last = b.last )
data
x
next
“a”
data
next
“b”
b
data
“c”
c
next
リスト構造の練習問題
リストがCellによって表わされているとする。
問題2．二つのリストをつなぎ合わせるメソッド concat
をCellに付け加えよ。
使用例： x.concat(y)
data
x
y
“a”
“d”
next
data
“b”
“e”
next
data
next
“c”
要するに、リストxの最後のCell
のポインタの値をnilからｙの値に
変える
concatメソッド
二つのリストをつなぎ合わせるメソッド concat
使用例： x.concat(y)
やりたいのは、
問題１の結果から
data
next
ここの値をyの値（ポインタ）
にすること
x.last
data
x
“a”
“b”
y
“d”
“e”
next
data
“c”
next
リスト構造の練習問題
リストがCellによって表わされているとする。
問題3．リストのデータ部を要素に持つ配列を返すメ
ソッド elements をCellに付け加えよ。
使用例: x.elements ⇒ [“a”, “b”, “c”]
data
x
“a”
next
data
“b”
next
data
next
“c”
ヒント：x.elementsは、xのセルの「後ろのセル」のelementsの結果
に、xのセルのデータ部をつけ加えたもの
ただし、xの値がnilの場合は空配列 [ ] を返す
リスト構造の練習問題
リストがCellによって表わされているとする。
問題4(やや難)．リストの順番が逆順になるようにポイ
ンタをつなぎかえるメソッドreverseをCellに付け加え
よ。
使用例: z=x.reverese
data
x
z
“a”
next
data
“b”
next
data
“c”
next
宿題（締め切りは５月１７日）
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部にもつリストと
なる
リストの実現のための別な方法
• 今見てきた方法だと、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
木の用語
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, …)
木の表現
• 線形リスト構造を、セル(の集まり）で表したよ
うに、木構造を次のようなデータ構造（ノード
と呼ぶ）で表す
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
