内部収納と外部収納の例

ウィキペディア小見出し辞書

内部収納と外部収納の例

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:30 UTC 版)

「連結リスト」の記事における「内部収納と外部収納の例」の解説

ここでは、家族とその構成員の連結リストを処理するコードを例として示す。内部収納の場合、構造体は次のようになる。 record member { // 家族のメンバー member next string firstName integer age } record family { // 家族 family next string lastName string address member members // この家族のメンバーのリストの先頭 } 家族のリストと各家族のメンバーを表示するルーチンは、内部収納の場合、次のようになる。 aFamily := Families // 家族リストの先頭から開始 while aFamily ≠ null { // 家族リスト上でループ 家族に関する情報を印字 aMember := aFamily.members // その家族のメンバーのリストの先頭を得る while aMember ≠ null { // メンバーのリスト上でループ メンバーに関する情報を印字 aMember := aMember.next } aFamily := aFamily.next } 外部収納を使うと、構造体は次のようになる。 record node { // 汎用リンク構造体 node next pointer data // ノードに付属するデータを指す汎用ポインタ } record member { // 家族構成員に関する構造体 string firstName integer age } record family { // 家族に関する構造体 string lastName string address node members // この家族のメンバーのリストの先頭 } 家族のリストと各家族のメンバーを表示するルーチンは、外部収納の場合、次のようになる。 famNode := Families // 家族リストの先頭から開始 while famNode ≠ null { // 家族リスト上でループ aFamily = (family)famNode.data // ノードから家族データ構造体を取り出す 家族に関する情報を印字 memNode := aFamily.members // その家族のメンバーのリストの先頭を得る while memNode ≠ null { // メンバーのリスト上でループ aMember := (member)memNode.data // ノードからメンバーデータ構造体を取り出す メンバーに関する情報を印字 memNode := memNode.next } famNode := famNode.next } 外部収納を使った場合、データ構造体を取り出して型変換するという余分なステップが必要になる。これは、2種類の連結リストが同じデータ構造（node）を使っているためである。 あるメンバーがいくつの家族に属することができるかがコンパイル時に分かっている場合、内部収納の方が適している。しかし、1人のメンバーが任意の個数の家族に属する可能性がある場合、かつその数が実行時にならないと分からない場合、外部収納にする必要がある。