0
0

双向链表，这也太简单了吧！(C语言实现)

   这部分内容建议大家在电脑上观看，这样的话效果会更好。

1.介绍：

   双向链表也是一种线性表，它区别于单链表的话，那是单链表是不带头单向不循环链表，而双链表是带头双向循环链表。

2e6f64cfb8f44cb0a430d37adf4a5d23.png

由上图我们可知，双向链表是有一个头节点的（也叫哨兵位），这个头节点在双向链表中起到的就是头指针的作用，双向链表是一种循环链表，是双向可循环的一种链表，哨兵位在这里虽然它是存在在双线链表当中的，但是在这里我们不会去访问它的，也就是说，他在这里只是起到一个头指针的作用。双向链表的每一个节点它都是由数据和一个指向下一个节点的指针再加上一个指向前一个节点的指针组成的。

2.实现：

   我们在讲实现的的步骤之前，我们先要了解一下，其实这个头指针它在链表这里面是指的是一个哨兵位节点，他其实也属于一个节点，只不过我们不去访问这个哨兵位节点，因此，它在这里实际上就是只起到一个节点的作用，它其实也没有我们想的那么高级。

(1).双向链表的定义

   （定义一个结构体，将数据，一个指向下一个节点的指针，一个指向前一个节点的指针全部都放到结构体中，那么，我们在建立节点的时候就建立一个结构体大小的节点即可）：

typedef int LTDataType;//双向链表中存放的数据它不只能存放固定一种类型的元素，还有可能存放char类型等等一些其他不同的类型，因此我们这里将int这个类型改一个名字，方便我们下次想再次使用该双向链表存放一些其他类型的数据时容易替换，否则，假如说你建立了一个拥有10000个节点的双向链表，里面的数据类型全部都是int类型，这时突然想存放char类型的数据，就需要将int 全部换为char类型，太过于麻烦，因此，我们在这里将数据类型换一个名字，好方便后续更换。

typedef struct ListNode

{
       LTDataType data;//该节点中存放的数据。

       struct ListNode*prev;//指向前一个节点的指针。

       struct ListNode*next;//指向后一个节点的指针。

}LTNode;//换一个名字，方便写。

(2).建立一个结构体大小的双向链表的节点：

   双向链表是通过指针将一个个在内存中分散开来的节点连接起来的，为此，我们就必须要建立节点来完成双向链表中对于数据的存储，这里我们在建立节点的时候，使用malloc函数来建立节点。

LTNode*LTBuyNode(LTDataType x)

{

       LTNode*node=(LTNode*)malloc(sizeof(LTNode));//建立一个新的节点，再进行插入元素的时候或者是进行建立哨兵位的时候。

       if(node==NULL)

       {
              perror("malloc fail");

              return NULL;

       }//判断是否开创节点成功

       node->data=0;//如果初始化成功，接下来，就要对节点中的变量进行初始化操作。

       node->prev=node->next=node;//这里我们并没有将指针直接初始化为NULL，这是我们基于双向链表的特点，由于双向链表是循环链表，我们为了顺应这中特点，就将新建立好的节点设置成循环样式的，也就是让节点的两个指针均指向节点它自己，这样就达到了循环效果。
}

建立好的节点如下图所示：

2e4e30b35244408fb289972b0a5247d5.png

(3).双向链表的初始化：

   这里的初始化操作和前面的一些操作的初始化是不一样的，双向链表它在为空的时候，链表中并不是一个节点都没有，而是存在有一个哨兵位，也就是说，不管双向链表它怎么变化，该链表始终都存在有一个哨兵位，所以，我们在进行双向链表的初始化操作时，其实就是创建一个哨兵位。

//双向链表的初始化
LTNode* LTInit()
{
    LTNode* phead = LTBuyNode(-1);//由于哨兵位的作用在这里只是起到一个指针的作用，我们并不用去访问哨兵位节点，因此，我们在建立好后哨兵位节点后，将其中的变量进行初始化操作时，data随便给它赋如何的值都可以。
    return phead;
}

