双向循环链表

双向循环链表能够访问前驱和后继，快速定位到尾节点，并在在尾部进行插入和删除，也能够找到任意节点前驱和后继，方便添加和删除元素。

双向链表的存储结构

1
2
3
4
typedef struct DulNode{
    ElemType data;
    struct DulNode *next,*prior;
}DulNode,*DulLinkList;

一个双向链表结点由三部分组成，分别是前驱指针，数据域，后驱指针。DulNode表示节点，*DulLinkList表示链表的头指针。

image-20240626094457416

链表初始化

1
2
3
4
5
6
7
8
9
10
/*初始化链表*/
Status InitList(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));
    if(L==NULL) return ERROR;
    L->next==L;
    L->prior=L;
    L->data=0;
    return OK;
}

初始化过程中，将前驱指向L自身，L的后继也指向自身，形成闭环。

image-20240626094828769

头插法和尾插法

头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*头插法*/
Status HeadCreateList(LinkList &L)
{
    int num;
    ElemType data;
    std::cin>>num;
    for(int i=0;i<num;i++){  
        std::cin>>data;
        LNode *s=(LNode *)malloc(sizeof(LNode));
        if(!s)  return ERROR;
        s->data=data;
        s->prior=L;
        s->next=L->next;
        L->next->prior=s;
        L->next=s;
    }
    return OK;
}

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*尾插法创建链表*/
Status TailCreateList(DulLinkList &L)
{
    LNode *tail=L;
    int num;
    ElemType data;
    std::cin>>num;
    for(int i=0;i<num;i++){  
        std::cin>>data;
        LNode *s=(LNode *)malloc(sizeof(LNode));
        if(!s) return ERROR;
        s->data=data;

        s->prior=L->prior;
        L->prior->next=s;
        L->prior=s;
        s->next=L;

    }
    return OK;
}

定位元素

获取第i个的元素的值

1
2
3
4
5
6
7
8
9
10
11
12
13
/*获取第i个的元素的值*/
Status GetElem(LinkList L,int i,ElemType &e)
{
    int j=1;
    LNode *p=L->next;
    while(p!=L&&j<i){
        p=p->next;
        j++;
    }
    if(p==NULL||j>i) return ERROR;
    e=p->data;
    return OK;
}

按值查找元素

1
2
3
4
5
6
7
8
9
/*按值查找节点*/
LNode *LocateElem(LinkList L,ElemType e)
{
    LNode *p=L->next;
    while(p!=L&&p->data!=e){
        p=p->next;
    }
    return p;
}

插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/*插入元素*/
Status ListInsert(DulLinkList &L,int i,ElemType e)
{
    int j=1;
    LNode* p=L->next;
    /*找到第i-1个元素*/
    while(p!=L&&j<i-1){
        p=p->next;
        j++;
    }
    LNode* s=(DulNode*)malloc(sizeof(LNode));
    if(!s) return ERROR;
    s->data=e;
    
    s->prior=p->prior;
    p->prior->next=s;

    s->next=p;
    p->prior=s;
    return OK;
}

删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*删除第i个元素*/
Status ListDelete(LinkList &L,int i)
{
    int j=1;
    LNode* p=L->next;
    /*找到第i-1个元素*/
    while(p&&j<i-1){
        p=p->next;
        j++;
    }
    DulNode *s=p->next;
    p->prior->next=s;
    s->prior=p->prior;
    free(s);
    return OK;
}

遍历链表

1
2
3
4
5
6
7
8
9
10
11
/*遍历链表*/
Status PrintList(LinkList L)
{
    LNode *p=L->next;
    while(p!=L){
        std::cout<<p->data<<"->";
        p=p->next;
    }
    std::cout<<std::endl;
    return OK;
}