1. Toy模板网首页
  2. > Toy博客

数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）

7月前 作者：舟清颺 分类：Toy博客 阅读(54) 违法举报

这篇具有很好参考价值的文章主要介绍了数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

版本:

2024年4月26日 V1.0 发布于博客园

/**
 * @file name : DoubleLinkedList.c
 * @brief     : 实现双向循环链表的相关功能
 * @author    :RISE_AND_GRIND@163.com
 * @date      :2024/04/26
 * @version   :1.0
 * @note      :
 * CopyRight (c)  2023-2024   RISE_AND_GRIND@163.com   All Right Reseverd
 */

目录

目录
  • 目录
  • 双向循环链表公式
  • 初始化双向循环链表
    • 构建双向循环链表结点
    • 创建一个空链表（仅头结点）
    • 创建一个新结点
  • 插入数据
    • 头插
    • 中插
    • 尾插
  • 删除数据
    • 头删
    • 中删
    • 尾删
  • 查询打印数据
    • 遍历打印
  • 测试
    • 测试结果:
  • 完整代码
    • DoubleCirLList.h
    • DoubleCirLList.c
    • projecttesting.c

双向循环链表公式

数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）

/**
 * 声明双向循环链表的结点
 *
 * 双向循环链表总结成公式
 *     struct xxx
 *     {
 *         //指针域(直接前驱的指针域)
 *         //数据域(需要存放什么类型的数据,你就定义对应的变量即可)
 *         //指针域(直接后继的指针域)
 *     };
 *   双向循环链表的基本操作:
 *     初始化单向循环链表 √
 *     插入数据 √
 *     删除数据 √
 *     修改数据
 *     查询打印数据√
 */

初始化双向循环链表

构建双向循环链表结点

DoubleLList_t[ *prev | data |*next ] 

// 指的是双向链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;

// 构造双向链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
    struct DoubleLinkedList *prev; // 直接前驱的指针域
    DataType_t data;               // 结点的数据域
    struct DoubleLinkedList *next; // 直接后继的指针域
} DoubleLList_t;

创建一个空链表（仅头结点）

/**
 * @name      DoubleCirLList_Create
 * @brief     创建一个空双向循环链表，空链表应该有一个头结点，头结点前驱指针域和后继指针域名均指向自己, 对链表进行初始化Head-->[*prev|data|*next]
 * @param
 * @return
 *      @retval    Head 头结点地址
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
DoubleLList_t *DoubleCirLList_Create(void)
{
    // 1.创建一个头结点并对头结点申请内存
    DoubleLList_t *Head = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
    if (NULL == Head)
    {
        perror("Calloc memory for Head is Failed");
        exit(-1);
    }

    // 2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身即可，体现“循环”
    Head->prev = Head;
    Head->next = Head;
    // 3.把头结点的地址返回即可
    return Head;
}

创建一个新结点

/**
 * @name      DoubleCirLList_NewNode
 * @brief     创建新的结点，并对新结点进行初始化（直接前驱指针域+ 数据域 + 直接后继指针域） [*prev|data|*next]
 * @param     data 要创建结点的元素
 * @return    程序执行成功与否
 *      @retval    NULL 申请堆内存失败
 *      @retval    New  新结点地址
 * @date      2024/04/26
 * @version   1.0
 * @note      新结点指针域初始化后默认指向自己
 */
DoubleLList_t *DoubleCirLList_NewNode(DataType_t data)
{
    // 1.创建一个新结点并对新结点申请内存
    DoubleLList_t *New = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
    if (NULL == New)
    {
        perror("Calloc memory for NewNode is Failed");
        return NULL;
    }

    // 2.对新结点的数据域和指针域（2个）进行初始化,指针域指向结点自身，体现“循环”
    New->prev = New;
    New->data = data;
    New->next = New;

    return New;
}

插入数据

头插

数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）

