第二章线性表——双向链表（6）

1 双向链表的结点及其类型定义

双向链表的结点的类型定义如下。

其结点形式如图2-7所示，带头结点的双向链表的形式如图2-8所示。 ;

1 typedef struct Dulnode
2 {     ElemType  data ;
3 struct Dulnode  *prior , *next ;
4 }DulNode ;

双向链表结构具有对称性，设p指向双向链表中的某一结点，

则其对称性可用下式描述： (p->prior)->next=p=(p->next)->prior ;

结点p的存储位置存放在其直接前趋结点p->prior的直接后继指针域中，

同时也存放在其直接后继结点p->next的直接前趋指针域中。

2 双向链表的基本操作

(1)  双向链表的插入  将值为e的结点插入双向链表中、

 1 ①  插入时仅仅指出直接前驱结点，钩链时必须注意先后次序是： “先右后左” 。部分语句组如下：
 2 S=(DulNode *)malloc(sizeof(DulNode)); 
 3 S->data=e;
 4 S->next=p->next;   p->next->prior=S;
 5 p->next=S;  S->prior=p;    /*  钩链次序非常重要  */



 6 ②   插入时同时指出直接前驱结点p和直接后继结点q，钩链时无须注意先后次序。部分语句组如下：
 7 S=(DulNode *)malloc(sizeof(DulNode));
 8 S->data=e;
 9 p->next=S;   S->next=q;
10 S->prior=p;   q->prior=S; 

(2) 双向链表的结点删除

设要删除的结点为p ，删除时可以不引入新的辅助指针变量，

可以直接先断链，再释放结点。

部分语句组如下：

p->prior->next=p->next;

p->next->prior=p->prior; free(p);

注意： 与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。