首页 > 其他分享 >双向循环链表实现插入、删除和遍历功能接口

双向循环链表实现插入、删除和遍历功能接口

时间：2024-04-25 14:56:00浏览次数：22  
标签：tmp head 遍历 接口 next 链表 New prev 

/**********************************************************************************
 *          
 *          file name:  004_双向循环链表.c
 *          author   :  [email protected]
 *          date     :  2024/04/25
 *          function :  设计双向循环链表的接口
 *          note     :  None
 *          
 *          CopyRight (c) 2024-2024  [email protected]    All Right Reseverd
 *      
 * *******************************************************************************/

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


//指的是双向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int  DataType_t;
//构造双向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
	DataType_t  		     data; //结点的数据域
	struct DoubleLinkedList	*prev; //直接前驱的指针域
	struct DoubleLinkedList	*next; //直接后继的指针域

}DoubleLList_t;

/* *********************************************************************************
 *
 *          
 *     @function name:	DoubleCirLList_Create
 *     @brief        :  创建一个空双向循环链表，空链表应该有一个头结点，对链表进行初始化
 *     @param        :  无
 *     @retval       :
 *              @head:  返回头节点
 *     @date         :  2024/04/25
 *     @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;
}

/* *********************************************************************************
 *
 *          
 *     @function name:	DoubleCirLList_NewNode
 *     @brief        :  创建新的结点，并对新结点进行初始化（数据域 + 指针域）
 *     @param        :  
 *                      @data:传将来的数据
 *     @retval       :
 *                      @New : 返回新数据的节点
 *     @date         : 2024/04/25
 *     @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->data = data;
	New->prev = New;
	New->next = New;

	return New;
}

/* *********************************************************************************
 *
 *          
 *     @function name:	DoubleCirHeadInsert
 *     @brief        :  将数据插入链表的头部
 *     @param        :  
 *                      @data:传将来的数据
 *                      @head:头节点
 *     @retval       :无
 *     @date         : 2024/04/25
 *     @version      ：1.0 
 *     @note         : 无
 * 
 *
 * *******************************************************************************/

void DoubleCirHeadInsert(DoubleLList_t *head,DataType_t data)
{
    DoubleLList_t *New = DoubleCirLList_NewNode(data);
    //如果插入的数据没有数据
    if (NULL == New)
    {
        printf("can not insert new node\n");
		return;
    }
    //如果为空链表
    if (head->next == head)
    {
        head->next = New;
        New->next  = New;
        New->prev  = New;
        return;
    }
    //如果不为空链表
    DoubleLList_t *tmp = head->next; //遍历尾节点并备份给tmp
    while (tmp->next != head->next)
    {
        tmp = tmp->next;
    }
    New->prev = tmp;
    New->next = head->next;
    tmp->next = New;
    head->next->prev = New;
    head->next = New;
    return;
}

/* *********************************************************************************
 *
 *          
 *     @function name:	DoubleCirTailInsert
 *     @brief        :  将数据插入链表的尾部
 *     @param        :  
 *                      @data:传将来的数据
 *                      @head:头节点
 *     @retval       :无
 *     @date         : 2024/04/25
 *     @version      ：1.0 
 *     @note         : 无
 * 
 *
 * *******************************************************************************/

void DoubleCirTailInsert(DoubleLList_t *head,DataType_t data)
{
    DoubleLList_t *New = DoubleCirLList_NewNode(data);
    //如果插入的数据是空的情况
    if (NULL == New)
    {
        printf("can not insert new node\n");
		return;
    }
    //如果为空链表
    if (head->next == head)
    {
        head->next = New;
        New->next  = New;
        New->prev  = New;
        return;
    }
    //如果不为空链表
    DoubleLList_t *tmp = head->next; //遍历尾节点并备份给tmp
    while (tmp->next != head->next)
    {
        tmp = tmp->next;
    }
    New->next = tmp->next;
    New->prev = tmp;
    tmp->next = New;
    head->next->prev = New;
    return;
}

/* *********************************************************************************
 *
 *          
 *     @function name:	DoubleCirDestvalInsert
 *     @brief        :  将数据插入链表指定数据后的位置
 *     @param        :  
 *                      @data   :传将来的数据
 *                      @destval:指定数据
 *                      @head   :头节点
 *     @retval       :无
 *     @date         : 2024/04/25
 *     @version      ：1.0 
 *     @note         : 该函数是将数据插入指定数据的直接后继节点
 * 
 *
 * *******************************************************************************/

