数据结构之双向链表

server/2025/1/13 9:53:06/

目录

双向链表的基本概念和结构

初始化

尾插

头插

尾删

头删

查找

在指定位置之后插入

删除指定位置节点

判空

销毁 

完整代码

测试代码

双向链表的基本概念和结构

双向链表（Doubly Linked List）‌是一种链式存储结构，每个节点除了存储数据外，还包含两个指针，分别指向前一个节点（prev）和后一个节点（next）。这种结构使得双向链表可以从头到尾遍历，也可以从尾到头遍历，非常灵活‌。

双向链表的每个节点包含以下部分：

  • ‌数据元素‌：可以是任何类型的数据，如整数、浮点数、字符串或对象。
  • ‌prev指针‌：指向前一个节点的指针。
  • ‌next指针‌：指向下一个节点的指针。

双向链表通常包含一个头节点（哨兵位节点），这个节点不存储有效数据，只有指向第一个有效节点的next指针和指向尾节点的prev指针。只要链表存在，哨兵位节点就存在‌。

‌优点‌：

  • ‌双向遍历‌：可以从两个方向遍历链表，既可以从头到尾，也可以从尾到头。
  • ‌插入和删除操作高效‌：在已知前后节点的情况下，插入或删除操作可以直接进行，不需要遍历整个链表。
  • ‌动态内存分配‌：链表可以在运行时动态地分配和释放内存，适合需要频繁增删操作的场景。

初始化

LTNode* ByNode(LTDatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("申请失败!\n");exit(1);}//自成循环newnode->val = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}void LTInit(LTNode **phead)
{//创建一个哨兵卫节点//*phead指向哨兵卫*phead = ByNode(-1);
}

初始化的目的就是创建一个哨兵卫节点，传参为二级指针是因为初始化时要对哨兵卫进行改变，改变一个指针就要传这个指针的地址，传指针的地址就要用二级指针来接收。

让每一个新增节点都先自成循环，这样方便与链表连接起来。

尾插

void LTPushBack(LTNode* phead, LTDatatype x)
{//不对哨兵卫进行改变，所以传一级指针assert(phead); //哨兵卫不能为空LTNode* newnode = ByNode(x);newnode->prev = phead->next;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

 

 与尾插相关的只有哨兵卫的prev指针指向的数据和哨兵卫。哨兵卫的prev指针指向的是链表中的最后一个数据，不管该数据是否是哨兵卫都没有关系。先让newnode的prev指针指向最后一个数据，next指针指向哨兵卫，再让最后一个数据的next指针指向newnode。

头插

void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = ByNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

 头插是往第一个有效数据前面插入，而不是在哨兵卫前面插入。先让newnode的next指针指向最后一个数据，newnode的prev指针指向哨兵卫，再让第一个有效数据的prev指针指向newnode，哨兵卫的next指针指向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;
}

 

尾删的前提是你要有有效的数据，那么哨兵卫节点的next指针就不能指向哨兵卫自己。首先要记录最后的一个数据存储在del变量里，先让del的前一个数据的next指针指向哨兵卫，哨兵卫的prev指针指向del的前一个数据。然后释放del空间，将del置为空。

头删

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

 首先要记录第一个有效数据存储在del变量里，先让del的下一个数据的prev指针指向哨兵卫，哨兵卫的next指针指向del的下一个数据。然后释放del空间，将del置为空。

查找

LTNode* LTFind(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->val == x)return pcur;pcur = pcur->next;}return NULL;
}

 直接从链表的第一个有效数据开始遍历，结束条件是遍历到哨兵卫就结束，如果节点的值是你要查询的值，就返回这个节点。如果链表中没有你要查找的数据，就返回空。

在指定位置之后插入

void LTInsertBack(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = ByNode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

这个接口的原理是根据查找函数返回的节点进行插入。如果你指定在d2的后面插入数据，你就要先查找d2在哪里，返回这个节点。newnode的next指针指向pos的next指针指向的节点，newnode的prev指针指向pos节点，pos的next指针指向的节点的prev指针指向newnode，pos的next指针指向newnode。

删除指定位置节点

void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

 这个接口的原理是根据查找函数返回的节点进行删除。让pos节点的next指向的节点和prev指向的节点连接起来，然后释放pos节点，将pos节点置为空。

判空

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

判断该链表是否有有效数据，直接查看哨兵卫指向第一个有效节点的next指针是否指向哨兵卫，如果是，则说明该链表中只有一个哨兵卫，没有有效数据，就说该链表为空链表。

销毁 

void LTDestory(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

 链表的销毁要先从第一个有效数据开始删，最后释放掉哨兵卫节点。先定义一个指针pcur指向哨兵卫节点的next指针指向的节点，然后开始遍历链表进行删除。

完整代码

#define _CRT_SECURE_NO_WARNINGS#include "list.h"//申请节点
LTNode* ByNode(LTDatatype x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("申请失败!\n");exit(1);}//自成循环newnode->val = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}void LTInit(LTNode **phead)
{//创建一个哨兵卫节点//*phead指向哨兵卫*phead = ByNode(-1);
}void LTDestory(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur->next != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->val);pcur = pcur->next;}printf("\n");
}//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{//不对哨兵卫进行改变，所以传一级指针assert(phead); //哨兵卫不能为空LTNode* newnode = ByNode(x);newnode->prev = phead->next;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = ByNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = 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 LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->val == x)return pcur;pcur = pcur->next;}return NULL;
}//在指定位置之后插入
void LTInsertBack(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = ByNode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}//在指定位置之前插入
void LTInitFront(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = ByNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;
}//删除pos节点
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}//判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

