应用题
已知一个双向链表,其结点结构为数据域data、左指针域llink、右指针域rlink;设指针P指向双向链表中的某个结点。写出一个算法,实现P所指向的结点和它的前缀结点之间顺序的互换。要求:
问答题
17.给出算法的基本设计思想。
【正确答案】算法的基本思想:已知双向循环链表中的一个结点P,与前驱交换涉及4个结点(P结点,前驱结点,前驱的前驱结点,后继结点)、6条链。
【答案解析】
问答题
18.根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
【正确答案】算法的设计如下:
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的后继指向其原来的前驱
}
【答案解析】