带头双向循环链表的基本操作（c语言实现）

 带头双向循环链表

带头双向循环链表是一种结合了双向链表和循环链表特性的数据结构。其主要特点如下：

  1. 双向性：链表中的每个节点都有两个指针，一个指向下一个节点（next），另一个指向前一个节点（prev）。这种双向性使得链表中的任何节点都可以方便地访问其前驱节点和后继节点，从而支持向前和向后的遍历操作。

  2. 循环性：在带头双向循环链表中，最后一个节点的next指针指向链表的第一个节点，而第一个节点的prev指针指向最后一个节点，形成一个闭环。这种循环结构使得链表没有明确的开始和结束，可以从任何节点开始遍历整个链表。

  3. 简化操作：由于链表的循环性，无论是从头部还是尾部开始遍历，都可以无缝地连接到链表的另一端。这简化了在链表两端进行插入和删除节点的操作。例如，在链表头部插入一个新节点时，只需将新节点的prev指针指向最后一个节点，next指针指向原链表的第一个节点，并更新最后一个节点和原第一个节点的指针即可。

  4. 内存使用：带头双向循环链表相对于普通链表需要额外的空间来存储指针，但这也带来了操作的便利性和灵活性。在实际应用中，根据具体需求权衡空间复杂度和时间复杂度是很重要的。

  5. 适用场景：带头双向循环链表适用于需要频繁在链表头部和尾部进行插入和删除操作的场景，如实现循环队列、循环双向链表等数据结构。其循环性和双向性使得这些操作变得简单和高效。

需要注意的是，虽然带头双向循环链表具有许多优点，但它并不适用于所有场景。在选择数据结构时，需要根据具体的应用需求和性能要求进行权衡。

定义结点 

// 定义一个新的数据类型LTDataType，它实际上就是int类型的一个别名。  
typedef int LTDataType;  
  
// 定义一个名为ListNode的结构体，用于表示双向链表的一个节点。  
typedef struct ListNode  
{  
    // 指向下一个节点的指针  
    struct ListNode* next;  
      
    // 指向前一个节点的指针  
    struct ListNode* prev;  
      
    // 存储数据的成员，其类型为之前定义的LTDataType，即int类型  
    LTDataType data;  
  
} LTNode;

 链表的基本操作

LTNode* BuyListNode(LTDataType x);

//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTDestroy(LTNode* phead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);

void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);

void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);

// posλ֮ǰһֵ
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);

创建新结点

// 定义一个函数BuyListNode，它接受一个LTDataType类型的参数x，返回一个LTNode类型的指针。  
LTNode* BuyListNode(LTDataType x)  
{  
    // 使用malloc为LTNode结构体分配内存空间，并将返回的void*指针强制转换为LTNode*类型。  
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));  
  
    // 检查malloc是否成功分配了内存。  
    if (node == NULL)  
    {  
        // 如果内存分配失败，使用perror函数输出错误信息。  
        perror("malloc fail");  
  
        // 直接退出程序，因为内存分配失败通常意味着严重的问题。  
        // 注意：通常这里应该返回NULL，让调用者处理错误，但这里选择了直接退出。  
        exit(-1);  
    }  
  
    // 初始化新节点的next和prev指针为NULL，表示这是链表中的一个孤立节点。  
    node->next = NULL;  
    node->prev = NULL;  
  
    // 将参数x赋值给新节点的data成员。  
    node->data = x;  
  
    // 返回新创建的节点指针。  
    return node;  
}

初始化双向链表

// 定义一个函数LTInit，它没有参数，返回一个LTNode类型的指针。  
LTNode* LTInit()  
{  
    // 调用BuyListNode函数，创建一个新的LTNode节点，并用-1初始化其data成员。  
    LTNode* phead = BuyListNode(-1);  
  
    // 将新节点的next指针指向其自身，表示这是一个循环链表。  
    phead->next = phead;  
  
    // 将新节点的prev指针也指向其自身，这是双向循环链表的特点。  
    phead->prev = phead;  
  
    // 返回头节点的指针。  
    return phead;  
}

销毁链表

