AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【带你了解C++标准库为何在八大链表结构中选择了它】双向循环带头链表的实质性操作

2022-08-22 142
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【带你了解C++标准库为何在八大链表结构中选择了它】双向循环带头链表的实质性操作

在这里插入图片描述

文章目录

✨逻辑实现text.c
✨头文件List.h
✨函数实现List.c

🚀八大链表结构为何选择了它

C++的STL库选择的最终链表结构为双向循环带头链表
为什么选择了它呢，是因为它的结构更优，虽然形式看似复杂，但的它便利性相比其他链表好得多

C++标准库中把list设计为带头节点的双向循环链表是很合理的，不信你往后看它的操作实现过程相比于单链表来说有多简单，当然你也可以用其他的六种结果来对比，结果一定是双向循环带头链表更胜一筹
认识八种链表的类型
  1. 单向带头非循环链表
  2. 单向不带头循环链表
  3. 单向不带头非循环链表
  4. 双向带头循环链表
  5. 双向带头非循环链表
  6. 双向不带头循环链表
  7. 双向不带头非循环链表
  8. 双向循环带头链表✨
一些链表图示
image.png

常用的两类链表结构
我们在单链表的一系列操作中讲过单链表是在一些OJ题的常考题

单链表只能单向循环链表
循环双向链表就是一个环形，可以逆时针走，可以顺时针走，而双向链表是一个链，只能双向遍历。image.png

🚀初始化和打印

初始化

我们的 双向循环链表采用的是 带哨兵位的头结点，它的初始化为了避免要传二级指针，可以 设置用返回值的函数带回地址
下面一张图再次带你认识 带哨兵位的头结点和 不带哨兵位的头结点区别

image.png

要注意双向循环带头链表的初始化跟单链表有所区别，双向循环链表是不会指向NULL的，它没有节点的时候是下面的这种形式>

image.png

其实就是自己的头和尾都指向自己，这才能体现它的循环结构

在初始的时候是需要创建新节点作为头结点的，而且后续的头插，尾插等等都需要创建新节点，为了避免重复操作，直接建立一个BuyListNode函数用来创建新节点

//创建新节点
LTNode* BuyListNode(LTDateType x)
{
    LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
    if (newNode == NULL)
    {
        exit(-1);
    }
    newNode->date = x;
    newNode->next = NULL;
    newNode->prev = NULL;

    return newNode;
}
//初始化
LTNode* ListInit()
{
    LTNode* phead = BuyListNode(0);

    phead->prev = phead;
    phead->next = phead;
    
    return phead;
}
//用一个指针接收地址
LTNode* list = ListInit();

打印

打印过程图解
image.png 
//打印
void ListPrint(LTNode* phead)
{
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->date);
        cur = cur->next;
    }
    printf("\n");
}

🚀尾插和尾删

尾插

双向循环带头链表的 尾插实在比单链表简单得多了，因为它是循环双向链表，你看 尾节点的next不就指向 头结点的phead吗，那 头结点的prev不就指向 尾节点吗
是不是就直接省去了像单链表哪样遍历链表找尾的过程，直接将 时间复杂度优化到O(1)
那找到尾之后的操作就是连接节点之间的关系，比较简单，直接看图理解
image.png 
//尾插
void ListPushBack(LTNode* phead,LTDateType x)
{
    assert(phead);
    //新节点
    LTNode* newNode = BuyListNode(x);
    //找尾
    LTNode* tail = phead->prev;
    //连接
    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = phead;
    phead->prev = newNode;

}

尾删

尾删也不难，同样的找尾步骤，注意的是要记录好尾节点的前一个节点，让它来当新的尾节点

动画演示>在这里插入图片描述

//尾删
void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    free(tail);
    tailPrev->next = phead;
    phead->prev = tailPrev;
}

🚀头插和头删

头插

头插要注意的是不是在哨兵位的头前面插入，而是在哨兵位的头结点的后一个插入，因为哨兵位只是是不存放有效数据的，但它一定是在最前的

动画演示>
在这里插入图片描述

//头插
void ListPushFront(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* newNode = BuyListNode(x);
    //连接
    LTNode* next = phead->next;
    phead->next = newNode;
    newNode->prev = phead;

    newNode->next = next;
    next->prev = newNode;

}

头删

头删也是像尾删一样要记录好要删节点的下一个节点

在这里插入图片描述

//头删
void ListPopFront(LTNode* phead)
{
    assert(phead);
    //链表为空
    assert(phead->next != phead);

    LTNode* next = phead->next;
    LTNode* nextNext = next->next;
    free(next);
    phead->next = nextNext;
    nextNext->prev = phead;

}

🚀查找和插入

查找