void DoubleCirDestvalInsert(DoubleLList_t *head,DataType_t destval,DataType_t data)
{
    DoubleLList_t *New = DoubleCirLList_NewNode(data);
    //如果插入的数据是空的情况
    if (NULL == New)
    {
        printf("can not insert new node\n");
		return;
    }
    //如果为空链表
    if (head->next == head)
    {
        printf("链表为空！找不到指定数据!\n");
        return;
    }
    //如果不为空链表
    DoubleLList_t *tmp = head; //给头节点备份给tmp
    while (head->next->prev != tmp)//遍历尾节点并备份给tmp
    {
        tmp = tmp->next;
        //插入指定位置的后面
        if (tmp->data == destval)
        {
            New->next = tmp->next;
            New->prev = tmp;
            tmp->next->prev = New;
            tmp->next = New;
            return;
        }
    }
    //特殊情况，此时tmp遍历到尾节点，判断尾节点是否和指定位置的数据一样，一样插入，不一样则显示找不到该数据
    if (tmp->data == destval)
    {
        New->next = head->next;
        New->prev = tmp;
        head->prev = New;
        tmp->next = New; 
    }
    else
        printf("该链表中没有指定的数据！\n");
    return ;
}

/* *********************************************************************************
 *
 *          
 *     @function name:	DoubleCirHeadDel
 *     @brief        :  将数据从头部删除
 *     @param        :  
 *                      @head:头节点
 *     @retval       :无
 *     @date         : 2024/04/25
 *     @version      ：1.0 
 *     @note         : 当链表删除掉为最后一个元素时需要重新对头节点做初始化,所以链表删掉只剩一个元素时做特殊处理
 * 
 *
 * *******************************************************************************/

void DoubleCirHeadDel(DoubleLList_t *head)
{
    //如果为空链表
    if (head->next == head)
    {
        printf("The Link is empty! can not delete!");
        return;
    }
    //如果不为空链表
    DoubleLList_t *tmp = head->next; //备份首节点的位置方便后续找到首节点
    DoubleLList_t *phead = head;
    //当删除为最后一个节点时(特殊处理)
    if (tmp->next == head->next)
    {
        head->next = head;
        head->prev = head;
        tmp->next = NULL;
        tmp->next = NULL;
        free(tmp);
        return;
    }
    while (head->next->prev != phead)//遍历尾节点并备份给tmp
    {
        phead = phead->next;
    }
    phead->next = tmp->next;
    tmp->next->prev = phead;
    head->next = tmp->next;
    tmp->next = NULL;
    tmp->prev = NULL;
    free(tmp);
    return ;
}

/* *********************************************************************************
 *
 *          
 *     @function name:	DoubleCirTailDel
 *     @brief        :  将数据从尾部删除
 *     @param        :  
 *                      @head   :头节点
 *     @retval       :无
 *     @date         : 2024/04/25
 *     @version      ：1.0 
 *     @note         : 当链表删除掉为最后一个元素时需要重新对头节点做初始化,所以链表删掉只剩一个元素时做特殊处理
 * 
 *
 * *******************************************************************************/

void DoubleCirTailDel(DoubleLList_t *head)
{
    //如果为空链表
    if (head->next == head)
    {
        printf("The Link is empty! can not delete!");
        return;
    }
    //如果不为空链表
    DoubleLList_t *tmp = head->next; //备份首节点的位置方便后续找到首节点
    DoubleLList_t *phead = head;
    //当删除为最后一个节点时(特殊处理)
    if (tmp->next == head->next)
    {
        head->next = head;
        head->prev = head;
        tmp->next = NULL;
        tmp->next = NULL;
        free(tmp);
        return;
    }
    while (head->next->prev != phead)//遍历尾节点并备份给tmp
    {
        phead = phead->next;
    }
    phead->prev->next = tmp;
    tmp->prev = phead->prev;
    phead->next = NULL;
    phead->prev = NULL;
    free(phead);
    return ;
}

/* *********************************************************************************
 *
 *          
 *     @function name:	DoubleCirDestvalDel
 *     @brief        :  将数据从指定数据位置删除
 *     @param        :  
 *                      @head   :头节点
 *                      @destval:指定的数据
 *     @retval       :无
 *     @date         : 2024/04/25
 *     @version      ：1.0 
 *     @note         : 当链表删除掉为最后一个元素时需要重新对头节点做初始化,所以链表删掉只剩一个元素时做特殊处理
 *                    当链表遍历到最后一个元素还没找到目标值时,分两种情况,最后一个元素是目标值和最后一个元素不是目标值
 *                    如果最后一个元素是目标值,则进行特殊尾删操作,如果最后一个元素不是目标值,则输出:该链表中没有找到需要删除的数据!并结束函数
 *
 * *******************************************************************************/

