双向链表的插入和删除】"/>
【双向链表的插入和删除】
文章目录
- 双向链表
- 双向链表的插入
- 双向链表的删除操作
双向链表
双向链表的结构定义如下:
//双向链表的结构定义
typedef struct DuLNode {ElemType data;struct DuLNode* prior, * next;
}DuLNode,*DuLinkList;
双向链表的结点有两个指针域:prior,next。
双向循环链表
- 让头结点的前驱指针指向链表的最后一个结点。
- 让最后一个结点的后继指向头结点。
双向链表的对称性(设指针p指向某一结点):
p->prior->next = p = p->next->prior
双向链表的插入
将新结点s插入到p指针指向结点的前面。
①修改a结点的后继,a结点变成x的前驱。将x结点的前驱赋值a结点的地址,a结点的地址是b结点的前驱:p->prior。
s->prior = p->prior;
这个时候a结点就变成x结点的前驱结点了。
② 将x结点变成x结点的后继,这里是将a结点的next域由结点x的地址给出, p->prior->next = s;
③这里是将x的后继结点赋值,赋的b结点。
s->next = p;
④这里是将b结点的前驱结点赋值,赋的是s结点的地址。
p->prior = s;
【算法】双向链表的插入
//双链表的插入
int ListInsert(DuLinkList& L, int i, ElemType e) {//在带头结点的双向循环链表L中的第i个位置之前插入元素eDuLinkList p;if (L = NULL) {return 0;}DuLinkList s = new DuLNode;s->data = e;s->prior = p->prior;//s的前驱赋值p->prior->next = s;//前一个结点的后继也要赋值s->next = p;//再给s的后继赋值p->prior = s;//再给后一个结点的前驱赋值
}
双向链表的删除操作
将b节点删除,则a结点的后继就是c结点。c结点的前驱就是a结点。
①将a结点的后继改为c结点。需要给a结点的后继重新赋值。
p->prior->next = p->next.
②将c结点的前驱修改成a结点
p->next->prior = p->prior.
//双链表的删除
int ListDelete(DuLinkList& L, ElemType& e) {//删除带头结点的双向循环链表L的第i个元素,并用e返回。DuLinkList p;if (!(p == GetElem_Dul(L, i))) {return 0;}e = p->data;p->prior->next = p->next;//给前一个结点的后继赋值,赋的是后一个结点p->next->prior = p->prior;//给后一个结点的前驱赋值,赋的是前一个结点。free(p);return 1;
}
更多推荐
【双向链表的插入和删除】
发布评论