首页 > 其他分享 >双向循环链表

双向循环链表

时间:2024-04-25 15:46:23浏览次数:16  
标签:结点 Phead Head next 链表 循环 双向 New prev

目录 [TOC]

/**
 * @file name:	main.c
 * @brief  双向循环链表的接口设计
 * @author [email protected]
 * @date 2024/04/24
 * @version 1.0 :版本
 * @property :属性介绍
 * @note   补充 注意 说明
 * CopyRight (c)  2023-2024   [email protected]   All Right Reseverd
 */

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

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

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

} DoubleCirLinked;
# 创建一个空双向链表
/**
 * @function name:	DoubleLList_Create
 * @brief   创建一个空双向链表,空链表应该有一个头结点,对链表进行初始化
 * @param  介绍函数参数 void
 * @retval void
 * @date 2024/04/23
 * @version 1.0 :版本
 * @note   补充 注意 说明
 */
// 创建一个空双向链表,空链表应该有一个头结点,对链表进行初始化
DoubleCirLinked *DoubleLList_Create(void)
{

    DoubleCirLinked *Head = (DoubleCirLinked *)calloc(1, sizeof(DoubleCirLinked));
    if (NULL == Head)
    {
        perror("Calloc memory for Head is Failed");
        exit(-1);
    }

    // 2.对头结点进行初始化,头结点是不存储数据域,指针域指向NULL
    Head->prev = Head;
    Head->next = Head;

    // 3.把头结点的地址返回即可
    return Head;
}

创建一个新的结点

// 创建新的结点,并对新结点进行初始化(数据域 + 指针域)

/**
 * @function name:	DoubleLList_NewNode
 * @brief       // 1.创建一个新结点并对新结点申请内存
 * @param  介绍函数参数 @data
 * @retval void
 * @date 2024/04/24
 * @version 1.0 :版本
 * @note   补充 注意 说明
 */
DoubleCirLinked *DoubleCircLList_NewNode(DataType_t data)
{
    // 1.创建一个新结点并对新结点申请内存
    DoubleCirLinked *New = (DoubleCirLinked *)calloc(1, sizeof(DoubleCirLinked));
    if (NULL == New)
    {
        perror("Calloc memory for NewNode is Failed");
        return NULL;
    }

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

    return New;
}

#头插

/**
 * @function name:	DoubleLList_NewNode
 * @brief       在列表头部插入新结点
 * @param  介绍函数参数 @head @data
 * @retval bool
 * @date 2024/04/23
 * @version 1.0 :版本
 * @note   补充 注意 说明
 */
bool DoubleCirLList_HeadInsert(DoubleCirLinked *Head, DataType_t data)
{
    // 对链表的头文件的地址进行备份
    DoubleCirLinked *Phead = Head->next;

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

    // 2.判断链表是否为空,如果为空,则直接插入即可
    if (Head == Head->next)
    {
        Head->next = New;
        New->next = New;

        return true;
    }

    // 3.如果链表为非空,则把新结点插入到链表的头部
    New->prev = Phead->prev; // 新结点的prev指针指向尾结点的地址
    Phead->prev->next = New; // 尾结点的next指针指向新结点的地址
    New->next = Head->next;  // 新结点的next指针指向原首结点的地址
    Head->next->prev = New;  // 原首结点的prev指针指向新结点的地址
    Head->next = New;        // 头结点的next指向新结点的地址

    return true;
}

尾插

/**
 * @function name:	DoubleLList_t_TailInsert
 * @brief       在列表尾部插入新结点
 * @param  介绍函数参数 @head @data
 * @retval bool
 * @date 2024/04/23
 * @version 1.0 :版本
 * @note   补充 注意 说明
 */
bool DoubleLList_t_TailInsert(DoubleCirLinked *Head, DataType_t data)
{
    // 1.创建新的结点,并对新结点进行初始化
    DoubleCirLinked *Phead = Head->next;
    DoubleCirLinked *New = DoubleCircLList_NewNode(data);
    if (NULL == New)
    {
        printf("can not insert new node\n");
        return false;
    }

    // 2.判断链表是否为空,如果为空,则直接插入即可
    if (Head == Head->next)
    {
        Head->next = New;
        return true;
    }
    New->prev = Phead->prev;
    Phead->prev->next = New;
    New->next = Head->next;
    Head->next->prev = New;
    return true;
}

中间位置插入

/**
 * @function name:	DoubleLList_t_DestInsert
 * @brief       在列表任意部插入新结点
 * @param  介绍函数参数 @head @data @dest
 * @retval bool
 * @date 2024/04/23
 * @version 1.0 :版本
 * @note   补充 注意 说明
 */
