六、双向链表 1、双向链表的存储结构 双向链表:链表中每个结点除后继指针域和数 据域外还有一个前驱指针域。 其结点的结构为: prior data next 双向链表结点的结构体定义如下: typedef struct Node i DataType data; struct node mnext: struct Node *prior DLNode
1 六、双向链表 １、双向链表的存储结构 双向链表：链表中每个结点除后继指针域和数 据域外还有一个前驱指针域。 其结点的结构为： 双向链表结点的结构体定义如下： typedef struct Node { DataType data; struct Node *next; struct Node *prior; }DLNode; prior data next
带头结点的双向循环链表的结构示意图。 head 山s|十a=|a+ 与单链表类同,双向链表分带头结点和不带头结 点两种,也分有循环和非循环两种结构。下面仅讨论 带头结点的双向循环链表
2 s a0 a1 an 带头结点的双向循环链表的结构示意图。 head … 与单链表类同，双向链表分带头结点和不带头结 点两种，也分有循环和非循环两种结构。下面仅讨论 带头结点的双向循环链表
2、双向链表的操作实现 (1)前插设p已指向第i元素,请在第i元素前插入元素ⅹ ai-1 a 指针域的变化: ①al的后继从ar(指针是p)变为x(指针是s) s->next=p; p->prior->next=s; ②a的前驱从a1(指针是p> prior)变为x(指针是s; S->prior=p ->prior p->prior=s;
3 2、双向链表的操作实现 (1)前插 设p已指向第i 元素，请在第i 元素前插入元素x x s ai-1 ai p 指针域的变化： ① ai-1的后继从 ai ( 指针是p)变为x（指针是s) : s->next = p ; p->prior->next = s ; ② ai 的前驱从 ai-1 ( 指针是p->prior)变为 x ( 指针是s); s->prior = p ->prior ; p->prior = s ;
(2)双向链表的删除操作 设p指向第i个元素,删除第i个元素 aj-1 ai ai+1 指针域的变化: 后继方向:a1的后继由a;(指针p)变为aH1(指针p->next): p->prior->next= p->next 前驱方向:aH的前驱由a(指针p)变为a1(指针p→> prior); p->next->prior=p->prior;
4 p 指针域的变化： 后继方向：ai-1的后继由ai ( 指针p)变为ai+1(指针 p ->next ); p ->prior->next = p->next ; 前驱方向：ai+1 的前驱由 ai ( 指针p)变为ai-1 (指针 p -> prior ); p->next->prior = p ->prior ; (2)双向链表的删除操作 设p指向第i 个元素，删除第i 个 元素 ai-1 ai ai+1
例:已知P结点是双向链表的中间结点,试从下列 提供的答案中选择合适的语句序列。 a.在P结点后插入S结点的语句序列是 b.在P结点前插入S结点的语句序列是 c.删除P结点的直接后继结点的语句序列是 d.删除P结点的直接前驱结点的语句序列是 e.删除P结点的语句序列是
5 例:已知P结点是双向链表的中间结点，试从下列 提 供 的 答 案 中 选 择 合 适 的 语 句 序 列 。 a．在P结点后插入S结点的语句序列是-----------。 b．在P结点前插入S结点的语句序列是-----------。 c．删除P结点的直接后继结点的语句序列是- -----。 d．删除P结点的直接前驱结点的语句序列是-------。 e．删除P结点的语句序列是------------