双向链表
2022-03-05 本文已影响0人
lxr_
双向链表是在单链表的每个结点中,在设置一个指向其前驱结点的指针域。如下图所示
双向链表也可以是循环表,成为双向循环链表,如下图所示
image.png
可以看出其具有对称性,即p->next->prior=p=p->prior->next
1.双向链表是单链表扩展出来的结构,所以它的很多操作与单链表相同的(用其中一个指针域next或prior即可),如求长度的ListLength,查找元素的GetElem,获得元素位置的LocateELem等。
2.同理,双向循环链表也与单循环链表有很多操作相同。
重点看一下双向循环链表的插入和删除:
DuLinkList.h
#pragma once
#pragma once
// 函数结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型,其值是函数结果状态代码
typedef int Status;
//数据类型
typedef int ElemType;
typedef struct DuLNode
{
ElemType data;
DuLNode* next, * prior;
}DuLNode, * DuLinkList;
//双向循环链表初始化
Status InitList_DuL(DuLinkList& L);
//返回双向循环链表中第i个结点
DuLNode* LocateElemP_DuL(DuLinkList L, int i);
//在带头结点的双向循环链表L中第i个位置之前插入元素e
Status ListInsert_DuL(DuLinkList& L, int i, ElemType e);
//删除带头结点的双向循环链表L的第i个元素,并用e返回
Status ListDelete_DuL(DuLinkList& L, int i, ElemType& e);
//遍历双向循环链表
void ListTraverse_DuL(DuLinkList L);
DuLinkList.cpp
#include "DuLinkList.h"
#include <iostream>
using namespace std;
//双向循环链表初始化
Status InitList_DuL(DuLinkList& L)
{
L = new DuLNode;
L->next = L; //头结点的后继为头结点
L->prior = L; //头结点的前驱为头结点
cout << "初始化成功" << endl;
return OK;
}
//返回链表中第i个结点
DuLNode* LocateElemP_DuL(DuLinkList L, int i)
{
DuLNode* p = L->next; //第一个结点
int j = 1;
while (p != L && j < i) //到最后一个节点或这到第i个结点
{
p = p->next;
j++;
}
if (j != i) //不相等表示插入位置不合理
{
return NULL;
}
return p;
}
插入(在第i个结点之前插入新结点):
步骤:
1.先找到第i个结点p
2.新结点s的前驱为结点p的前驱
3.结点p的前驱的后继为新结点s
4.新结点s的后继为结点p
5.结点p的前驱为新结点s
当然,也可找到第i-1个结点q,利用此结点进行插入
//在带头结点的双向循环链表L中第i个位置之前插入元素e
Status ListInsert_DuL(DuLinkList& L, int i, ElemType e)
{
DuLNode* p = LocateElemP_DuL(L, i); //返回链表中第i个元素结点,即为要插入结点的后继结点
if (!p)
{
cout << "位置不合理" << endl;
return ERROR;
}
DuLNode* s = new DuLNode; //建立新结点
s->data = e;
s->prior = p->prior; //新结点前驱为原来p结点的前驱
p->prior->next = s; //原来p结点前驱的后继本来还是p结点,现在改为新结点
s->next = p; //新结点的后继为p结点
p->prior = s; //p结点的前驱为新结点
cout << "插入成功" << endl;
return OK;
}
删除(删除第i个结点p):
步骤:
1.先找到第i个结点p
2.结点p的前驱的后继为p的后继
3.结点p的后继的前驱为p的前驱
//删除带头结点的双向循环链表L的第i个元素,并用e返回
Status ListDelete_DuL(DuLinkList& L, int i, ElemType& e)
{
DuLNode* p = LocateElemP_DuL(L, i);
if (!p || p == L)
{
cout << "位置不合理" << endl;
return ERROR;
}
p->prior->next = p->next;
p->next->prior = p->prior;
e = p->data;
cout << "删除" << e << "成功" << endl;
delete p;
return OK;
}
//遍历双向循环链表
void ListTraverse_DuL(DuLinkList L)
{
DuLNode* p = L->next;
while (p != L)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
main.cpp
测试:
#include <iostream>
#include "DuLinkList.h"
using namespace std;
int main(int argc, char** argv)
{
DuLinkList L;
InitList_DuL(L); //初始化双向循环链表
ListInsert_DuL(L, 1, 1); //双向循环链表第一个位置插入1
ListInsert_DuL(L, 2, 2);
ListInsert_DuL(L, 3, 3);
ListInsert_DuL(L, 5, 5); //测试插入是否成功
ListTraverse_DuL(L); //遍历
ElemType e;
ListDelete_DuL(L, 1, e); //删除第一个元素所在节点
ListDelete_DuL(L, 2, e);
ListDelete_DuL(L, 2, e); //测试删除是否成功
ListTraverse_DuL(L);
return 0;
}