bool DoubleCirLList_DestInsert(DoubleCirLinked *Head, DataType_t destval, DataType_t data)
{
    // 对链表的头文件的地址进行备份
    DoubleCirLinked *Phead = Head;

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

    // 2.判断链表是否为空,如果为空,则直接插入即可
    if (NULL == Head->next)
    {
        Head->next = New;
        return true;
    }

    // 3.如果链表为非空,则把新结点插入到双向链表的指定位置
    while (Phead->next) // 遍历找到目标结点进行后插
    {
        Phead = Phead->next;

        if (Head->next == Phead->next || Phead->data == destval)
        {
            break;
        }
    }

    // 如果遍历链表找不到目标结点,则退出即可
    if (Phead->next == Head->next && Phead->data != destval)
    {
        printf("dest node is not found\n");
        return false;
    }

    // 如果遍历链表找到目标结点,则有三种情况(头部插入 尾部插入 中间插入)
    if (Phead->next == Head->next) // 进行尾插
    {
        New->prev = Phead;      // 新结点的prev指针指向原尾结点地址
        Phead->next = New;      // 尾结点的next指针指向新结点地址
        New->next = Head->next; // 新结点的next指针指向首结点的地址
        Head->next->prev = New; // 首结点的prev指针指向新结点的地址
    }
    else
    {
        New->next = Phead->next; // 新结点的next指向目标结点的直接后继结点的地址
        Phead->next->prev = New; // 目标结点的直接后继结点的prev指针指向新结点
        New->prev = Phead;       // 新结点的prev指向目标结点的地址
        Phead->next = New;       // 目标结点的next指针指向新结点
    }

    return true;
}

头删

/**
 * @function name:	DoubleLList_t_HeadDel
 * @brief       删除首结点
 * @param  介绍函数参数 @head @data
 * @retval bool
 * @date 2024/04/23
 * @version 1.0 :版本
 * @note   补充 注意 说明
 */
bool DoubleLList_t_HeadDel(DoubleCirLinked *Head)
{
    DoubleCirLinked *Phead = Head->next;
    if (Head->next == Head)
    {
        printf("list is empty , can not delate");
        return false;
    }
    else if (Phead->next == Phead)
    {
        Head->next = Head;
        free(Phead);
        return true;
    }
    else
    {
        Phead->prev->next = Phead->next;
        Phead->next->prev = Phead->prev;
        Head->next = Phead->next;
        Phead->prev = NULL;
        Phead->next = NULL;
        free(Phead);
        return true;
    }
}

尾删

/**
 * @function name:	DoubleLList_t_TailDel
 * @brief       删除尾结点
 * @param  介绍函数参数 @head @data
 * @retval bool
 * @date 2024/04/23
 * @version 1.0 :版本
 * @note   补充 注意 说明
 */
bool DoubleLList_t_TailDel(DoubleCirLinked *Head)
{
    DoubleCirLinked *Phead = Head->next->prev;
    if (Head->next == Head)
    {
        printf("list is empty , can not delate");
        return false;
    }
    // 判断是否只有一个结点
    else if (Head->next->next == Head->next)
    {
        Head->next->next = NULL;
        Head->next->prev = NULL;
        Head->next = Head;

        free(Phead);
        return true;
    }
    else
    {
        Phead->prev->next = Head->next;
        Head->next->prev = Phead->prev;
        Phead->prev = NULL;
        Phead->next = NULL;
        free(Phead);

        return false;
    }
}

指定位置删除结点

/**
 * @function name:	DoubleLList_t_DestDel
 * @brief       删除指定位置结点
 * @param  介绍函数参数 @head @data @dest
 * @retval bool
 * @date 2024/04/23
 * @version 1.0 :版本
 * @note   补充 注意 说明
 */

bool DoubleLList_t_DestDel(DoubleCirLinked *Head, DataType_t destval)
{
    DoubleCirLinked *Phead = Head;
    DoubleCirLinked *Temp = Head->next;
    // 判断链表是否为空
    if (Head->next == Head)
    {
        printf("list is empty , can not delate");
        return false;
    }
    // 判断链表是否只有一个结点
    else if (Phead->next == Phead)
    {
        Head->next = Head;
        free(Phead);
        return true;
    }
    // 遍历到指定结点
    while (Temp->next) // 遍历找到目标结点进行后插
    {
        Temp = Temp->next;
        if (Temp->data == destval)
        {
            break;
        }
    }
    // 判断所给数据是否是在尾结点
    if (Temp->next == Head->next)
    {
        Head->next->prev = Temp->prev;
        Temp->prev->next = Head->next;
        Temp->prev = NULL;
        Temp->next = NULL;
        free(Temp);
    }
    Temp->prev->next = Temp->next;
    Temp->next->prev = Temp->prev;
    Temp->next = NULL;
    Temp->prev = NULL;
    free(Temp);
    return true;
}

遍历链表

/**
 * @function name:	DoubleCirLList_Print
 * @brief       遍历链表输出
 * @param  介绍函数参数 @head
 * @retval bool
 * @date 2024/04/23
 * @version 1.0 :版本
 * @note   补充 注意 说明
 */
