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