0


链表之“带头双向循环链表”

1.链表的分类

    链表会根据是单向或者双向,带头或者不带头,循环或者非循环进行分类组合。以上情况组合起来就有8种链表结构。

其中,头指针头节点是两个概念:

  • 头指针: 它是一个指针,指向链表中第一个节点的地址。
  • 头节点:它是一个结构体,区分数据域和指针域。数据域不存储元素,指针域则存放第一个节点的地址。
  • 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
  • 带头双向循环链表:带头是指链表最前面有一个头节点,它是一个结构体变量,分为数据域和指针域,数据域一般不存储数据,指针域存放的是第一个元素的地址。双向是指一个节点中有两个指针域,一个叫前驱指针,指向当前节点的前一个节点的指针,用于向前遍历;一个叫后继指针,指向当前节点的后一个节点的指针,用于向后遍历。循环是指链表最后一个节点的指针域存放的是头节点的地址,这样一来,整个链表就形成了循环的效果。

2.带头双向循环链表的实现

1.创建结构体

因为是带头双向循环链表,所以我们要定义两个指针,一个前驱指针,指向当前节点的前一个节点;还有一个后继指针,指向当前节点的后一个节点。

typedef int LTDataType;

typedef struct ListNode
{
    struct ListNode* next;//后继指针
    struct ListNode* prev;//前驱指针
    LTDataType val;
}LTNode;

2.创建返回链表的头节点

//返回创建链表的头节点
LTNode* CreateLTNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        perror("malloc");
        exit(-1);
    }

    newnode->val = x;
    newnode->next = NULL;
    newnode->prev = NULL;

    return newnode;
}

3.双向链表销毁

//销毁
void LTDestory(LTNode* phead)
{
    assert(phead);

    LTNode* cur = phead->next;
    while (cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);
}

4.双向链表打印

要想打印链表中的值,就得找到跳出循环的条件。因为哨兵位不存储有效的值,所以我们可以定义一个cur变量,让它指向哨兵位的下一个节点,如果cur != phead,就打印值,直到cur走到哨兵位就跳出循环。

//打印
void LTPrint(LTNode* phead)
{
    assert(phead);

    LTNode* cur = phead->next;
    printf("哨兵位<=>");
    while (cur != phead)
    {
        printf("%d<=>", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

5.双向链表尾插

带哨兵位的头节点不可能为空,哪怕链表一个值都没有,它也是指向自己的,所以要断言一下。尾插的第一步首先要找到尾,双向链表中找尾非常简单,哨兵位的前一个节点phead->prev就是尾,然后将尾节点tail的后继指针指向新节点newnode,新节点newnode的前驱指针指向tail;再将新节点newnode的后继指针指向哨兵位phead,哨兵位phead的前驱指针指向新节点newnode。

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);

    LTNode* tail = phead->prev;//找尾节点
    LTNode* newnode = CreateLTNode(x);

    //phead       tail   newnode
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
}

6.双向链表尾删

因为哨兵位不可能为空,所以还是得先断言一下。当链表为空时,我们不能在进行尾删,但是此时链表里边还有个哨兵位,我们得保证不能将哨兵位也删掉,所以哨兵位也得断言一下,因为链表为空时哨兵位是指向它自己的,所以断言的条件应该写成assert(phead->next != phead)。尾删时一样得先找到尾,即哨兵位得前一个节点phead->prev,因为要free掉尾,所以还得找到尾的前一个节点tailprev = tail->prev。这两个都找到后,先free掉tail,然后让tail的前一个节点tailprev的后继指针指向哨兵位phead,再让哨兵位phead的前驱指针指向tailpeev。

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

    LTNode* tail = phead->prev;
    LTNode* tailprev = tail->prev;

    free(tail);
    tailprev->next = phead;
    phead->prev = tailprev;
}

7.双向链表头插

头插时我们先搞一个新节点newnode出来,然后将newnode与哨兵位和第一个节点链接起来就可以了。但是这儿得注意一下,我们要将newnode与第一个节点链接,然后将哨兵位与newnode链接,如果先将哨兵位与newnode链接容易找不到第一个节点,就会很麻烦。

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = CreateLTNode(x);

    //第1种方法
    //newnode->next = phead->next;
    //phead->next->prev = newnode;
    //phead->next = newnode;
    //newnode->prev = phead;

    //第2种方法
    LTNode* first = phead->next;
    newnode->next = first;
    first->prev = newnode;
    phead->next = newnode;
    newnode->prev = phead;
}

8.双向链表头删

