链表(详解)

一、链表

1.1、什么是链表

1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。

2、结点包括两个部分:(1)存储数据元素的数据域(内存空间),(2)存储指向下一个结点地址的指针域。

3、相对于线性表顺序结构,操作复杂。

1.2、链表的分类

链表的结构非常多样,以下的情况组合起来就有8种链表结构

(1)单项和双向

(2)带头和不带头

(3)循环和不循环

1.3、链表和顺序表的比较

(1)数组:使用一块连续的内存空间地址去存放数据,但

例如:
int  a[5]={1,2,3,4,5}。突然我想继续加两个数据进去,但是已经定义好的数组不能往后加,只能通过定义新的数组

int b[7]={1,2,3,4,5,6,7};  这样就相当不方便比较浪费内存资源,对数据的增删不好操作。

(2)链表:使用多个不连续的内存空间去存储数据, 可以 节省内存资源(只有需要存储数据时,才去划分新的空间),对数据的增删比较方便

注意:

1.链式结构在逻辑上是连续的,但在物理上不一定连续

2.现实中的结点一般都是从堆上申请出来的

3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续

二、无头单向非循环链表

2.1、无头单向非循环链表的结构

链表有一个数据域存放数据,一个指针域存放下一个结点的地址。

typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

2.2、无头单向非循环链表的实现

//打印
void SLTPrint(SLTNode* phead);//创建一个新节点
SLTNode* BuySListNode(SLTDataType x);//尾增
void SLTPushBack(SLTNode** pphead, SLTDataType x);//头增
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLTPopFront(SLTNode** pphead);// 作业
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);// 在pos以后插入x   
void SLTInsertAfter(SLTNode* pos, SLTDataType x);// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);// 删除pos的后一个位置
void SLTPopAfter(SLTNode* pos);// 单链表的销毁
void SListDestroy(SLTNode** pphead);

2.2.1、创建一个新节点

SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

创建一个新节点,用malloc开辟一个链表节点空间,强制转换成链表结构体,将data置为X,将next置为空,并返回新节点。

2.2.2、单链表的尾插

//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);//没有一个节点if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

单链表的尾插首先需要判断是否是空链表,如果为空就把该节点置为头节点,若不为空,先便利找到尾结点,然后将新节点插入尾节点后面。

2.2.3、单链表的头插法

//单链表的头插法   效率高,简单
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}

头插法相对简单,只需要将新节点插到头结点的前面,并且将头结点指针赋给新节点。

2.2.4、单链表的尾删

//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);// 1个节点if ((*pphead)->next == NULL){free((*pphead));*pphead = NULL;}else  //两个或者多个节点{   //方法一 /*SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;*///方法二SLTNode* tail = *pphead;SLTNode* tailprev = NULL;while (tail->next){tailprev = tail;tail = tail->next;}free(tail);tail = NULL;tailprev->next = NULL;}
}

和尾插法一样,首先先判断链表是否只有一个节点或者没有节点(为空),将会最后一个链表置空,如果超过一个节点,先找到倒数第二个节点,然后置空最后一个节点,将倒数第二个节点的next置空

2.2.5、单链表的头删法

//链表的头删法   效率高,简单
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* newnode = (*pphead)->next;free(*pphead);*pphead = newnode;
}

free第一个节点,将头指针后移一位。

2.2.6、单链表的查找

//查找元素  修改
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

借助cur指针,便利链表,cur=cur->next;若cur->data==x,返回cur,没找到返回NULL。

2.2.7、在pos之前插入

//在pos之前插入
//  传头指针是因为有可能时头插
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);if (pos == *pphead){SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}

在pos位置插入,相对

2.2.8、在pos之后插入

//在pos之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next=newnode;}

2.2.9、删除pos位置

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);//pos == NULL;  //可有可无,因为pos只是形参,对他的操作不影响外部的节点}
}

2.2.10、删除pos后一位置

//删除pos后一位置
void SLTPopAfter(SLTNode* pos)
{assert(pos);assert(pos->next == NULL);SLTNode* posnext = pos->next;pos->next = posnext->next;free(posnext);posnext = NULL;
}
//删除一个pos,没有头节点
// 把pos下一个节点的值赋给pos,将下一个节点删除
//但是无法删除尾结点

2.2.11、单链表的销毁

//单链表的销毁
void SListDestroy(SLTNode** pphead)
{assert(*pphead);SLTNode* pre = *pphead;SLTNode* p = pre->next;while (p!=NULL){free(pre);pre = p;p = p->next;}free(pre->next);pre->next = NULL;
}

三、带头双向循环链表

