PowerPoint プレゼンテーション

基本情報技術概論 (第４回)
中間試験
12/2 (水) 5,6限
教室未定
データ構造
埼玉大学理工学研究科
堀山貴史
1
前回までの復習
（計算の仕組みの基礎）

数値、文字の表現方法

四則演算 (＋, －, ×, ÷)


10進法での筆算と同じようにできる
２進数では、０, １を操作すれば実現できる
ハ  論理素子
ー

０, １の「入力」から、０, １の「出力」を得る仕組み
ド
ウ
ェ  論理回路
ア
 論理素子を用いて、
の
計算を実現する仕組み
基
礎
 組合せ回路、順序回路
2
ソフトウェアの基礎
ハードウェア (hardware) … 装置
ソフトウェア (software) … 装置を動かすための情報
3
データ構造

データ構造
 データをどのように記憶するか

基本的なデータ構造
 配列 (array)
 リスト (list)
___________

その他のデータ構造
 スタック (stack)
 待ち行列 (queue, キュー)
 木 (tree)
___________
4
データ構造： ________________
配列

データを順番にならべて、
添字でアクセスできるようにしたもの
________

操作：参照、探索、更新、削除、挿入
配列 A
A [1]
30
A [2]
50
A [3]
20
A [4]
70
A [5]
10
…
5
コンピュータ上での配列
配列 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]
二次元配列
メモリ
（主記憶装置）
一次元に変換して
メモリに配置する
…
…
6
探索キー
配列の操作
（探索データ）
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] から順番に
一致するか調べる
7
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] の場所を空けるため、
後ろに１つずつずらす
8
A[4] の位置の
データを削除

削除
A[4] の位置の
データを削除

削除（その２）
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] が空いたため、
１つずつつめる
A[4] に削除マークをつけて、
無いものとして扱う
9
データ構造： ________________
リスト

となりの要素の位置（アドレス）を、
ポインタとして明示的に持つ
________
単方向リスト
双方向リスト
環状リスト
head (リストの
先頭を指す)
30
30
30
50
50
50
20
20
20
逆方向の探索が容易
10
コンピュータ上でのリスト
メモリ
（主記憶装置）
2000
2010
50
番地
2010
（アドレス）
30
2070
20
2030
20
0
2070
50
2030
…
…
30
となりの要素の位置（アドレス）を、
ポインタとして明示的に持つ
11
リストの操作

探索
探索キー
（探索データ）

更新
20 を更新
20
30
30
50
50
20
35
20
70
70
先頭から順番に
ポインタをたどって調べる
20 を探索 + 更新
12
リストの操作

挿入
50 の次に
35 を挿入

削除
20 を削除
30
30
50
50
35
20
20
70
70
前のデータのポインタを、自分に
自分のポインタを、次のデータに
前のデータのポインタを、
次のデータに
13
練習：



配列を用いたリストの実現
表は、配列を用いたリストの実現を示しており、
リスト [ 東京、品川、名古屋、新大阪 ] を表している。
このリストを、[ 東京、新横浜、名古屋、新大阪 ] に
変化させる操作はどれか。
ここで、A ( i, j ) は、表の第 i 行第 j 列の要素を表す。
また、→ は代入を表す。
A
列 1
行
1
“東京”
2
“品川”
3 “名古屋”
4 “新大阪”
5 “新横浜”
2
2
3
4
0
14
練習：
ア
イ
ウ
エ
配列を用いたリストの実現
第１の操作
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(A(1, 2), 2) → A(5, 2)
A(A(2, 2), 2) → A(5, 2)
5 → A(1, 2)
5 → A(1, 2)
15
データ構造

基本的なデータ構造
 配列 (array)
 リスト (list)

その他のデータ構造
 スタック (stack)
 待ち行列 (queue, キュー)
 木 (tree)
16
データ構造： ________________
スタック

push と pop による Last-In First-Out (LIFO)
___________
イメージ）積み上げた書類や本
生協の入口のトレイ
5
push
pop
30
50
20
17
スタックの実現法
5
push
pop

A [1]
A [2]
A [3]
20
50
30
…
30
50
20
配列
スタック
ポインタ

リスト
30
50
20
18
データ構造：待ち行列
（キュー）
________________

enqueue と dequeue による First-In First-Out (FIFO)
___________

イメージ）レジの前の行列
5
enqueue
30
50
20
dequeue
19
キューの実現法
5

