2章 データ構造
データ構造
• 本章では基本的なデータ構造を紹介する
• 本章で紹介する基本的なデータ構造
– 2.1
– 2.2
– 2.3
– 2.4
– 2.5
リスト
スタックとキュー
グラフ
木
ヒープ
2.1 リスト
3,5,2,1,4の順でデータを保存
リスト構造
3
5
2
1
4
ポインタ
3
5
2
1
4
配列
3 5 2 1 4
リストの基本操作
•
•
•
•
初期化
探索
挿入
削除
データへのアクセス
場面をサーチ
データを検索
3
5
2
1
ビデオテープ
35214
DVD
4
データの挿入
6
ポインタ
3
5
2
6
配列
3 5 2 1 4
1
4
データの削除
ポインタ
配列
3
5
2
3 5 2 1 4
1
4
データの検索(違いはあるか?)
・ 2はあるか? 6はあるか?
ポインタ
3
1
6
7
4
3 1 6 7 4
配列
・ データが小さい順に並んでいたらどうか?
ポインタ
配列
1
3
4
1 3 4 6 7
6
7
2.2 スタックとキュー
• スタック :後入れ先出し (LIFO)
– 木構造、入れ子構造、括弧対応、ディレクトリ構造
– 深さ優先探索
• キュー :先入れ先出し (FIFO)
– 最短路、辞書式順序
– 幅優先探索
スタック
C
B
A
C
B
A
キュー
C
B
A
スタック
・全てのディレクトリを探査せよ
/
home
local
etc
user
home
etc
local
user
スタック、入れ子構造、括弧対応
home
/
home
etc
etc
user
user
local
local
( (
(
) ),
(
) )
キュー
・各頂点に対しAからの距離を求めよ
A
B
C
D
E
F
G
H
I
0
2
3
1
1
3
2
2
4
G
D
C
H
A
E
B
FI
ダウンロード

2章 データ構造