首页 > 其他分享 >数据结构_链表_单向循环链表 & 双向链表的初始化、插入、删除、修改、查询打印(基于C语言实现)

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

时间:2024-11-07 20:30:28浏览次数:4  
标签:Current 结点 C语言 Head CircLList next 链表 数据结构

一、单向循环链表的原理与应用

思考:对于单向链表而言,想要遍历链表,则必须从链表的首结点开始进行遍历,请问有没有更简单的方案实现链表中的数据的增删改查?

回答:是有的,可以使用单向循环的链表进行设计,单向循环的链表的使用规则和普通的单向链表没有较大的区别,需要注意:单向循环链表的尾结点的指针域中必须指向链表的首结点的地址,由于带头结点的单向循环链表更加容易进行管理,所以教学以带头结点的为例:

img

上图所示的就是一个典型的单向循环链表的结构,可以发现单向循环链表的结构属于环形结构,链表中的最后一个结点的指针域中存储的是链表的第一个结点的地址。

img

为了管理单向循环链表,需要构造头结点的数据类型以及构造有效结点的数据类型,如下:

img

(1) 创建一个空链表,由于是使用头结点,所以就需要申请头结点的堆内存并初始化即可!

img

(2) 创建新结点,为新结点申请堆内存并对新结点的数据域和指针域进行初始化,操作如下:

img

(3) 根据情况把新结点插入到链表中,此时可以分为尾部插入、头部插入、指定位置插入:
  • 头插

img

  • 尾插

img

  • 中插

img

(4) 根据情况可以从链表中删除某结点,此时可以分为尾部删除、头部删除、指定元素删除:
  • 头删

img

  • 尾删

img

  • 中删

img

代码

/**
 * @file name : CircularLinkedList.c
 * @brief     : 实现单向循环链表的相关功能
 * @author    :[email protected]
 * @date      :2024/11/07
 * @version   :1.0
 * @note      :
 * CopyRight (c)  2023-2024   [email protected]   All Right Reseverd
 */

单向循环链表公式

img

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

初始化单向循环链表

构建单向循环链表结点

CircLList_t[ data |*next ]
// 指的是单向循环链表中的结点有效数据类型,用户可以根据需要进行修改
typedef int DataType_t;

// 构造单向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct CircularLinkedList
{
    DataType_t data;                 // 结点的数据域
    struct CircularLinkedList *next; // 直接后继的指针域
} CircLList_t;

创建一个空链表(仅头结点)

img

