C语言:双链表

2024-06-10 00:20
文章标签 语言 双链

本文主要是介绍C语言:双链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、什么是双链表?

双链表,顾名思义,是一种每个节点都包含两个链接的链表:一个指向下一个节点,另一个指向前一个节点。这种结构使得双链表在遍历、插入和删除操作上都表现出色。与单链表相比,双链表不仅可以从头节点开始遍历,还可以从尾节点开始遍历,甚至从中间某个节点开始双向遍历。

二、双链表的特点

双向性:每个节点都包含两个指针,一个指向前一个节点,一个指向后一个节点。这使得双链表在遍历上更加灵活。
动态性:链表的大小可以根据需要动态地增加或减少,无需预先分配固定大小的内存空间。
三、实现双链表

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;

三、实现的功能

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);//指定删除
LTNode* LTFind(LTNode* phead, LTDataType x);//查找

 1.创建节点

// 创建新的双链表节点  
LTNode* LTBuyNode(LTDataType x) {  LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));  if (newNode == NULL) {  perror("malloc fail!");  exit(1);  }  newNode->data = x;  newNode->next = NULL;  newNode->prev = NULL;  return newNode;  
}  

使用malloc函数在堆上动态地分配内存空间,以存储LTNode结构体的大小。
检查malloc是否成功分配了内存。如果返回NULL,表示内存分配失败,此时调用perror函数打印错误消息,并使用exit(1)退出程序。
如果内存分配成功,将新节点的数据成员data设置为参数x的值。
初始化新节点的next和prev指针为NULL,表示这个新节点在创建时并不指向任何其他的节点。
返回指向新创建节点的指针。

2.初始化

LTNode* LTInit() {  LTNode* pheda = LTBuyNode(-1); // 使用-1作为哨兵位头节点的数据  pheda->next = pheda; // 指向自己,表示链表为空  pheda->prev = pheda;  return pheda;  
}

 3.双链表的尾插

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);// 创建一个新节点newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;}

newnode->prev = phead->prev; 将新节点的prev指针设置为当前链表的尾节点。
newnode->next = phead; 将新节点的next指针设置为头节点。

phead->prev->next = newnode; 更新当前尾节点的next指针,使其指向新节点。
phead->prev = newnode; 更新头节点的prev指针,使其指向新节点

4.双链表的尾删

//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

prev指针指向链表的最后一个节点

del->prev->next = phead; 和 phead->prev = del->prev; 这两行代码更新了链表的链接,将尾节点从链表中移除。

 5.双链表的头插

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode ->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

newnode ->next = phead->next;将新节点的next指针指向当前链表的第一个节点

newnode->prev = phead;将新节点的prev指针指向链表的头节点

phead->next->prev = newnode;更新当前链表第一个节点的prev指针,使其指向新节点。

phead->next = newnode;:更新链表的头节点的next指针,使其指向新节点,这样新节点就成为了链表的第一个节点。

6.双链表的头删

void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;phead->next->prev = phead;free(del);del = NULL;}

 LTNode* del = phead->next;:将待删除的节点的地址赋给del指针。
phead->next = del->next;:更新链表的头节点的next指针,使其跳过待删除的节点,直接指向下一个节点。
phead->next->prev = phead;:由于我们刚刚更新了phead->next,现在它指向的是原第一个节点的下一个节点。我们将这个新节点的prev指针更新为指向链表的头节点。

7.双链表的打印 

void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d ", pcur->data);pcur = pcur->next;}printf("\n");
}

8.在pos位置之后插入数据

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);	newnode-> next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

9.指定删除     

void LTErase(LTNode* pos)
{assert(pos);assert(pos != pos->next);pos->prev->next = pos->next;// 更新pos的前一个节点的next指针pos->next->prev = pos->prev;//更新pos的下一个节点的prev指针free(pos);pos = NULL;
}

 10.判空

bool LTEmpty(LTNode* phead)
{return phead->next == phead;
}

 11.销毁

//销毁
void LTDestroy(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead){LTNode* tmp = cur;cur = cur->next;free(tmp);}free(phead);
}

四、全部源码

LTNode* LTBuyNode(LTDataType x)
{LTNode* Node = (LTNode*)malloc(sizeof(LTNode));if (Node == NULL){perror("malloc fail!");exit(1);}Node->data = x;Node->next = NULL;  Node->prev = NULL;   return Node;
}
LTNode* LTInit() {LTNode* pheda = LTBuyNode(-1); // 使用-1作为哨兵头节点的数据  pheda->next = pheda; // 指向自己,表示链表为空  pheda->prev = pheda;  return pheda;
}//销毁
void LTDestroy(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead){LTNode* tmp = cur;cur = cur->next;free(tmp);}free(phead);
}
//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d ", pcur->data);pcur = pcur->next;}printf("\n");
}
//判断链表是否为空·
bool LTEmpty(LTNode* phead)
{return phead->next == phead;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode ->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;phead->next->prev = phead;free(del);del = NULL;}
//查找LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur=cur->next;}return NULL;
}在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);	newnode-> next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//指定删除
void LTErase(LTNode* pos)
{assert(pos);assert(pos != pos->next);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

五、结语 

让我们一起在编程的道路上不断前行,创造更加美好的未来!

这篇关于C语言:双链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1046718

相关文章

Go语言编译环境设置教程

《Go语言编译环境设置教程》Go语言支持高并发(goroutine)、自动垃圾回收,编译为跨平台二进制文件,云原生兼容且社区活跃,开发便捷,内置测试与vet工具辅助检测错误,依赖模块化管理,提升开发效... 目录Go语言优势下载 Go  配置编译环境配置 GOPROXYIDE 设置(VS Code)一些基本

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例:泄漏缓冲区的产生项目场景:Web 服务器中的请求缓冲场景描述代码

Go语言如何判断两张图片的相似度

《Go语言如何判断两张图片的相似度》这篇文章主要为大家详细介绍了Go语言如何中实现判断两张图片的相似度的两种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 在介绍技术细节前,我们先来看看图片对比在哪些场景下可以用得到:图片去重:自动删除重复图片,为存储空间"瘦身"。想象你是一个

Go语言中Recover机制的使用

《Go语言中Recover机制的使用》Go语言的recover机制通过defer函数捕获panic,实现异常恢复与程序稳定性,具有一定的参考价值,感兴趣的可以了解一下... 目录引言Recover 的基本概念基本代码示例简单的 Recover 示例嵌套函数中的 Recover项目场景中的应用Web 服务器中

Go语言中使用JWT进行身份验证的几种方式

《Go语言中使用JWT进行身份验证的几种方式》本文主要介绍了Go语言中使用JWT进行身份验证的几种方式,包括dgrijalva/jwt-go、golang-jwt/jwt、lestrrat-go/jw... 目录简介1. github.com/dgrijalva/jwt-go安装:使用示例:解释:2. gi