PowerPoint プレゼンテーション

基本情報技術概論 I (第4回)
アルゴリズム と データ構造
埼玉大学 理工学研究科
堀山 貴史
1
データ構造

データ構造
 データをどのように記憶するか

基本的なデータ構造
 配列 (array)
 リスト (list)
___________

その他のデータ構造
 スタック (stack)
 待ち行列 (queue, キュー)
 木 (tree)
___________
2
データ構造: ________________
配列

データを順番にならべて、
添字 でアクセスできるようにしたもの
________

操作: 参照、探索、更新、削除、挿入
配列 A
A [1]
30
A [2]
50
A [3]
20
A [4]
70
A [5]
10
…
3
コンピュータ上での配列
配列 A
A [2]
50
A [4]
70
A [5]
10
…
70
10
…
20
30
50
20
A [1, 1] A [1, 2] …
A [2, 1] A [2, 2] …
A [3, 1] A [3, 2] …
…
A [3]
番地
2000
(アドレス) 2001
2002
2003
2004
…
30
…
A [1]
二次元配列
メモリ
(主記憶装置)
一次元に変換して
メモリに配置する
…
…
4
探索キー
配列の操作
(探索データ)
70

参照

探索
A [1]
30
A [2]
50
A [3]
20
70
A [4]
70
10
A [5]
10
A [1]
30
A [2]
50
A [3]
20
A [4]
A [5]
配列Aの
4番は?
…
…
添字を使って指定 … A[4]
先頭 A[1] から順番に
一致するか調べる
5
A[4] の位置に
35 を 挿入
70 を 更新

更新

挿入
A [1]
30
A [1]
30
A [2]
50
A [2]
50
A [3]
20
A [3]
20
A [4]
35
70
A [4]
70
A [5]
10
A [5]
10
…
…
70 を探索 + 更新
35
A[4] の場所を空けるため、
後ろに1つずつずらす
6
A[4] の位置の
データ を 削除

削除
A[4] の位置の
データ を 削除

削除 (その2)
A [1]
30
A [1]
30
A [2]
50
A [2]
50
A [3]
20
A [3]
20
A [4]
70
A [4]
70
A [5]
10
A [5]
10
…
…
A[4] が空いたため、
1つずつつめる
A[4] に削除マークをつけて、
無いものとして扱う
7
データ構造: ________________
リスト

となりの要素の位置(アドレス)を、
ポインタ として明示的に持つ
________
単方向リスト
双方向リスト
環状リスト
head (リストの
先頭を指す)
30
30
30
50
50
50
20
20
20
逆方向の探索が容易
8
コンピュータ上でのリスト
メモリ
(主記憶装置)
2000
2010
50
番地
2010
(アドレス)
30
2070
20
2030
20
0
2070
50
2030
…
…
30
となりの要素の位置(アドレス)を、
ポインタ として明示的に持つ
9
リストの操作

探索
探索キー
(探索データ)

更新
20 を 更新
20
30
30
50
50
20
35
20
70
70
先頭から順番に
ポインタをたどって調べる
20 を探索 + 更新
10
※ 双方向リストの場合は、
逆方向のポインタも
同様にケアする必要あり
リストの操作

挿入
50 の次に
35 を挿入

削除
20 を 削除
30
30
50
50
35
20
20
70
70
前のデータのポインタを、自分に
自分のポインタを、次のデータに
前のデータのポインタを、
次のデータに
11
データ構造

基本的なデータ構造
 配列 (array)
 リスト (list)

その他のデータ構造
 スタック (stack)
 待ち行列 (queue, キュー)
 木 (tree)
12
データ構造: ________________
スタック

push と pop による Last-In First-Out (LIFO)
___________
イメージ) 積み上げた書類や本
生協の入口の トレイ
5
push
pop
30
50
20
13
スタックの実現法
5
push
pop

A [1]
A [2]
A [3]
20
50
30
…
30
50
20
配列
スタック
ポインタ

リスト
30
50
20
14
データ構造: 待ち行列
(キュー)
________________

enqueue と dequeue による First-In First-Out (FIFO)
___________

イメージ) レジの前の行列
5
enqueue
30
50
20
dequeue
15
キューの実現法
5

enqueue
front
A [1]
A [2]
A [3]
20
50
30
rear
…
30
50
20
配列
dequeue  リスト
front
20
rear
50
30
16
練習:



配列を用いたリストの実現
表は、配列を用いたリストの実現を示しており、
リスト [ 東京、品川、名古屋、新大阪 ] を表している。
このリストを、[ 東京、新横浜、名古屋、新大阪 ] に
変化させる操作はどれか。
ここで、A ( i, j ) は、表の第 i 行 第 j 列の要素を表す。
また、→ は代入を表す。
A
列 1
行
1
“東京”
2
“品川”
3 “名古屋”
4 “新大阪”
5 “新横浜”
2
2
3
4
0
17
練習:
ア
イ
ウ
エ
配列を用いたリストの実現
第1の操作
5 → A(1, 2)
5 → A(1, 2)
A(A(1, 2), 2) → A(5, 2)
A(A(2, 2), 2) → A(5, 2)
第2の操作
A(A(1, 2), 2) → A(5, 2)
A(A(2, 2), 2) → A(5, 2)
5 → A(1, 2)
5 → A(1, 2)
18
練習:

A, B, C, D の順に到着するデータに対して、
1つのスタックだけを用いて出力可能なデータ列はどれか
ア.
イ.
ウ.
エ.
ウ
スタック
(H16年度 春)
A, D, B, C
B, D, A, C
C, B, D, A
D, C, A, B
B
A
A
B
A
C
C
B
A
D
A
B
A
D
A
A
19
アルゴリズム
20
アルゴリズム