双向链表的原理与单链表类似,双向链表需要两个指针来链接,一个指向前面的,一个指向后面的。同时需要一个head,头链表,方便操作。

3.1带头双向链表实现

3.1.1、创建结构体

typedef int DataType;
typedef struct ListNode
{struct ListNode *next;struct ListNode *pre;DataType data;
}LTNode;

此结构中比单链表结构增加一个结构体指针pre,用于存放上一个节点的地址。
next是存放一个节点的地址。
data是存放数据。

3.1.2、申请结点

LTNode* BuyListNode(DataType x)//申请结点
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror( "malloc fail");exit(-1);}node->next = NULL;node->pre = NULL;node->data = x;return node;
}

动态申请结点,函数返回的是一个指针类型,用malloc开辟一个LTNode大小的空间,并用node指向这个空间,再判断是否为空,如为空就perror,显示错误信息。反之则把要存的数据x存到newnode指向的空间里面,把指针置为空。

3.1.3、初始化创建头结点

LTNode* LTInit()//初始化创建头结点
{LTNode* phead = BuyListNode(0);phead->next = phead;phead->pre = phead;return phead;
}

单链表开始是没有节点的,可以定义一个指向空指针的结点指针,但是此链表不同,需要在初始化函数中创建个头结点,它不用存储有效数据。因为链表是循环的,在最开始需要让头结点的next和pre指向头结点自己。
因为其他函数也不需要用二级指针(因为头结点指针是不会变的,变的是next和pre,改变的是结构体,只需要用结构体针即可,也就是一级指针)为了保持一致此函数也不用二级指针,把返回类型设置为结构体指针类型。

3.1.4、打印链表