/**
 * @name      DoubleCirLList_HeadInsert
 * @brief     在双向循环链表的头结点后插入
 * @param     Head 头指针
 * @param     data 新元素
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_HeadInsert(DoubleLList_t *Head, DataType_t data)
{
    // 备份头指针, 创建操作指针
    DoubleLList_t *Current = Head;

    // 1.创建新结点并对新结点进行初始化
    DoubleLList_t *New = DoubleCirLList_NewNode(data);
    if (NULL == New)
    {
        printf("Failed to create a node, can not insert new node \n");
        return false;
    }

    // 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
    if (Head->next == Head)
    {

        Head->next = New; // 让头结点的next指针指向新结点
        return true;
    }

    Head->next->prev->next = New; // 首结点前驱为尾结点地址, 将尾结点链接新首结点
    New->prev = Head->next->prev; // 将新结点前驱链接尾结点

    New->next = Head->next; // 新首结点链接旧首结点
    Head->next->prev = New; // 旧首结点链接新结点
    Head->next = New;       // 头结点链接新首结点

    return true;
}

中插

数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）

/**
 * @name       DoubleCirLList_DestInsert
 * @brief     双向循环链表中的指定元素后面插入新结点
 * @param     Head 头指针
 * @param     dest 要查找的结点
 * @param     data 要插入的数据
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_DestInsert(DoubleLList_t *Head, DataType_t dest, DataType_t data)
{
    DoubleLList_t *Current = Head->next; // 操作指针 初始为指向首结点, 若为空链表则指向头结点

    // 1.创建新结点并对新结点进行初始化
    DoubleLList_t *New = DoubleCirLList_NewNode(data);
    if (NULL == New)
    {
        printf("can not insert new node , Failed to create a node\n");
        return false;
    }

    // 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
    if (Head->next == Head)
    {

        Head->next = New; // 让头结点的next指针指向新结点
        return true;
    }

    // 3.若双向循环链表非空,需要让尾结点的next指针指向新结点,新结点指向首结点
    // 目标结点是首结点, 不再继续查找. 目标结点非首结点, 继续向下查找
    while (Current->data != dest)
    {
        Current = Current->next;                                      // 进入下一个结点
        if ((Current->next == Head->next) && (Current->data != dest)) // 达到末尾 且 末尾不是目标
        {
            printf("The target doesn't exist! \n");
            return false;
        }
    } // 找到目标结点, Current此时指向目标

    if (Current->next == Head->next) // 目标结点是尾结点
    {

        New->next = Head->next; // 尾处理: 新结点直接后继链接首结点
        Head->next->prev = New; // 头处理: 首结点直接前驱链接新结点
        New->prev = Current;    // 内部处理: 新结点直接前驱链接旧尾结点
        Current->next = New;    // 内部处理: 旧结点链接新尾结点
    }
    else // 目标结点是中间结点 或首结点
    {
        New->next = Current->next;
        New->prev = Current;
        Current->next->prev = New;
        Current->next = New;
    }
    return true;
}

尾插

数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）

/**
 * @name      DoubleCirLList_TailInsert
 * @brief     将新元素插入到尾结点后面
 * @param     Head 头指针
 * @param     data 新元素
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_TailInsert(DoubleLList_t *Head, DataType_t data)
{
    DoubleLList_t *Phead = Head; // 备份头结点地址,防止头结点丢失

    // 1.创建新结点并对新结点进行初始化
    DoubleLList_t *New = DoubleCirLList_NewNode(data);
    if (NULL == New)
    {
        printf("can not insert new node , Failed to create a node\n");
        return false;
    }

    // 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
    if (Head->next == Head)
    {

        Head->next = New; // 让头结点的next指针指向新结点
        return true;
    }

    // 3.如果双向循环链表为非空,需要让尾结点的next指针指向新结点,新结点指向首结点
    New->next = Head->next;       // 新结点链接首结点
    New->prev = Head->next->prev; // 新结点链接尾结点
    Head->next->prev->next = New; // 内部处理: 旧尾结点链接新尾结点
    Head->next->prev = New;       // 首结点链接新尾结点

    return true;
}

删除数据

头删

数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）

/**
 * @name      DoubleCirLList_HeadDel
 * @brief     删除首节点
 * @param      Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败
 *      @retval    true  删除成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_HeadDel(DoubleLList_t *Head)
{
    // 1.创建操作指针
    // 指向头结点, 操作指针
    DoubleLList_t *Current = Head;

    // 2.判断双向循环链表是否为空链表,如果为空, 则退出
    if (Head == Head->next)
    {
        printf("DoubleLList is Empty! \n");
        return false;
    }

    // 3.判断链表非空链表
    // ①若只有首结点
    if (Head->next == Head->next->next)
    {
        Head->next->prev = NULL; // 首结点指针域处理, 防止内存泄漏
        Head->next->next = NULL;
        free(Head->next);  // 释放首结点, 防止内存泄漏
        Head->next = Head; // 头结点指向自己, 表示循环
        return true;
    }
    // ②若不止首结点
    Head->next->prev->next = Head->next->next; // 尾结点直接后继指针域链接新首结点
    Current = Head->next;                      // 操作指针备份首结点地址
    Head->next = Current->next;                // 头结点链接新首结点
    Head->next->prev = Current->prev;          // 新首结点直接前驱指针域链接尾结点
    Current->prev = NULL;
    Current->next = NULL;
    free(Current); // 释放首结点, 防止内存泄漏
    return true;
}

中删

数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）

/**
 * @name       DoubleCirLList_DestDel
 * @brief     中删, 删除双向循环链表某个元素结点
 * @param     Head 头指针
 * @param     dest 要删除的目标元素
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 未找到目标元素结点
 *      @retval    true  删除成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_DestDel(DoubleLList_t *Head, DataType_t dest)
{
    // 1.创建操作指针
    // 指向头结点, 操作指针
    DoubleLList_t *Current = Head;

    // 2.判断双向循环链表是否为空链表,如果为空, 则退出
    if (Head == Head->next)
    {
        printf("DoubleLList is Empty! \n");
        return false;
    }
    // 3.若双向循环链表非空
    // 寻找目标结点
    while (Current->data != dest)
    {
        Current = Current->next;                                      // 进入下一个结点, 第一次从头结点跳到尾结点
        if ((Current->next == Head->next) && (Current->data != dest)) // 若尾结点不是目标结点
        {
            printf("The target doesn't exist! \n");
            return false;
        }
    } // 找到目标结点, Current此时指向目标

    // 目标结点是首结点
    if (Current == Head->next)
    {
        // ①若链表只有首结点
        if (Current->next == Head->next)
        {
            // 删除首结点, 变成空链表
            Head->next = Head;

        } // ②若链表不止首节点
        Head->next->prev->next = Current->next; // 更新尾结点指针域为新首结点地址
        Current->next->prev = Head->next->prev; // 更新新首节点的前驱指针域链接尾结点
        Head->next = Current->next;             // 更新首结点链接新首结点
    }
    else if (Current->next == Head->next) // ③目标结点是尾结点
    {
        Current->prev->next = Head->next; // 新尾结点链接首结点, 行成循环
        Head->next->prev = Current->prev;
    }
    else // ④目标结点是中间结点
    {
        Current->prev->next = Current->next;
        Current->next->prev = Current->prev;
    }
    // 删除目标结点
    Current->prev = NULL;
    Current->next = NULL;
    free(Current); // 防止内存泄漏
    return true;
}

尾删

数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）文章来源地址https://www.toymoban.com/news/detail-859324.html

/**
 * @name      DoubleCirLList_TailDel
 * @brief     删除尾结点
 * @param     Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 链表为空
 *      @retval    true  删除成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_TailDel(DoubleLList_t *Head)
{
    // 1.创建操作指针
    // 指向头结点, 操作指针
    DoubleLList_t *Current = Head;

    // 2.判断双向循环链表是否为空链表,如果为空, 则退出
    if (Head->next == Head)
    {
        printf("Error,  Double Circular Linked List is empty! \n");
        return false;
    }

    Current = Head->next->prev; // 备份尾结点
    // 3.①若双向循环链表非空
    //  若链表只有首结点
    if (Head->next == Head->next->next)
    {
        // 删除首结点, 变成空链表
        Head->next = Head;
        // printf("只有首节点的值 %d \n", Head->next->data);
    }
    else if (Head->next != Head->next->next) // ②若首结点直接前驱不是自己， 则还有别的结点
    {
        // printf("不止只有首节点的值 %d \n", Head->next->data);
        Head->next->prev = Current->prev; // 首结点直接前驱链接新尾结点
        Current->prev->next = Head->next; // 新尾结点的直接后继指针域链接首结点
    }
}

查询打印数据

遍历打印

/**
 * @name      DoubleCirLList_Print
 * @brief     从头到尾遍历链表
 * @param     Head 头指针
 * @return    无
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
void DoubleCirLList_Print(DoubleLList_t *Head)
{
    // 判断是否为空链表
    if (Head->next == Head)
    {
        printf("The list is empty.\n");
        return;
    }

    DoubleLList_t *Current = Head->next; // 指向首结点

    printf("Double Circular Linked List: ");

    while (Current->next) // 不断向下检查结点指针域
    {
        printf(" -> %d", Current->data); // 打印结点数据
        if (Current->next == Head->next) // 结束条件: 达尾结点
        {
            break;
        }
        Current = Current->next; // 进入下一个结点
    }
    printf("\n"); // 刷新行缓冲, 输出缓冲区
}

测试

#include "DoubleCirLList.h"

int main(int argc, char const *argv[])
{
    // 创建单向循环链表, 空链表
    DoubleLList_t *Manager = DoubleCirLList_Create();

    // 头插法 向链表中插入新结点
    printf("*********************************DoubleCirLList_HeadInsert********************************\n");
    DoubleCirLList_HeadInsert(Manager, 7);
    DoubleCirLList_HeadInsert(Manager, 4);
    DoubleCirLList_HeadInsert(Manager, 1);
    DoubleCirLList_HeadInsert(Manager, 8);
    DoubleCirLList_HeadInsert(Manager, 5);
    DoubleCirLList_HeadInsert(Manager, 2);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 2 -> 5 -> 8 -> 1 -> 4 -> 7*/

    // 中插法 向链表中插入新结点
    printf("*********************************DoubleCirLList_DestInsert********************************\n");
    DoubleCirLList_DestInsert(Manager, 7, 9);
    DoubleCirLList_DestInsert(Manager, 4, 6);
    DoubleCirLList_DestInsert(Manager, 2, 3);
    DoubleCirLList_DestInsert(Manager, 5, 10);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9*/

    // 尾插法 向链表中插入新结点
    printf("*********************************DoubleCirLList_TailInsert********************************\n");
    DoubleCirLList_TailInsert(Manager, 13);
    DoubleCirLList_TailInsert(Manager, 12);
    DoubleCirLList_TailInsert(Manager, 11);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11*/

    // 头删法 删除首结点
    printf("*********************************DoubleCirLList_HeadDel********************************\n");
    DoubleCirLList_HeadDel(Manager);
    DoubleCirLList_HeadDel(Manager);
    DoubleCirLList_HeadDel(Manager);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11*/

    // 中删法 删除指定结点
    printf("*********************************DoubleCirLList_DestDel********************************\n");
    DoubleCirLList_DestDel(Manager, 10);
    DoubleCirLList_DestDel(Manager, 1);
    DoubleCirLList_DestDel(Manager, 6);
    DoubleCirLList_DestDel(Manager, 11);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 8 -> 4 -> 7 -> 9 -> 13 -> 12*/

    // 尾删法 删除尾结点
    printf("*********************************DoubleCirLList_TailDel********************************\n");
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 8 -> 4*/
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_TailDel(Manager);
    /*Error,  Double Circular Linked List is empty! */
    DoubleCirLList_HeadInsert(Manager, 66);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 66*/

    // 等待用户响应
    printf("***Press any key to exit the test***\n");
    getchar();
    return 0;
}