(4).双向链表的打印：

   将双向链表中的所有的节点中存储的元素全部都打印出来。

void LTPrint(LTNode* phead)
{
    bool pas = LTEmpty(phead);//判断是否含有哨兵位（ LTEmpty这个函数下面会讲到，这里我们只需要知道它是判断链表是否为空就可以了）。
    if (pas == true)//如果链表为空，就对它其中的所有的节点中存储的值一一进行访问，将其一一的打印出来。
    {
        LTNode* pcur = phead->next;//因为这里我们传过来的phead指针是哨兵位，是不用去访问它的，所以我们在这里定义一个指针的时候，是让它指向哨兵位后面那个节点的。
        while (pcur != phead)//因为链表是循环结构，链表不指向空，我们只能判断它不指向哨兵位就行了。
        {
            printf("%d->", pcur->val);//打印元素
            pcur = pcur->next;//让指针走到下一个节点的位置，以遍历链表
        }
        printf("NULL\n");//当程序运行这里时，说明链表已经遍历结束了
    }
    else//说明链表中不含有哨兵位，链表为空
    {
        return 1;//直接返回就行，结束程序运行
    }
}

(5).双向链表的尾插：

   在原链表后面插入一个新的节点。

void LTPushBack(LTNode* phead, LTDataType x)
{
    bool pas = LTEmpty(phead);//既然要尾插元素，就要判断一下phead这个指针是否接收到了实参传过来的哨兵位的地址，LTEmpty，这个函数我们暂时还没有说到，后面会说，这里我们只需要知道这个函数是判断是否为空就可以了。
    if (pas == true)//如果pas指针为true，则证明不为空，说明含有哨兵位的存在。
    {
        LTNode* newnode = LTBuyNode(x);//插入元素，首先要建立一个节点。

        //接下来，我们开始进行插入节点的操作，我们再进行插入节点的时候，需要注意一件事情，就是必须先将刚刚开创的新节点的两个指针给进行赋值操作，这样不会造成节点的丢失问题，否则的话，我们会找不到相应的节点。从而造成插入错误的问题。。
        newnode->next = phead;//我们先将新开创的节点的next指针赋值，让其指向第一个节点（根据双向链表的特点来决定这里新节点的两个指针应该指向哪里）。
        newnode->prev = phead->prev;//让新节点的prev指针指向第一个指针指向的节点，也就是原链表中的最后一个节点。

        //处理好新节点之后，接下来我们来将链表中的一些指针的指向来换一下，使其成为一个新的完整的双向链表。
        phead->prev->next = newnode;//这里我们先让第一个指针的prev指针的next指针指向新节点，这一步操作就相当于是将原链表中的尾节点的next指针指向新节点。
        phead->prev = newnode;//再让第一个指针的prev指针指向新节点。
    }
    else//如果pas指针为假，则直接结束程序。
    {
        return 1;//返回1（不正当返回）
    }
}

5526b914069849e59e82c8c279dbb3d1.png

(6).双向链表的头插：

   在原链表之前再插入一个新节点，让这个新插入的节点作为原链表中新的第一个节点，就是哨兵位后面那个节点。

void LTPushFront(LTNode* phead, LTDataType x)
{
    bool pas = LTEmpty(phead);//既然要尾插元素，就要判断一下phead这个指针是否接收到了实参传过来的哨兵位的地址，LTEmpty，这个函数我们暂时还没有说到，后面会说，这里我们只需要知道这个函数是判断是否为空就可以了。
    if (pas == true)//如果pas指针为true，则证明不为空，说明含有哨兵位的存在。
    {
        LTNode* newnode = LTBuyNode(x);//插入元素，首先要建立一个节点。

        //接下来，我们开始进行插入节点的操作，我们再进行插入节点的时候，需要注意一件事情，就是必须先将刚刚开创的新节点的两个指针给进行赋值操作，这样不会造成节点的丢失问题，否则的话，我们会找不到相应的节点。从而造成插入错误的问题。
        newnode->next = phead->next;//我们先将新开创的节点的next指针赋值，让其指向第一个节点（根据双向链表的特点来决定这里新节点的两个指针应该指向哪里）。
        newnode->prev = phead;//再将新节点的prev指针指向第一个节点。
        phead->next->prev = newnode;//让第一个节点的next指针的prev指针指向新节点，也就是让原链表中的第一个节点的next指针指向新节点。
        phead->next = newnode;/再让第一个指针的next指针指向新节点就可以了。
    }
    else
    {
        return 1;
    }
}

