![](https://csdnimg.cn/release/download_crawler_static/88232390/bg9.jpg)
(13)解:首先找到双链表 L 的尾结点 p。pre 指向 p 结点的前驱结点,然后从链表
中删除 p 结点,再将 p 结点插入到 pre 结点之前。本算法需要遍历整个双链表才能找到尾
结点,所以算法的时间复杂度为 O(n)。对应的算法如下:
void SwapLast(DLinkNode *&L)
{
}
DLinkNode *p=L,*pre;
while (p->next!=NULL)
p=p->next;
//post指向p结点的前驱结点
//删除p结点
pre=p->prior;
pre->next=p->next;
if (p->next!=NULL)
p->next->prior=pre;
//将p结点插入到pre结点之前pre->prior->next=p;
p->prior=pre->prior;
pre->prior=p;
p->next=pre;
(14)解:p 从循环双链表 L 的首结点开始扫描,当 p≠L 时循环:若 p 结点值为
x,post=p->next 临时保存其后继结点,通过 p 结点前后指针域删除 p 结点,并释放其空
间,置 p=post 继续查找;若 p 结点值不为 x,执行 p=p->next。对应的算法如下:
void DeleteAllx(DLinkNode *&L,ElemType x)
{
}
DLinkNode *p=L->next,*post;
while (p!=L)
{
}
{
}
else p=p->next;
//扫描数据结点p
if (p->data==x)
post=p->next;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
p=post;
//释放p结点
//删除p结点
(15)解:通过 L->prior 找到尾结点 p。pre 指向 p 结点的前驱结点,然后从链表中
删除 p 结点,再将 p 结点插入到 pre 结点之前。本算法不含有循环语句,所以算法的时间
复杂度为 O(1)。对应的算法如下:
void SwapLast(DLinkNode *&L)
{ DLinkNode *p=L->prior,*pre;
pre=p->prior; //pre指向p结点的前驱结点
//删除p结点pre->next=p->next;
p->next->prior=pre;
9