双链表全部知识总结(初始化、插入、删除、遍历)
【摘要】 1.双链表的初始化初始化双链表:首先通过malloc函数分配一个头结点空间,通过判断链表L是否为空来确定是否分配成功。将头结点的prior永远指向NULL,头结点的下一个结点暂时没有所以也指向NULLbool InitDLinkList(DLinkList &L){ L=(DNode *) malloc(sizeof(DNode)); if(L==NULL) ret...
1.双链表的初始化
初始化双链表:首先通过malloc函数分配一个头结点空间,通过判断链表L是否为空来确定是否分配成功。将头结点的prior永远指向NULL,头结点的下一个结点暂时没有所以也指向NULL
bool InitDLinkList(DLinkList &L){
L=(DNode *) malloc(sizeof(DNode));
if(L==NULL)
return false;
L->prior=NULL;
L->next=NULL;
retrun true;
}
1.1 判断双链表是否为空
要想判断双链表是否为空,即判断头结点的next的指针是否为空
bool Empty(DLinkList L){
if(L->next==NULL)
return false;
else
return true;
}
2.双链表的插入
实现需求:在p结点之后插入s结点
2.1 p结点不是最后一个结点
分析步骤:
- 首先会把s结点指向p->next结点
- p的后继结点的前向指针指向s
- s结点的前向指针指向p结点
- p的后向指针指向s结点
代码实现:
bool InsertNextDNode(DNode *p, DNode *s){
s->nest=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;
}
2.2 p结点是最后一个结点
当p结点是最后一个结点的时候,显然这时候p->next=NULL,所以就需要对 p->next->prior=s
改良,判断p结点是否有后续结点,从而判断是不是需要修改p下一个结点的前向指针
if(p==NULL || S==NULL)
return false;
s->next=p->next;
if(p->next!=NULL)
p->next->prior=s;
3.双链表的删除
3.1 删除p的后继节点
分析:和插入的思考方式一样,同样我们需要考虑p的后继结点是否为NULL。
- 找到p的后继结点
- 判断p的后继结点是否为NULL,为NULL即p没有后继
- 将p的下一个结点指向q的下一个结点
- 判断q结点是否为最后一个结点
- free(q)
代码实现:
bool DeleteNextDNode(DNode *p){
if(p==NULL)
return false;
DNode *q=p->next;
if(q==NULL)
return false;
p->next=q->next;
if(q->next!=NULL)
q->next->prior=q;
free(q);
return true;
}
3.2 销毁链表
实现步骤:
- 循环释放各个数据结点
- 同时释放头结点
- 头指针指向空
void DestoryList(DLinkList &L){
while(L->nex!=NULL)
DeleteNextDNode(L);
free(L);
L=NULL;
}
4.双链表的遍历
对结点p做相应的处理,如打印
4.1 后向遍历
while(p!=NULL){
p=p->next;
}
4.2 前向遍历
while(p!=NULL){
p=p->prior;
}
4.3 前向遍历(跳过头结点)
while(p->prior=NULL){
p=p->prior;
}
5.总结
- 修改指针的时候需要注意顺序
- 双链表可以很方便的找到给定结点的前驱节点,对前驱节点执行后插操作,这样就可以实现按位序插入的前插操作。
- 双链表不具备随机存取特性,查找操作只能通过顺序遍历实现
【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)