データ構造(全52問中10問目)
No.10解説へ
リストを二つの1次元配列で実現する。配列要素 box[i] と next[i] の対がリストの一つの要素に対応し，box[i] に要素の値が入り，next[i] に次の要素の番号が入る。配列が図の状態の場合，リストの3番目と4番目との間に値が H である要素を挿入したときの next[8] の値はどれか。ここで，next[0] がリストの先頭(1番目)の要素を指し，next[i] の値が0である要素はリストの最後を示し，next[i] の値が空白である要素はリストに連結されていない。
出典：平成30年春期 問 6
- 3
- 5
- 7
- 8
広告
解説
リスト構造は、隣接するデータ同士をポインタで連結して表現するデータ構造です。
設問の配列の値にしたがってデータを連結していき、リスト構造を可視化したものが下図です。
このリストの3番目と4番目の間に値がHである要素を挿入すると、リスト構造は以下のように変化することになります。
追加・挿入・削除などの操作でリスト構造に変化が生じた場合、適切な前後関係を保つために一部のポインタの値を更新する必要があります。このケースでは挿入された要素の次が、値がGである要素（box[7]とnext[7]）なので next[8] に入るのは7です。さらに挿入位置の手前の要素である next[3] も8番目の配列要素を参照するように書き換えなければなりません。
したがって要素挿入後の next[8] の値は7になります。
広告