测试结果:

*********************************DoubleCirLList_HeadInsert********************************
Double Circular Linked List:  -> 2 -> 5 -> 8 -> 1 -> 4 -> 7
*********************************DoubleCirLList_DestInsert********************************
Double Circular Linked List:  -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9
*********************************DoubleCirLList_TailInsert********************************
Double Circular Linked List:  -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11
*********************************DoubleCirLList_HeadDel********************************
Double Circular Linked List:  -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11
*********************************DoubleCirLList_DestDel********************************
Double Circular Linked List:  -> 8 -> 4 -> 7 -> 9 -> 13 -> 12
*********************************DoubleCirLList_TailDel********************************
Double Circular Linked List:  -> 8 -> 4
Error,  Double Circular Linked List is empty! 
Double Circular Linked List:  -> 66
***Press any key to exit the test***

完整代码

DoubleCirLList.h

#ifndef __DOUBLECIRLLIST_H // ifndef是(如果 没有 定义 那么) (__该头文件的名称)
#define __DOUBLECIRLLIST_H // #define是 进行定义
/**
 * @file name : DoubleLinkedList.c
 * @brief     : 实现双向循环链表的相关功能
 * @author    :RISE_AND_GRIND@163.com
 * @date      :2024/04/26
 * @version   :1.0
 * @note      :
 * CopyRight (c)  2023-2024   RISE_AND_GRIND@163.com   All Right Reseverd
 */

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