/**
 * @name       CircLList_Create
 * @brief     创建一个空单向循环链表,仅含头结点,并对链表进行初始化
 * @param
 * @return
 *      @retval    Head 头结点地址
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
CircLList_t *CircLList_Create(void)
{
    // 1.创建一个头结点并对头结点申请内存
    CircLList_t *Head = (CircLList_t *)calloc(1, sizeof(CircLList_t));
    if (NULL == Head)
    {
        perror("Calloc memory for Head is Failed");
        exit(-1);
    }

    // 2.对头结点进行初始化,头结点是不存储数据域,指针域指向自己, 体现循环的思想 [date|*next]
    Head->next = Head;

    // 3.把头结点的地址返回即可   Head-->[date|*next]
    return Head;
}

创建一个新结点

image

/**
 * @name       CircLList_NewNode
 * @brief     创建一个新的结点,并对新结点进行初始化(数据域 + 指针域)
 * @param     data 要创建结点的元素
 * @return    程序执行成功与否
 *      @retval    NULL 申请堆内存失败
 *      @retval    New  新结点地址
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
CircLList_t *CircLList_NewNode(DataType_t data)
{
    // 1.创建一个新结点并对新结点申请内存
    CircLList_t *New = (CircLList_t *)calloc(1, sizeof(CircLList_t));
    if (NULL == New)
    {
        perror("Calloc memory for NewNode is Failed");
        return NULL;
    }

    // 2.对新结点的数据域和指针域进行初始化
    New->data = data;
    New->next = NULL;

    return New;
}

插入数据

头插

image

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

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

    // 2.判断单向循环链表是否为空,如果为空,则直接插入到头结点之后, 新结点作为首结点, 体现循环
    if (Head == Head->next)
    {
        Head->next = New; // 让头结点的next指针指向新结点
        New->next = New;  // 新节点指向自己, 体现循环, 仅有一个首结点的单循环链表
        return true;
    }

    // 3.如果单向循环链表为非空,需要让尾结点的next指针指向首结点
    while (Current->next) // 不断向下检查结点指针域
    {
        Current = Current->next;         // 进入下一个结点
        if (Current->next == Head->next) // 结束条件: 达尾结点
        {
            break;
        }
    } // Current到达未尾结点
    Current->next = New;    // 尾结点指针域指向新的首结点
    New->next = Head->next; // 新结点链接旧首结点
    Head->next = New;       // 头结点的next指针域指向新结点的地址

    return true;
}

中插

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

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

    // 2.判断单向循环链表是否为空,如果为空,则新结点作为首结点, 体现循环
    if (Head == Head->next)
    {
        Head->next = New; // 让头结点的next指针指向新结点
        New->next = New;  // 新节点指向自己, 体现循环, 单有效结点
        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 == Head->next)
    {
        New->next = Current->next; // 新结点链接目标结点直接后继
        Current->next = New;
    }
    else if (Current->next == Head->next) // 目标结点是尾结点
    {
        New->next = Head->next; // 作为新尾结点
        Current->next = New;
    }
    else // 目标结点是中间结点
    {
        New->next = Current->next; // 新结点链接目标结点直接后继
        Current->next = New;       // 目标结点的直接后继更新为新结点
    }
    return true;
}

尾插

image

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

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

    // 2.判断单向循环链表是否为空,如果为空,则新结点作为首结点, 体现循环
    if (Head == Head->next)
    {
        Head->next = New; // 让头结点的next指针指向新结点
        New->next = New;  // 新节点指向自己, 体现循环
        return true;
    }

    // 3.如果单向循环链表为非空,需要让尾结点的next指针指向新结点,新结点指向首结点
    while (Phead->next) // 不断向下检查结点指针域
    {
        Phead = Phead->next;           // 进入下一个结点
        if (Phead->next == Head->next) // 当到达尾结点
        {
            break;
        }
    }
    Phead->next = New;      // 尾结点指针域 链接 新结点
    New->next = Head->next; // 新结点指针域 指向 首结点

    return true;
}

删除数据

头删

image

/**
 * @name       CircLList_HeadDel
 * @brief     删除头结点后面的一个结点
 * @param     Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool CircLList_HeadDel(CircLList_t *Head)
{
    // 1.创建操作指针
    // 备份头结点地址,防止头结点丢失
    CircLList_t *Phead = Head;
    // 备份首结点, 用于操作
    CircLList_t *Temp = Head->next;

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

    // 3.判断链表中是否只有首结点

    if (Head->next == Head->next->next)
    {
        Temp->next = NULL; // 首结点的指针域指向NULL, 且防止野指针和内存泄漏
        Head->next = Head; // 头结点next指针指向头结点, 体现"循环"
        free(Temp);        // 释放结点内存, 防止内存泄漏
        return true;
    }

    // 3.如果单向循环链表为非空,需要让尾结点的next指针指向新的首结点(原首结点的直接后继)
    while (Phead->next) // 不断向下检查结点指针域
    {
        Phead = Phead->next;           // 进入下一个结点
        if (Phead->next == Head->next) // 当到达尾结点
        {
            break;
        }
    }

    Phead->next = Head->next->next; // 让尾结点的next指针指向新的首结点(原首结点的直接后继)
    Head->next = Phead->next;       // 头结点的指针域 修改链接为 新的首结点
    Temp->next = NULL;              // 让旧的首结点的指针域指向NULL, 从链表中断开, 且防止野指针和内存泄漏
    free(Temp);                     // 释放旧首结点的内存, 防止内存泄漏
    return true;
}

中删

image

/**
 * @name       CircLList_DestDel
 * @brief     中删, 删除某个元素结点
 * @param     Head 头指针
 * @param     dest 要删除的目标元素
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 未找到目标元素结点
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool CircLList_DestDel(CircLList_t *Head, DataType_t dest)
{
    CircLList_t *Current = Head->next; // 操作指针 初始为指向首结点, 若为空链表则指向头结点
    CircLList_t *Prev = Head;          // 操作指针 存放当前操作指针的前一个结点地址

    // 1.判断单向循环链表是否为空,如果为空,则报错
    if (Head == Head->next)
    {
        printf("Error,  CircularLinkList is empty! \n");
        return false;
    }

    // 2.若单向循环链表非空
    // 目标结点是首结点, 不再继续查找. 目标结点非首结点, 继续向下查找
    while (Current->data != dest)
    {
        Prev = Current;                                               // 备份Current的前一个位置
        Current = Current->next;                                      // 进入下一个结点
        if ((Current->next == Head->next) && (Current->data != dest)) // 达到末尾 且 末尾不是目标
        {
            printf("The target doesn't exist! \n");
            return false;
        }
    } // 找到目标结点, Current此时指向目标  Prev为Current 的前一个位置
    // 目标结点是首结点
    if (Current == Head->next)
    {
        // 若链表只有首结点
        if (Current->next == Head->next)
        {
            Head->next = Head; // 空链表状态
            Current->next = NULL;
            free(Current); // 防止内存泄漏
            return true;
        }
        while (Prev->next) // 不断向下检查结点指针域
        {
            Prev = Prev->next;            // 进入下一个结点
            if (Prev->next == Head->next) // 结束条件: 达尾结点
            {
                break;
            }
        } // Prev到达未尾结点
        Prev->next = Current->next; // 更新尾结点指针域为新首结点地址
        Head->next = Current->next; // 更新首结点链接新首结点
    }
    else if (Current->next == Head->next) // 目标结点是尾结点
    {
        Prev->next = Head->next; // 新尾结点链接首结点, 行成循环
    }
    else // 目标结点是中间结点
    {
        Prev->next = Current->next;
    }
    Current->next = NULL;
    free(Current); // 防止内存泄漏
    return true;
}

尾删

image

/**
 * @name      CircLList_TailDel
 * @brief     删除尾结点
 * @param     Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 链表为空
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool CircLList_TailDel(CircLList_t *Head)
{
    CircLList_t *Current = Head->next; // 操作指针 初始为指向首结点, 若为空链表则指向头结点
    CircLList_t *Prev = Head;          // 操作指针 存放当前操作指针的前一个结点地址

    // 1.判断单向循环链表是否为空,如果为空,则报错
    if (Head == Head->next)
    {
        printf("Error,  CircularLinkList is empty! \n");
        return false;
    }

    // 2.若单向循环链表非空
    // 若链表只有首结点
    if (Current->next == Head->next)
    {
        Head->next = Head; // 空链表状态
        Current->next = NULL;
        free(Current); // 防止内存泄漏
        return true;
    }
    // 若还有别的结点
    while (Current->next) // 不断向下检查结点指针域
    {
        Prev = Current;
        Current = Current->next;         // 进入下一个结点
        if (Current->next == Head->next) // 结束条件: 达尾结点
        {
            break;
        }
    } // Current到达未尾结点 Prev为Current 的前一个位置
    Prev->next = Head->next; // 新尾结点链接首结点, 行成循环
    Current->next = NULL;
    free(Current); // 防止内存泄漏
    return true;
}

查询打印数据

遍历打印

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

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

    printf("Circular Linked List: ");

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

测试

#include "CircularLinkedList.h"

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

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

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

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

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

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

    // 尾删法 删除尾结点
    printf("*********************************CircLList_HeadDel********************************\n");
    CircLList_TailDel(Manager);
    CircLList_TailDel(Manager);
    CircLList_TailDel(Manager);
    CircLList_TailDel(Manager);
    CircLList_Print(Manager);
    /*Circular Linked List:  -> 8 -> 4*/
    CircLList_TailDel(Manager);
    CircLList_TailDel(Manager);
    CircLList_TailDel(Manager);
    /*Error,  CircularLinkList is empty! */
    CircLList_HeadInsert(Manager, 66);
    CircLList_Print(Manager);
    /*Circular Linked List:  -> 66*/
    // 等待用户响应
    printf("***Press any key to exit the test***\n");
    getchar();
    return 0;
}

