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

1

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

第３回基本的なデータ構造

（リスト、スタック、キュー）

2

今年度の授業計画

1 2019年4月4日 木曜日 2 喜田 ガイダンス

2 2019年4月9日 火曜日 4 喜田 アルゴリズムと計算量

3 2019年4月11日 木曜日 2 有村 基本的なデータ構造(1) リスト・スタック・キュー 4 2019年4月16日 火曜日 4 有村 基本的なデータ構造(2) ヒープ

5 2019年4月18日 木曜日 2 有村 基本的なデータ構造(3) 再帰アルゴリズム

6 2019年4月23日 火曜日 4 喜田 探索のためのデータ構造(1) 二分探索木・AVL木 7 2019年4月25日 木曜日 2 喜田 探索のためのデータ構造(2) 木の巡回

2019年4月30日 火曜日 祝日

2019年5月2日 木曜日 祝日

8 2019年5月7日 火曜日 4 有村 探索のためのデータ構造(3) 最適二分探索木 9 2019年5月9日 木曜日 2 有村 探索のためのデータ構造(4) ハッシュ

10 2019年5月14日 火曜日 4 喜田 整列のアルゴリズム（１）

11 2019年5月16日 木曜日 2 喜田 整列のアルゴリズム（２）

12 2019年5月21日 火曜日 4 喜田 グラフとネットワークのアルゴリズム（１）

13 2019年5月23日 木曜日 2 喜田 グラフとネットワークのアルゴリズム（２）

出席・試験・成績について

出席

毎回出席簿を付けます

欠席する場合は欠席届を提出してください

様式は工学部学生便覧の最終ページにあります 欠席届の無い場合は無断欠席とみなします

試験

科目最終回（１６回目）に行う予定です 持ち込みは不可です

成績

シラバスの通りです

（授業への参加態度 10 ％，レポート 20 ％，学期末試験 70 ％）

3

ビッグデータ，人工知能，・・・，アルゴリズム

ワトソン君

• IBM

リサーチ

•

クイズ番組で人間に勝利！

• 100

万冊の本を読んで回答

•

人工知能と自然言語，

アルゴリズム，検索の技術で

米国の人気クイズ番組「ジョパディ！」のワトソン君 クイズ王に挑戦中

AlphaGo

• Google DeepMind

が開発したコンピ ュータ囲碁プログラム

• 2015

年

月にプロ囲碁棋士をハン ディなしで破った

• 2017

年

月には世界トップ棋士であ る柯潔（コ・ジェ）に勝利

• DNN

とモンテカルロ木探索

4

screenshot: DeepMind/YouTube

授業で学ぶデータ構造の範囲



機械語のデータ型

 レジスタ値とその番地



基本データ型

 char, int, large int, double,



構造データ型

 配列（ array ），構造体（ struct ）



基本的データ構造

 リスト（ linked list ），スタック（ stack ），待ち行列

（ queue ）



先進的データ構造

 二分探索木（ binary search tree ），平衡探索木

（ balanced search tree ），ハッシュ表（ hash table ）

昔の言語も持って いる型（ C ，

Pascal ） 機械語

（型がない）

最近の言語

（ C++ ， Java, etc. ）

この「アルゴリズムとデー タ構造」で学ぶところ

「プログラミング」

5

データ構造

データ構造とは

セル (cell) の集合にある構造を与えたもの

データを格納する基本単位

Algorithms + Data Structures = Programs

Niklaus Wirth

（二クラウス・ビルト）が書いた本の題名

Niklaus Wirth(1934-)

はスイスの計算機科学者。

コンピュータ言語

の設計者。

１９８４年にチューリング賞受賞。

抽象 データ型 (Abstruct Data Type) とは？

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

データ 操作

Linked List

CREATE INSERT DELETE . . .

•

データ構造（の

）を「抽象データ型」ともいう．

•

データ構造には，「それは何か（

）」と「それをどのように実現す るか？（

）」の二つの面がある．

•

現代的なプログラム言語やライブラリーはこの考え方に基づく．（例：

C++

，

，

などなど）

7 重要

前回の内容 : 第２回 アルゴリズムと計算量

よいアルゴリズムとは？



いろいろな性能

 計算時間

 メモリサイズ

 外部記憶への入出力数

 ネットワークの通信量



ほかの要素

 モジュラリティ Modularity

 再利用可能性 Reusability

 読みやすさ Readability

 移植しやすさ Portability

 ... ここでは，計算時間とメモリサイズで測る

計算時間 メモリサイズ

2016/04/07

9

第 3 回基本データ構造

 今日の内容：



リスト



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



スタック



スタックの応用（再帰呼び出し）



キュー

 ポイント



ポインタを用いたデータ構造



抽象データ型とその実装

リストとは？ （抽象データ型として）

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

12



空リスト：要素を含まないリストのこと



