Ｃ言語で双方向リストを実現するために、次の構造体を定義した。
struct cell { int data;
struct cell *prev;
struct cell *next; };
双方向リストが存在して、p がその中のセル (リストの要素) を指しているとする。p が指しているセルと p->next が指しているセルの間に新しいセル (変数 newcell が指しているものとする) を追加したい。[ア]～[カ]のうち実行すべき文と、その実行順序として最も適切なものはどれか。
[ア] newcell->next = p->next;
[イ] newcell->prev = p;
[ウ] p->next = newcell;
[エ] p->prev = newcell;
[オ] p->next->next = newcell;
[カ] p->next->prev = newcell;
① ア － イ － ウ － カ
② イ － ア － カ － ウ
③ イ － ウ － オ － カ
④ オ － ウ － イ － エ
⑤ カ － ウ － ア － イ
②
例えば以下の数値が入っているとする。
pの前のセルの場所 000
prev のポインタ NULL
データ 0
next のポインタ 100
pが指しているセルの場所 100
pの前のセルへのポインタ(prev) 000
データ 1
pの次のセルへのポインタ(next) 200
pの次のセルの場所 200
pへのポインタ(prev) 100
データ 3
pの次の次のセルへのポインタ(next) 300
このとき、
p.data = 1
p->prev = 000 (p の 前のセルへのポインタ)
p->next = 200 (p の 次のセルへのポインタ)
p = 100 (pへのポインタ)
となる。この状態で、
newcell.data = 2 を追加することを考える。
なお、newcell の場所は150とする。
まず、新しいセルの「前のセルへのポインタ(prev)」に p(100) を入れる。
newcell->prev = p; ・・・イ
さらに、新しいセルの「次のセルへのポインタ(next)」を
元々 p のnextが指し示していた値(200) とする。
newcell->next = p->next; ・・・ア
次に p の次のセルであったセルの「前のセルへのポインタ(prev)」を
newcell (150)とする。
p->next->prev = newcell ・・・カ
最後に、p の「次のセルへのポインタ(next)」をnewcell (150) とする。
p->next = newcell ・・・ウ
結果は以下のとおりである。
pが指しているセルの場所 100
pの前のセルへのポインタ(prev) 000
データ 1
pの次のセルへのポインタ(next) 150
新しいセルの場所 150
新しいセルの前のセルへのポインタ(prev) 100
データ 2
新しいセルの次のセルへのポインタ(next) 200
p->next が指していたセル場所 200
前のセルへのポインタ(prev) 150
データ 3
イとアの順序は変わってもよいが、ウの順序は最後にしなければ、おかしくなってしまう。
| Ⅳ－２ | 目次 | Ⅳ－４ |