测试结果:

*********************************CircLList_HeadInsert********************************
Circular Linked List:  -> 2 -> 5 -> 8 -> 1 -> 4 -> 7
*********************************CircLList_DestInsert********************************
Circular Linked List:  -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9
*********************************CircLList_TailInsert********************************
Circular Linked List:  -> 2 -> 3 -> 5 -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11
*********************************CircLList_HeadDel********************************
Circular Linked List:  -> 10 -> 8 -> 1 -> 4 -> 6 -> 7 -> 9 -> 13 -> 12 -> 11
*********************************CircLList_DestDel********************************
Circular Linked List:  -> 8 -> 4 -> 7 -> 9 -> 13 -> 12
*********************************CircLList_HeadDel********************************
Circular Linked List:  -> 8 -> 4
Error,  CircularLinkList is empty! 
Circular Linked List:  -> 66
***Press any key to exit the test***

完整代码

CircularLinkedList.h

#ifndef __CIRCULARLINKEDLIST_H // ifndef是(如果 没有 定义 那么) (__该头文件的名称)
#define __CIRCULARLINKEDLIST_H // #define是 进行定义
/**
 * @file name : CircularLinkedList.c
 * @brief     : 实现单向循环链表的相关功能
 * @author    :[email protected]
 * @date      :2024/11/07
 * @version   :1.0
 * @note      :
 * CopyRight (c)  2023-2024   [email protected]   All Right Reseverd
 */

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

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

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

// 构造单向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct CircularLinkedList
{
    DataType_t data;                 // 结点的数据域
    struct CircularLinkedList *next; // 直接后继的指针域
} CircLList_t;

