2021年双向链表.ppt

void dele(s)
NODE *s;
{ NODE *p,*q;
p=s;
while (p->link!=s)
{ q=p;
p=p->link;}
q->link=s;
free(p);
}
*
双向链表
*
编写在链表中s结点之前插入新结点的算法
s
q
p
*
双向链表
*
要访问某个结点的前趋结点很麻烦,…...
要删除链表中一个结点时,仅给出该结点的指针还不行……
在指定的结点之前插入一个新结点…..
*
双向链表
*
双向链表
左指针:llink 指向该结点的前趋结点
右指针:rlink 指向该结点的后继结点
llink data rlink
*
双向链表
*
#include <>
struct node { char data;
struct node *llink,*rlink;
};
typedef struct node NODE;
NODE *head;
*
双向链表
*
双向链表
^
head
^
…...
^
…...
空的双向链表
非空的双向链表
head
head=NULL
*
双向链表
*
环形双向链表
^
head
…...
…...
空的环形双向链表
非空的环形双向链表
head
p->rlink->llink= p->llink->rlink= p
*
双向链表
*
带表头结点的双向链表
head
空的带表头结点双向链表
^
^
…...
^
…...
非空的带表头结点双向链表
^
head
*
双向链表
*
带表头结点的环形双向链表
head
空的带表头结点环形双向链表
…...
…...
非空的带表头结点环形双向链表
head
*
双向链表
*
带表头的环形双向链表的插入
…...
^
…...
x
p
y
1
4
q
2
3
*
*
将值为y的结点插在值为x的结点之后
->rlink=p->rlink
->rlink=q
->rlink->llink=q
->llink=p
*
双向链表
*