プログラミングの基礎(擬似言語のトレース)
次のプログラムは、配列 next でつないだ連結リスト A → C → E → D → B の「C」(要素番号3)の直後に、val[6] の「F」を挿入してから、要素番号1の要素から順にたどって出力する。配列の要素番号は1から始まる。next の値0はリストの終わりを表す。出力が A, C, F, E, D, B となるように【a】に入れる処理はどれか。
文字列型の配列: val ← {"A", "B", "C", "D", "E", "F"}
整数型の配列: next ← {3, 0, 5, 2, 4, 0}
【a】
整数型: p ← 1
while (p ≠ 0)
出力 val[p]
p ← next[p]
endwhile- Anext[3] ← 6 の後に next[6] ← next[3]
- Bnext[6] ← 3 の後に next[3] ← next[6]
- Cnext[6] ← next[3] の後に next[3] ← 6
答えと解説を見る
正解：C. next[6] ← next[3] の後に next[3] ← 6
挿入では、新しい要素 F の次を、C が元々指していた E(next[3] = 5)にしてから、C の次を F にします。next[6] ← next[3] で next[6] = 5、続く next[3] ← 6 で C → F → E がつながります。順を逆にすると、next[3] を6に書き換えた後で next[6] ← next[3] を行うので next[6] = 6 となり、F が自分自身を指して C, F, F, … と終わらなくなります。連結リストのつなぎ替えでは、後ろの要素への道筋を失わない順に代入します。
- A. next[6] が6になり、F が自分自身を指して、たどる処理が終わらなくなります。
- B. next[6] = 3、next[3] = 3 となって C が自分自身を指し、A, C, C, … と終わらなくなります。
- C. 正しい。F の次を E にしてから、C の次を F にします。