Ｃ言語で双方向リストを実現するために、次の構造体を定義した。
struct cell { int data;
struct cell *prev;
struct cell *next; };
struct cell *p, *newcell;
newcell = (struct cell*) malloc(sizeof (struct cell));
双方向リストが存在して、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
イとアの順序は変わってもよいが、ウの順序は最後にしなければ、おかしくなってしまう。
| Ⅳ－３ | 目次 | Ⅳ－５ |