/**
 * 声明双向循环链表的结点
 *
 * 双向循环链表总结成公式
 *     struct xxx
 *     {
 *         //指针域(直接前驱的指针域)
 *         //数据域(需要存放什么类型的数据,你就定义对应的变量即可)
 *         //指针域(直接后继的指针域)
 *     };
 *   双向循环链表的基本操作:
 *     初始化单向循环链表 √
 *     插入数据 √
 *     删除数据 √
 *     修改数据
 *     查询打印数据√
 */

// 指的是双向链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;

// 构造双向链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
    struct DoubleLinkedList *prev; // 直接前驱的指针域
    DataType_t data;               // 结点的数据域
    struct DoubleLinkedList *next; // 直接后继的指针域
} DoubleLList_t;

/**
 * @name      DoubleCirLList_Create
 * @brief     创建一个空双向循环链表，空链表应该有一个头结点，头结点前驱指针域和后继指针域名均指向自己, 对链表进行初始化Head-->[*prev|data|*next]
 * @param
 * @return
 *      @retval    Head 头结点地址
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
DoubleLList_t *DoubleCirLList_Create(void);

/**
 * @name      DoubleCirLList_NewNode
 * @brief     创建新的结点，并对新结点进行初始化（直接前驱指针域+ 数据域 + 直接后继指针域） [*prev|data|*next]
 * @param     data 要创建结点的元素
 * @return    程序执行成功与否
 *      @retval    NULL 申请堆内存失败
 *      @retval    New  新结点地址
 * @date      2024/04/26
 * @version   1.0
 * @note      新结点指针域初始化后默认指向自己
 */
DoubleLList_t *DoubleCirLList_NewNode(DataType_t data);

