Document

[B6] リスト処理
[B6] リスト処理
大崎博之
関西学院大学理工学部情報科学科
[email protected]
プログラミング実習 III
1/ 9
[B6] リスト処理
[B6] リスト処理
▶
▶
1. リスト
2. 二分木
これらを学ぶことに何の意味があるのか?
プログラミング実習 III
2/ 9
[B6] リスト処理
リスト (list)
data
link
123
コンピュータサイエンスにお
ける、もっとも基本的なデー
タ構造の一つ
▶
▶
node
ノード (node) の順列
(sequence)
ノードとノードが連結
(link) されている
プログラミング実習 III
456
789
375
3/ 9
[B6] リスト処理
リストの利点と欠点
(配列と比較した時の) リストの利点
▶
要素を自由に挿入・削除できる
(配列と比較した時の) リストの欠点
▶
各要素を参照するのが面倒 (リストを辿らないとダメ)
▶
途中のノードに直接アクセスできない
プログラミング実習 III
4/ 9
[B6] リスト処理
代表的なリスト: 片方向リスト (singly linked list)
data
link
123
node
456
789
375
プログラミング実習 III
5/ 9
[B6] リスト処理
代表的なリスト: 双方向リスト (doubly linked list)
link
data
123
link
node
456
789
375
プログラミング実習 III
6/ 9
[B6] リスト処理
代表的なリスト: 循環リスト (circular list)
data
link
123
456
node
789
375
プログラミング実習 III
7/ 9
[B6] リスト処理
二分木 (binary tree)
コンピュータサイエンスにお
ける、基本的なデータ構造の
一つ
▶
ノード (node) の木 (tree)
▶
ノードは 2 つの子ノード
を持つ (左 (left)、右
(right))
高速なアルゴリズムが実現で
きるのはツリーのおかげ
▶
root
5
link (edge)
3
8
node (vertex)
left right
1
4
leaf
leaf
ノード数 N の二分木は
深さ log2 N
プログラミング実習 III
12
10
leaf
8/ 9
[B6] リスト処理
リストやツリーはなぜ必要か?
▶
プログラミングの本質はアルゴリズムとデータ構造
▶ プログラミングの成功/失敗は……
▶ 良いアルゴリズムを考えられるか?
▶ 良いデータ構造を考えられるか?
▶ プログラミングテクニックは実は瑣末 (さまつ) な
問題
▶ だから大学の講義はとても重要!
→ 設計したデータ構造を実現するためにリストやツリー
が不可欠
プログラミング実習 III
9/ 9

Download Report