一.双链表的初始化:
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode*prior, *next; //前驱和后继指针
}DNode,*DLinklist;
//初始化双链表
bool InitDLinkList(DLinklist &L){
L = ( DNode *) malloc(sizeof ( DNode) ) ; //分配一个头结点
if (L==NULL) //内存不足,分配失败
return false;
L->prior = NULL; //头结点的prior永远指向NULL
L->next = NULL; //头结点之后暂时还没有节点
return true;
}void testDLinkList( ) { //初始化双链表
DLinklist L;
InitDLinkList(L);
//后续代码........
}
tips:DLinklist 等价 DNode*
判断双链表是否为空(带头结点)
bool Empty(DLinklist L) {if (L->next == NULL)return true;elsereturn false;
}
二.双链表的插入:
//在p结点之后插入s结点
bool InsertNextDNode ( DNode *p,DNode *s )is->next=p->next; //将结点*s插入到结点*p之后p->next->prior=s;s->prior=p;p->next=s;
}
如图所示:
step1:
step2:
step3:
step4:
但是,如果p结点是双链表的最后一个结点,那么上述代码将会发生错误,下面为优化后的代码:
在p结点之后插入s结点
bool InsertNextDNode( DNode *p,DNode *s ){if ( p==NULL ls==NULL) //非法参数return false;
s->next=p->next;
if ( p->next != NULL) //如果p结点有后继结点p->next->prior=s;
s->prior=p;
p->next=s;
return true;
}
tips:在编写代码时要注意修改指针的顺序,如若语序不合理也会发生错误。
三.双链表的删除
//删除p结点的后继结点
bool DeleteNextDNode ( DNode *p){if ( p==NULL) return false;DNode *q = p->next; //找到p的后继结点qif (q==NULL)return false; //p没有后继p->next=q->next;if (q->next !=NULL) //q结点不是最后一个结点q->next->prior=p;free(q); //释放结点空间return true;
}
step1:
step2:
step3:
销毁一个双链表:
void DestoryList(DLinklist &L){//循环释放各个数据结点while (L->next != NULL)DeleteNextDNode(L);free(L); //释放头结点L=NULL; //头指针指向NULL
}
四.双链表的遍历:
1.前向遍历:
while (p!=NULL){//对结点p做相应处理p=p->prior;
}
前向遍历(跳过头结点):
while (p-> prior != NULL){//对结点p做相应处理p = p->prior;
}
2.后向遍历:
while (p!=NULL){//对结点p做相应处理,如打印p = p->next;
}