/**
 * @name      DoubleCirLList_HeadInsert
 * @brief     在双向循环链表的头结点后插入
 * @param     Head 头指针
 * @param     data 新元素
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_HeadInsert(DoubleLList_t *Head, DataType_t data);

/**
 * @name       DoubleCirLList_DestInsert
 * @brief     双向循环链表中的指定元素后面插入新结点
 * @param     Head 头指针
 * @param     dest 要查找的结点
 * @param     data 要插入的数据
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_DestInsert(DoubleLList_t *Head, DataType_t dest, DataType_t data);

/**
 * @name      DoubleCirLList_TailInsert
 * @brief     将新元素插入到尾结点后面
 * @param     Head 头指针
 * @param     data 新元素
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_TailInsert(DoubleLList_t *Head, DataType_t data);

/**
 * @name      DoubleCirLList_HeadDel
 * @brief     删除首节点
 * @param      Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败
 *      @retval    true  删除成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_HeadDel(DoubleLList_t *Head);

/**
 * @name       DoubleCirLList_DestDel
 * @brief     中删, 删除双向循环链表某个元素结点
 * @param     Head 头指针
 * @param     dest 要删除的目标元素
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 未找到目标元素结点
 *      @retval    true  删除成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_DestDel(DoubleLList_t *Head, DataType_t dest);

/**
 * @name      DoubleCirLList_TailDel
 * @brief     删除尾结点
 * @param     Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 链表为空
 *      @retval    true  删除成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_TailDel(DoubleLList_t *Head);

/**
 * @name      DoubleCirLList_Print
 * @brief     从头到尾遍历链表
 * @param     Head 头指针
 * @return    无
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
void DoubleCirLList_Print(DoubleLList_t *Head);

#endif
// 结束定义

DoubleCirLList.c

/**
 * @file name : DoubleCirLList.c
 * @brief     : 实现双向循环链表的相关功能
 * @author    :RISE_AND_GRIND@163.com
 * @date      :2024/04/26
 * @version   :1.0
 * @note      :
 * CopyRight (c)  2023-2024   RISE_AND_GRIND@163.com   All Right Reseverd
 */
#include "DoubleCirLList.h"

/**
 * @name      DoubleCirLList_Create
 * @brief     创建一个空双向循环链表，空链表应该有一个头结点，头结点前驱指针域和后继指针域名均指向自己, 对链表进行初始化Head-->[*prev|data|*next]
 * @param
 * @return
 *      @retval    Head 头结点地址
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
DoubleLList_t *DoubleCirLList_Create(void)
{
    // 1.创建一个头结点并对头结点申请内存
    DoubleLList_t *Head = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
    if (NULL == Head)
    {
        perror("Calloc memory for Head is Failed");
        exit(-1);
    }

    // 2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身即可，体现“循环”
    Head->prev = Head;
    Head->next = Head;
    // 3.把头结点的地址返回即可
    return Head;
}

/**
 * @name      DoubleCirLList_NewNode
 * @brief     创建新的结点，并对新结点进行初始化（直接前驱指针域+ 数据域 + 直接后继指针域） [*prev|data|*next]
 * @param     data 要创建结点的元素
 * @return    程序执行成功与否
 *      @retval    NULL 申请堆内存失败
 *      @retval    New  新结点地址
 * @date      2024/04/26
 * @version   1.0
 * @note      新结点指针域初始化后默认指向自己
 */
DoubleLList_t *DoubleCirLList_NewNode(DataType_t data)
{
    // 1.创建一个新结点并对新结点申请内存
    DoubleLList_t *New = (DoubleLList_t *)calloc(1, sizeof(DoubleLList_t));
    if (NULL == New)
    {
        perror("Calloc memory for NewNode is Failed");
        return NULL;
    }

    // 2.对新结点的数据域和指针域（2个）进行初始化,指针域指向结点自身，体现“循环”
    New->prev = New;
    New->data = data;
    New->next = New;

    return New;
}