/**
 * @name       CircLList_Create
 * @brief     创建一个空单向循环链表,仅含头结点,并对链表进行初始化
 * @param
 * @return
 *      @retval    Head 头结点地址
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
CircLList_t *CircLList_Create(void);

/**
 * @name       CircLList_NewNode
 * @brief     创建一个新的结点,并对新结点进行初始化(数据域 + 指针域)
 * @param     data 要创建结点的元素
 * @return    程序执行成功与否
 *      @retval    NULL 申请堆内存失败
 *      @retval    New  新结点地址
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
CircLList_t *CircLList_NewNode(DataType_t data);

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

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

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

/**
 * @name       CircLList_HeadDel
 * @brief     删除头结点后面的一个结点
 * @param     Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool CircLList_HeadDel(CircLList_t *Head);

/**
 * @name       CircLList_DestDel
 * @brief     中删, 删除某个元素结点
 * @param     Head 头指针
 * @param     dest 要删除的目标元素
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 未找到目标元素结点
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool CircLList_DestDel(CircLList_t *Head, DataType_t dest);

/**
 * @name      CircLList_TailDel
 * @brief     删除尾结点
 * @param     Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 链表为空
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool CircLList_TailDel(CircLList_t *Head);
/**
 * @name      CircLList_Print
 * @brief     从头到尾遍历链表
 * @param     Head 头指针
 * @return    无
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
void CircLList_Print(CircLList_t *Head);
#endif
// 结束定义

CircularLinkedList.c

/**
 * @file name : CircularLinkedList.c
 * @brief     : 实现单向循环链表的相关功能
 * @author    :[email protected]
 * @date      :2024/11/07
 * @version   :1.0
 * @note      :
 * CopyRight (c)  2023-2024   [email protected]   All Right Reseverd
 */
#include "CircularLinkedList.h"

