講義「アルゴリズムとデータ構造」

(1)

講義「アルゴリズムとデータ構造」

第３回基本的なデータ構造（リスト、スタック、キュー）

大学院情報科学研究科情報理工学専攻情報知識ネットワーク研究室

喜田拓也

2019/5/21 講義資料

(2)

今日の内容

抽象データ型とは

基本的なデータ構造（抽象データ型）

リスト：最も基本的なデータ集合の表現

配列／連結リスト／双連結リストによる実装

スタック：積み上げ式のデータ格納方式

キュー：入れた順に取り出せるデータ格納方式ポイント

抽象データ型とその実装

(3)

抽象データ型（ Abstract Data Type ）とは

データ型を，それに適用される一連の操作で抽象的に定めたもの

データ insert

delete find

抽象データ型

データとその操作を抽象データ型でカプセル化することのメリット

• 定められた正しい方法でのみデータがアクセスされる

• 不正な操作からデータを保護することができる

• ユーザはデータ構造の実現方法について知る必要がない

• プログラマは他の部分とは独立して内部を実現することができる

たとえば

Linked list

3

(4)

リストとは？

0個以上の要素を一列にならべたもの

要素 𝐿𝐿

_𝑖𝑖

: 最初から 𝑖𝑖 番目の要素（ 1 ≤ 𝑖𝑖 ≤ 𝑛𝑛 ）

リスト中の場所を指示するための「位置」をもつリストの長さ：要素数 𝑛𝑛

リスト 𝐿𝐿 太郎

二郎

花子

道子

𝐿𝐿

₁

𝐿𝐿

₂

𝐿𝐿

₃

𝐿𝐿

₄

(5)

リストに対する操作

INSERT (𝑥𝑥, 𝑝𝑝, 𝐿𝐿) ：リスト 𝐿𝐿 （要素数 𝑛𝑛 ）の位置 𝑝𝑝 の次の位置に要素 𝑥𝑥 を挿入

DELETE (𝑝𝑝, 𝐿𝐿) : リスト 𝐿𝐿 の位置 𝑝𝑝 の次の要素を削除 FIND (𝑖𝑖 , 𝐿𝐿) : リスト 𝐿𝐿 の 𝑖𝑖 番目のセルの内容を返す LAST (𝐿𝐿) : リスト 𝐿𝐿 の最後のセルの位置を返す

PREVIOUS (𝑝𝑝, 𝐿𝐿) : リスト 𝐿𝐿 において、位置 𝑝𝑝 の１つ前のセルの位置を返す

リスト 𝐿𝐿 太郎

二郎

花子

道子

𝐿𝐿

₁

𝐿𝐿

₂

𝐿𝐿

₃

𝐿𝐿

₄

5

ここで「位置

𝑝𝑝

」

とはメモリ上の

位置を指し示す

ポインタのこと

(6)

ポインタ（ pointer ）ってなに？

セルの位置を示すデータ

機械語レベルではセルの番地とセルの型情報の組

プログラミングにおいては，その値を具体的に知る必要はない 𝐴𝐴

ポインタ 𝑝𝑝 データ 𝑥𝑥

ポインタ p

132 ^値 x

5

C 言語の場合

ポインタ p が指す変数の値を，

*p で取り出せる

変数 x のアドレス（格納場所）は

&x で参照できる

(7)

リストの実装の方策

1. 配列 (array) ：メモリ上の 𝑛𝑛 個の連続領域に格納

2. 連結リスト (linked list) ：ポインタで次の要素の格納領域を指す

3. 双方向連結リスト (doubly linked list) ：２個のポインタで前後を指す 𝐿𝐿

₁

𝐿𝐿

₂

𝐿𝐿

₃

𝐿𝐿

₄

・・・ 𝐿𝐿

_𝑛𝑛

1 2 3 4 𝑛𝑛

𝐿𝐿

₂

・・・ 𝐿𝐿

_𝑛𝑛 ^nul^l

𝐿𝐿

₁

init

^nul^l

𝐿𝐿

₁

𝐿𝐿

₂

・・・ 𝐿𝐿

_𝑛𝑛 ^nul^l

last

7

(8)

typedef struct cell { int element;

struct cell *next;

} cell;

cell *init=NULL; //

空のリスト

void list_add(int x)