void LTDestroy(LTNode* phead)  
{  
    LTNode* current = phead;  
    LTNode* next;  
  
    // 遍历链表，释放每个节点的内存  
    do {  
        next = current->next; // 保存下一个节点的指针  
        free(current);         // 释放当前节点的内存  
        current = next;        // 移动到下一个节点  
    } while (current != phead); // 遍历直到回到头节点  
  
    // 此时current指向头节点，但头节点已经在循环中被释放了  
    // 因此不需要再次释放phead  
}

打印双向链表

void LTPrint(LTNode* phead)
{
	assert(phead);

	printf("<=head=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

链表判空

#include <assert.h> // 引入assert.h头文件以使用assert宏  
#include <stdbool.h> // 引入stdbool.h头文件以使用bool类型  
  
bool LTEmpty(LTNode* phead)  
{  
    // 使用assert宏来确保phead不为NULL，如果为NULL则终止程序  
    assert(phead != NULL);  
  
    // 判断链表是否为空，即头节点的next是否指向自身  
    // 如果是，说明链表为空（只有头节点），返回true  
    // 否则，返回false 
//也就是下面这个代码
/*if (phead->next == phead)
	{
		return true;
	}
	else
	{
		return false;
	}*/ 
//为了简化，改为下面这个
    return phead->next == phead;  


}

插入结点

void LTInsert(LTNode* pos, LTDataType x)  
{  
    assert(pos); // 确保pos不为NULL  
  
    LTNode* prev = pos->prev; // 获取pos节点的前一个节点  
    LTNode* newnode = BuyListNode(x); // 创建一个新的节点，并用x初始化其data成员  
  
    // 将newnode插入到prev和pos之间  
    prev->next = newnode; // prev的下一个节点指向newnode  
    newnode->prev = prev; // newnode的前一个节点指向prev  
    
    newnode->next = pos;  // newnode的下一个节点指向pos  
    pos->prev = newnode;  // pos的前一个节点指向newnode  
}

后插 

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	//LTNode* newnode = BuyListNode(x);
	//LTNode* tail = phead->prev;

	 phead            tail  newnode
	//tail->next = newnode;
	//newnode->prev = tail;
	//newnode->next = phead;
	//phead->prev = newnode;

	LTInsert(phead, x);
}

尾删

void LTPopBack(LTNode* phead)  
{  
    assert(phead); // 确保phead不为NULL  
    assert(!LTEmpty(phead)); // 确保链表不为空  
  
    LTNode* tail = phead->prev; // 获取链表的尾节点  
    LTNode* tailPrev = tail->prev; // 获取尾节点的前一个节点  
  
    // 更新tailPrev的next指针，使其指向头节点  
    tailPrev->next = phead;  
    // 更新头节点的prev指针，使其指向tailPrev  
    phead->prev = tailPrev;  
    // 释放尾节点占用的内存  
    free(tail);  
    // 将tail指针置为NULL，避免悬挂指针  
    tail = NULL;  
}

头插

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	//LTNode* newnode = BuyListNode(x);
	//LTNode* first = phead->next;
	//phead->next = newnode;
	//newnode->prev = phead;

	//newnode->next = first;
	//first->prev = newnode;

	// 㻻˳
	//newnode->next = phead->next;
	//phead->next->prev = newnode;

	//phead->next = newnode;
	//newnode->prev = phead;

	LTInsert(phead->next, x);
}

头删

void LTPopFront(LTNode* phead)  
{  
    assert(phead); // 确保phead不为NULL  
    assert(!LTEmpty(phead)); // 确保链表不为空  
  
    LTNode* first = phead->next; // 获取链表的头节点（非哨兵节点）  
    LTNode* second = first->next; // 获取头节点的下一个节点  
  
    // 更新头节点的next指针，使其指向second  
    phead->next = second;  
    // 更新second的prev指针，使其指向头节点  
    second->prev = phead;  
  
    // 释放头节点占用的内存  
    free(first);  
      
    // 特别注意：如果链表中只有一个节点（包括头节点自身），则second此时就是头节点  
    // 在这种情况下，我们需要将头节点的prev和next指针都指向自身，以维持循环结构  
    if (second == phead) {  
        phead->prev = phead;  
        phead->next = phead;  
    }  
}