bool DoubleCirLList_Print(DoubleCirLinked *Head)
{
    // 对单向循环链表的头结点的地址进行备份
    DoubleCirLinked *Temp = Head;

    // 判断当前链表是否为空,为空则直接退出
    if (Head->next == Head)
    {
        printf("current DoubleCirLList is empty!\n");
        return false;
    }

    // 从首结点开始遍历
    while (1)
    {
        // 把头结点的直接后继作为新的头结点
        Temp = Temp->next;
        // 输出头结点的直接后继的数据域
        printf("data = %d\n", Temp->data);

        // 判断是否到达尾结点,尾结点的next指针是指向首结点的地址
        if (Temp->next == Head->next)
        {
            break;
        }
    }
    printf("\n");
    return true;
}

函数验证

int main()
{
    DoubleCirLinked *Manager = DoubleLList_Create();
    // 头插
    DoubleCirLList_HeadInsert(Manager, 1);
    DoubleCirLList_HeadInsert(Manager, 2);
    DoubleCirLList_HeadInsert(Manager, 3);
    DoubleCirLList_HeadInsert(Manager, 4);
    DoubleCirLList_HeadInsert(Manager, 5);
    DoubleCirLList_HeadInsert(Manager, 6);
    // 尾差
    DoubleLList_t_TailInsert(Manager, 7);
    DoubleLList_t_TailInsert(Manager, 8);
    // 指定值后插入
    DoubleCirLList_DestInsert(Manager, 5, 10);
    // 头删
    DoubleLList_t_HeadDel(Manager);
    // 尾删
    DoubleLList_t_TailDel(Manager);
    // 打印
    DoubleCirLList_Print(Manager);
    // 指定值删除
    DoubleLList_t_DestDel(Manager, 3);
    // 最终遍历验证
    DoubleCirLList_Print(Manager);

    return 0;
}

标签:结点,Phead,Head,next,链表,循环,双向,New,prev
From: https://www.cnblogs.com/zeratul/p/18157826

相关文章

  • 单向链表
    /***********************************************************************************************************单向链表**Copyright(c)[email protected]********************************************************************......
  • 双向循环链表接口
    双向循环链表接口/*************************************************************filename:DoubleCircularLinkedListinterface*author:[email protected]*date:2024/04/23*function:MakegreatCVengineer*......
  • 双向循环链表实现插入、删除和遍历功能接口
    /************************************************************************************filename:004_双向循环链表.c*author:[email protected]*date:2024/04/25*function:设计双向循环链......
  • 单向循环链表的删除与插入
    单向循环链表单向循环链表是一种数据结构,它在单向链表的基础上进行了扩展。在单向链表中,最后一个节点的指针域为空,即指向NULL。而在单向循环链表中,最后一个节点的指针域不再指向NULL,而是指向链表的头节点,从而形成一个环状的链表结构。单向循环链表有两种主要类型:带头指针的单向......
  • 双链螺旋链表的头插中插尾插 头删中删尾删
    双链螺旋链表的头插中插尾插头删中删尾删#include<stdio.h>#include<stdbool.h>#include<stdlib.h>/**********************************************************************************函数名称:CircLList_NewNode*函数功能:创建一个新节点,实现头插......
  • 数据结构:双向循环链表的创建·插入·删除
    数据结构:双向循环链表的创建·插入·删除/***@filename:数据结构:双向循环链表的创建·插入·删除*@brief:实现双向循环链表的创建·插入·删除*@author :[email protected]*@date :2024/04/24*@version:2.0*@note:none*CopyRig......
  • CIRCLEQ_INSERT_AFTER, C语言循环队列
     CMakeLists.txt#CMakeList.txt:CMakeprojectforllist,includesourceanddefine#projectspecificlogichere.#cmake_minimum_required(VERSION3.2)#Addsourcetothisproject'sexecutable.add_executable(poj2823"main.c""......
  • 双向循环链表的创建练习
    include<stdio.h>include<stdlib.h>/**@filename: Untitled-1.c@brief双向链表@[email protected]@date2024/04/[email protected]:版本@property:属性介绍@noteCopyRight(c)[email protected]*/typedefstru......
  • excel 用VBA循环打印数据
    SubPrintData()DimwsAsWorksheetSetws=ThisWorkbook.Sheets("Sheet1")'修改为你的工作表名DimrngAsRangeSetrng=ws.Range("A1:D10")'修改为你的数据区域DimcellAsRangeDimiAsIntegerAp......
  • 数据结构——单向循环链表
    一、单向循环链表(一)单向循环链表的构造单向循环链表的尾结点的指针域中必须指向链表的首结点的地址1)构造单向循环链表的结点//单向循环链表中的结点有效数据类型,用户可以根据需要进行修改typedefintDataType_t;//构造单向循环链表的结点,链表中所有结点的数据类型应该......