void LTPrint(LTNode* phead)//打印链表
{assert(phead);LTNode* cur = phead->next;while (cur!=phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

打印链表,先断言phead,它不能为空,再把头结点下个地址存到cur中,用while循环去遍历,终止条件是等于头指针停止,因为他是循环的,并更新cur。

3.1.5、在pos位置之前插入

void LTInsert(LTNode* pos, DataType x)//在pos位置之前插入数据
{assert(pos);LTNode* node = BuyListNode(x);LTNode* bef = pos->pre;bef->next = node;node->pre = bef;node->next = pos;pos->pre = node;
}

断言pos,不能为空,插入数据先申请一结点放到定义的node指针变量中,为了不用考虑插入顺序,先把pos前面的存到bef中,然后就可以随意链接:
bef指向新节点,新节点前驱指针指向bef,新节点指向pos,pos前驱指针指向新节点。

3.1.6、删除任意位置数据

void LTErase(LTNode* pos)//删除pos位置数据
{assert(pos);pos->pre->next = pos->next;pos->next->pre = pos->pre;free(pos);
}

删除把pos位置之前的结点直接指向pos的下一个结点,把pos下一个结点的前驱指针指向pos之前的结点。

3.1.7、尾插

void LTPushBack(LTNode* phead, DataType x)//尾插
{/*assert(phead);//复杂方法/*LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;*/assert(phead);//简便方法LTInsert(phead, x);
}

简便方法:尾插是在尾部插入,用简便方法调用LTInsert函数,传入头指针和x。

复杂方法是:申请结点newnode,把头指针前的上一个结点存到尾指针变量中,再双向链接newnode,最后还得把头和尾(刚申请的结点)循环起来。

3.1.8、尾删

void LTPopBack(LTNode* phead)//尾删
{//assert(phead);//复杂方法//assert(phead->next != phead);  // 空//LTNode* tail = phead->prev;//LTNode* tailPrev = tail->prev;//tailPrev->next = phead;//phead->prev = tailPrev;//free(tail);assert(phead);//简便方法assert(phead->next != phead);  // 空LTErase(phead->pre);
}

简便方法:因为是尾删,删的是尾部,直接调用LTErase函数传入头指针的上一个结点,也就是尾部,因为是双向循环不用遍历直接直到尾部。

复杂方法:先把头结点上一个结点地址存起来,再把尾部的上一个结点地址存起来,再把第二次存的直接链接头部,头部链接第二次存的结点,再把第一次的结点释放掉。

3.1.9、头插

void LTPushFront(LTNode* phead, DataType x)//头插
{//assert(phead);//复杂方法//LTNode* newnode = BuyListNode(x);//LTNode* back = phead->next;//phead->next = newnode;//newnode->prev = phead;//newnode->next = back;//back->prev = newnode;assert(phead);//简便方法LTInsert(phead->next, x);
}

简便方法:因为是头插直接调用LTInsert函数传 头结点下一个结点指针和x。

复杂方法:申请结点存到newnode,再把头结点下一个结点地址存到指针back里,头部和新节点和back,三节点双向链接。

3.1.10、头删

void LTPopFront(LTNode* phead)//头删
{//assert(phead);//assert(phead->next != phead); // 空/*LTNode* back = phead->next;LTNode* second = back->next;free(back);phead->next = second;second->prev = phead;*/assert(phead);assert(phead->next != phead);  // 空LTErase(phead->next);}

简便方法:因为头删,直接调LTErase函数传入头结点下一个指针。

复杂方法:先把头结点下一个结点地址存到back指针里,再把back一个结点地址存到second指针里,先释放中间的back,最后头结点和second双向链接。

3.1.11、查找元素

LTNode* LTFind(LTNode* phead, DataType x)//查找
{assert(phead);LTNode* cur = phead->next;while (cur!=phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}

查找把头结点下一个结点存到cur,然后用while循环遍历,终止条件是cur等于头结点指针,如果cur等于x,直接返回cur指针,再更新cur,最后遍历完返回NULL,表示没有该数据。

3.1.12、释放链表

void LTDestroy(LTNode* phead)//释放链表
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

释放链表从头开始释放,把头结点下一个结点存到cur中,再用用while循环,终止条件是cur不等于头指针,在里面把cur下一个指针存到next中,释放掉cur,再把next更新为cur。
最后头结点也是申请的,也得释放。

3.1.13、判断是否为空

bool LTEmpty(LTNode* phead)//判断是否为空
{assert(phead);return phead->next == phead;
}

3.1.14、求链表长度

size_t LTSize(LTNode* phead)//求链表长度
{assert(phead);size_t size = 0;LTNode* cur = phead->next;while (cur != phead){++size;cur = cur->next;}return size;
}

求链表长度,先把头结点下一个结点存到cur中,再用while循环遍历终止条件是cur等于头结点,用size++记录长度,并更新cur,最后返回size,32位机器下是无符号整型size_t。


到这里链表的基本问题就解释完了,相信多多少少会解决大家心头的疑问,在数据结构的学习中应当善于思考,多画图,死磕代码,注意细节,将伪代码转换为代码,这样才能很好的掌握数据结构的有关知识,共勉,加油!!!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

OLED透明屏显示技术:未来显示科技的领航者

OLED透明屏显示技术是一种创新性的显示技术,它的特殊性质使其成为未来显示科技的领航者。 OLED透明屏具有高对比度、快速响应时间、广视角和低功耗等优势,同时,其透明度、柔性和薄型设计使其成为创新设计的理想选择。 本文将深入探讨OLED透…

NSS [NUSTCTF 2022 新生赛]Ezjava1

NSS [NUSTCTF 2022 新生赛]Ezjava1 题目描述:你能获取flag{1}吗 开题,一眼java web中的index.jsp。 默认index.jsp中的body内容是$END$ 附件jar包导入IDEA,会自动反编译。看看源码。 附件结构大致如此。主要看classes.com.joe1sn中的代码就…

MyBatisx代码生成

MyBatisx代码生成 1.创建数据库表 CREATE TABLE sys_good (good_id int(11) NOT NULL,good_name varchar(255) COLLATE utf8mb4_general_ci DEFAULT NULL,good_desc varchar(255) COLLATE utf8mb4_general_ci DEFAULT NULL,PRIMARY KEY (good_id) ) ENGINEInnoDB DEFAULT CHA…

【C++设计模式】用动画片《少年骇客》(Ben10)来解释策略模式

2023年8月25日,周五上午 今天上午学习设计模式中的策略模式时,发现这个有点像很多卡通片里面的变身器... 2023年8月26日,周六上午 更新:和简单工厂模式结合 目录 用策略模式写主角的变身器 使用策略模式的好处和简单工厂模式结…

手写实现call() apply() bind()函数,附有详细注释,包含this指向、arguments讲解

手写实现call() apply() bind()函数是很经典的问题,但是能掰扯清楚的文章确实不算多,于是笔者才决定写下本文,希望能给读者带来一些启发,如有错误欢迎指正。 目录 补充知识 函数中的this指向 类数组对象arguments call() 原理…

每日三题 1448统计二叉树中好节点的个数 100相同的树 101对称二叉树

1448 题目 给你一棵根为 root 的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 输入:root [3,1,4,3,null,1,5] 输出&#xff…

弯道超车必做好题集锦三(C语言选择题)

前言: 编程想要学的好,刷题少不了,我们不仅要多刷题,还要刷好题!为此我开启了一个弯道超车必做好题锦集的系列,每篇大约10题左右。此为第三篇选择题篇,该系列会不定期更新,后续还会…

MongoDB实验——在Java应用程序中操作 MongoDB 数据

在Java应用程序中操作 MongoDB 数据 1. 启动MongoDB Shell 2. 切换到admin数据库,使用root账户 3.开启Eclipse,创建Java Project项目,命名为MongoJava File --> New --> Java Project 4.在MongoJava项目下新建包,包名为mo…

《Go 语言第一课》课程学习笔记(十三)

方法 认识 Go 方法 Go 语言从设计伊始,就不支持经典的面向对象语法元素,比如类、对象、继承,等等,但 Go 语言仍保留了名为“方法(method)”的语法元素。当然,Go 语言中的方法和面向对象中的方…

C++------map和set的使用

文章目录 关联式容器键值对树型结构的关联式容器set的介绍map的介绍 关联式容器 什么是关联式容器&#xff1f;它与序列式容器有什么区别&#xff1f; 关联式容器也是用来存储数据的&#xff0c;与序列式容器不同的是&#xff0c;其里面存储的是<key&#xff0c;value>结…

【数据结构】手撕顺序表

一&#xff0c;概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构&#xff0c;一般情况下采用数组存储&#xff1b; 在数组上完成数据的增删查改。 1&#xff0c; 静态顺序表&#xff1a;使用定长数组存储元素。 2.&#xff0c;动态顺序表&#xff1…

系统架构设计高级技能 · 云原生架构设计理论与实践

系列文章目录 系统架构设计高级技能 软件架构概念、架构风格、ABSD、架构复用、DSSA&#xff08;一&#xff09;【系统架构设计师】 系统架构设计高级技能 系统质量属性与架构评估&#xff08;二&#xff09;【系统架构设计师】 系统架构设计高级技能 软件可靠性分析与设计…

webservice调用对接第三方系统

#webservice调用对接第三方系统# 最近接到一个任务&#xff0c;需要对接第三方数据&#xff0c;第三方提供对接方式的是通过webservice调用&#xff0c;webservice调用有好几种方式&#xff0c;具体可以自行了解&#xff0c;我选择的是通过wsdl文件自动生成客户端代码对接。 …

基于野狗算法优化的BP神经网络(预测应用) - 附代码

基于野狗算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码 文章目录 基于野狗算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码1.数据介绍2.野狗优化BP神经网络2.1 BP神经网络参数设置2.2 野狗算法应用 4.测试结果&#xff1a;5.Matlab代码 摘要…

计算机毕设之Python的高校成绩分析(含文档+源码+部署)

本系统阐述的是一个高校成绩分析系统的设计与实现&#xff0c;对于Python、B/S结构、MySql进行了较为深入的学习与应用。主要针对系统的设计&#xff0c;描述&#xff0c;实现和分析与测试方面来表明开发的过程。开发中使用了 django框架和MySql数据库技术搭建系统的整体架构。…

[Android]JNI的基础知识

目录 1.什么是JNI 2.配置JNI开发环境NDK 3.创建Native C类型的项目 4. 了解CMakeLists.txt 文件 5.了解native-lib.cpp 文件 6.在 Android 的 MainActivity 中调用 native-lib.cpp 中实现的本地方法 1.什么是JNI JNI&#xff08;Java Native Interface&#xff09;是一…

2023年8月22日OpenAI推出了革命性更新:ChatGPT-3.5 Turbo微调和API更新,为您的业务量身打造AI模型

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…

记录--怎么实现一个3d翻书效果

这里给大家分享我在网上总结出来的一些知识&#xff0c;希望对大家有所帮助 本篇主要讨论以下两种翻书动画的实现&#xff1a; 第一种是整页翻转的效果&#xff1a; 这种整页翻转的效果主要是做rotateY的动画&#xff0c;并结合一些CSS的3d属性实现。 第二种折线翻转的效果&…

【项目 计网7】4.20 多进程实现并发服务器 4.22 多线程实现并发服务器

文章目录 4.20 多进程实现并发服务器server_process.cclient.c4.22 多线程实现并发服务器客户端代码&#xff1a;服务端代码&#xff1a; 4.20 多进程实现并发服务器 要实现TCP通信服务器处理并发的任务&#xff0c;使用多线程或者多进程来解决。 思路&#xff1a; 1、一个父进…

企业微信cgi-bin/gateway/agentinfo接口存在未授权访问漏洞 附POC

文章目录 企业微信cgi-bin/gateway/agentinfo接口存在未授权访问漏洞 附POC1. 企业微信cgi-bin/gateway/agentinfo接口简介2.漏洞描述3.影响版本4.fofa查询语句5.漏洞复现6.POC&EXP7.整改意见8.往期回顾 企业微信cgi-bin/gateway/agentinfo接口存在未授权访问漏洞 附POC 免…