数据结构 | 每日一练（52）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．已知p指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域，写出算法change(p),交换 p 所指向的结点和它的前缀结点的顺序。

正确答案

ps：||代表注释

1．[题目分析] 知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。

void Exchange（LinkedList p）∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。

{q=p->llink；

q->llink->rlink=p； ∥p的前驱的前驱之后继为p

p->llink=q->llink； ∥p的前驱指向其前驱的前驱。

q->rlink=p->rlink； ∥p的前驱的后继为p的后继。

q->llink=p； ∥p与其前驱交换

p->rlink->llink=q； ∥p的后继的前驱指向原p的前驱

p->rlink=q； ∥p的后继指向其原来的前驱

}∥算法exchange结束。

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-