void DoubleCirDestvalDel(DoubleLList_t *head,DataType_t destval)
{
    //如果为空链表
    if (head->next == head)
    {
        printf("The Link is empty! can not delete!");
        return;
    }
    //如果不为空链表
    DoubleLList_t *tmp = head->next; //备份首节点的位置方便后续找到首节点
    DoubleLList_t *phead = head->next;
    //当删除为最后一个节点时(特殊处理)
    if (tmp->next == head->next)
    {
        head->next = head;
        head->prev = head;
        tmp->next = NULL;
        tmp->next = NULL;
        free(tmp);
        return;
    }
    while (tmp->data != destval)//条件为判断首节点是否和指定数据相同，不相同进入循环遍历下一个
    {
        tmp = tmp->next;
        // 如果在尾节点
        if (tmp->next == phead)
        {
            if (tmp->data != destval)
            {
                printf("该链表中没有找到需要删除的数据!\n");
                return;
            }
            tmp->prev->next = phead;
            phead->prev = tmp->prev;
            tmp->next = NULL;
            tmp->prev = NULL;
            free(tmp);
            return;
        }
    }
    // 如果在头节点
    if (tmp->data == head->next->data)
    {
        while (phead->next != head->next) // 遍历尾节点并备份给phead
        {
            phead = phead->next;
        }
        phead->next = tmp->next;
        tmp->next->prev = phead;
        head->next = tmp->next;
        tmp->next = NULL;
        tmp->prev = NULL;
        free(tmp);
        return;
    }
    tmp->prev->next = tmp->next;
    tmp->next->prev = tmp->prev;
    tmp->next = NULL;
    tmp->prev = NULL;
    free(tmp);
    return;
}

/* *********************************************************************************
 *
 *          
 *     @function name:	DoubleCirLinkPrintf
 *     @brief        :  将数据从链表中打印出来
 *     @param        :  
 *                      @head   :头节点
 *     @retval       :
 *                      无
 *     @date         : 2024/04/25
 *     @version      ：1.0 
 *     @note         : 无
 * 
 *
 * *******************************************************************************/

void DoubleCirLinkPrintf(DoubleLList_t *head)
{
    //对单向循环链表的头结点的地址进行备份
	DoubleLList_t *Phead = head;
	
	//判断当前链表是否为空，为空则直接退出
	if (head->next == head)
	{
		printf("current linkeflist is empty!\n");
		return;
	}
    while (head->next->prev != Phead)
    {
        Phead = Phead->next;
        printf("data = %d\n",Phead->data);
    }
}

int main(int argc, char const *argv[])
{
	DoubleLList_t *head = DoubleCirLList_Create();
    //头插
    printf("头插法:\n");
    DoubleCirHeadInsert(head,1);
    DoubleCirHeadInsert(head,2);
    DoubleCirHeadInsert(head,3);
    DoubleCirHeadInsert(head,4);
    DoubleCirLinkPrintf(head);

    printf("\n");
    //尾插法
    printf("尾插法:\n");
    DoubleCirTailInsert(head,8);
    DoubleCirTailInsert(head,9);
    DoubleCirTailInsert(head,10);
    DoubleCirLinkPrintf(head);

    printf("\n");
    //指定插法
    printf("指定插法:\n");
    DoubleCirDestvalInsert(head,4,12);
    DoubleCirDestvalInsert(head,8,20);
    DoubleCirDestvalInsert(head,10,50);
    DoubleCirDestvalInsert(head,7,12);
    DoubleCirLinkPrintf(head);

    printf("\n");
    //头删法
    printf("头删法:\n");
    DoubleCirHeadDel(head);
    // DoubleCirHeadDel(head);
    // DoubleCirHeadDel(head);
    // DoubleCirHeadDel(head);
    // DoubleCirHeadDel(head);
    // DoubleCirHeadDel(head);
    // DoubleCirHeadDel(head);
    // DoubleCirHeadDel(head);
    // DoubleCirHeadDel(head);
    // DoubleCirHeadDel(head);
    DoubleCirLinkPrintf(head);

    printf("\n");
    //尾删法
    printf("尾删法:\n");
    DoubleCirTailDel(head);
    // DoubleCirTailDel(head);
    // DoubleCirTailDel(head);
    // DoubleCirTailDel(head);
    // DoubleCirTailDel(head);
    // DoubleCirTailDel(head);
    // DoubleCirTailDel(head);
    // DoubleCirTailDel(head);
    // DoubleCirTailDel(head);
    DoubleCirLinkPrintf(head);

    printf("\n");
    //指定删法
    printf("指定删法:\n");
    // DoubleCirDestvalDel(head,12);
    // DoubleCirDestvalDel(head,10);
    // DoubleCirDestvalDel(head,8);
    // DoubleCirDestvalDel(head,3);
    // DoubleCirDestvalDel(head,1);
    // DoubleCirDestvalDel(head,2);
    // DoubleCirDestvalDel(head,20);
    // DoubleCirDestvalDel(head,9);
    DoubleCirDestvalDel(head,10);
    DoubleCirLinkPrintf(head);

    return 0;
}

