第8讲 双向链表
● 循环单链表的出现，虽然能够实现从任一结点出发沿着链能到其前趋结点，但时间耗费是O (n) 。
● 如果希望从表中快速确定某一个结点的前趋，另一个解决方法就是在单链表的每个结点里再增加一个指向其前趋的指针域prior 。这样形成的链表中就有
两条方向不同的链，我们称之为双向链表。
● 双向链表的结构定义如下：
typedef struct DNode
{ ElemType data ；
struct DNode *prior ，*next ；
}DNode, * DoubleList ；
● 双向链表的结点结构如图所示。
图：双链表的结点结构
注：
● 双向链表也是由头指针唯一确定的，
● 增加头结点能使双链表的某些运算变得方便
● 由于在双向链表中既有前向链又有后向链，寻任一个结点的直接前驱结点与直接后继结点变得非常方便。
● 设指针p 指向双链表中某一结点，则有下式成立：
p->prior->next = p = p->next->prior
●
在双向链表中，那些只涉及后继指针的算法，如求表长度、取元素、元素定位等，与单链表中相应的算法相同，
● 但对于前插和删除操作则涉及到前驱和后继两个方向的指针变化，因此与单链表中的算法不同。
1、 双向链表的前插操作
【算法思想】欲在双向链表第i 个结点之前插入一个的新的结点，则指针的
变化情况如图所示：
… p  …
s->prior=p->prior; ①
p->prior->next=s;②
s->next=p; ③
p->prior=s;④
【算法描述】
int DlinkIns(DoubleList L,int i,ElemType e)
{
DNode  *s,*p;
… /*先检查待插入的位置i是否合法（实现方法同单链表的前插操作）*/
… /*若位置i合法，则到第i个结点并让指针p指向它*/
s=(DNode*)malloc(sizeof(DNode));
if (s)
{ s->data=e;
s->prior=p->prior; ①
p->prior->next=s; ②
s->next=p; ③
p->prior=s; ④
r eturn TRUE;
}
else return FALSE;
}
2、双向链表的删除操作
【算法思想】欲删除双向链表中的第i个结点，则指针的变化情况如图所示：
p->prior->next=p->next; ①
p->next->prior=p->prior; ②
free(p);
【算法描述】
int DlinkDel(DoubleList L,int i,ElemType *e)
{
DNode  *p;
…
/*先检查待插入的位置i 是否合法（实现方法同单链表的删除操作）*/
… /*若位置i 合法，则到第i 个结点并让指针p 指向它*/
*e=p->data;
p->prior->next=p->next;  ①
p->next->prior=p->prior;  ②
free(p);
return TRUE;
}sizeof 指针
3、 双向循环链表
双向链表可以有循环表，称为双向循环链表。
(a)空的双向循环链表
(b)非空的双向循环链表
图2.15 双向循环链表图示
4、 应用举例
编写算法：将一个循环双链表
L=（a,b,c,d ）转换为L=（b,a,c,d ）。
算法思想：实际上是改变表中两个元素的链接。在修改有关链域之前，注意做必要的备份。
本节要点：
单链表只能通过后继域从一个方向访问结点，双向链表可从两个方向访问任一结点，快速，方便。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。