/**
 * @name      DoubleCirLList_HeadInsert
 * @brief     在双向循环链表的头结点后插入
 * @param     Head 头指针
 * @param     data 新元素
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_HeadInsert(DoubleLList_t *Head, DataType_t data)
{
    // 备份头指针, 创建操作指针
    DoubleLList_t *Current = Head;

    // 1.创建新结点并对新结点进行初始化
    DoubleLList_t *New = DoubleCirLList_NewNode(data);
    if (NULL == New)
    {
        printf("Failed to create a node, can not insert new node \n");
        return false;
    }

    // 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
    if (Head->next == Head)
    {

        Head->next = New; // 让头结点的next指针指向新结点
        return true;
    }

    Head->next->prev->next = New; // 首结点前驱为尾结点地址, 将尾结点链接新首结点
    New->prev = Head->next->prev; // 将新结点前驱链接尾结点

    New->next = Head->next; // 新首结点链接旧首结点
    Head->next->prev = New; // 旧首结点链接新结点
    Head->next = New;       // 头结点链接新首结点

    return true;
}

/**
 * @name       DoubleCirLList_DestInsert
 * @brief     双向循环链表中的指定元素后面插入新结点
 * @param     Head 头指针
 * @param     dest 要查找的结点
 * @param     data 要插入的数据
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_DestInsert(DoubleLList_t *Head, DataType_t dest, DataType_t data)
{
    DoubleLList_t *Current = Head->next; // 操作指针 初始为指向首结点, 若为空链表则指向头结点

    // 1.创建新结点并对新结点进行初始化
    DoubleLList_t *New = DoubleCirLList_NewNode(data);
    if (NULL == New)
    {
        printf("can not insert new node , Failed to create a node\n");
        return false;
    }

    // 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
    if (Head->next == Head)
    {

        Head->next = New; // 让头结点的next指针指向新结点
        return true;
    }

    // 3.若双向循环链表非空,需要让尾结点的next指针指向新结点,新结点指向首结点
    // 目标结点是首结点, 不再继续查找. 目标结点非首结点, 继续向下查找
    while (Current->data != dest)
    {
        Current = Current->next;                                      // 进入下一个结点
        if ((Current->next == Head->next) && (Current->data != dest)) // 达到末尾 且 末尾不是目标
        {
            printf("The target doesn't exist! \n");
            return false;
        }
    } // 找到目标结点, Current此时指向目标

    if (Current->next == Head->next) // 目标结点是尾结点
    {

        New->next = Head->next; // 尾处理: 新结点直接后继链接首结点
        Head->next->prev = New; // 头处理: 首结点直接前驱链接新结点
        New->prev = Current;    // 内部处理: 新结点直接前驱链接旧尾结点
        Current->next = New;    // 内部处理: 旧结点链接新尾结点
    }
    else // 目标结点是中间结点 或首结点
    {
        New->next = Current->next;
        New->prev = Current;
        Current->next->prev = New;
        Current->next = New;
    }
    return true;
}

/**
 * @name      DoubleCirLList_TailInsert
 * @brief     将新元素插入到尾结点后面
 * @param     Head 头指针
 * @param     data 新元素
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_TailInsert(DoubleLList_t *Head, DataType_t data)
{
    DoubleLList_t *Phead = Head; // 备份头结点地址,防止头结点丢失

    // 1.创建新结点并对新结点进行初始化
    DoubleLList_t *New = DoubleCirLList_NewNode(data);
    if (NULL == New)
    {
        printf("can not insert new node , Failed to create a node\n");
        return false;
    }

    // 2.判断双向循环链表是否为空,如果为空,则直接插入到头结点之后
    if (Head->next == Head)
    {

        Head->next = New; // 让头结点的next指针指向新结点
        return true;
    }

    // 3.如果双向循环链表为非空,需要让尾结点的next指针指向新结点,新结点指向首结点
    New->next = Head->next;       // 新结点链接首结点
    New->prev = Head->next->prev; // 新结点链接尾结点
    Head->next->prev->next = New; // 内部处理: 旧尾结点链接新尾结点
    Head->next->prev = New;       // 首结点链接新尾结点

    return true;
}

/**
 * @name      DoubleCirLList_HeadDel
 * @brief     删除首节点
 * @param      Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败
 *      @retval    true  删除成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_HeadDel(DoubleLList_t *Head)
{
    // 1.创建操作指针
    // 指向头结点, 操作指针
    DoubleLList_t *Current = Head;

    // 2.判断双向循环链表是否为空链表,如果为空, 则退出
    if (Head == Head->next)
    {
        printf("DoubleLList is Empty! \n");
        return false;
    }

    // 3.判断链表非空链表
    // ①若只有首结点
    if (Head->next == Head->next->next)
    {
        Head->next->prev = NULL; // 首结点指针域处理, 防止内存泄漏
        Head->next->next = NULL;
        free(Head->next);  // 释放首结点, 防止内存泄漏
        Head->next = Head; // 头结点指向自己, 表示循环
        return true;
    }
    // ②若不止首结点
    Head->next->prev->next = Head->next->next; // 尾结点直接后继指针域链接新首结点
    Current = Head->next;                      // 操作指针备份首结点地址
    Head->next = Current->next;                // 头结点链接新首结点
    Head->next->prev = Current->prev;          // 新首结点直接前驱指针域链接尾结点
    Current->prev = NULL;
    Current->next = NULL;
    free(Current); // 释放首结点, 防止内存泄漏
    return true;
}

/**
 * @name       DoubleCirLList_DestDel
 * @brief     中删, 删除双向循环链表某个元素结点
 * @param     Head 头指针
 * @param     dest 要删除的目标元素
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 未找到目标元素结点
 *      @retval    true  删除成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_DestDel(DoubleLList_t *Head, DataType_t dest)
{
    // 1.创建操作指针
    // 指向头结点, 操作指针
    DoubleLList_t *Current = Head;

    // 2.判断双向循环链表是否为空链表,如果为空, 则退出
    if (Head == Head->next)
    {
        printf("DoubleLList is Empty! \n");
        return false;
    }
    // 3.若双向循环链表非空
    // 寻找目标结点
    while (Current->data != dest)
    {
        Current = Current->next;                                      // 进入下一个结点, 第一次从头结点跳到尾结点
        if ((Current->next == Head->next) && (Current->data != dest)) // 若尾结点不是目标结点
        {
            printf("The target doesn't exist! \n");
            return false;
        }
    } // 找到目标结点, Current此时指向目标

    // 目标结点是首结点
    if (Current == Head->next)
    {
        // ①若链表只有首结点
        if (Current->next == Head->next)
        {
            // 删除首结点, 变成空链表
            Head->next = Head;

        } // ②若链表不止首节点
        Head->next->prev->next = Current->next; // 更新尾结点指针域为新首结点地址
        Current->next->prev = Head->next->prev; // 更新新首节点的前驱指针域链接尾结点
        Head->next = Current->next;             // 更新首结点链接新首结点
    }
    else if (Current->next == Head->next) // ③目标结点是尾结点
    {
        Current->prev->next = Head->next; // 新尾结点链接首结点, 行成循环
        Head->next->prev = Current->prev;
    }
    else // ④目标结点是中间结点
    {
        Current->prev->next = Current->next;
        Current->next->prev = Current->prev;
    }
    // 删除目标结点
    Current->prev = NULL;
    Current->next = NULL;
    free(Current); // 防止内存泄漏
    return true;
}

/**
 * @name      DoubleCirLList_TailDel
 * @brief     删除尾结点
 * @param     Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 链表为空
 *      @retval    true  删除成功
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
bool DoubleCirLList_TailDel(DoubleLList_t *Head)
{
    // 1.创建操作指针
    // 指向头结点, 操作指针
    DoubleLList_t *Current = Head;

    // 2.判断双向循环链表是否为空链表,如果为空, 则退出
    if (Head->next == Head)
    {
        printf("Error,  Double Circular Linked List is empty! \n");
        return false;
    }

    Current = Head->next->prev; // 备份尾结点
    // 3.①若双向循环链表非空
    //  若链表只有首结点
    if (Head->next == Head->next->next)
    {
        // 删除首结点, 变成空链表
        Head->next = Head;
        // printf("只有首节点的值 %d \n", Head->next->data);
    }
    else if (Head->next != Head->next->next) // ②若首结点直接前驱不是自己， 则还有别的结点
    {
        // printf("不止只有首节点的值 %d \n", Head->next->data);
        Head->next->prev = Current->prev; // 首结点直接前驱链接新尾结点
        Current->prev->next = Head->next; // 新尾结点的直接后继指针域链接首结点
    }
}

/**
 * @name      DoubleCirLList_Print
 * @brief     从头到尾遍历链表
 * @param     Head 头指针
 * @return    无
 * @date      2024/04/26
 * @version   1.0
 * @note
 */
