已知一个双向链表,其结点结构为数据域data、左指针域Uink、右指针域rlink;设指针P指向双向链表中的某个结点。写出一个算法,实现P所指向的结点和它的前缀结点之间顺序的互换。要求: (1)给出算法的基本设计思想。 (2)根据设计思想,

admin2019-01-16  49

问题 已知一个双向链表,其结点结构为数据域data、左指针域Uink、右指针域rlink;设指针P指向双向链表中的某个结点。写出一个算法,实现P所指向的结点和它的前缀结点之间顺序的互换。要求:
    (1)给出算法的基本设计思想。
    (2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。

选项

答案(1)算法的基本思想:已知双向循环链表中的一个结点P,与前驱交换涉及4个结点(P结点,前驱结点,前驱的前驱结点,后继结点)、6条链。 (2)算法的设计如下: typedef struct DuLNode{ int data; struct DuLNode*llink,*rlink: }DuLNode*Linkedlist; void Exchange(LinkedList P){ //将P所指结点与其前驱结点交换 Linkedlist*q: 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的后继指向其原来的前驱 }

解析
转载请注明原文地址:https://kaotiyun.com/show/FaRi777K
0

最新回复(0)