データ構造と
アルゴリズム
第六回
知能情報学部
新田直也
双方向リスト
連結リスト
双方向リスト
双方向リストの構造体
struct CELL {
int value;
struct CELL *next;
struct CELL *prev;
}
内容
次ページのアドレス
前ページのアドレス
CELL
value
next
prev
1ページに相当
(構造体)
双方向リストの insert
insert(k,e)は?
※ p は k 個目の要素を指す
p
*(p->prev)
p->prev->value
p->prev->next
p->prev->prev
新しいページのURLを r とすると…
r->next = p;
r->prev = p->prev;
p->prev->next = r;
p->prev = r;
*p
p->value
p->next
p->prev
r->value
r->next
r->prev
双方向リストの delete
delete(k)は?
*(p->prev)
※ p は k 個目の要素を指す
p
*p
p->prev->value
p->prev->next
p->prev->prev
p->next->prev = p->prev;
p->prev->next = p->next;
*(p->next)
p->value
p->next
p->prev
p->next->value
p->next->next
p-next->prev
木構造
木： 閉路（サイクル）を持たない連結グラフ．
節，ノード，頂点
辺，エッジ
閉路
→「木」である
→「木」でない
木構造の例
木は典型的なデータ構造
ファイルシステム
数式
図形
XML
計算過程
(a + b) * c + (d / e)
グループ1
+
/
*
+
a
グループ3
c
グループ2
d
e
b
グループ4
グループ5
各部の名称(1)
ラベル，根，葉，親，子，兄弟：
(a + b) * c + (d / e)
根
ラベル
+
/
*
親
+
子
a
c
b
兄弟
d
e
葉
各部の名称(2)
祖先，子孫，部分木，レベル：
(a + b) * c + (d / e)
+
祖先
/
*
子孫
+
a
部分木
レベル0
c
b
d
レベル1
e
レベル2
レベル3
木の種類
順序木: 兄弟間で順序づけられている木．
+
1:
*
+
a
c
b
2:
1:
d
(a + b) * c + (d / e)
/
e
2:
順序が変わると意味が変わる
無順序木： 兄弟間に順序がない木．
順序に意味がない
二分木
二分木： すべての節点が子をたかだか2つしか持
たない順序木．
(a + b) * c + (d / -e)
+
子が2個
/
*
+
a
c
b
d
子が2個
-
子が1個
e
子が0個
二分木の表現(1)
例によってWebで．．．
二分木の表現(2)
struct node {
char value;
struct node *left;
struct node *right;
}
ラベル
左の子のアドレス
右の子のアドレス
1ノードに相当
(構造体)
© Copyright 2024 ExpyDoc