リストの長さ：要素数 n



A

: 最初から i 番目の要素（1 ≦ i ≦ n ）



リスト中の場所を指示するための「位置」をも つ

太 郎

二 郎

花 子

道 子

A

A

A

A

リストA

重要

リストに対する操作

 INSERT(x,p,L) : ^{リスト L （要素数 n ）の位置 p の次}

の位置に要素 x を挿入

 DELETE(p,L) : ^{リスト L の位置 p の次の位置の次}

の要素を削除

 FIND(i,L) : ^{リスト L の i} 番目のセルの内容を返す

 LAST(L) : ^{リスト L} の最後のセルの位置を返す

 PREVIOUS(p,L) : ^{リスト L において、位置 p の１つ}

前のセルの位置を返す

14

リスト

リストとは

要素を０個以上１列に並べたもの

（注意）リストは連結リストを指すことが多い

[

リスト

の実現法

配列

2.

連結リスト

3.

双方向連結リスト

a₀ a₁

・・・

n

個の連続領域に格納

a_n-1 null a₁

a₀

init

・・・

ポインタで次の要素の格納領域を指す

a_n-1 null a₁

a₀

init null

・・・ ・・・

ポインタで前後の要素の格納領域を指す

太 郎

二 郎

花 子

道 子

重要

復習：ポインタとは？



ポインタ （ pointer ）

 セルの位置を示すデータ

 機械語レベルでは、セルの番地そのもの

 プログラミングにおいては、その値を具体的に

知る必要はない。

ポインタは番地

16

ポインタ p

132 ^値 x

5

C 言語の場合

 ポインタ p が指す変数

の値 x を、 x = *p で表す。

 変数 x を指すポインタ p を p = &x で取り出せ る。

レジスタレベルでみた計算機

リスト

リストとは

要素を０個以上１列に並べたもの

（注意）リストは連結リストを指すことが多い

[

リスト

の実現法

配列

2.

連結リスト

3.

双方向連結リスト

a₀ a₁

・・・

n

個の連続領域に格納

a_n-1 null a₁

a₀

init

・・・

ポインタで次の要素の格納領域を指す

ポインタで前後の要素の格納領域を指す

太 郎

二 郎

花 子

道

子

リスト：

 配列 (array) による実装

18

a

a

a

a

配列

個の整数

からなる配列

1.

配列

個の連続領域に格納

a

a

・・・ a

0 1

・・・

n=4

リスト：連結リスト (linked list) による実装



要素を保持する「セル」をポインタでつないで，リストを表す．



途中への挿入削除を効率よくで行える

a_n null a₁

head -1

・・・

・・・

a

a

a

a

セル

の構造体（

言語のコード）

typedef struct _cell { int element;

struct cell *next;

ダミーの セル

先頭

a_i

cell

element next

セル

（箱図）

20

C 言語によるリストの定義 (1/3)

連結リスト

typedef struct cell { int element;

struct cell *next;

} cell;

cell *init=NULL; %

空のリスト

{ %

整数要素

を先頭へ追加

new->element=x;

new->next=init;

init=new;

}

struct cell {

・・・

： 構造体

を・・・と定義

・・・

： ・・・をデータタイプ

型

として定義

init

は

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

sizeof(cell)

：

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

malloc(n)

：

バイトのメモリーを確保

(cell *)malloc(n)

： 確保した

バイトの領域を

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

重要

a_i

cell

要素

element ^cellnext

^{へのポインタ}

C 言語によるリストの定義 (2/3)

typedef struct cell { int element;

struct cell *next;

} cell;

cell *init=NULL; %

空のリスト

{ %

整数要素

を先頭へ追加

new->element=x;

new->next=init;

init=new;

}

init

3 6

NULL

element

領域

next

領域

list_add(5)

を実行すると

①メモリの確保

5

②

の代入

init

3 6

③

に

ポインタ

をコピー

5 init

④

に

ポインタ

をコピー

23

C 言語によるリストの定義 (3/3)

双方向連結リスト

int element;

struct cell *prev;

struct cell *next;

} cell;

cell *init=NULL; %

空のリスト

void list_add(int 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

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

ももつ

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

も必要

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

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

が指すデータ

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

ポインタを新しい先頭データを 指すように更新する

重要

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

INSERT(x,p,L) :

リスト

（要素数

）の位置

の次の位置に要素

を挿入

a₀ a₁

・・・

・・・

a₀ a₁

・・・

・・・

最悪

平均

時間計算量は

配列の場合

p

x

a_n-1 null a₁

a₀

init

・・・

・・・

a_n-1 null a₁

a₀

init

・・・

・・・

連結リスト の場合

最悪

平均時間計算量は

a_n-1 null a₀

init

null

・・・ ・・・

final

a_i-1 a_i

・・・ ・・・

a null a

init

null

・・・

final

a a

・・・

双方向連結リストの場合

重要

考えて みよう

25

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

DELETE(p,L) :

リスト

（要素数

）の位置

の次の位置の次の要素を削除

a₀ a₁

・・・

・・・

a₀ a₁

・・・

・・・

最悪

平均

時間計算量は

配列の場合

a_n-1 null a_i-1

a₀

init

・・・

・・・

連結リスト

の場合

最悪

平均時間計算量は

a_i-1 a_i a_i+1

・・・ ・・・

双方向連結リストの場合

最悪

平均時間計算量は

a_i+1

a_n-1 null a_i-1

a₀

init

・・・

・・・

・・・ ・・・

a_i-1 a_i+1

・・・ ・・・

・・・ ・・・

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

FIND(i,L) :

リスト

（要素数

）の

番目のセルの内容を返す

リスト

（要素数

）の最後のセルの位置を返す

PREVIOUS(p,L) :

リスト

（要素数

）において、位置

の１つ前のセルの位置を返す

a₀ a₁

・・・

・・・

配列の場合

a_n-1 null a_i-1

a₀

init

・・・

・・・

連結リスト の場合

双方向連結リストの場合

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) : Θ(n), LAST(L) : Θ(n), PREVIOUS(p,L) : Θ(n)

p

連続領域であるため

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

PREVIOUS(p,L) LAST(L)

＝

FIND(i,L)

＝

a_n-1 null a₀

init

null

・・・ ・・・

final

a_i-1 a_i

・・・ ・・・

p

＝

27

配列による連結リストの実現

a₁ a₀ a₂ a_n-1

・・・

2 4 6 1 9 -1 7

・・・

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

free_init 0 init 3

メリット

•

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

•

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

•

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

ちょっとむずか しい！

スタックとキュー

特別な（制限された）リストのいろいろ

28

29

スタック (stack)

スタックとは

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

LIFO(last-in-fast-out) [

基本操作

TOP(S)

スタック

の先頭の位置を返す

スタック

の先頭の要素を削除

スタック

の先頭に要素

を挿入

a₀ a₁

a_{2 PUSH(a}

2,S)

a₀ a₁ a₂

a₀ a₁

a₂

POP(S) TOP(S)

重要

スタックの実現法

a₀ a₁

・・・

・・・

i

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

配列による実現

a₀ null a_i

top

・・・

連結リストによる実現

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

top

S

=TOP(S)

a₀ a₁

・・・

・・・

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

・・・

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

重要

31

スタックの応用例（関数呼び出し）

プログラム（階乗

の計算）

int factorial(int n) { if(n==1) return 1;

else return n*factorial(n-1);

}

実行コードシークエンス

1: if n≠1 then goto 3 2: return 1

3: r=factorial(n-1) 4: return n*r

局所変数

実行コード

2:3:

4:

実行アドレス

n 2

1:2:

3:4:

n=3,

戻り

スタック

n 1:2:

3:4:

n=3,

戻り

戻り

n=3,

戻り

スタック

3

3 1:2:

3:4: 4

1

2

n 2

1:2:

3:4: 4

n

factorial(3) factorial(2)

factorial(1)

3

6

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



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



FIFO(fast-in-fast-out) ともいう

[ 基本操作 ]



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



ENQUEUE(x,Q) 要素 x をキュー Q の最後尾に入れる

A 1 , A 2 , . . . , A n

C D E F A B

G H I

重要

33

待ち行列 ( キュー , queue)

待ち行列 ( キュー）とは

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

FIFO(fast-in-fast-out) [

基本操作

TOP(Q)

キュー

の先頭の位置を返す

ENQUEUE(x,Q)

要素

をキュー

の最後尾に入れる

先頭の要素をキュー

から除く

a₀ a₁ ENQUEUE(aa_{2 2},Q)

a₀ a₁ a₂ TOP(Q)

a₀ a₁ a₂

DEQUEUE(Q)

キューの実現法

・・・

・・・

j

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

配列による実現

a_i null a₀

front

・・・

連結リスト による実現

front

Q

TOP(Q)

ENQUEUE(a_i+1,Q)

a₁ TOP(Q)=

a_i a₀

front a₁

・・・

ENQUEUE(a_i+1,S)

a_i

・・・

=

(j+i)%n

0 rear n-1

DEQUEUE(Q)

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

DEQUEUE(Q)

すべての操作の

時間計算量は

A

A

A

A

A

0 1 2 3 4 5

front rear



配列で巡回リストを表わす．



キューの長さ

が限定された場合



先頭と末尾がつながって，輪になったリスト



要素の位置を，

の剰余演算で決定.

配列によるキューの実現

front から i 番目の要素 = Element[ (front + i) mod n ]

Element

ex. Elem[(head + 5) mod n] (head = 1 and n = 6)

= Elem[7 mod 6] = E[1]

35 考えて

みよう