void DoubleCirLList_Print(DoubleLList_t *Head)
{
    // 判断是否为空链表
    if (Head->next == Head)
    {
        printf("The list is empty.\n");
        return;
    }

    DoubleLList_t *Current = Head->next; // 指向首结点

    printf("Double Circular Linked List: ");

    while (Current->next) // 不断向下检查结点指针域
    {
        printf(" -> %d", Current->data); // 打印结点数据
        if (Current->next == Head->next) // 结束条件: 达尾结点
        {
            break;
        }
        Current = Current->next; // 进入下一个结点
    }
    printf("\n"); // 刷新行缓冲, 输出缓冲区
}

projecttesting.c

/**
 * @file name : projecttesting.c
 * @brief     : 实现双向循环链表的相关功能测试
 * @author    :RISE_AND_GRIND@163.com
 * @date      :2024/04/26
 * @version   :1.0
 * @note      :
 * CopyRight (c)  2023-2024   RISE_AND_GRIND@163.com   All Right Reseverd
 */

#include "DoubleCirLList.h"

int main(int argc, char const *argv[])
{
    // 创建单向循环链表, 空链表
    DoubleLList_t *Manager = DoubleCirLList_Create();

    // 头插法 向链表中插入新结点
    printf("*********************************DoubleCirLList_HeadInsert********************************\n");
    DoubleCirLList_HeadInsert(Manager, 7);
    DoubleCirLList_HeadInsert(Manager, 4);
    DoubleCirLList_HeadInsert(Manager, 1);
    DoubleCirLList_HeadInsert(Manager, 8);
    DoubleCirLList_HeadInsert(Manager, 5);
    DoubleCirLList_HeadInsert(Manager, 2);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 2 -> 5 -> 8 -> 1 -> 4 -> 7*/

    // 中插法 向链表中插入新结点
    printf("*********************************DoubleCirLList_DestInsert********************************\n");
    DoubleCirLList_DestInsert(Manager, 7, 9);
    DoubleCirLList_DestInsert(Manager, 4, 6);
    DoubleCirLList_DestInsert(Manager, 2, 3);
    DoubleCirLList_DestInsert(Manager, 5, 10);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9*/

    // 尾插法 向链表中插入新结点
    printf("*********************************DoubleCirLList_TailInsert********************************\n");
    DoubleCirLList_TailInsert(Manager, 13);
    DoubleCirLList_TailInsert(Manager, 12);
    DoubleCirLList_TailInsert(Manager, 11);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11*/

    // 头删法 删除首结点
    printf("*********************************DoubleCirLList_HeadDel********************************\n");
    DoubleCirLList_HeadDel(Manager);
    DoubleCirLList_HeadDel(Manager);
    DoubleCirLList_HeadDel(Manager);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11*/

    // 中删法 删除指定结点
    printf("*********************************DoubleCirLList_DestDel********************************\n");
    DoubleCirLList_DestDel(Manager, 10);
    DoubleCirLList_DestDel(Manager, 1);
    DoubleCirLList_DestDel(Manager, 6);
    DoubleCirLList_DestDel(Manager, 11);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 8 -> 4 -> 7 -> 9 -> 13 -> 12*/

    // 尾删法 删除尾结点
    printf("*********************************DoubleCirLList_TailDel********************************\n");
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 8 -> 4*/
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_TailDel(Manager);
    DoubleCirLList_TailDel(Manager);
    /*Error,  Double Circular Linked List is empty! */
    DoubleCirLList_HeadInsert(Manager, 66);
    DoubleCirLList_Print(Manager);
    /*Double Circular Linked List:  -> 66*/

    // 等待用户响应
    printf("***Press any key to exit the test***\n");
    getchar();
    return 0;
}