enqueue
front
A [1]
A [2]
A [3]
20
50
30
rear
…
30
50
20
配列
dequeue  リスト
front
20
rear
50
30
20
ポーランド記法

と
逆ポーランド記法
演算 a + b を以下のように記す方法


ポーランド記法
逆ポーランド記法
+ a b
a b +
… 日本語で「a に b を加える」

( ) を使う必要がない
 例) ( a + b ) x ( c - d )
逆ポーランド記法 a b + c d - x

スタックマシンでの実行が容易
21
逆ポーランド記法
と
スタックマシン

例) ( 2 + 8 ) x ( 5 - 1 )
2 8 + 5 1 - x
逆ポーランド記法

スタックマシンでの実行
5
10
2
8
2
10
1
5
10
4
10
40
22
練習：

スタック
A, B, C, D の順に到着するデータに対して、
１つのスタックだけを用いて出力可能なデータ列はどれか
ア.
イ.
ウ.
エ.
A, D, B, C
B, D, A, C
C, B, D, A
D, C, A, B
(H16年度春)
23
24
補足説明：
1
2
4
8
16
32
64
…
…
n回
2n
2倍
2倍
2倍
2倍
2倍
2倍
2倍
2倍
ｌｏｇ 2 ｎ
0
1
2
3
4
5
6
（次回、必要です）
回
回
回
回
回
回
回
1
2
4
8
16
32
64
…
回
回
回
回
回
回
回
と
…
0
1
2
3
4
5
6
ｎ
２
log 2 n 回
n
2倍
2倍
2倍
2倍
2倍
2倍
2倍
2倍
25
26
練習：
配列を用いたリストの実現
[ 東京、品川、名古屋、新大阪 ]
[ 東京、新横浜、名古屋、新大阪 ]
ア
イ
ウ
エ
第１の操作
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
第２の操作
A(A(1, 2), 2) → A(5, 2)
A(A(2, 2), 2) → A(5, 2)
5 → A(1, 2)
5 → A(1, 2)
27
28
練習：

A, B, C, D の順に到着するデータに対して、
１つのスタックだけを用いて出力可能なデータ列はどれか
ア.
イ.
ウ.
エ.
ウ
スタック
(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
29
練習：

スタック
A, B, C, D の順に到着するデータに対して、
１つのスタックだけを用いて出力可能なデータ列はどれか
(H16年度春)
ア. A, D, B, C
A
A
B
D
C
B
C
B
D
C
B
30
練習：

スタック
A, B, C, D の順に到着するデータに対して、
１つのスタックだけを用いて出力可能なデータ列はどれか
イ.
(H16年度春)
B, D, A, C
B
B
A
A
D
C
A
A
C
A
D
C
A
31
練習：

スタック
A, B, C, D の順に到着するデータに対して、
１つのスタックだけを用いて出力可能なデータ列はどれか
(H16年度春)
エ. D, C, A, B
C
B
A
B
A
A
D
C
B
A
D
C
B
A
C
B
A
32
33
34
この教材のご利用について




この文面は、TOKYO
TECH OCW の利用
条件を参考にしました
この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を
求めることなく、無償で自由にご利用いただけます。講義、自主学習は
もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。
非商業利用に限定

この教材は、翻訳や改変等を加えたものも含めて、著作権者の許
諾を受けずに商業目的で利用することは、許可されていません。
著作権の帰属

この教材および教材中の図の著作権は、次ページ以降に示す著
作者に帰属します。この教材、または翻訳や改変等を加えたもの
を公開される場合には、「本教材 (or 本資料) は
http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です
(or 教材を改変したものです」との旨の著作権表示を明確に実施
してください。なお、この教材に改変等を加えたものの著作権は、
次ページ以降に示す著作者および改変等を加えた方に帰属しま
す。
同一条件での頒布・再頒布

この教材、または翻訳や改変等を加えたものを頒布・再頒布する
場合には、頒布・再頒布の形態を問わず、このページの利用条件35
この教材のご利用について

配布場所

http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/

この powerpoint ファイルの著作者

堀山貴史 2007-2010 [email protected]

改変等を加えられた場合は、お名前等を追加してください
図の著作者

p. 2, 5 ～ 9, 11 ～ 15, 17, 19, 23, 27, 29 ～ 32
 クリップアート : Microsoft Office Online / クリップアート

p. 6, 11
 メモリ : http://webweb.s92.xrea.com/

その他
 堀山貴史

36

Download Report