查找就是遍历链表，跟单链表一样的操作，找到了就返回改节点的地址，找不到就返回NULL 
//查找
LTNode* ListFind(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->date == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

插入

插入是往该数据的前一个位置插入
插入就跟单链表的操作大大不同了， 双向循环带头链表的插入比起 单链表来说是非常容易的，你把你要在哪个位置插入的指针传给它，它可以直接找到 前一个节点，而单链表却没有这个性质

插入功能是和查找功能搭配使用的，用之前先用查找获取把该数据的指针，然后传给插入函数
那你们想想，如果我把 phead的指针传给插入函数，那phead的前一个不就是尾节点吗，那不就是相当于 尾插吗，同样如果我们把 phead的next传给插入函数，哪不就是相当于 头插吗！！
所以我们的头插和尾插是不是可以改造成这样子
image.png

这样之后我们写头插和尾插就省去了很大时间

//插入
void ListInsert(LTNode* pos, LTDateType x)
{
    assert(pos);

    LTNode* newNode = BuyListNode(x);


    LTNode* posPrev = pos->prev;

    posPrev->next = newNode;
    newNode->prev = posPrev;
    newNode->next = pos;
    pos->prev = newNode;
}

🚀删除和销毁

删除

删除也是搭配查找函数一起使用，把要的地址传过去即可删除

在这里插入图片描述

//删除
void ListErase(LTNode* pos)
{
    assert(pos);

    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;

    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
}

销毁

销毁就是遍历链表一个一个的free即可 
//销毁链表
void ListDestroy(LTNode* phead)
{
    LTNode* cur = phead->next;

    while (cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);
}
//记得最后把销毁链表，还要把list置空
    ListDestroy(list);
    list = NULL;

🚀小结
如果你动手实操了，一定感受到双向循环链表中的一些操作实现是不用考虑像单链表那样的分情况讨论，比如单链表在实现头插的时候不就是要分链表为空和不为空的情况吗，而它却不必考虑这些顾虑，还有很多区别于其他链表的优势，只能你自己去一 一感受！！

✨链表功能动画演示

在这里插入图片描述

✨逻辑实现text.c
text.c为工程整体逻辑实现 
void menu()
{
    printf("*******************************\n");
    printf("       1.尾插   2.尾删         \n");
    printf("       3.头插   4.头删         \n");
    printf("       5.插入   6查找          \n");
    printf("       7.删除   -1.退出        \n");
    printf("       8.打印                  \n");
    printf("*******************************\n");
    printf(" 请选择>:   \n");

}
void Textmenu()
{
    LTNode* list = ListInit();
    int input = 0;
    LTDateType x1 = 0;
    LTNode* pos = NULL;
    while(input != -1)
    {
        menu();
        scanf("%d", &input);
        switch (input)
        {
        case 1:
            printf("请输入要尾插的数据，以-1为结束\n");
            scanf("%d", &x1);
            while(x1 != -1)
            {
                ListPushBack(list, x1);
                scanf("%d", &x1);
            }
            printf("尾插成功\n");
            break;
        case 2:
            ListPopBack(list);
            printf("尾删成功\n");
            break;
        case 3:
            printf("请输入要头插的数据，以-1为结束\n");
            scanf("%d", &x1);
            while (x1 != -1)
            {
                ListPushFront(list, x1);
                scanf("%d", &x1);
            }
            printf("头插成功\n");
            break;
        case 4:
            ListPopFront(list);
            printf("头删成功\n");
            break;
        case 5:
            printf("请输入你要在哪里个数据前插入>:\n");
            scanf("%d", &x1);
             pos= ListFind(list, x1);
             if (pos != NULL)
             {
                 printf("请输入你要插入的数据>:\n");
                 scanf("%d", &x1);
                 ListInsert(pos, x1);
                 printf("插入成功\n");
             }
             else
             {
                 printf("无此数据\n");
             }
            break;
        case 6:
            printf("请输入你要查找的数据\n");
            scanf("%d", &x1);
            pos=ListFind(list, x1);
            if (pos != NULL)
            {
                printf("%d的地址为%p\n", x1, pos);
            }
            else
            {
                printf("链表没有此数据\n");
            }
            break;
        case 7:
            printf("请输入你要删除的数据\n");
            scanf("%d", &x1);
            pos = ListFind(list, x1);
            if (pos != NULL)
            {
                ListErase(pos);
                printf("删除成功\n");
            }
            else
            {
                printf("链表中没有此数据\n");
            }
            break;
        case 8:
            printf("链表数据为：");
            ListPrint(list);
            break;
        case -1:
            printf("退出成功\n");
            break;
        default:
            printf("无此选项，请重新输入！\n");
            break;
        }
    }
    //记得最后把销毁链表，还要把list置空
    ListDestroy(list);
    list = NULL;
    
}

int main()
{
    Textmenu();
}

✨头文件List.h
List.h为工程头文件（头文件和函数声明） 
#pragma once

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

typedef int LTDateType;

typedef struct ListNode
{
    LTDateType date;
    struct ListNode* next;
    struct ListNode* prev;
}LTNode;

//初始化
LTNode* ListInit();

//打印
void ListPrint(LTNode* phead);

//创建新节点
LTNode* BuyListNode(LTDateType x);

//尾插
void ListPushBack(LTNode* phead, LTDateType x);

//尾删
void ListPopBack(LTNode* phead);

//头插
void ListPushFront(LTNode* phead, LTDateType x);

//头删
void ListPopFront(LTNode* phead);

//查找,找到返回对应数据地址，找不到返回NULL
LTNode* ListFind(LTNode* phead, LTDateType x);

//插入，在pos位置之前插入
void ListInsert(LTNode* pos, LTDateType x);

//删除指定位置
void ListErase(LTNode* pos);

//销毁链表
void ListDestroy(LTNode* phead);

✨函数实现List.c
List.c为工程源文件（函数实现） 
#define _CRT_SECURE_NO_WARNINGS
#include"List.h"

//初始化
LTNode* ListInit()
{
    LTNode* phead = BuyListNode(0);

    phead->prev = phead;
    phead->next = phead;
    
    return phead;
}
//打印
void ListPrint(LTNode* phead)
{
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->date);
        cur = cur->next;
    }
    printf("\n");
}