/**
 * @name       CircLList_Create
 * @brief     创建一个空单向循环链表,仅含头结点,并对链表进行初始化
 * @param
 * @return
 *      @retval    Head 头结点地址
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
CircLList_t *CircLList_Create(void)
{
    // 1.创建一个头结点并对头结点申请内存
    CircLList_t *Head = (CircLList_t *)calloc(1, sizeof(CircLList_t));
    if (NULL == Head)
    {
        perror("Calloc memory for Head is Failed");
        exit(-1);
    }

    // 2.对头结点进行初始化,头结点是不存储数据域,指针域指向自己, 体现循环的思想 [date|*next]
    Head->next = Head;

    // 3.把头结点的地址返回即可   Head-->[date|*next]
    return Head;
}

/**
 * @name       CircLList_NewNode
 * @brief     创建一个新的结点,并对新结点进行初始化(数据域 + 指针域)
 * @param     data 要创建结点的元素
 * @return    程序执行成功与否
 *      @retval    NULL 申请堆内存失败
 *      @retval    New  新结点地址
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
CircLList_t *CircLList_NewNode(DataType_t data)
{
    // 1.创建一个新结点并对新结点申请内存
    CircLList_t *New = (CircLList_t *)calloc(1, sizeof(CircLList_t));
    if (NULL == New)
    {
        perror("Calloc memory for NewNode is Failed");
        return NULL;
    }

    // 2.对新结点的数据域和指针域进行初始化
    New->data = data;
    New->next = NULL;

    return New;
}

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

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

    // 2.判断单向循环链表是否为空,如果为空,则直接插入到头结点之后, 新结点作为首结点, 体现循环
    if (Head == Head->next)
    {
        Head->next = New; // 让头结点的next指针指向新结点
        New->next = New;  // 新节点指向自己, 体现循环, 仅有一个首结点的单循环链表
        return true;
    }

    // 3.如果单向循环链表为非空,需要让尾结点的next指针指向首结点
    while (Current->next) // 不断向下检查结点指针域
    {
        Current = Current->next;         // 进入下一个结点
        if (Current->next == Head->next) // 结束条件: 达尾结点
        {
            break;
        }
    } // Current到达未尾结点
    Current->next = New;    // 尾结点指针域指向新的首结点
    New->next = Head->next; // 新结点链接旧首结点
    Head->next = New;       // 头结点的next指针域指向新结点的地址

    return true;
}

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

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

    // 2.判断单向循环链表是否为空,如果为空,则新结点作为首结点, 体现循环
    if (Head == Head->next)
    {
        Head->next = New; // 让头结点的next指针指向新结点
        New->next = New;  // 新节点指向自己, 体现循环, 单有效结点
        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 == Head->next)
    {
        New->next = Current->next; // 新结点链接目标结点直接后继
        Current->next = New;
    }
    else if (Current->next == Head->next) // 目标结点是尾结点
    {
        New->next = Head->next; // 作为新尾结点
        Current->next = New;
    }
    else // 目标结点是中间结点
    {
        New->next = Current->next; // 新结点链接目标结点直接后继
        Current->next = New;       // 目标结点的直接后继更新为新结点
    }
    return true;
}

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

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

    // 2.判断单向循环链表是否为空,如果为空,则新结点作为首结点, 体现循环
    if (Head == Head->next)
    {
        Head->next = New; // 让头结点的next指针指向新结点
        New->next = New;  // 新节点指向自己, 体现循环
        return true;
    }

    // 3.如果单向循环链表为非空,需要让尾结点的next指针指向新结点,新结点指向首结点
    while (Phead->next) // 不断向下检查结点指针域
    {
        Phead = Phead->next;           // 进入下一个结点
        if (Phead->next == Head->next) // 当到达尾结点
        {
            break;
        }
    }
    Phead->next = New;      // 尾结点指针域 链接 新结点
    New->next = Head->next; // 新结点指针域 指向 首结点

    return true;
}

/**
 * @name       CircLList_HeadDel
 * @brief     删除头结点后面的一个结点
 * @param     Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool CircLList_HeadDel(CircLList_t *Head)
{
    // 1.创建操作指针
    // 备份头结点地址,防止头结点丢失
    CircLList_t *Phead = Head;
    // 备份首结点, 用于操作
    CircLList_t *Temp = Head->next;

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

    // 3.判断链表中是否只有首结点

    if (Head->next == Head->next->next)
    {
        Temp->next = NULL; // 首结点的指针域指向NULL, 且防止野指针和内存泄漏
        Head->next = Head; // 头结点next指针指向头结点, 体现"循环"
        free(Temp);        // 释放结点内存, 防止内存泄漏
        return true;
    }

    // 3.如果单向循环链表为非空,需要让尾结点的next指针指向新的首结点(原首结点的直接后继)
    while (Phead->next) // 不断向下检查结点指针域
    {
        Phead = Phead->next;           // 进入下一个结点
        if (Phead->next == Head->next) // 当到达尾结点
        {
            break;
        }
    }

    Phead->next = Head->next->next; // 让尾结点的next指针指向新的首结点(原首结点的直接后继)
    Head->next = Phead->next;       // 头结点的指针域 修改链接为 新的首结点
    Temp->next = NULL;              // 让旧的首结点的指针域指向NULL, 从链表中断开, 且防止野指针和内存泄漏
    free(Temp);                     // 释放旧首结点的内存, 防止内存泄漏
    return true;
}

/**
 * @name       CircLList_DestDel
 * @brief     中删, 删除某个元素结点
 * @param     Head 头指针
 * @param     dest 要删除的目标元素
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 未找到目标元素结点
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool CircLList_DestDel(CircLList_t *Head, DataType_t dest)
{
    CircLList_t *Current = Head->next; // 操作指针 初始为指向首结点, 若为空链表则指向头结点
    CircLList_t *Prev = Head;          // 操作指针 存放当前操作指针的前一个结点地址

    // 1.判断单向循环链表是否为空,如果为空,则报错
    if (Head == Head->next)
    {
        printf("Error,  CircularLinkList is empty! \n");
        return false;
    }

    // 2.若单向循环链表非空
    // 目标结点是首结点, 不再继续查找. 目标结点非首结点, 继续向下查找
    while (Current->data != dest)
    {
        Prev = Current;                                               // 备份Current的前一个位置
        Current = Current->next;                                      // 进入下一个结点
        if ((Current->next == Head->next) && (Current->data != dest)) // 达到末尾 且 末尾不是目标
        {
            printf("The target doesn't exist! \n");
            return false;
        }
    } // 找到目标结点, Current此时指向目标  Prev为Current 的前一个位置
    // 目标结点是首结点
    if (Current == Head->next)
    {
        // 若链表只有首结点
        if (Current->next == Head->next)
        {
            Head->next = Head; // 空链表状态
            Current->next = NULL;
            free(Current); // 防止内存泄漏
            return true;
        }
        while (Prev->next) // 不断向下检查结点指针域
        {
            Prev = Prev->next;            // 进入下一个结点
            if (Prev->next == Head->next) // 结束条件: 达尾结点
            {
                break;
            }
        } // Prev到达未尾结点
        Prev->next = Current->next; // 更新尾结点指针域为新首结点地址
        Head->next = Current->next; // 更新首结点链接新首结点
    }
    else if (Current->next == Head->next) // 目标结点是尾结点
    {
        Prev->next = Head->next; // 新尾结点链接首结点, 行成循环
    }
    else // 目标结点是中间结点
    {
        Prev->next = Current->next;
    }
    Current->next = NULL;
    free(Current); // 防止内存泄漏
    return true;
}

/**
 * @name      CircLList_TailDel
 * @brief     删除尾结点
 * @param     Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 链表为空
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool CircLList_TailDel(CircLList_t *Head)
{
    CircLList_t *Current = Head->next; // 操作指针 初始为指向首结点, 若为空链表则指向头结点
    CircLList_t *Prev = Head;          // 操作指针 存放当前操作指针的前一个结点地址

    // 1.判断单向循环链表是否为空,如果为空,则报错
    if (Head == Head->next)
    {
        printf("Error,  CircularLinkList is empty! \n");
        return false;
    }

    // 2.若单向循环链表非空
    // 若链表只有首结点
    if (Current->next == Head->next)
    {
        Head->next = Head; // 空链表状态
        Current->next = NULL;
        free(Current); // 防止内存泄漏
        return true;
    }
    // 若还有别的结点
    while (Current->next) // 不断向下检查结点指针域
    {
        Prev = Current;
        Current = Current->next;         // 进入下一个结点
        if (Current->next == Head->next) // 结束条件: 达尾结点
        {
            break;
        }
    } // Current到达未尾结点 Prev为Current 的前一个位置
    Prev->next = Head->next; // 新尾结点链接首结点, 行成循环
    Current->next = NULL;
    free(Current); // 防止内存泄漏
    return true;
}
/**
 * @name      CircLList_Print
 * @brief     从头到尾遍历链表
 * @param     Head 头指针
 * @return    无
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
void CircLList_Print(CircLList_t *Head)
{
    // 判断是否为空链表
    if (Head->next == Head)
    {
        printf("The list is empty.\n");
        return;
    }

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

    printf("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    :[email protected]
 * @date      :2024/11/07
 * @version   :1.0
 * @note      :
 * CopyRight (c)  2023-2024   [email protected]   All Right Reseverd
 */