到了这里，关于数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印（基于C语言实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】双向带头循环链表的实现

    【数据结构】双向带头循环链表的实现

    前言：在前面我们学习了顺序表、单向链表，今天我们在单链表的基础上进一步来模拟实现一个带头双向链表。 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关注博主和博主一起学习!一起努力！ 带头双向循环链

    2024年01月15日
    浏览(49)
  • 数据结构-带头双向循环链表的实现

    数据结构-带头双向循环链表的实现

    前言           带头双向循环链表是一种重要的数据结构，它的结构是很完美的，它弥补了单链表的许多不足，让我们一起来了解一下它是如何实现的吧！         它的节点中存储着数据和两个指针，一个 指针_prev 用来记录前一个节点的地址，另一个指针 _next 用来记录后一

    2024年02月13日
    浏览(49)
  • 【数据结构 -- C语言】 双向带头循环链表的实现

    【数据结构 -- C语言】 双向带头循环链表的实现

    目录 1、双向带头循环链表的介绍 2、双向带头循环链表的接口 3、接口实现 3.1 开辟结点 3.2 创建返回链表的头结点 3.3 判断链表是否为空 3.4 打印 3.5 双向链表查找 3.6 双向链表在pos的前面进行插入 3.6.1 头插 3.6.2 尾插 3.6.3 更新头插、尾插写法 3.7 双向链表删除pos位置的节点

    2024年02月09日
    浏览(64)

  • C语言数据结构：双向循环链表的增删操作

    2024年04月25日
    浏览(51)
  • 数据结构 - 链表详解（二）—— 带头双向循环链表

    数据结构 - 链表详解（二）—— 带头双向循环链表

    链表的结构一共有 八种 ：带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。 今天我们来详解带头双向循环链表 带头双向循环链表是一种数据结构，它通

    2024年04月26日
    浏览(57)
  • 数据结构day06（单向循环链表、双向链表）

    数据结构day06（单向循环链表、双向链表）

    双向链表的练习代码 head.h fun.c main.c 今日思维导图哈 ​​​​​​​

    2024年02月10日
    浏览(36)
  • 【数据结构和算法】实现带头双向循环链表（最复杂的链表）

    【数据结构和算法】实现带头双向循环链表（最复杂的链表）

    前文，我们实现了认识了链表这一结构，并实现了无头单向非循环链表，接下来我们实现另一种常用的链表结构，带头双向循环链表。如有仍不了解单向链表的，请看这一篇文章(7条消息) 【数据结构和算法】认识线性表中的链表，并实现单向链表_小王学代码的博客-CSDN博客

    2024年01月17日
    浏览(78)
  • 【数据结构】链表的分类和双向链表

    【数据结构】链表的分类和双向链表

    本篇是基于上篇单链表所作，推荐与上篇配合阅读，效果更加 http://t.csdnimg.cn/UhXEj 链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构： 我们一般叫这个头为哨兵位 我们上回讲的单链表就是不带头单项不循环链表。 今天我们要讲带头双向循环的链表。 不过

    2024年01月25日
    浏览(38)
  • 『初阶数据结构 • C语言』⑨ - 基于结点的数据结构——链表（单链表&&双向循环链表）附完整源码

    『初阶数据结构 • C语言』⑨ - 基于结点的数据结构——链表（单链表&&双向循环链表）附完整源码

      本章内容 1.什么是链表 2.链表常见几种形式 3.无头单向非循环链表的实现 3.1结点结构的定义 3.2函数接口的实现 3.2.1尾插 3.2.2尾删 4. 带头双向循环链表的实现 4.1结点结构的定义 4.2函数接口的实现 5.两种链表的差异 ①尾插与尾删的时间复杂度 ②头插与头删的时间复杂度 ③

    2024年02月16日
    浏览(81)
  • 【数据结构】双向链表的实现

    【数据结构】双向链表的实现

    我要扼住命运的咽喉，他却不能使我完全屈服。                      --贝多芬 目录 一.带头循环的双向链表的特点 二.不带头不循环单向链表和带头循环的双向链表的对比 三.初始化链表，创建哨兵结点 四.双向链表的各种功能的实现 1.双向链表的尾插 2.双向链表的打印 

    2023年04月10日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包