2.3.4动态链表与静态链表 2.3.5双向链表 ·例2-2 ·双向链表 ,动态链表：（算法2.12，P31) ·问题 ■例2-3 如何在O(1)时间内找到一个结燕的直接前驱和后 继 ·求差集，即(A-B)U(B-A】 一双向链表 ·用静态链表：（算法2.17，P33~34) 。类型定义 VD edef struct DuLNode{ ElemType data; struct DuLNode prior: struct DuLNode "next: )DuLNode,*DuLinkList: ·基本操作：插入、别除 55/73 57B ☑图 2.3.5双向链表 23.5双向能表 ■双向链表 叭O ·双向链表 ·插入 中a0=… ·副除 00a8 o、'⑥06 一 ②x亡 可 ③ 1. 著有头结点，则第i-个结点一定存在，第个结点可能不存在： 若有头结点，则第11个结点和第个结点一定存在，第+1个结点 故让p指向第i-1个结点： 可能不存在；故让指肉第-1个结点或第个结点： 注意第7步： 注意第3步： if (s>next!=NULL)snext->prior =s: 重p>next-NUL小p>aex->pior=h->prior: 5773 回 58/73 图 2.3.6其他表示 123.6其他表示 存铺储构的具体设计 站合实脉问题操作的什在以及环境进行选取 ■有序表 一一种特殊的线性表 ·有序顺序表、有序链表 ElemType data; struct LNode *next; ,插入操作的特殊性：对于有序表，在插入一 >LNode,*Link,*Position; 个元素时，无须给出插入位置；其插入位置 typedef struct 与插入元素的值（序关键字）相关。 Link head,tail; int len; ListInsert L(LinkList L,int i,ElemType e) >LinkList; ListInsert_L(LinkList &L,ElemType e) 5/7万 图 图55/73 2.3.4 动态链表与静态链表 „ 例2-2 „ 动态链表: (算法2.12, P31) „ 例2-3 „ 求差集，即(A-B)U(B-A) „ 用静态链表: (算法2.17, P33~34) 56/73 „ 双向链表 „ 问题 如何在O(1)时间内找到一个结点的直接前驱和后 继？ ——双向链表 „ 类型定义 typedef struct DuLNode{ ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode, *DuLinkList; „ 基本操作：插入、删除 2.3.5 双向链表 57/73 „ 双向链表 „ 插入 2.3.5 双向链表 ai-1 ai 1 p 4 5 2 s 6 7 3 x 1. 若有头结点，则第i-1个结点一定存在，第i个结点可能不存在； 故让p指向第i-1个结点； 2. 注意第7步： if (s->next!=NULL) s->next->prior = s; 58/73 „ 双向链表 „ 删除 2.3.5 双向链表 p 1 2 3 4 存储池 ai-1 ai ai+1 1. 若有头结点，则第i-1个结点和第i个结点一定存在，第i+1个结点 可能不存在；故让p指向第i-1个结点或第i个结点； 2. 注意第3步： if (p->next!=NULL) p->next->prior = p->prior; 59/73 „ 存储结构的具体设计 结合实际问题操作的特征以及环境进行选取 如单链表的另一种结构 typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *Link, *Position; typedef struct { Link head, tail; int len; }LinkList; 2.3.6 其他表示 60/73 „ 有序表 ——一种特殊的线性表 „ 有序顺序表、有序链表 „ 插入操作的特殊性：对于有序表，在插入一 个元素时，无须给出插入位置；其插入位置 与插入元素的值(序关键字)相关。 ListInsert_L(LinkList & L, int i, ElemType e) Î ListInsert_L(LinkList & L, ElemType e) 2.3.6 其他表示