#include "CircularLinkedList.h"

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

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

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

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

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

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

    // 尾删法 删除尾结点
    printf("*********************************CircLList_HeadDel********************************\n");
    CircLList_TailDel(Manager);
    CircLList_TailDel(Manager);
    CircLList_TailDel(Manager);
    CircLList_TailDel(Manager);
    CircLList_Print(Manager);
    /*Circular Linked List:  -> 8 -> 4*/
    CircLList_TailDel(Manager);
    CircLList_TailDel(Manager);
    CircLList_TailDel(Manager);
    /*Error,  CircularLinkList is empty! */
    CircLList_HeadInsert(Manager, 66);
    CircLList_Print(Manager);
    /*Circular Linked List:  -> 66*/
    // 等待用户响应
    printf("***Press any key to exit the test***\n");
    getchar();
    return 0;
}

二、双向链表的原理与应用

如果想要提高单向链表或者单向循环链表的访问速度,则可以在链表中的结点中再添加一个指针域,让新添加的指针域指向当前结点的直接前驱的地址,也就意味着一个结点中有两个指针域(prev + next),也被称为双向链表(Double Linked List)。

img

由于带头结点更加方便用户进行数据访问,所以本次创建一条带头结点的双向不循环的链表。

img

(1) 创建一个空链表,由于是使用头结点,所以就需要申请头结点的堆内存并初始化即可!

img

(2) 创建新结点,为新结点申请堆内存并对新结点的数据域和指针域进行初始化,操作如下:

img

(3) 根据情况可以从链表中插入新结点,此时可以分为尾部插入、头部插入、指定位置插入:
  • 头插

img

  • 尾插

img

  • 中插

img

(4) 根据情况可以从链表中删除某结点,此时可以分为尾部删除、头部删除、指定结点删除:
  • 头删

img

  • 尾删

img

  • 中删

img

代码

/**
  * @file name : 双向链表
  * @brief     : 双向链表的初始化、插入、删除、修改、查询打印
  * @author    : [email protected]
  * @date      : 2024/11/07
  * @version   : 1.0
  * @note      : 待续:修改数据、 查询打印数据 
  * CopyRight (c)  2023-2024   [email protected]   All Right Reseverd
*/

双向链表公式

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

初始化双向链表

构建双向链表结点

image

DoubleLList_t [*prev | data |*next ]
// 指的是双向链表中的结点有效数据类型,用户可以根据需要进行修改
typedef int DataType_t;

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

} DoubleLList_t;

创建一个空链表(仅头结点)

image

