六、双向链表 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结点的语句序列是------------
(1)P->next=P->next->next;(10) P->prior->next=P (2)P->prior=-P->prior->prior;(11) P->next->prior=P (3)P->next=S (12)P->next->prior=s (4)P->prior=S (13) P->prior->next=S (5S->next=P (14)P->next->prior=P->prior (6)S→> prior=P; (15)Q=P->next (7)S->next= P->next (16)Q=P→> prior; (8)S>prior= P->prior (17)free (P) (9)p->prior->next=p->next:(18 free(Q) 解答: a.(12)(7)(3)(6)3必须在12和7的后面,其余的顺序可变 b.(13)(8)(4)(5)同上 C.(15)(1)(11)(18)不可变 d.(16)(2)(10)(18)不可变 e.(9)(14)(17)
6 (1)P->next=P->next->next; (10) P->prior->next=P; (2)P->prior=P->prior->prior; (11) P->next->prior =P; (3) P->next=S; (12)P->next->prior=S; (4) P->prior=S; (13) P->prior->next=S; (5)S->next=P; (14) P->next->prior=P->prior (6)S->prior=P; (15)Q=P->next; (7) S->next= P->next; (16)Q= P->prior; (8) S->prior= P->prior; (17)free(P); (9) P->prior->next=p->next; (18)free(Q); 解答： a.(12)(7)(3)(6) 3必须在12和7的后面，其余的顺序可变 b.(13)(8)(4)(5) 同上 c.(15)(1)(11)(18) 不可变 d.(16)(2)(10)(18) 不可变 e.(9)(14)(17)
2.4静态链表 静态链表:在数组中增加一个(或两个)指针 域,这些指针域用来存放下一个(或上一个) 数据元素在数组中的下标,从而构成用数组 构造的单链表(或双链表)。静态链表中的 指针又称仿真指针
7 2.4 静态链表 静态链表：在数组中增加一个（或两个）指针 域，这些指针域用来存放下一个（或上一个） 数据元素在数组中的下标，从而构成用数组 构造的单链表（或双链表）。静态链表中的 指针又称仿真指针
例1:软考题:L=[23,17,47,05,31 05U17X23V31Y47Z 100 104 108 112 116 119 若此分量定义为指针型,属于动态链表(题目中是指针); 若此分量定义为整型(通常存放下标),则属于静态链表 静态单链表的类型定义如下: # define maXsize1000预分配最大的元素个数(连续空间 typedef struct DataType data;/,数据域 int next;//指示域 } component, SLinkList MAXSIZE;//这是一维结构型数组
8 静态单链表的类型定义如下： #define MAXSIZE 1000 //预分配最大的元素个数（连续空间 typedef struct { DataType data ; //数据域 int next ; //指示域 }component , SLinkList[MAXSIZE] ; //这是一维结构型数组 例1：软考题：L={ 23，17，47，05，31 } 若此分量定义为指针型，属于动态链表（题目中是指针）； 若此分量定义为整型（通常存放下标），则属于静态链表。 05 U 17 X 23 V 31 Y 47 Z 100 104 108 112 116 119
例2:一线性表S=(ZHAO,QIAN,SUN,LL,ZHOU, wU),用静态链表如何表示? data cur 说明1:假设S为 SLinkLlist型变量,则 0头结点1 S[ MAXSIZE]为—个静态链表; ZHAO S[0]next则表示第1个结点在数组中的 位置。 LI QIAN WU ZHOU 356042 说明2:如果数组的第个分量表示链表 的第k个结点,则 s[i]data表示第k个结点的数据; SUN s[i]next表示第k+1个结点即k的直 接后继)的位置。 1000
9 例 2：一线性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )，用静态链表如何表示？ data 1 ZHAO 3 LI 5 QIAN 6 WU 0 ZHOU 4 SUN 2 …… …… 0 1 2 3 4 5 6 … 1000 cur 说明1：假设S为SLinkList型变量，则 S[MAXSIZE] 为一个静态链表； S[0].next则表示第1个结点在数组中的 位置。 说明2：如果数组的第i个分量表示链表 的第k个结点，则： S[i].data表示第k个结点的数据； S[i].next 表示第k+1个结点(即k的直 接后继)的位置。 i 头结点
说明3:静态链表的插入与删除操作与普通链表一样,不需要移 动元素,只需修改指示器就可以了 例如:在线性表S=( ZHAO, QIAN,SUNL,ZHOU,WU的 QIAN,SUN之间插入新元素LIU,可以这样实现: data cur step1:将QAN的游标值存入next的 0头结点1|游标中 ZHAO 3 S[7]. next =s[3].next 5 step2:将QAN的游标换为新元素LIU 3 QIAN 的下标: WU 0 S[3. next =7 5 ZHOU 4 SUN 2 7 LIU 6 1000
10 说明3：静态链表的插入与删除操作与普通链表一样，不需要移 动元素，只需修改指示器就可以了。 例如：在线性表S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )的 QIAN, SUN之间插入新元素LIU，可以这样实现： S[7].next = S[3].next； Step2:将QIAN的游标换为新元素LIU 的下标： S[3].next = 7 Step1:将QIAN的游标值存入next的 游标中： data … … SUN 2 ZHOU 4 WU 0 QIAN 6 LI 5 ZHAO 3 0 1 1 2 3 4 5 6 1000 i cur 头结点 7 LIU 6 7