データ構造と アルゴリズム 第六回 知能情報学部 新田直也.

Presentation on theme: "データ構造と アルゴリズム 第六回 知能情報学部 新田直也."— Presentation transcript:

1 データ構造と アルゴリズム 第六回 知能情報学部 新田直也

2 双方向リスト 連結リスト 双方向リスト

3 双方向リストの構造体 struct CELL { int value; struct CELL *next;
struct CELL *prev; } 内容 1ページに相当 (構造体) 次ページのアドレス 前ページのアドレス CELL value next prev

4 双方向リストの insert insert(k,e)は? 新しいページのURLを r とすると… r->next = p;
※ p は k 個目の要素を指す *(p->prev) p *p p->prev->value p->value p->prev->next p->next p->prev->prev p->prev 新しいページのURLを r とすると… r->next = p; r->prev = p->prev; p->prev->next = r; p->prev = r; r->value r->next r->prev

5 双方向リストの delete delete(k)は? p->next->prev = p->prev;
※ p は k 個目の要素を指す *(p->prev) p *p *(p->next) p->prev->value p->value p->next->value p->prev->next p->next p->next->next p->prev->prev p->prev p-next->prev p->next->prev = p->prev; p->prev->next = p->next;

6 木構造 木： 閉路（サイクル）を持たない連結グラフ． 節，ノード，頂点 辺，エッジ 閉路 →「木」である →「木」でない

7 木構造の例 木は典型的なデータ構造 ファイルシステム 数式 組織図 系統樹 図形のグルーピング :
(a + b) * c + (d / e) * + a b c / d e

8 各部の名称(1) ラベル，根，葉，親，子，兄弟： (a + b) * c + (d / e) ラベル 根 + 親 * / 葉 + + c d

9 各部の名称(2) 祖先，子孫，部分木，レベル： (a + b) * c + (d / e) 祖先 レベル0 レベル1 レベル2 レベル3 +

10 木の種類 順序木: 兄弟間で順序づけられている木． 無順序木： 兄弟間に順序がない木． + (a + b) * c + (d / e) *
1: 2: (a + b) * c + (d / e) * / 1: 2: + c d e a b 順序が変わると意味が変わる 順序に意味がない

11 二分木 二分木： すべての節点が子をたかだか2つしか持たない順序木． (a + b) * c + (d / -e) + 子が2個 * /
子が1個 a b e 子が0個

12 二分木の表現(1) 例によってWebで．．．

13 二分木の表現(2) struct node { char value; struct node *left;
struct node *right; } ラベル 1ノードに相当 (構造体) 左の子のアドレス 右の子のアドレス