赞
踩
1、双向链表的定义:在单链表的每个结点里再增加一个指向其直接前驱的指针域prior,这样链表中就形成了有两个方向不同的链,故称为双向链表。
2、优点:双向链表可以克服单链表查找链表中某结点不方便的缺点。
3、双向循环链表:和单链的循环表类似,双向链表也可以有循环表。让头结点的前驱指针指向链表的最后一个结点,让最后一个结点的后继指针指向头结点。
1、双向链表结构的对称性:设指针P指向某一结点,侧有:
p->next->prior=p=p->prior->next
2、在双向链表中有些操作(如: ListLength、GetElem等) ,因仅涉及一个方向的指针,故它们的算法与线性链表的相同。但在插入、删除时,则需同时修改两个方向上的指针,则与单链表不相同。
1、双向链表的插入
①算法步骤,如下图所示:
②算法描述
- void ListInsert_DuL(DuLinkList &L, Int i, ElemType e) {
-
- //在带头结点的双向循环链表L中第i个位置之前插入元素e
- if(!(p=GetElemP_DuL(L,i))) return ERROR; //插入的位置是链表的第i个位置之前,否则返回错误
-
- s=new DuLNode;
-
- S->date=e;
-
- S->prior=p->prior;
-
- p->prior->next=s;
-
- S->next=p;
-
- p->prior=s;
-
- return OK;
-
- } // ListInsert_DuL

2、双向链表的删除
①算法步骤,如下图所示:
②算法描述
- void ListDelete_DuL(DuLink &L,Int i, ElemType &e){
-
- //删除带头结点的双向循环链表L的第i个元素,并用e返回。
-
- if(!(p=GetElemP_DuL(L,i))) return ERROR;
-
- e=p->data;
-
- p->prior->next = p->next;
-
- p->next->prior= p->prior;
-
- free(p);
-
- return OK;
-
- } // ListDelete_DuL

1、双向链表的结构定义如下:
typedef struct DuLNode{
Elemtype data;
struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;
2、双向链表结点结构
prior | data | next |
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。