問題を解決するための、有限ステップからなる手順
自然言語や、流れ図(フローチャート)で示す
重要 ・ 問題を解く鍵になるアイデアを把握
・ アイデアを実現する手順を考える
開始
1.
2.
3.
4.
5.
6.
生協に行く
棚のチョコレートを手に持つ
レジに行く
財布から代金を払う
お釣りがあれば、受け取る
チョコレートを食べる
1→i
i >n
Yes
No
A(i) = K
Yes
No
i+1→i
探索成功
の処理
終了
探索失敗
の処理
21
流れ図 (フローチャート)

制御の流れを図で表したもの
基本的な記号
開始や終了
繰り返しの開始と終了
(ループ名、終了条件を
記述)
処理
参考: その他の記号
処理の流れ
条件に応じて、
次の処理を変える
(分岐条件を記述)
データの入出力
書類を印刷
ディスプレイに表示
22
情報処理技術者試験での 疑似言語
記述形式
○
説明
手続, 変数の名前, 型などの宣言
/* 文 */
・ 変数 ← 式
・ 手続 ( 引数, … )
注釈
変数に式を代入する
手続を呼び出す
処
条件式
処理1
処理2
選択処理
( if then else )
理
条件式
処理
前判定繰返し処理
( while ループ )
変数:初期値, 条件式, 増分
処理
繰返し処理
( for ループ )
23
アルゴリズム (超入門):
X,Y, Z の最大値
開 始
X, Y, Z を入力
X → MAX
MAX < Y
Yes
Y → MAX
MAX を出力
MAX < Z
Yes
Z → MAX
No
X
3
Y
2
Z
5
MAX
No
y
z
x
終 了
24
アルゴリズム:
開始
1→i
0 → SUM
1~100 の和
開始
初期値設定
1→i
0 → SUM
繰返し条件
繰返しループ
while 型の
繰返し
No
i ≦100
Yes
SUM + i → SUM
次の繰返しの
準備
i+1→i
i ≦100
SUM + i → SUM
i+1→i
繰返しループ
SUM を出力
SUM を出力
終了
終了
25
26
補足説明:
1
2
4
8
16
32
64
…
…
n回
2n
2倍
2倍
2倍
2倍
2倍
2倍
2倍
2倍
log 2 n
0
1
2
3
4
5
6
(次回、必要です)
回
回
回
回
回
回
回
1
2
4
8
16
32
64
…
回
回
回
回
回
回
回
と
…
0
1
2
3
4
5
6
n
2
log 2 n 回
n
2倍
2倍
2倍
2倍
2倍
2倍
2倍
2倍
27
28
練習:
配列を用いたリストの実現
[ 東京、品川、名古屋、新大阪 ]
[ 東京、新横浜、名古屋、新大阪 ]
ア
イ
ウ
エ
第1の操作
5 → A(1, 2)
5 → A(1, 2)
A(A(1, 2), 2) → A(5, 2)
A(A(2, 2), 2) → A(5, 2)
A
列 1
行
1
“東京”
2
“品川”
3 “名古屋”
4 “新大阪”
5 “新横浜”
2
2
3
4
0
第2の操作
A(A(1, 2), 2) → A(5, 2)
A(A(2, 2), 2) → A(5, 2)
5 → A(1, 2)
5 → A(1, 2)
29
30
練習:

スタック
A, B, C, D の順に到着するデータに対して、
1つのスタックだけを用いて出力可能なデータ列はどれか
(H16年度 春)
ア. A, D, B, C
A
A
B
D
C
B
C
B
D
C
B
31
練習:

スタック
A, B, C, D の順に到着するデータに対して、
1つのスタックだけを用いて出力可能なデータ列はどれか
イ.
(H16年度 春)
B, D, A, C
B
B
A
A
D
C
A
A
C
A
D
C
A
32
練習:

スタック
A, B, C, D の順に到着するデータに対して、
1つのスタックだけを用いて出力可能なデータ列はどれか
(H16年度 春)
エ. D, C, A, B
C
B
A
B
A
A
D
C
B
A
D
C
B
A
C
B
A
33
34
35
この教材のご利用について




この文面は、TOKYO
TECH OCW の利用
条件を参考にしました
この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を
求めることなく、無償で自由にご利用いただけます。講義、自主学習は
もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。
非商業利用に限定

この教材は、翻訳や改変等を加えたものも含めて、著作権者の許
諾を受けずに商業目的で利用することは、許可されていません。
著作権の帰属

この教材および教材中の図の著作権は、次ページ以降に示す著
作者に帰属します。この教材、または翻訳や改変等を加えたもの
を公開される場合には、「本教材 (or 本資料) は
http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です
(or 教材を改変したものです」 との旨の著作権表示を明確に実施
してください。なお、この教材に改変等を加えたものの著作権は、
次ページ以降に示す著作者および改変等を加えた方に帰属しま
す。
同一条件での頒布・再頒布

この教材、または翻訳や改変等を加えたものを頒布・再頒布する
場合には、頒布・再頒布の形態を問わず、このページの利用条件36
この教材のご利用について

配布場所

http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/

この powerpoint ファイルの著作者

堀山 貴史 2007-2011 [email protected]

改変等を加えられた場合は、お名前等を追加してください
図の著作者

p. 3 ~ 7, 9 ~ 11, 13, 15, 17 ~ 19, 24, 29, 31 ~ 33
 クリップアート : Microsoft Office Online / クリップアート

p. 8, 13
 メモリ : http://webweb.s92.xrea.com/

その他
 堀山 貴史

37