测试代码

#define _CRT_SECURE_NO_WARNINGS#include "list.h"void test()
{LTNode *plist = NULL;LTInit(&plist);  //创建了一个哨兵卫头插//LTPushBack(plist, 1);//LTPrint(plist);//LTPushBack(plist, 2);//LTPrint(plist);//LTPushBack(plist, 3);//LTPrint(plist);//尾插LTPushFront(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPushFront(plist, 3);LTPrint(plist);尾删//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);头删//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//查找LTNode* find = LTFind(plist, 2);//if (find)//	printf("找到了\n");//else//	printf("没有找到\n");//在指定位置之后插入//LTInsertBack(find, 66);//LTPrint(plist);//LTInsertBack(find, 88);//LTPrint(plist);在指定位置之前插入//LTInitFront(find, 66);//LTPrint(plist);//LTInitFront(find, 88);//LTPrint(plist);删除pos节点//LTErase(find);//LTPrint(plist);//判空//if (LTEmpty(plist))//	printf("为空\n");//else//	printf("不为空\n");LTDestory(plist);
}int main()
{test();return 0;
}


http://www.ppmy.cn/server/157983.html

相关文章

spark functions函数合集（无示例）

spark functions函数合集（无示例）

ctrlF进行页面查找 没有示例，仅用于查询，具体用法自行搜索 函数名称作用avg计算指定列的平均值count计算指定列或所有行的数量countDistinct计算指定列中不同值的数量corr计算两个列之间的相关系数covar_pop计算两个列之间的总体协方差covar_samp计算两…
阅读更多...
08cms房产系统开源源码与链家房产系统小程序源码两套的安装教程步骤大同小异

08cms房产系统开源源码与链家房产系统小程序源码两套的安装教程步骤大同小异

简介： 08cms系统源码目前没有任何域名限制，一个实实在在的房产门户系统功能比较强悍，包括新房二手房等所有房产门户的特征功能都具备，自带全景看房，仿链家功能带小程序app工程源码， 2.TP房产系统源码也是一…
阅读更多...
pdf提取文本，表格以及转图片：spire.pdf

pdf提取文本，表格以及转图片：spire.pdf

文章目录 🐒个人主页：信计2102罗铠威🏅JavaEE系列专栏📖前言：🎀 1. pdfbox1.1导入pdfbox 的maven依赖1.1 提取文本1.2 提取文本表格（可自行加入逻辑处理）1.3 pdf转换成图片代码&…
阅读更多...
检验统计量与p值笔记

检验统计量与p值笔记

一、背景 以雨量数据为例，当获得一个站点一年的日雨量数据后，我们需要估计该站点的雨量的概率分布情况，因此我们利用有参估计的方式如极大似然法估计得到了假定该随机变量服从某一分布的参数，从而得到该站点的概率密度函数&#x…
阅读更多...
【网络】计算机网络的分类 局域网 (LAN) 广域网 (WAN) 城域网 (MAN)个域网(PAN)

【网络】计算机网络的分类 局域网 (LAN) 广域网 (WAN) 城域网 (MAN)个域网(PAN)

局域网是通过路由器接入广域网的 分布范围 局域网Local Area Network：小范围覆盖，速度高，延迟低(办公室，家庭，校园，网络) 广域网Wide Area Network 大范围覆盖，速度相对低，延迟高…
阅读更多...
【会话详解】

【会话详解】

会话详解 概述 会话： 用户通过浏览器访问多个Web资源的过程，从打开浏览器开始访问特定网站，直到关闭浏览器的过程称为会话（Session）。会话管理是Web应用中跟踪和存储用户状态的重要机制。 有状态会话： …
阅读更多...
使用conda出现requests.exceptions.HTTPError 解决方案

使用conda出现requests.exceptions.HTTPError 解决方案

大家好，我是爱编程的喵喵。双985硕士毕业，现担任全栈工程师一职，热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…
阅读更多...
openstack下如何生成centos9 centos10 和Ubuntu24 镜像

openstack下如何生成centos9 centos10 和Ubuntu24 镜像

如何生成一个centos 10和centos 9 的镜像1. 下载 对应的版本 wget https://cloud.centos.org/centos/10-stream/x86_64/images/CentOS-Stream-GenericCloud-x86_64-10-latest.x86_64.qcow2 wget https://cloud.centos.org/centos/9-stream/x86_64/images/CentOS-Stream-Gener…
阅读更多...
最新文章

Copyright @ 2022~2023