8fcf8aa223be4a4b910b401076bd4fc6.png

（这里的图画的有一点粗糙，需要结合上述的代码看，如果大家对哪里有疑问，可以随时在评论区问我，评论区随时都欢迎大家发言。）

(7).双向链表的尾删：

   删除链表中的最后一个节点。

void LTPopBack(LTNode* phead)
{
    bool pas = LTEmpty(phead);//与上解释相同
    bool fas = LTEmpty(phead->next);//这里我们既然要删除节点，首先就要保证原链表中含有节点（哨兵位除外）。
    if (pas == true && fas == true)
    {
        LTNode* del = phead->prev;//这里我们定义一个指针让其指向链表中的最后一个节点，由于我们在这里要删除节点，所以我们必须将原链表中的指针进行重新的指向，指向完毕后，就不会再有指针指向我们想要删除的节点了，因此，我们在这里必须定义一个指针指向要删除的节点。
        phead->prev = del->prev;//这里我们先将哨兵位的prev指针指向尾节点。
        del->prev->next = phead;//然后我们再将尾节点的prev指针指向的next指针指向哨兵位节点，也就是原链表中的倒数第二个节点的next节点指向哨兵位节点。
        //上面这两步在这里可以进行相互交换，只不过会代码有所不同，大家可以自行去进行修改。
        free(del);//将尾节点删除掉。
        del = NULL;
    }
    else
    {
        return 1;
    }
}

ffad4688d0a74313992f6124ed2eb5b0.png

(8).双向链表的头删：

   将链表中得到除哨兵位以外的第一个节点删除掉。

void LTPopFront(LTNode* phead)
{
    bool pas = LTEmpty(phead);
    bool fas = LTEmpty(phead->next);//以上两句代码与上面那一步的解释相同。
    if (pas == true && fas == true)
    {
        assert(phead && phead->next);//既然我们这里要进行头删操作，那么，我们就要判断一下此链表中有没有节点，这里之所以要加入这一步，是因为我们要去访问链表中的指针元素，重新让指针有另一个指向。
        LTNode* del = phead->next;//这里我们定义一个指针让其指向链表中的最后一个节点，由于我们在这里要删除节点，所以我们必须将原链表中的指针进行重新的指向，指向完毕后，就不会再有指针指向我们想要删除的节点了，因此，我们在这里必须定义一个指针指向要删除的节点。
        phead->next = del->next;//这里我们先将哨兵位的prev指针指向尾节点。
        del->next->prev = phead;//然后我们再将尾节点的prev指针指向的next指针指向哨兵位节点，也就是原链表中的倒数第二个节点的next节点指向哨兵位节点。
        //上面这两步在这里可以进行相互交换，只不过会代码有所不同，大家可以自行去进行修改。
        free(del);//释放掉除哨兵位以外的第一个节点所开创的空间。
        del = NULL;
    }
    else
    {
        return 1;
    }
}

425c5085e44d496a8f5329ba609f94ac.png

(9).查找元素：

   给定一个元素，到链表中去找有没有一个节点中的存储的元素是与这个元素相同。