标签：tmp,head,遍历,接口,next,链表,New,prev
From： https://www.cnblogs.com/wwwwariana/p/18157714

相关文章

  • 单向循环链表的删除与插入
    单向循环链表单向循环链表是一种数据结构，它在单向链表的基础上进行了扩展。在单向链表中，最后一个节点的指针域为空，即指向NULL。而在单向循环链表中，最后一个节点的指针域不再指向NULL，而是指向链表的头节点，从而形成一个环状的链表结构。单向循环链表有两种主要类型：带头指针的单向......
  • 双链螺旋链表的头插中插尾插 头删中删尾删
    双链螺旋链表的头插中插尾插头删中删尾删#include<stdio.h>#include<stdbool.h>#include<stdlib.h>/**********************************************************************************函数名称：CircLList_NewNode*函数功能：创建一个新节点,实现头插......
  • JS之调用百度地图接口进行打卡
    调用百度地图接口进行打卡1.在百度地图开放平台申请AK2.在index.html导入百度地图SDK（此AK值为假）<scripttype="text/javascript"src="https://api.map.baidu.com/api?v=2.0&ak=f029hEOpyCQnXySQsug94D1yUU0Yil"></script>3.新增coordTransform.js//定义一些常量varx_PI......
  • 数据结构：双向循环链表的创建·插入·删除
    数据结构：双向循环链表的创建·插入·删除/***@filename:数据结构：双向循环链表的创建·插入·删除*@brief:实现双向循环链表的创建·插入·删除*@author :[email protected]*@date ：2024/04/24*@version：2.0*@note:none*CopyRig......
  • 双向循环链表的创建练习
    include<stdio.h>include<stdlib.h>/**@filename: Untitled-1.c@brief双向链表@[email protected]@date2024/04/[email protected]：版本@property：属性介绍@noteCopyRight(c)[email protected]*/typedefstru......
  • 顺序栈————遍历、出栈、入栈
    以数组作为基础实现栈空间（顺序栈）数组在内存中占用一块连续的空间，也就是数组元素的内存地址是连续的。为了实现栈，一般是把数组头作为栈底，数组头部到数组尾部作为栈的增长方向，也就是用户只在数组尾部对数据进行插入和删除。为了方便管理顺序栈所以需要构造管理顺序栈信息的结构体......
  • 数据结构——单向循环链表
    一、单向循环链表(一)单向循环链表的构造单向循环链表的尾结点的指针域中必须指向链表的首结点的地址1）构造单向循环链表的结点//单向循环链表中的结点有效数据类型，用户可以根据需要进行修改typedefintDataType_t;//构造单向循环链表的结点,链表中所有结点的数据类型应该......
  • 双向循环链表的增删改查
    数据结构双向循环链表双向循环链表的增删改查/***************************************************************************************filename:1.c*author: [email protected]*date:2024/04/24*function: 双向循环链表的增删......
  • C语言数据结构：双向循环链表的增删操作
    /***********************************************************************************************************设计双向循环链表的接口****Copyright(c)[email protected]**********************************************......
  • 双向循环链表的接口
    双向循环链表的接口头文件#include<stdbool.h>#include<stdio.h>#include<string.h>#include<stdlib.h>​```创建链表、节点//指的是双向循环链表中的结点有效数据类型，用户可以根据需要进行修改hjtypedefintDataType_t;//构造双向循环链表的结点,链表中所有结......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99