头删时我们还得注意链表不能为空的情况,即哨兵位不能被删掉,所以还得断言assert(phead->next != phead)。只有销毁链表的时候才能将哨兵位free掉。

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

    LTNode* first = phead->next;
    LTNode* second = first->next;

    phead->next = second;
    second->prev = phead;
    free(first);
    first = NULL;
}

9.双向链表查找

查找可以配合其它函数来使用,如果找到了,就返回那个节点的地址,找不到,则返回空。

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
    assert(phead);

    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->val == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

10.双向链表在pos的前面进行插入

将这个函数写完后,我们在回过头看头插、尾插,发现头插、尾插刚好可以利用这个函数以一种更简便的方式来实现。LTInsert(phead->next, x)就是头插,因为phead的下一个节点刚好就是头节点,在头节点的前面插入就是头插;LTInsert(phead, x)就是尾插,因为phead的前一个节点刚好就是尾。

//在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
    assert(pos);

    LTNode* posprev = pos->prev;
    LTNode* newnode = CreateLTNode(x);

    posprev->next = newnode;
    newnode->prev = posprev;
    newnode->next = pos;
    pos->prev = newnode;
}

11.双向链表删除pos位置的节点

这个删除操作也可以用来头删和尾删,头删就是LTErase(phead->next),尾删就是LTErase(phead->prev)。

//删除pos的值
void LTErase(LTNode* pos)
{
    assert(pos);

    LTNode* posprev = pos->prev;
    LTNode* posnext = pos->next;

    posprev->next = posnext;
    posnext->prev = posprev;
    free(pos);
}

3.源码

🌻List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;

typedef struct ListNode
{
    struct ListNode* next;//后继指针
    struct ListNode* prev;//前驱指针
    LTDataType val;
}LTNode;

//初始化
LTNode* LTInit();
//返回创建链表的头节点
LTNode* CreateLTNode(LTDataType x);
//打印
void LTPrint(LTNode* phead);

//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);

//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

//在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
//删除pos的值
void LTErase(LTNode* pos);

//销毁
void LTDestory(LTNode* phead);

🌻List.c

#include "List.h"

//初始化
LTNode* LTInit()
{
    LTNode* phead = CreateLTNode(-1);

    phead->next = phead;
    phead->prev = phead;

    return phead;
}

//返回创建链表的头节点
LTNode* CreateLTNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        perror("malloc");
        exit(-1);
    }

    newnode->val = x;
    newnode->next = NULL;
    newnode->prev = NULL;

    return newnode;
}

//打印
void LTPrint(LTNode* phead)
{
    assert(phead);

    LTNode* cur = phead->next;
    printf("哨兵位<=>");
    while (cur != phead)
    {
        printf("%d<=>", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);

    //第1种方法
    LTNode* tail = phead->prev;//找尾节点
    LTNode* newnode = CreateLTNode(x);

    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;

    //第2种方法
    //LTInsert(phead, x);
}

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

    //第1种写法
    LTNode* tail = phead->prev;
    LTNode* tailprev = tail->prev;

    free(tail);
    tailprev->next = phead;
    phead->prev = tailprev;

    //第2种写法
    //LTErase(phead->prev);
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = CreateLTNode(x);

    //第1种方法
    //newnode->next = phead->next;
    //phead->next->prev = newnode;
    //phead->next = newnode;
    //newnode->prev = phead;

    //第2种方法
    LTNode* first = phead->next;
    newnode->next = first;
    first->prev = newnode;
    phead->next = newnode;
    newnode->prev = phead;

    //第3种方法
    //LTInsert(phead->next, x);

}

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

    //第1种写法
    LTNode* first = phead->next;
    LTNode* second = first->next;

    phead->next = second;
    second->prev = phead;
    free(first);
    first = NULL;

    //第2种写法
    //LTErase(phead->next);
}

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
    assert(phead);

    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->val == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

//在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
    assert(pos);

    LTNode* posprev = pos->prev;
    LTNode* newnode = CreateLTNode(x);

    posprev->next = newnode;
    newnode->prev = posprev;
    newnode->next = pos;
    pos->prev = newnode;
}

//删除pos的值
void LTErase(LTNode* pos)
{
    assert(pos);

    LTNode* posprev = pos->prev;
    LTNode* posnext = pos->next;

    posprev->next = posnext;
    posnext->prev = posprev;
    free(pos);
}

//销毁
void LTDestory(LTNode* phead)
{
    assert(phead);

    LTNode* cur = phead->next;
    while (cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);
}

4.顺序表和链表的区别


本文转载自: https://blog.csdn.net/weixin_65931202/article/details/136344235
版权归原作者 南风与鱼 所有, 如有侵权,请联系我们删除。

“链表之“带头双向循环链表””的评论:

还没有评论