【数据结构】——拿捏链表 ( 带头双向循环链表 )2

2022-05-11 127

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】——拿捏链表 ( 带头双向循环链表 )2

⛲二、带头双向循环链表实现思路

和前面实现无头单向非循环链表类似，我们也要创建创建一个结点数据类型，里面为数据域和指针域，不过指针域里面要存放上一个结点的地址和下一个结点的地址。

typedef int LTDataType;//存储的数据类型

typedef struct ListNode
{
    LTDataType data;//数据域
    struct ListNode* prev;//前驱指针
    struct ListNode* next;//后继指针
}ListNode;

1.初始化链表

因为我们的链表是带头的，所以我们在初始化的时候需要开辟一个头结点出来
头结点的特征：**不存储有效数据，**所以我们初始化的时候不需要初始化头结点中的数据

我们为了满足循环的特征，将头结点的next和prev都指向自己

【数据结构】——拿捏链表 ( 带头双向循环链表 )_循环链表_04

//创建一个新结点
ListNode* BuyListNode(LTDataType x)
{
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if (node == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    node->data = x;//新结点赋值
    node->prev = NULL;
    node->next = NULL;

    return node;//返回新结点
}

//初始化链表
ListNode* ListInit()
{
    ListNode* phead = BuyListNode(-1);//申请一个头结点，头结点不存储有效数据
    //起始时只有头结点，让它的前驱和后继都指向自己
    phead->prev = phead;
    phead->next = phead;
    return phead;//返回头结点
}

2.Destroy & Clear

这一小部分主要是链表的销毁或者清除，这两唯一不同的区别就是:

destroy是把所有结点都删除且没有保留头结点，不能继续使用

clear保留了头结点，允许继续使用。所以destroy需要将头结点置空，所以需要用二级指针传址调用来改变一级指针从而达到将传递的指针置空的效果。

代码如下：

void ListClear(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }
}

void ListDestroy(ListNode** phead)
{
    assert(*phead);
    ListClear(*phead);
    free(*phead);
    *phead = NULL;
}

3.打印双向链表

打印双向链表时也是从头结点的后一个结点处开始向后遍历并打印，直到遍历到头结点处时便停止遍历和打印（头结点数据不打印）。

//打印双向链表
void ListPrint(ListNode* phead)
{
    assert(phead);

    ListNode* cur = phead->next;//从头结点的后一个结点开始打印
    while (cur != phead)//当cur指针指向头结点时，说明链表以打印完毕
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

4.查找元素

给定一个值，在链表中寻找与该值相同的结点，若找到了，则返回结点地址；若没有找到，则返回空指针(NULL)。

//查找元素
ListNode* ListFind(ListNode* phead, LTDataType x)
{
    assert(phead);

    ListNode* cur = phead->next;//从头结点的后一个结点开始查找
    while (cur != phead)//当cur指向头结点时，说明链表已遍历完毕
    {
        if (cur->data == x)
        {
            return cur;//返回目标结点的地址
        }
        cur = cur->next;
    }
    return NULL;//没有找到目标结点
}

增加结点

5.头插

头插，即申请一个新结点，将新结点插入在头结点和头结点的后一个结点之间即可。

【数据结构】——拿捏链表 ( 带头双向循环链表 )_C语言_05

//头插
void ListPushFront(ListNode* phead, LTDataType x)
{
    assert(phead);

    ListNode* newnode = BuyListNode(x);//申请一个结点，数据域赋值为x
    ListNode* front = phead->next;//记录头结点的后一个结点位置
    //建立新结点与头结点之间的双向关系
    phead->next = newnode;
    newnode->prev = phead;
    //建立新结点与front结点之间的双向关系
    newnode->next = front;
    front->prev = newnode;
}

6.尾插

尾插，申请一个新结点，将新结点插入到头结点和头结点的前一个结点之间即可。因为链表是循环的，头结点的前驱指针直接指向最后一个结点，所以我们不必遍历链表找尾。

【数据结构】——拿捏链表 ( 带头双向循环链表 )_C语言_06

//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);

    ListNode* newnode = BuyListNode(x);//申请一个结点，数据域赋值为x
    ListNode* tail = phead->prev;//记录头结点的前一个结点的位置
    //建立新结点与头结点之间的双向关系
    newnode->next = phead;
    phead->prev = newnode;
    //建立新结点与tail结点之间的双向关系
    tail->next = newnode;
    newnode->prev = tail;
}

7.在指定位置插入结点

在直到位置插入结点，准确来说，是在指定位置之前插入一个结点。我们只需申请一个新结点插入到指定位置结点和其前一个结点之间即可。

【数据结构】——拿捏链表 ( 带头双向循环链表 )_带哨兵的链表_07

//在指定位置插入结点
void ListInsert(ListNode* pos, LTDataType x)
{
    assert(pos);

    ListNode* before = pos->prev;//记录pos指向结点的前一个结点
    ListNode* newnode = BuyListNode(x);//申请一个结点，数据域赋值为x
    //建立新结点与before结点之间的双向关系
    before->next = newnode;
    newnode->prev = before;
    //建立新结点与pos指向结点之间的双向关系
    newnode->next = pos;
    pos->prev = newnode;
}

删除结点

8.头删

头删，即释放头结点的后一个结点，并建立头结点与被删除结点的后一个结点之间的双向关系即可。

【数据结构】——拿捏链表 ( 带头双向循环链表 )_带哨兵的链表_08

//头删
void ListPopFront(ListNode* phead)
{
    assert(phead);
    assert(phead->next != phead);

    ListNode* front = phead->next;//记录头结点的后一个结点
    ListNode* newfront = front->next;//记录front结点的后一个结点
    //建立头结点与newfront结点之间的双向关系
    phead->next = newfront;
    newfront->prev = phead;
    free(front);//释放front结点
}

9.尾删

尾删，即释放最后一个结点，并建立头结点和被删除结点的前一个结点之间的双向关系即可。

【数据结构】——拿捏链表 ( 带头双向循环链表 )_带哨兵的链表_09

//尾删
void ListPopBack(ListNode* phead)
{
    assert(phead);
    assert(phead->next != phead);

    ListNode* tail = phead->prev;//记录头结点的前一个结点
    ListNode* newtail = tail->prev;//记录tail结点的前一个结点
    //建立头结点与newtail结点之间的双向关系
    newtail->next = phead;
    phead->prev = newtail;
    free(tail);//释放tail结点
}

10.删除指定位置结点

删除指定位置结点，释放掉目标结点后，建立该结点前一个结点和后一个结点之间的双向关系即可。

【数据结构】——拿捏链表 ( 带头双向循环链表 )_C语言_10

//删除指定位置结点
void ListErase(ListNode* pos)
{
    assert(pos);

    ListNode* before = pos->prev;//记录pos指向结点的前一个结点
    ListNode* after = pos->next;//记录pos指向结点的后一个结点
    //建立before结点与after结点之间的双向关系
    before->next = after;
    after->prev = before;
    free(pos);//释放pos指向的结点
}

11.链表判空

链表判空，即判断头结点的前驱或是后驱指向的是否是自己即可。

12.获取链表中的元素个数

获取链表中的元素个数，即遍历一遍链表，统计结点的个数（头结点不计入）并返回即可。

//获取链表中的元素个数
int ListSize(ListNode* phead)
{
    assert(phead);

    int count = 0;//记录元素个数
    ListNode* cur = phead->next;//从头结点的后一个结点开始遍历
    while (cur != phead)//当cur指向头结点时，遍历完毕，头结点不计入总元素个数
    {
        count++;
        cur = cur->next;
    }
    return count;//返回元素个数
}