完整代码

typedef int LTDataType;  
typedef struct ListNode  
{  
  
    struct ListNode* next;  

    struct ListNode* prev;  
    LTDataType data;  
  
} LTNode;

LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		//return NULL;
		exit(-1);
	}
	node->next = NULL;
	node->prev = NULL;
	node->data = x;

	return node;
}

LTNode* LTInit()
{
	LTNode* phead = BuyListNode(-1);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

void LTDestroy(LTNode* phead);

void LTPrint(LTNode* phead)
{
	assert(phead);

	printf("<=head=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

bool LTEmpty(LTNode* phead)
{
	assert(phead);

	/*if (phead->next == phead)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return phead->next == phead;
}


void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	//LTNode* newnode = BuyListNode(x);
	//LTNode* tail = phead->prev;

	 phead            tail  newnode
	//tail->next = newnode;
	//newnode->prev = tail;
	//newnode->next = phead;
	//phead->prev = newnode;

	LTInsert(phead, x);
}

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;

	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
	tail = NULL;
}

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	//LTNode* newnode = BuyListNode(x);
	//LTNode* first = phead->next;
	//phead->next = newnode;
	//newnode->prev = phead;

	//newnode->next = first;
	//first->prev = newnode;

	// 㻻˳
	//newnode->next = phead->next;
	//phead->next->prev = newnode;

	//phead->next = newnode;
	//newnode->prev = phead;

	LTInsert(phead->next, x);
}

void LTPopFront(LTNode* phead)  
{  
    assert(phead); // 确保phead不为NULL  
    assert(!LTEmpty(phead)); // 确保链表不为空  
  
    LTNode* first = phead->next; // 获取链表的头节点（非哨兵节点）  
    LTNode* second = first->next; // 获取头节点的下一个节点  
  
    // 更新头节点的next指针，使其指向second  
    phead->next = second;  
    // 更新second的prev指针，使其指向头节点  
    second->prev = phead;  
  
    // 释放头节点占用的内存  
    free(first);  
      
    // 特别注意：如果链表中只有一个节点（包括头节点自身），则second此时就是头节点  
    // 在这种情况下，我们需要将头节点的prev和next指针都指向自身，以维持循环结构  
    if (second == phead) {  
        phead->prev = phead;  
        phead->next = phead;  
    }  
}

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);
	// prev newnode pos

	prev->next = newnode;
	newnode->prev = prev;

	newnode->next = pos;
	pos->prev = newnode;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/571252.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

11.泛型

11.泛型

文章目录 1 泛型概念2. 自定义泛型结构3 泛型方法4 泛型在继承上的体现5 通配符的使用 1 泛型概念 所谓泛型就是用标识符标识不确定的类型&#xff0c;详细说就是&#xff1a;定义类或接口时用标识符表示类中某个属性的类型或者是某个方法的返回值及参数类型。泛型将在使用时&a…
阅读更多...
《QT实用小工具·三十九》仿 Windows10 画图3D 的颜色选择器, 但更加强大

《QT实用小工具·三十九》仿 Windows10 画图3D 的颜色选择器, 但更加强大

1、概述 源码放在文章末尾 该项目实现了仿 Windows10 画图3D 的颜色选择器&#xff0c;功能更加丰富更加强大。 项目部分代码如下所示&#xff1a; import QtQuick 2.15 import QtQuick.Controls 2.15 import QtQuick.Layouts 1.15 import QtGraphicalEffects 1.15Item {id…
阅读更多...
基于OSAL 实现UART、LED、ADC等基础示例 4

基于OSAL 实现UART、LED、ADC等基础示例 4

1 UART 实验目的 串口在我们开发单片机项目是很重要的&#xff0c;可以观察我们的代码运行情况&#xff0c;本节的目的就 是实现串口双工收发。 虽然说 osal 相关的代码已经跟硬件关系不大了&#xff0c;但是我们还是来贴出相关的硬件原理图贴出来。 1.1 初始化 osal_init_s…
阅读更多...
Leetcode743. 网络延迟时间

Leetcode743. 网络延迟时间

Every day a Leetcode 题目来源&#xff1a;743. 网络延迟时间 本题需要用到单源最短路径算法 Dijkstra&#xff0c;现在让我们回顾该算法&#xff0c;其主要思想是贪心。 将所有节点分成两类&#xff1a;已确定从起点到当前点的最短路长度的节点&#xff0c;以及未确定从起…
阅读更多...
分类分析|KNN分类模型及其Python实现

分类分析|KNN分类模型及其Python实现

KNN分类模型及其Python实现 1. KNN算法思想2. KNN算法步骤2.1 KNN主要优点2.2 KNN主要缺点 3. Python实现KNN分类算法3.1 自定义方法实现KNN分类3.2 调用scikit-learn模块实现KNN分类 4. K值的确定 在之前文章 分类分析|贝叶斯分类器及其Python实现中&#xff0c;我们对分类分…
阅读更多...
DHCP的原理与配置

DHCP的原理与配置

一.了解DHCP服务 1. DHCP (Dynamic Host Configuration Protocol)动态主机配置协议 是由Internet工作小组设计开发的&#xff0c;专门用于为TCP/IP网络中的计算机自动分配TCP/IP参数的协议 DHCP协议采用的是UDP作为传输协议&#xff0c;是给网络内的客户机自动分配IP地址&…
阅读更多...
Redis入门到通关之Redis实现Session共享

Redis入门到通关之Redis实现Session共享

文章目录 ☃️前期概要☃️基于Session实现登录方案☃️现有方案存在的问题☃️Redis代替Session的业务流程❄️❄️设计key的结构❄️❄️设计key的具体细节❄️❄️整体访问流程 欢迎来到 请回答1024 的博客 &#x1f353;&#x1f353;&#x1f353;欢迎来到 请回答1024的博…
阅读更多...
羊大师分析，羊奶和牛奶哪个更适合夏天喝？

羊大师分析，羊奶和牛奶哪个更适合夏天喝？

羊大师分析&#xff0c;羊奶和牛奶哪个更适合夏天喝&#xff1f; 羊奶和牛奶都是营养丰富的饮品&#xff0c;适合不同人群在不同季节饮用。在夏天&#xff0c;选择羊奶还是牛奶主要取决于个人的体质、口味偏好以及需求。 羊奶的营养价值较高&#xff0c;含有丰富的蛋白质、矿物…
阅读更多...
ESP8266+STM32+阿里云保姆级教程（AT指令+MQTT）

ESP8266+STM32+阿里云保姆级教程（AT指令+MQTT）

前言&#xff1a;在开发过程中&#xff0c;几乎踩便了所有大坑小坑总结出的文章&#xff0c;我是把坑踩满了&#xff0c;帮助更过小白快速上手&#xff0c;如有错误之处&#xff0c;还麻烦各位大佬帮忙指正、 目录 一、ESP-01s介绍 1、ESP-01s管脚功能&#xff1a; 模组启动模…
阅读更多...
元数据管理和数据目录对于现代数据平台的重要性——Lakehouse架构（四）

元数据管理和数据目录对于现代数据平台的重要性——Lakehouse架构（四）

文章目录 前言解读元数据技术元数据业务元数据 元存储和数据目录如何协同工作&#xff1f;数据目录的特点查询、检索和发现数据数据分类数据治理数据血缘 前言 Lakehouse 架构中的存储层负责存储整个平台的数据&#xff0c;要查询存储的这些数据&#xff0c;我们需要一个数据目…
阅读更多...
xgp怎么取消续费 微软商店xgp会员取消自动续费详细教程

xgp怎么取消续费 微软商店xgp会员取消自动续费详细教程

xgp怎么取消续费 微软商店xgp会员取消自动续费详细教程 XGP这个游戏平台小伙伴们并不陌生吧&#xff0c;它是微软Xbox游戏部门推出的游戏租赁制会员服务&#xff0c;主要用于主机和PC两个平台。这个平台的会员就可以免费享受多款大制作游戏&#xff0c;而且每个月还会自动更新…
阅读更多...
ruoyi-nbcio-plus基于vue3的flowable收回任务后重新进行提交表单的处理

ruoyi-nbcio-plus基于vue3的flowable收回任务后重新进行提交表单的处理

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 http://122.227.135.243:9666/ 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a…
阅读更多...
JAVA毕业设计137—基于Java+Springboot+Vue的物流快递仓库管理系统(源代码+数据库)

JAVA毕业设计137—基于Java+Springboot+Vue的物流快递仓库管理系统(源代码+数据库)

毕设所有选题&#xff1a; https://blog.csdn.net/2303_76227485/article/details/131104075 基于JavaSpringbootVue的物流快递仓库管理系统(源代码数据库)137 一、系统介绍 本项目前后端分离&#xff0c;分为员工、销售员、仓库员、商品管理员、超级管理员五种角色 1、员工…
阅读更多...
Linux 的情况下实现贪吃蛇 -- 第二十八天

Linux 的情况下实现贪吃蛇 -- 第二十八天

1. 打印地图 keypad(stdsrc,1) 参数表示是否接收&#xff0c;1表示接收指令 2.思路&#xff1a;初始化initNcurses()&#xff0c; 封装地图函数实现地图gamePic&#xff08;&#xff09; 分三部分实现&#xff1a;2.1: 在第0行&#xff1a;打印 "--",&quo…
阅读更多...
矩阵连乘算法

矩阵连乘算法

矩阵连乘&#xff1a; #include<iostream> #define inf 0x7fffffff using namespace std; int a[256] { 0 };//存储矩阵的行和列 int m[256][256] { 0 };//存储i到j的最少计算次数 int s[256][256] { 0 };//存储i到j的中转站k void m_print(int i, int j) {if (i …
阅读更多...
javaWeb项目-房屋房租租赁系统功能介绍

javaWeb项目-房屋房租租赁系统功能介绍

项目关键技术 开发工具&#xff1a;IDEA 、Eclipse 编程语言: Java 数据库: MySQL5.7 框架&#xff1a;ssm、Springboot 前端&#xff1a;Vue、ElementUI 关键技术&#xff1a;springboot、SSM、vue、MYSQL、MAVEN 数据库工具&#xff1a;Navicat、SQLyog 1、JSP技术 JSP(Jav…
阅读更多...
数据结构-二叉树-链式

数据结构-二叉树-链式

一、链式二叉树的结构 typedef int BTNodeDataType; typedef struct BTNode {BTNodeDataType data;struct BTNode* left;struct BTNode* right; }BTNode; 二叉树的前中后序遍历 前序&#xff1a;根左右 中序&#xff1a;左根右 后序&#xff1a;左右根 void PreOrder(BTNo…
阅读更多...
栈 、队列

栈 、队列

1.stack的介绍和使用 1.1stack的介绍 stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff0c;其删除只能从容器的一端进行元素的插入与提取操作。 1.2 stack的使用 函数说明 接口说明 stack() 构造空的栈 empty() 检测stack是否为空 size…
阅读更多...
Opencv | 边缘检测 轮廓信息

Opencv | 边缘检测 轮廓信息

目录 一. 边缘检测1. 边缘的定义2. Sobel算子 边缘提取3. Scharr算子 边缘提取4. Laplacian算子 边缘提取5. Canny 边缘检测算法5.1 计算梯度的强度及方向5.2 非极大值抑制5.3 双阈值检测5.4 抑制孤立弱边缘 二. 轮廓信息1. 获取轮廓信息2. 画轮廓 一. 边缘检测 1. 边缘的定义…
阅读更多...
【QT】Ubuntu22.04 配置 QT6.5 LTS

【QT】Ubuntu22.04 配置 QT6.5 LTS

【QT】Ubuntu22.04 配置 QT6.5 LTS 文章目录 【QT】Ubuntu22.04 配置 QT6.5 LTS1.注册QT Group的账号2.安装QT Creator3.启动QT Creator报错from 6.5.0, xcb-cursor0 or libxcb-cursor0 is needed to load the Qt xcb platform plugin.4.运行QT的demoReference 1.注册QT Group的…
阅读更多...
最新文章

Copyright @ 2022~2023