一: 双链表的初始化(带头结点)
1.1 初始化实现代码
typedef struct DNode{
ElemType data;
struct DNode *prior,*next;//prior:前驱结点
}DNode,*DLinkList;
//初始化双链表
bool InitDLinkList(DLinkList){
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);
//后续代码。。。
}
1.2 判断双链表是否为空
//判断双链表是否为空(带头结点)
bool Empty(DLinklist L){
if(L->next == NULL)
return true;
else
return false;
}
二:双链表的插入
2.1 实现代码
//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
if(p==NULL || s==NULL)//非法参数
return false;
s->next = p->next;//将结点*s插入到结点*p之后
if(p->next != NULL) //如果p结点有后继结点
p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}
2.2 插入的不是最后一个结点的执行流程
执行过程:如果插入的结点不是双链表的最后一个结点的话
-
插入的链表如下:
-
s->next = p->next;
-
p->next->prior = s;
-
s->prior = p;
-
p->next = s;
2.3 插入的是最后一个结点的执行流程
执行过程2:如果插入的结点是双链表的最后一个结点的话
-
s->next = p->next;
-
进行判断,得出没有后继结点,所有执行s->prior = p;
-
p->next = s;
三:双链表的删除
3.1 删除结点的后继结点实现代码
//删除p结点的后继结点
bool DeleteNextNode(DNode *p){
if(p==NULL)
return false;
DNode *q = p->next;//找到p的后继结点q
if(q==NULL)// p没有后继
return false;
p->next = q->next;
if(q->next!=NULL)//q结点不是最后一个结点
q->next->prior = p;
free(q);//释放结点空间
return true;
}
3.2 删除的不是最后一个结点的执行流程
执行流程:
-
p->next = q->next;
-
q->next->prior = p;
-
free(q);
3.3 删除的是最后一个结点的执行流程
执行流程:
-
p->next = q->next;
-
结果判断,为null所以不执行q->next->prior = p;
-
free(q);
3.4 销毁一个双链表实现代码
void DestoryList(DLinklist &L){
//循环释放各个数据结点
while(L->next != NULL)
DeleteNextDNode(L);
free(L);//释放头结点
L=NULL;//头指针指向NULL
}
四:双链表的遍历
4.1 后向遍历
while(p!=NULL){
//对结点p做相应处理,如打印
p = p->next;
}
4.2 前向遍历
while(p!=NULL){
//对结点p做相应处理,如打印
p = p->prior;
}
4.3 前向遍历(跳过头结点)
while(p->prior!=NULL){
//对结点p做相应处理,如打印
p = p->prior;
}
4.4 时间复杂度
双链表不可随机存取,按位查找、按值查找操作都只能用遍历的方式实现。
时间复杂度O(n)