{ //

整数要素

x

を先頭へ追加

cell *new=

(cell *)malloc(sizeof(cell));

new->element=x;

new->next=init;

init=new;

}

struct cell {

・・・

}

：構造体

cell

を・・・と定義

typedef

・・・

cell

：・・・をデータタイプ

cell

型

として定義

init

は

cell

型データを指すポインタ型

sizeof(cell)

：

cell

型のデータサイズ（バイト）

malloc(n)

：

n

バイトのメモリーを確保

(cell *)malloc(n)

：確保した

n

バイトの領域を

cell

型データ格納領域とみなす

連結リストによるリストの実装（ C 言語版）

(9)

struct cell *next;

} cell;

cell *init=NULL; //

空のリスト

{ //

整数要素

x

を先頭へ追加

cell *new=

new->element=x;

new->next=init;

init=new;

}

連結リストによるリストの実装（ C 言語版）つづき

9

list_add(5)

を実行すると

① メモリ上に空のセルが作られる

最初に空リストができる

null

init

② そのセルの

element

部分に値

x

が入る

5 ③ ポインタ

init

が指す位置が入る

最初は，どこも指していないことを示す特別な値「

null

」が入っている

5 ^nul _l

④

init

はその新しくできたセルを指す

init 5 ^nul _l

最初に

add

される

要素の場合は

null

(10)

struct cell *next;

} cell;

cell *init=NULL; //

空のリスト

{ //

整数要素

x

を先頭へ追加

cell *new=

new->element=x;

new->next=init;

init=new;

}

連結リストによるリストの実装（ C 言語版）つづき

さらに

list_add(3)

を実行すると

① メモリ上に空のセルが作られる

② そのセルの

element

部分に値

x

が入る

3 ③ ポインタ

init

が指す位置が入る

3 ④

init

はその新しくできたセルを指す

init

5 ^nul _l

nul

(11)

struct cell *prev;

struct cell *next;

} cell;

cell *init=NULL; //

空のリスト

cell *final=NULL;

void list_add(int x) { //

整数要素

x

を先頭へ追加

cell *new=(cell *)malloc(sizeof(cell));

new->element=x;

new->next=init;

new->prev=NULL;

if(init==NULL) final=new;

else init->prev=new;

init=new;

}

双方向連結リストによる実装

cell

型は１つ前のデータを指すポインタ

最後尾のデータを指すポインタ

final

も必要

先頭に追加する場合は１つ前のデータはなし

最初に格納されたデータが最後尾のデータ（

final

が指すデータ

)

となる２つ目以降に格納されたデータは

双方向連結リストによるリストの実装（ C 言語版）

11

(12)

a₀ a₁ ・・・ a_i-1 a_i ・・・ a_n-1 p

a₀ a₁ ・・・ a_i-1 x a_i ・・・ a_n-1

最悪 / 平均

時間計算量は Θ(𝑛𝑛) 配列の場合

a_n-1 null a₁

a₀

init ・・・ a_i-1 a_i ・・・

p

a_n-1 null a₁

a₀

init ・・・ a_i-1 a_i ・・・

x

連結リストの場合

最悪 / 平均時間計算量は Θ(1)

a_n-1 null a₀

init

null ・・・・・・

final

a_i-1 a_i ・・・・・・

init final

双方向連結リストの場合

p

連結リストが得意な処理（挿入の場合）

(13)

a₀ a₁ ・・・ a_i-1 a_i ・・・ a_n-1 p

a₀ a₁ ・・・ a_i-1 a_i+1 ・・・ a_n-1

最悪 / 平均

時間計算量は Θ(𝑛𝑛) 配列の場合

a_n-1 null a_i-1

a₀

init ・・・ a_i a_i+1 ・・・

連結リスト

p

の場合

最悪 / 平均時間計算量は Θ(1)

a_i-1 a_i a_i+1 ・・・・・・

双方向連結リストの場合

p

最悪 / 平均時間計算量は Θ(1)

a_i+1

a_n-1 null a_i-1

a₀

init ・・・ a_i+1 ・・・

・・・・・・

a_i-1 a_i+1 ・・・・・・

・・・・・・

13

連結リストが得意な処理（削除の場合）

(14)

a₀ a₁ ・・・ a_i-1 a_i ・・・ a_n-1

配列の場合

a_n-1 null a_i-1

a₀

init ・・・ a_i a_i+1 ・・・

連結リストの場合

双方向連結リストの場合

