GESP 五级 · GESP 202409 C++ 五级 第 2 题

通过（ ）操作，能完成在双向循环链表结点 $p$ 之后插入结点 $s$ 的功能（其中 next 域为结点的直接后继，prev 域为结点的直接前驱）。

图的存储方式：邻接矩阵（O(n²)空间，适合稠密图）、邻接表（O(n+m)空间，适合稀疏图）。

有向完全图边数为n(n-1)，无向完全图边数为n(n-1)/2。简单图不含自环和重边。

【考点】双向链表操作｜指针语义｜循环链表特性

解题思维：双向循环链表插入的核心是"先修前后，再修自身"。正确顺序应为：先让原后继的前驱指向新结点（p->next->prev = s），再让原后继指向新结点（p->next = s），再让新结点的前驱指向 p（s->prev = p），最后让新结点的后继指向原后继（s->next = p->next）。选项D严格遵循此顺序，且p->next在插入前已被保存，避免循环断裂。

陷阱拆解：选项A错误地把新结点的前驱直接赋给p->next，导致p->next指向s之前，s的前驱仍是p，形成p->next->prev = s时s的前驱是p，但p->next已经是s，造成s的前驱仍是p，逻辑矛盾。选项B在修改p->next之前就更新s->prev，使s的前驱指向s本身，破坏双向性。选项C先设s->prev = p和s->next = p->next，再改p->next = s，此时p->next已指向s，再去改s->prev = p会导致s的前驱是s，循环断裂。命题人利用学生对指针顺序的混淆和对循环链表头尾一致性的忽视，让看似合理的顺序实则出错。

反命题思维：若改为单向链表，只需p->next = s; s->prev = p; s->next = p->next; p->next->prev = s; 顺序不同。若插入到头结点后，需特别处理头结点的prev域。刷题时先确认链表类型和插入位置，再按"先修前后，再修自身"的原则设计指针操作。