- データ構造とは
データはただ記憶するだけではなく操作(取出、追加、
削除、更新)が必要です。データのつながりを考慮した
記憶管理の方式をデータ構造と呼び処理に応じて
様々な方式を使い分けます
- 配列
データをグループ化（物理的に連続）
同じ種類（数値、文字）、要素数固定
※1次元、2次元の表など
※すべてのデータ構造のベースとなる(メモリの構造に従う)
配列のイメージ
第1
要素
(0) |
第2
要素
(1) |
第3
要素
(2) |
第4
要素
(3) |
第5
要素
(4) |
「配列名」(配列全体の名前)
「添え字」(要素の連番)
※プログラムでは「0」から数えることが多い
要素の特定
(応用)
- キュー(待ち行列)
データを記憶順で管理
データを末尾に追加し、先頭から取り出す
（先入先出：FIFO)
| (Dequeue) ← ← (Enqueue) |
1番目
の要素 |
2番目
の要素 |
3番目
の要素 |
4番目
の要素 |
※キー入力、印刷処理、ログ出力
- スタック（積重ね）
データを記憶順で管理
データを末尾に追加、末尾から取り出す
（後入先出：LIFO）
| （Push）↓ ↑（Pop) |
| 3番目の要素 |
| 2番目の要素 |
| 1番目の要素 |
※プログラムの制御(ローカル変数、関数のアドレス)
CPU内のスタックポインタ、メモリのスタック領域を利用
- リスト構造
連結リスト
データに付加情報を追加→
記憶順とは別に論理的な順序を割り当てる
※必ずしも整列ではなく順序付けられたデータの集まり
(例)ファイルやメールの並び替え順など
| ※付加情報 |
次のデータの場所(アドレス）
ポインタとも呼ばれる |
ポインタ(アドレス)の変更でデータの追加、削除が可能
※要素数が可変
（追加の例）
|
「い」と「う」の間に
「か」を追加 → |
|
※2次元配列を利用
(種類)
・線形リスト
| (1) |
単方向リスト |
次のデータへのアドレスを付加 |
|
|
先頭 → 中間 → 末尾 |
| (2) |
双方向リスト |
前後のデータへのアドレスを付加 |
|
|
先頭 ← → 中間 ← → 末尾 |
・循環リスト
| (3) |
循環（環状）
リスト |
双方向に加え、先頭と末尾も
それぞれのアドレスを持つ |
|
|
↑ → → ↓ |
|
|
先頭 ← → 中間 ← → 末尾 |
|
|
↑ ← ← ↓ |
※最終的にリスト完成後は配列へ変換することが多い
→データの検索などが行いやすいため
- ツリー構造
データを階層的に管理
親子関係（１：多）
| （根：ルート） |
○ |
親 |
|
｜ |
↑ |
| （枝：ブランチ） |
｜−−−−−−−｜ |
↓ |
|
○ ○ |
子 |
|
（節：ノード 又は 葉：リーフ） |
|
|
|
|
※ファイル管理（フォルダ、ファイル）、DB
（種類）
- 2分木
節から分岐する枝が2本以下
※完全２分木（左から順に子を作る）
- 2分探索木
2文木であり、データの関係が
「左の子 ＜ 親 ＜ 右の子」
※バランス木（AVL木）
親子の階層差が１以内
- 多分木
枝が３本以上
※多分探索木(B木)
ルートからの深さがすべて等しい
リーフのみデータを持ち、その他はインデックスの役割
（2分探索木を配列で表現）
|
|
→ |
| （右） |
３ |
０ |
５ |
０ |
０ |
| データ |
う |
い |
え |
あ |
お |
| （左） |
２ |
４ |
０ |
０ |
０ |
|
（データ探索 例：「お」）
（１）「お」＞「う」 → （２）「お」＞「え」 → （３）「お」＝「お」
（木の巡回）
- 幅優先順（根から同じ階層）
- 深さ優先順
- 先行順（親、左、右 ※ポーランド）
- 中間順（左、親、右 ※算術式、二分探索木ソート順）
- 後行順（左、右、親 ※逆ポーランド、コンパイラ）
(例) 先行、中間、後行順での式の表現
(先行) −＋１２＋３４
(中間) １＋２−３＋４
(後行) １２＋３４＋−
|