a_i+1

FIND(i,L): Θ(1) a LAST(L): Θ(1)

PREVIOUS(p,L): Θ(1)

p

FIND(i,L) LAST(L) PREVIOUS(p,L)

FIND(i,L): Θ(𝑛𝑛) , LAST(L): Θ(𝑛𝑛) , PREVIOUS(p,L): Θ(𝑛𝑛)

p

連続領域であるため

𝑖𝑖

番目の要素や前後の要素に１ステップでアクセス可能

PREVIOUS(p,L) LAST(L)

＝

FIND(i,L)

＝

a null a

init

null ・・・

final

a a ・・・

p

配列が得意な処理（ i 番目の要素へのアクセス）

(15)

メリット

• メモリー確保、解放の時間を節約できる

• メモリー使用量を制御できる

• ガベージコレクションの必要がない

• INSERT 操作が Θ 1 時間でできる

a₁ a₀ a₂ a_n-1 ・・・ a_n-2

2 4 6 1 9 -1 7 ・・・ m-1 5 -1

0 1 2 3 4 5 6 m-3 m-2 m-1

free_init 0 init 3

15

配列によるコンパクトな連結リストの実現方法

連結リストを配列内に配置し，要素が入っていないセルを管理するリストと混在させることで実現する

DELETE は Θ 𝑛𝑛 時間

(16)

要素の挿入、削除がいつも先頭からなされるリスト

基本操作

TOP (𝑆𝑆) スタック 𝑆𝑆 の先頭の位置を返す POP (𝑆𝑆) スタック 𝑆𝑆 の先頭の要素を削除 PUSH (𝑥𝑥, 𝑆𝑆) スタック 𝑆𝑆 の先頭に要素 𝑥𝑥 を挿入

a

₂

PUSH(a

₂

,S)

a

₂

a

₂

POP(S)

TOP(S)

スタック (stack) とは？

LIFO (last-in-first-out)

(17)

a₀ a₁ ・・・ a_i ・・・

i

すべての操作の時間計算量は Θ(1)

配列による実現

a₀ null a_i

top ・・・

連結リストによる実現

すべての操作の時間計算量は Θ(1)

top

S

=TOP(S)

a₀ a₁ ・・・ a_i ・・・

i+1 top

S

^ai+1

PUSH(a_i+1,S) POP(S)

a_i-1 TOP(S)=

a₀ null a_i

top a_i-1 ・・・

a_i+1

PUSH(a_i+1,S) POP(S)

17

スタックの実現法

(18)

基本操作

TOP (𝑄𝑄 ) キュー 𝑄𝑄 の先頭の位置を返す

ENQUEUE (𝑥𝑥, 𝑄𝑄 ) 要素 𝑥𝑥 をキュー 𝑄𝑄 の最後尾に入れる DEQUEUE (𝑄𝑄) 先頭の要素をキュー 𝑄𝑄 から除く

※ 「エンキュー」「デキュー」と読む

キュー（ queue; 待ち行列）とは？

要素の挿入は最後尾、削除は先頭からなされるリスト

FIFO (first-in-first-out)

a₀ a₁ ENQUEUE(aa₂ ₂,Q)

a₀ a₁ a₂ TOP(Q)

DEQUEUE(Q)

(19)

・・・ a₀ ・・・

j

すべての操作の時間計算量は

Θ(1)

配列による実現

a_i null a₀

front ・・・

連結リストによる実現

front

Q

TOP(Q)

ENQUEUE(a_i+1,Q)

a₁ TOP(Q)=

a_i a₀

front a₁ ・・・ a_i+1

ENQUEUE(a_i+1,S)

a_i ・・・

=

(j+i)%n

0 rear n-1

DEQUEUE(Q)

a₁

・・・ a₀ ・・・

front

Q

^ai ・・・

(j+i+1)%n

0 rear n-1

a₁ a_i+1

・・・・・・

(j+1)%n front

a_i ・・・

(j+i+1)%n

0 rear n-1

a₁ a_i+1

j

rear

null rear

a_i

front a₁ ・・・ a_i+1 null rear

DEQUEUE(Q)

すべての操作の時間計算量は

Θ(1)

19

キューの実現法

(20)

𝐴𝐴

₄

𝐴𝐴

₁

𝐴𝐴

₂

𝐴𝐴

₃

講義「アルゴリズムとデータ構造」