双方向リストを三つの一次元配列 elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき、要素Dの次に要素Cを挿入した後の
next[6]、
prev[6] の値の組合せはどれか。ここで、双方向リストは次のように表現する。
・双方向リストの要素は、elem[i]に値、next[i] に次の要素の要素番号、prev[i] に前の要素の要素番号を設定
・双方向リストの先頭、末尾の要素番号は、それぞれ変数Head、Tailに設定
・next[i]、prev[i] の値が0である要素は、それぞれ双方向リストの末尾、先頭を表す。
・双方向リストへの要素の追加は、一次元配列の末尾に追加
一次元配列の末尾
┏━┓
要素番号 １ ２ ３ ４ ５┃６┃
┌─┬─┬─┬─┬─╂─┨
elem │Ａ│Ｆ│Ｄ│Ｂ│Ｅ┃ ┃
└─┴─┴─┴─┴─╂─┨
要素番号 １ ２ ３ ４ ５┃６┃
┌─┬─┬─┬─┬─╂─┨
next │４│０│５│３│２┃ ┃
└─┴─┴─┴─┴─╂─┨
要素番号 １ ２ ３ ４ ５┃６┃
┌─┬─┬─┬─┬─╂─┨
prev │０│５│４│１│３┃ ┃
└─┴─┴─┴─┴─╂─┨
┌─┐ ┗━┛
Head │１│
└─┘
┌─┐
Tail │２│
└─┘
┌────┬────┐
│ next[6]│ prev[6]│
┌─┼────┼────┤
│ア│ ２│ ３│
├─┼────┼────┤
│イ│ ３│ ４│
├─┼────┼────┤
│ウ│ ５│ ３│
├─┼────┼────┤
│エ│ ５│ ４│
└─┴────┴────┘
ウ
挿入前の要素の並びは
Headが1だから、elem[1]を参照し、その要素はA。
next[1]が4だから、elem[4]を参照し、その要素はＢ。
next[4]が3だから、elem[3]を参照し、その要素はD。
next[3]が5だから、elem[5]を参照し、その要素はE。
next[5]が2だから、elem[2]を参照し、その要素はF。
next[2]が0だし、Tailが2だから、要素Ｆが末尾。
ということで、ABDEFの順で並んでいる。
ここで、要素Dの次に要素Cを挿入するが、双方向リストへの要素の追加は、一次元配列の末尾に追加することから、配列6、つまりelem[5] に要素Cを挿入する。
そして、要素Cの次は要素Eになるので next[6] には要素Eが設定されている要素番号5を設定する必要がある。
一方、要素Cの前は要素Dになるので prev[6] には要素Dが設定されている要素番号3を設定する必要がある。
したがって、ウが正しい。
ちなみに next[3]には6、prev[5]には6を設定しなおす必要がある。
| 問４ | 目次 | 問６ |