//尾插
void ListPushBack(LTNode* phead,LTDateType x)
{
    assert(phead);
    //新节点
    //LTNode* newNode = BuyListNode(x);
    //找尾
    //LTNode* tail = phead->prev;
    //连接
    //tail->next = newNode;
    //newNode->prev = tail;
    //newNode->next = phead;
    //phead->prev = newNode;
    
    //可用插入函数代替尾插
    ListInsert(phead, x);
}
//尾删
void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);
    //LTNode* tail = phead->prev;
    //LTNode* tailPrev = tail->prev;
    //free(tail);
    //tailPrev->next = phead;
    //phead->prev = tailPrev;

    //可用删除函数代替尾删
    ListErase(phead->prev);
}

//头插
void ListPushFront(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* newNode = BuyListNode(x);
    //连接
    LTNode* next = phead->next;
    phead->next = newNode;
    newNode->prev = phead;

    newNode->next = next;
    next->prev = newNode;

    //可用插入函数代替头插
    //ListInsert(phead->next, x);

}

//头删
void ListPopFront(LTNode* phead)
{
    assert(phead);
    //链表为空
    assert(phead->next != phead);

    LTNode* next = phead->next;
    LTNode* nextNext = next->next;
    free(next);
    phead->next = nextNext;
    nextNext->prev = phead;

    //可用删除函数代替头删
    //ListErase(phead->next);

}

//查找
LTNode* ListFind(LTNode* phead, LTDateType x)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->date == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

//插入
void ListInsert(LTNode* pos, LTDateType x)
{
    assert(pos);

    LTNode* newNode = BuyListNode(x);


    LTNode* posPrev = pos->prev;

    posPrev->next = newNode;
    newNode->prev = posPrev;
    newNode->next = pos;
    pos->prev = newNode;
}
//删除
void ListErase(LTNode* pos)
{
    assert(pos);

    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;

    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
}
//创建新节点
LTNode* BuyListNode(LTDateType x)
{
    LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
    if (newNode == NULL)
    {
        exit(-1);
    }
    newNode->date = x;
    newNode->next = NULL;
    newNode->prev = NULL;

    return newNode;
}

//销毁链表
void ListDestroy(LTNode* phead)
{
    LTNode* cur = phead->next;

    while (cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);
}
文章标签：
C++
关键词：
C++库
C++结构
链表结构
链表操作
C++循环
一介凡夫
目录
相关文章
Svan.
|
2月前
|
算法 C++ 容器
C++标准库（速查）总结
C++标准库（速查）总结
Svan.
71 6
半截诗
|
2月前
|
存储 算法 C++
C++ STL 初探：打开标准模板库的大门
C++ STL 初探：打开标准模板库的大门
半截诗
106 10
Svan.
|
2月前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
Svan.
73 5
Svan.
|
2月前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
Svan.
59 1
希望_睿智
|
3月前
|
编译器 API C语言
超级好用的C++实用库之跨平台实用方法
超级好用的C++实用库之跨平台实用方法
希望_睿智
41 6
希望_睿智
|
3月前
|
安全 C++
超级好用的C++实用库之环形内存池
超级好用的C++实用库之环形内存池
希望_睿智
51 5
希望_睿智
|
3月前
|
缓存 网络协议 Linux
超级好用的C++实用库之套接字
超级好用的C++实用库之套接字
希望_睿智
34 1
希望_睿智
|
3月前
|
存储 算法 安全
超级好用的C++实用库之sha256算法
超级好用的C++实用库之sha256算法
希望_睿智
106 1
希望_睿智
|
3月前
|
存储 算法 安全
超级好用的C++实用库之国密sm4算法
超级好用的C++实用库之国密sm4算法
希望_睿智
70 0
希望_睿智
|
3月前
|
网络协议 Linux C++
超级好用的C++实用库之网络
超级好用的C++实用库之网络
希望_睿智
49 0