/**
 * @name      DoubleLList_Create
 * @brief     创建一个空双向链表,空链表应该有一个头结点,对链表进行初始化
 * @param
 * @return
 *      @retval    Head 头结点地址
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
DoubleLList_t *DoubleLList_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.对头结点进行初始化,头结点是不存储数据域,指针域指向NULL [prev|date|next]
    Head->prev = NULL;
    Head->next = NULL;

    // 3.把头结点的地址返回即可   Head-->[prev|date|next]
    return Head;
}

创建一个新结点

image

/**
 * @name      DoubleLList_NewNode
 * @brief     创建新的结点,并对新结点进行初始化(数据域 + 指针域)
 * @param     data 要创建结点的元素
 * @return    程序执行成功与否
 *      @retval    NULL 申请堆内存失败
 *      @retval    New  新结点地址
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
DoubleLList_t *DoubleLList_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->data = data;
    New->prev = NULL;
    New->next = NULL;

    return New;
}

插入数据

头插

image

/**
 * @name      DoubleLList_HeadInsert
 * @brief     在双向链表的头结点后插入
 * @param     Head 头指针
 * @param     data 新元素
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool DoubleLList_HeadInsert(DoublelList_t *Head, DataType_t data)
{
    // 1.创建新结点并对新结点进行初始化
    DoubleLList_t *New = DoubleLList_NewNode(data);
    if (NULL == New)
    {
        printf("can not insert new node , Failed to create a node\n");
        return false;
    }
    // 2.判断双向链表是否为空,如果为空,则直接插入到头结点之后
    if (NULL == Head->next)
    {
        Head->next = New; // 让头结点的next指针指向新结点
        return true;
    }
    // 3.如果双向链表为非空,则把新结点插入到链表的头部
    New->next = Head->next; // 新结点的next指针指向原本的首结点地址
    Head->next->prev = New; // 原本的首结点的prev指针指向新结点的地址
    Head->next = New;       // 更新头结点的next指针,让next指针指向新结点的地址
    return true;
}

中插

image

/**
 * @name      Doublellist_DestInsert
 * @brief     双向链表中的指定元素后面插入新结点
 * @param     Head 头指针
 * @param     dest 要查找的结点
 * @param     data 要插入的数据
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool Doublellist_DestInsert(DoubleLList_t *Head, DataType_t dest, DataType_t data)
{
    DoubleLList_t *Phead = Head; // 备份头结点地址,防止头结点丢失

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

    // 2.判断双向链表是否为空,如果为空,则直接插入到头结点之后
    if (NULL == Head->next)
    {
        Head->next = New; // 让头结点的next指针指向新结点
        return true;
    }

    // 3.如果双向链表为非空,此时分为3种情况(尾部or中间)
    while (Phead->next)
    {
        Phead = Phead->next;
        if (Phead->data == dest)
        {
            break;
        }
    }

    // 如果遍历链表之后发现没有目标结点,则退出即可
    if (Phead->next == NULL && Phead->data != dest)
    {
        printf("dest node is not found\n");
        return false;
    }

    // 如果遍历链表找到目标结点,则分为(尾部or中间)
    if (Phead->next == NULL) // 尾插
    {
        New->prev = Phead; // 新结点的prev指针指向尾结点的地址
        Phead->next = New; // 尾结点的next指针指向新结点
    }
    else // 中间
    {
        New->next = Phead->next; // 新结点的next指针指向目标结点的直接后继结点
        New->prev = Phead;       // 新结点的prev指针指向目标结点的地址
        Phead->next->prev = New; // 目标结点的直接后继结点的prev指针指向新结点
        Phead->next = New;       // 目标结点的next指针指向新结点
    }
    return true;
}

尾插

image

/**
 * @name      DoubleLList_TailInsert
 * @brief     将新元素插入到尾结点后面
 * @param     Head 头指针
 * @param     data 新元素
 * @return 程序执行成功与否
 *      @retval    false 插入失败
 *      @retval    true  插入成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool DoubleLList_TailInsert(DoubleLList_t *Head, DataType_t data)
{
    DoubleLList_t *Phead = Head; // 备份头结点地址,防止头结点丢失
    // 1.创建新结点并对新结点进行初始化
    DoubleLList_t *New = DoubleLList_NewNode(data);
    if (NULL == New)
    {
        printf("can not insert new node , Failed to create a node\n");
        return false;
    }
    // 2,判断双向链表是否为空,如果为空,则直接插入到头结点之后
    if (NULL == Head->next)
    {
        Head->next = New; // 让头结点的next指针指向新结点
        return true;
    }
    // 3.如果双向链表为非空,则把新结点插入到链表的尾部
    while (Phead->next)
    {
        Phead = Phead->next;
    }
    Phead->next = New; // 尾结点的next指针指向新结点地址
    New->prev = Phead; // 新结点的prev指针指向原本的尾结点地址
    return true;
}

删除数据

头删

image

/**
 * @name      DoublelList_HeadDel
 * @brief     删除头结点后面的一个结点
 * @param     Head 头指针
 * @return 程序执行成功与否
 *      @retval    false 删除失败
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool DoublelList_HeadDel(DoubleLList_t *Head)
{
    // 检查链表是否为空或只有头结点
    if (Head == NULL || Head->next == NULL)
    {
        return false;
    }

    DoubleLList_t *Phead = Head->next; // 指向头结点后的第一个结点

    // 如果头结点后还有更多结点
    if (Phead->next != NULL)
    {
        Phead->next->prev = Head;
    }
    Head->next = Phead->next; // 更新头结点的next指针
    Phead->next = NULL;       // 防止野指针和内存泄漏
    // 清理节点
    free(Phead); // 释放内存

    return true;
}

中删

image

/**
 * @name      DoublelList_DestDel
 * @brief     中删, 删除某个元素结点
 * @param     Head 头指针
 * @param     dest 要删除的目标元素
 * @return 程序执行成功与否
 *      @retval    false 删除失败, 未找到目标元素结点
 *      @retval    true  删除成功
 * @date      2024/11/07
 * @version   1.0
 * @note
 */