LTNode* LTFind(LTNode* phead, LTDataType x)
{
    bool pas = LTEmpty(phead);//判断形参是否接收到了传过来的实参的地址。
    if (pas == true)//如果接收到了，就进入这个if语句中去实现。
    {
        LTNode* find = phead->next;//这一步是我自己的一个习惯，我在进行链表的访问等等一些功能的时候，我一般不使用指向第一个有效节点的指针，我会另外定义一个指针，让这个新定义的指针去遍历链表去找，这里我们定义一个指针让其指向哨兵位的下一个节点。
        while (find != phead)//由于双向链表是循环结构，所以我们在这里以find指针是否指向哨兵位这一条件来作为循环的结束条件。
        {
            if (find->val == x)//如果满足，则说明找到了。
            {
                return find;//返回该结点的地址。
            }
            find = find->next;//如果没找到，则让他继续向后遍历。
        }
        return NULL;//如果程序运行到这里的话，则说明此链表中没有我们要找的元素，返回NULL。
    }
    else
    {
        return 1;
    }
}

(10).删除pos节点：

   删除链表中的某一个节点。

void LTErase(LTNode* pos)
{
    bool pas = LTEmpty(pos);//与上一步操作中的相同的代码的解释相同。
    if (pas == true)//如果接收到了，就进入if语句。
    {
        pos->next->prev = pos->prev;//这一步是让pos节点的后一个节点的prev指针指向pos节点的前一个节点。
        pos->prev->next = pos->next;//这一步又是让pos指针的前一个节点额next指针指向pos节点的下一个节点。
        free(pos);释放要删除的pos节点所开创的空间。
        pos = NULL;
    }
    else
    {
        return 1;
    }
}

6ddb9287093f4ac88250108170b86dcb.png

(11).在pos位置之后插入数据：

    创建一个节点，将这个新创建的节点插在给定的pos位置的后面。

void LTInsert(LTNode* pos, LTDataType x)
{
    bool pas=LTEmpty(pos);//解释和上述解释一样。
    if (pas == true)
    {
        LTNode* newnode = LTBuyNode(x);//建立一个节点。

        //我们在这里进行双向链表的插入操作时，一般来说，我们是先对新创建的节点的各个指针赋值，这样能避免一些指针的指向问题，就是找到某个指针的指向很难找到。
        newnode->next = pos->next;//我们先对新节点的next指针指向pos指针指向的节点的next指针指向的节点。
        newnode->prev = pos;//让后再让新节点的prev指针指向pos指针指向的节点。
        pos->next->prev = newnode;//接下来我们对原链表中的其他指针进行重新指向的操作，就是当我们要向原链表中插入或删除一个元素时，原链表中有一些指针的指向是要发生一些变化的。
        pos->next = newnode;

        //这里就不再给大家画图了，大家可以自行画图去求解，请见谅。
    }
    else
    {
        return 1;
    }
}

(12).双向链表的销毁：

   销毁我们建立的双向链表。

void LTDestroy(LTNode* phead)
{
    bool pas=LTEmpty(phead);//判空
    if (pas == true)
    {
        LTNode* pcur = phead->next;//我们在这里重新定义一个指针指向哨兵位后面的那个节点，原因前面已经解释过。
        while (pcur != phead)//如果pcur指针==哨兵位，那么说明已经遍历了一遍链表了，将链表销毁完了。
        {
            LTNode* next = pcur->next;//定义一个next指针指向pcur指针的下一个节点，这里之所以要再定义一个指针让其指向pcur指针的下一个节点，是因为我们在这里要释放节点，如果不加上这一步的话，那么我们在将节点删除后，就无法找到下一个要删除的节点的地址，找起来很麻烦。
            free(pcur);
            pcur = next;
        }
        free(phead);//当循环结束时，就说明整个链表就只剩下了哨兵位节点还没有删除，这时我们还需要将哨兵位节点给释放掉。
        phead = NULL;
    }
    else
    {
        return 1;
    }
}

(13).判空：

   判断是否为空。

bool LTEmpty(LTNode* phead)
{
    LTNode* cur = phead;
    if (phead == NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
}
标签： 链表 数据结构 c语言
本文转载自: https://blog.csdn.net/2301_81390458/article/details/139195870
版权归原作者 轩源源 所有， 如有侵权，请联系我们删除。
登录后发布评论

“双向链表，这也太简单了吧！(C语言实现)”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航