bool DoublelList_DestDel(DoubleLList_t *Head, DataType_t dest)
{
    DoubleLList_t *Phead = Head; // 备份头结点地址,防止头结点丢失
    // 1.判断双向链表是否为空, 如果为空, 则直接插入到头结点之后
    if (NULL == Head->next)
    {
        printf("linked list is empty\n");
        return false;
    }
    // 2.如果双向链表为非空,此时遍历链表查找没有目标结点(找到or未找到)
    while (Phead->next)
    {
        Phead = Phead->next;

        if (Phead->data = dest)
        {
            break;
        }
    }

    // 如果链表中没有目标结点,此时直接退出即可
    if (Phead->next == NULL && Phead->data != dest)
    {
        printf("dest node is not found\n");
        return false;
    }

    // 如果链表中发现目标结点,此时分为(头部 or尾部 or中间)
    if (Phead == Head->next) // 头部
    {
        Head->next = Phead->next; // 更新头结点,让头结点的next指针指向首结点的直接后继
        if (Phead->next != NULL)
        {
            Phead->next->prev = NULL;
            Phead->next = NULL;
        }
        free(Phead); // 释放待删除结点内存
    }
    else if (Phead->next == NULL) // 尾部
    {
        Phead->prev->next = NULL; // 尾结点的直接前驱结点的next指针指向NULL
        Phead->prev = NULL;       // 尾结点的prev指针指向NULL
        free(Phead);              // 释放待删除结点内存
    }
    else
    {
        Phead->prev->next = Phead->next; // 让待删除结点的直接前驱结点的next指针指向待删除结点的直接后继地址
        Phead->next->prev = Phead->prev; // 让待删除结点的直接后继结点的prev指针指向待删除结点的直接前驱地址
        Phead->next = NULL;              // 让待删除结点的next指针指向NULL
        Phead->prev = NULL;              // 让待删除结点的prev指针指向NULL
        free(Phead);                     // 释放待删除结点内存
    }
    return true;
}

尾删

image

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

    // 检查链表是否为空或只有头结点
    if (Head == NULL || Head->next == NULL)
    {
        return false;
    }

    // 遍历到尾结点
    while (current->next != NULL)
    {
        current = current->next;
    }

    // current现在指向尾结点
    if (current->prev != NULL)
    {
        current->prev->next = NULL; // 将尾结点的直接前驱设置为NULL
    }

    // 释放尾结点的内存, 防止内存泄漏
    free(current);

    return true;
}

其它

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 主函数,用于演示
int main(int argc, char *argv[]) {


    return 0;
}

练习:

img

img

img

img

img

img

img

img

标签:Current,结点,C语言,Head,CircLList,next,链表,数据结构
From: https://www.cnblogs.com/wyfm/p/18533925

相关文章

  • 使用c语言,用keil5进行stm32F103c8点灯实验
    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录前言学习stm32首先要学会最基础的电灯实验。进行电灯实验需要进行一些前提工作,需要建立启动文件start和标准外设驱动文件library文件和uesr文件这三个工程文件。具体文件可在网站上进行搜素拷贝......
  • C语言学习8
    最近学的不是很多,只能更几个C语言小游戏给大家看看。一.猜数字游戏(难)1.随机数的生成要想完成猜数字游戏,⾸先得产⽣随机数,那怎么产⽣随机数呢?2.randC语⾔提供了⼀个函数叫rand,这函数是可以⽣成随机数的,函数原型如下所⽰:intrand(void);rand函数会返回⼀个伪随机数......
  • C语言逻辑操作符
    C语言逻辑操作符在C语言中,逻辑操作符用于执行逻辑运算,它们通常用于控制流语句中,如if和while循环,以根据给定的条件逻辑来决定程序的执行路径。C语言提供了三种逻辑操作符: 1.逻辑与(&&):当两个操作数都为真(非零)时,结果为真;否则结果为假。 2.逻辑或(||):当两个操作数中......
  • 用C语言代码输出三个数
    题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?已知:1、三位数2、1-43、各不相同输出:1、有多少个这样的三位数2、依次输出#include<stdio.h>intmain(){for(intb=1;b<5;b++)  {   for(ints=1;s<5;s++)    ......
  • 【LeetCode】返回链表的中间结点、删除链表的倒数第 N 个结点
    主页:HABUO......
  • 插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序
    #include<stdio.h>#include<stdlib.h>//插入排序voidInsertSort(intA[],intn){inti,j,temp;for(i=1;i<n;i++){temp=A[i];j=i-1;while(j>=0&&A[j]>temp){A......
  • 链表的插入排序
    #include<stdio.h>#include<stdlib.h>//定义链表节点结构typedefstructNode{intdata;structNode*next;}Node;//创建新节点Node*createNode(intdata){Node*newNode=(Node*)malloc(sizeof(Node));newNode->data=data;newN......
  • 数据结构学习
    computer数据结构第一章算法一个有限指令集接受一些输入产生输出一定要在有限的步骤之后终止每一条指令必须有明确色目标,不可以有歧义,计算机能处理的范围之内,不依赖任何语言和描述。什么是好算法时间复杂度空间复杂度复杂度的渐进表示法输入规模n每十亿`......
  • C语言 联合体(共用体)学习笔记
    一、联合体(共用体)的定义       联合体是一种特殊的自定义类型,这种类型定义的变量也包含一系列的成员,特征是这些成员共用一块空间(所以联合体也叫共用体)。       联合体的声明格式:unionUn//去掉联合体名即为匿名联合{ charc; inti;};二、联合体的特......
  • 链表(C 语言)
    目录一、链表的概念1.链表的结构2.链表的分类3.链表的优势二、链表的实现1.无头单项非循环链表的实现1.1代码说明2.带头双向循环链表的实现2.1代码说明三、链表和顺序表的区别四、链表总结一、链表的概念链表是一种顺序表,它由一个一个的节点组成,该节点中......