单链表详解

在这里插入图片描述
今天我们继续来学习我们的链表,今天我们来学习单链表,什么是单链表呢,我们逻辑结构上可以·认为是下面这个图。

在这里插入图片描述

然后我们结构体的定义就是下面这个

在这里插入图片描述

typedef int SLDateType;
typedef struct SList
{
	SLDateType x;
	struct SList* next;
}SL;

为什么是这样会定义,大家有没有想过,我们有一个指针叫next,顾名思义就是指向下一个节点,如果我们来完善上面的这张图就是

在这里插入图片描述
我们的这张内容就是来实现这样的一个链表,然后在这个基础上继续实现增删查改

那和顺序表是一样的,我们需要先来初始化我们的链表,我们这里可以采用两种方式,一种是直接先给一个事先开好的节点,然后进行增删查改,你也可以理解为有哨兵位的头节点,但是我们这里先不用这个方法,我们初始化的时候就是给个空指针,然后进行我们下一步的操作。

在这里我也先给出我们要写的几个函数的声明。

// slist.h
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入?
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置?
void SListEraseAfter(SListNode* pos);

// 在pos的前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);
// 删除pos位置
void SLTErase(SLNode** pphead, SLNode* pos);
void SLTDestroy(SLNode** pphead);

后面的代码还是按照我自己习惯的定义风格,上面的只是给出一个大概来供大家参考

我们来按照上面的声明来一个一个实现他们的定义,我们先来实现如何让尾插,因为考虑到尾插肯定是要先创建新的节点,所以我们先来实现的函数时创造新节点的函数。

SL* BuySListNode(SLDateType x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	newnode->Date = x;
	newnode->next = NULL;
	return newnode;
}

创造新的节点出来我们现在先写一个尾插函数,尾插就是把新节点插入到尾节点的后面

在这里插入图片描述
上面的这个图里尾节点就是空指针的前一个节点

在这里插入图片描述
那我们要实现尾插的思路就是在tail的后面插入就行了,思路是很简单的,但是我们需要注意的一个点就是如果我们一开始的时候就是空指针的话,我们不能直接插入,这个时候head就是空,所以我们第一个节点是头节点也是尾节点。

尾插的实现

void SLPushBack(SL** ppHead, SLDateType x)
{
	assert(ppHead);
	SL* NewNode = BuySListNode(x);
	if (*ppHead == NULL)
	{
		*ppHead = NewNode;
	}
	else
	{
		SL* tail = *ppHead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = NewNode;
	}
}

我们再来分析头插是怎么个事,首先我们先要来分析一个节点都没有的时候,我们一开始就是我们的空指针,其实就是直接把我们创造出来的节点给我们的头指针就可以了,那如果是多个节点的话,就是newnode指向我们的ppHead,然后再继续更新头节点ppHead就可以解决问题了

下面是头插的代码

void SLPushFront(SL** ppHead, SLDateType x)
{
	assert(ppHead);
	SL* NewNode = BuySListNode(x);
	NewNode->next = *ppHead;
	*ppHead = NewNode;
}

我们可以看到头插的代码其实很简单,这也能说明单链表头插的效率是很高的,在我们后面学习stl中单链表也是只有头插,因为头插的时间复杂度就是O(1)。
因为我们要来看我们的的效果,其实我们这里可以写个打印的函数,打印函数很简单,直接遍历单链表就行。
打印函数代码

void SLPrint(SL* phead)
{
	SL* cur = phead;
	while (cur)
	{
		printf("%d->", cur->Date);
		cur = cur->next;
	}
	printf("NULL\n");
}

我们的节点因为都是malloc出来的,我们使用过程中需要对其释放,所以这里再写一个destory的函数

void SLDestory(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	SL* cur = *ppHead;
	while (cur)
	{
		SL* next = cur->next;
		free(cur);
		cur = next;
	}

}

讲完头插和尾插,这里对写链表给出的建议,一个我们需要来断言,比如assert需要断言的是我们的ppHead不能为空,因为这是head的地址,它一定不能为空,下一个就是我们*ppHead,再头插和尾插的时候,单链表为空的时候我们也是可以进行插入的,所以这里不用写,但是我们的尾插需要分没有节点的时候和有节点的时候,这个需要我们来画图进行分析。

尾插实现好之后我们再来就是尾删和头删,这两个的断言就需要再三考虑,比如我们为空的时候就不能再删除了。。

尾删的时候我们需要有一个前指针来指向我们尾指针的前一个,这里我们就可以释放尾指针的时候,保持单链表的连续性,如果没有前指针就会出现找不到的现象。

尾删的代码

void SLPopBack(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	//只有一个节点和多个节点的释放是不同的。
	SL* tail = *ppHead;
	if (tail->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		SL* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}

}

但是我们的头删代码就是很简单,我们来看看
代码

void SLPopFront(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	SL* next = (*ppHead)->next;
	free(*ppHead);
	*ppHead = next;

}

只要free第一个节点再移动head就ok了

我们已经实现了增删,那肯定还有查找,我们再来补充一下我们在pos位置前面或者后面实现插入和删除,会了这些之后算是对单链表已经有了深入的理解了。

先是我们的查找是怎么个样子,遍历一遍就可以了

SL* SLFind(SL* ppHead, SLDateType x)
{
	assert(ppHead);
	SL* cur = ppHead;
	while (cur)
	{
		if (cur->Date == x)
		{
			return  cur;
		}
		cur = cur->next;
	}
	return NULL;

}

我们这里给了一个断言,原因就是如果我们的链表为空,我们就不能进行查找,然后我们这里返回节点的位置,我们在后面的随机插入和删除有妙用。

在这里插入图片描述
首先我们先来对我们这个进行断言,要么都是空是什么意思和要么都不是空,首先是要么都是空的意思就是单链表一个节点都没有的时候,这个时候pos位置其实就是空,我们就相当于在空的位置前进行了插入,那其实就是相当于调用了头插,如果链表不是空,那理所当然,如果pos位置是空,也就相当于我们没有这个节点的位置,也就不能插入,所以这里的assert就是要确定要么都是空,要么都不是空。

//在pos前位置进行插入
void SLInsert(SL** ppHead, SL* pos, SLDateType x)
{
	
	assert(ppHead);
	//要么都是空,要么都不是空
	assert((pos && *ppHead) || (!pos && !(*ppHead)) );
	if (*ppHead == NULL)
	{
		SLPushFront(ppHead, x);
	}
	else
	{
		SL* NewNode = BuySListNode(x);
		SL* pre = *ppHead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		NewNode->next = pos;
		pre->next = NewNode;
	}
	


}

那我们上面的代码也不知道对不对,我们需要我们来进行测试看看。
测试代码也在下面

void test4()
{
	SL* head = NULL;
	SLInsert(&head, NULL, 10);
	SLPrint(head);
	SLPushBack(&head, 1);
	SLPushBack(&head, 2);
	SLPushBack(&head, 3);
	SLPushBack(&head, 4);
	SLPrint(head);
	SL* pos = SLFind(head, 3);
	SLInsert(&head, pos, 20);
	SLPrint(head);


}

在这里插入图片描述
可以看到我们的代码其实和预期结果是没有问题的,那我们马上写我们后面·的代码在pos位置进行删除。

在这里插入图片描述
先来看我们的断言环节,首先就是ppHead不能为空,因为这个是外面函数head的地址,如果这个也是空的话,就是对空指针的非法访问。
链表为空也不行,pos位置也不能为空,如果为空就是找不到了,我们也就不让他进入程序。

void SLErase(SL** ppHead, SL* pos)
{
	assert(ppHead);
	assert(*ppHead);
	assert(pos);
	if ((*ppHead)->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		SL* cur = *ppHead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SL* tmp = pos->next;
		free(pos);
		pos = NULL;
		cur->next = tmp;
	}
	
}

这里也是要分一个节点和多个节点,因为我们已经asser过,pos不可能为空,但是如果是只有一个节点的时候,那我们这里pos肯定是头节点,我们直接释放就行。当然还有其他方法,如果我们下面的代码不保存tmp位置,也可以不用写上面的了。

写完在pos之前添加,那我们继续写一个在pos位置之后删除和添加的代码,单链表的内容也就完善很多了。

在这里插入图片描述

这里断言只要断言这两个就行,一个是空进来就是找不到情况,还有一个就是指向节点的空位置,因为我们是在pos位置之后插入,所以这里确保必须得有一个节点。我们也可以继续断言assert(*ppHead),但是我觉得没有必要。

void SLInsertAfter(SL** ppHead, SL* pos, SLDateType x)
{
	assert(ppHead);
	assert(pos);
	if ((*ppHead)->next == NULL)
	{
		SLPushBack(ppHead, x);
	}
	else
	{
		SL* NewNode = BuySListNode(x);
		SL* next = pos->next;
		NewNode->next = next;
		pos->next = NewNode;
	}
}

在继续写下一个随机删除的代码
也是在pos位置之后进行。

在这里插入图片描述
因为我们是在pos位置之后释放,所以这里其实至少也是得有两个节点以上,如果是一个节点的话我们pos的next就是我们的NULL,我们虽然是可以对空指针进行释放的,但是我觉得没有意义,那我们干脆就是考虑有两个节点以上的。

void SLEraseAfter(SL** ppHead, SL* pos)
{
	assert(ppHead);
	assert(*ppHead);
	assert(pos);
	SL* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

而且上面其实还有一个问题就是我们的pos位置其实不能是为节点,因为pos->next不能为空,我们才能访问pos->next->next,所以单链表还有好多细节,但是单链表有很多的写法,这里就不一一举列子,下面分享整个代码

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDateType;
typedef struct SListNode
{
	SLDateType Date;
	struct SListNode* next;
}SL;



SL* BuySListNode(SLDateType x);

void SLPushBack(SL** ppHead, SLDateType x);

void SLPrint(SL* phead);

void SLDestory(SL** ppHead);

void SLPushFront(SL** ppHead, SLDateType x);


void SLPopBack(SL** ppHead);


void SLPopFront(SL** ppHead);


SL* SLFind(SL* ppHead, SLDateType x);

void SLInsert(SL** ppHead, SL* pos, SLDateType x);

void SLErase(SL** ppHead, SL* pos);


void SLInsertAfter(SL** ppHead, SL* pos, SLDateType x);


void SLEraseAfter(SL** ppHead, SL* pos);


SList.c

#include"SL.h"


SL* BuySListNode(SLDateType x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	newnode->Date = x;
	newnode->next = NULL;
	return newnode;
}


void SLPushBack(SL** ppHead, SLDateType x)
{
	assert(ppHead);
	SL* NewNode = BuySListNode(x);
	if (*ppHead == NULL)
	{
		*ppHead = NewNode;
	}
	else
	{
		SL* tail = *ppHead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = NewNode;
	}
}

void SLPrint(SL* phead)
{
	SL* cur = phead;
	while (cur)
	{
		printf("%d->", cur->Date);
		cur = cur->next;
	}
	printf("NULL\n");
}


void SLDestory(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	SL* cur = *ppHead;
	while (cur)
	{
		SL* next = cur->next;
		free(cur);
		cur = next;
	}

}

void SLPushFront(SL** ppHead, SLDateType x)
{
	assert(ppHead);
	SL* NewNode = BuySListNode(x);
	NewNode->next = *ppHead;
	*ppHead = NewNode;
}

void SLPopBack(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	//只有一个节点和多个节点的释放是不同的。
	SL* tail = *ppHead;
	if (tail->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		SL* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}

}


void SLPopFront(SL** ppHead)
{
	assert(ppHead);
	assert(*ppHead);
	SL* next = (*ppHead)->next;
	free(*ppHead);
	*ppHead = next;

}

SL* SLFind(SL* ppHead, SLDateType x)
{
	assert(ppHead);
	SL* cur = ppHead;
	while (cur)
	{
		if (cur->Date == x)
		{
			return  cur;
		}
		cur = cur->next;
	}
	return NULL;

}

//在pos前位置进行插入
void SLInsert(SL** ppHead, SL* pos, SLDateType x)
{
	
	assert(ppHead);
	//要么都是空,要么都不是空
	assert((pos && *ppHead) || (!pos && !(*ppHead)) );
	if (*ppHead == NULL)
	{
		SLPushFront(ppHead, x);
	}
	else
	{
		SL* NewNode = BuySListNode(x);
		SL* pre = *ppHead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		NewNode->next = pos;
		pre->next = NewNode;
	}
	


}

void SLErase(SL** ppHead, SL* pos)
{
	assert(ppHead);
	assert(*ppHead);
	assert(pos);
	if ((*ppHead)->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		SL* cur = *ppHead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SL* tmp = pos->next;
		free(pos);
		pos = NULL;
		cur->next = tmp;
	}
	
}


void SLInsertAfter(SL** ppHead, SL* pos, SLDateType x)
{
	assert(ppHead);
	assert(pos);
	if ((*ppHead)->next == NULL)
	{
		SLPushBack(ppHead, x);
	}
	else
	{
		SL* NewNode = BuySListNode(x);
		SL* next = pos->next;
		NewNode->next = next;
		pos->next = NewNode;
	}
}



void SLEraseAfter(SL** ppHead, SL* pos)
{
	assert(ppHead);
	assert(*ppHead);
	assert(pos);
	SL* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

那今天的分享就到这里,我们下次再见。

在这里插入图片描述

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

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

相关文章

(14)学习笔记:动手深度学习(Pytorch神经网络基础)

文章目录 神经网络的层与块块的基本概念自定义块 问答 神经网络的层与块 块的基本概念 以多层感知机为例&#xff0c; 整个模型接受原始输入&#xff08;特征&#xff09;&#xff0c;生成输出&#xff08;预测&#xff09;&#xff0c; 并包含一些参数&#xff08;所有组成层…

vue3 开启 https

1、安装mkcert证书创建器 npm i mkcert -g 2、检验是否安装成功 mkcert --version 有版本好出现则成功 3、创建证书颁发机构 mkcert create-ca 会在当前目录生成&#xff0c;ca.crt 和 ca.key 两个文件 4、创建证书 mkcert create-cert 会在当前目录生成&#xff0c;…

【2023.11.6】OpenAI发布会——近期chatgpt被攻击,不能使用

OpenAI发布会 写在最前面发布会内容GPT-4 Turbo 具有 128K 上下文函数调用更新改进了指令遵循和 JSON 模式可重现的输出和对数概率更新了 GPT-3.5 Turbo 助手 API、检索和代码解释器API 中的新模式GPT-4 Turbo 带视觉DALLE 3文字转语音 &#xff08;TTS&#xff09;收听语音样本…

Linux第一个小程序进度条

缓冲区 ​ 在写进度条程序之前我们需要介绍一下缓冲区&#xff0c;缓冲区有两种&#xff0c;输入和输出缓冲区&#xff0c;这里主要介绍输出缓冲区。在我们用C语言写代码时&#xff0c;输出一些信息&#xff0c;实际上是先输出到输出缓冲区里&#xff0c;然后才输出到我们的显…

AI系统ChatGPT程序源码+AI绘画系统源码+支持GPT4.0+Midjourney绘画+已支持OpenAI GPT全模型+国内AI全模型

一、AI创作系统 SparkAi创作系统是基于OpenAI很火的ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如…

3D全景技术,为我们打开全新宣传领域

随着科技的发展&#xff0c;3D全景技术正在融入我们的生活&#xff0c;这种全新视觉体验方式为我们打开了一扇全新的宣传领域&#xff0c;可以让我们多方位、多视角地探索各个行业&#xff0c;无论是对教育、商业、还是其他领域&#xff0c;都产生了深远的影响。 3D全景技术结合…

【云备份|| 日志 day5】文件热点管理模块

云备份day5 热点管理模块 热点管理模块 服务器端的热点文件管理是对上传的非热点文件进行压缩存储&#xff0c;节省磁盘空间。 而热点文件的判断在于上传的文件的最后一次访问时间是否在热点判断时间之内&#xff0c;比如如果一个文件一天都没有被访问过我们就认为这是一个非…

多VLAN之间的通信,静态路由

一、适用场景 1、多个C类网络&#xff08;不同网段&#xff09;之间需要通信&#xff0c;每个网段有1个网关ip。 2、当网络结构比较简单时&#xff0c;只需配置静态路由就可以使网络正常工作。本例采用简单网络结构 3、在复杂网络环境中&#xff0c;配置静态路由可以改进网络的…

牛客出bug(华为机试HJ71)

Hj71&#xff1a;字符串通配符 描述 问题描述&#xff1a;在计算机中&#xff0c;通配符一种特殊语法&#xff0c;广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。 要求&#xff1a; 实现如下2个通配符&#xff1a; *&#xff1a;匹配0个…

Java --- Mybatis的动态sql标签

一、if标签 <select id"queryEmpByCondition" resultType"User">select * from t_user where 11<if test"username ! null and username ! ">and username #{username}</if></select> if&#xff1a;根据标签中的test…

AWTK 与 Qt 的异同点比较

相似之处&#xff1a; 跨平台支持&#xff1a; AWTK 和 Qt 都提供了跨平台的支持&#xff0c;可以在多种操作系统上进行开发和部署&#xff0c;包括 Windows、Linux、macOS 等。丰富的组件库&#xff1a; 两者都提供了丰富的图形界面组件库&#xff0c;能够满足各种应用程序的…

pytest全局变量的使用

这里重新阐述下PageObject设计模式&#xff1a; PageObject设计模式是selenium自动化最成熟&#xff0c;最受欢迎的一种模式&#xff0c;这里用pytest同样适用 这里直接提供代码&#xff1a; 全局变量 conftest.py """ conftest.py 全局变量&#xff0c;主要实…

华为eNSP实验-三层交换机的不同网段通信(通过OSPF路由方式)

1.拓扑图 2.过程如下 2.1 首先PC1和PC2配置好IP地址 2.2 在SW1上配置虚拟网关及VLAN <Huawei>system-view [Huawei]sysname SW1 [SW1]undo info-center enable [SW1] [SW1]vlan batch 10 20 [SW1]interface GigabitEthernet 0/0/1 [SW1-GigabitEthernet0/0/1]port li…

docker.service配置docker镜像加速

加速器配置方法很多&#xff0c;小白我用的是docker.service文件&#xff0c;所以直接在里面配置啊 配置以后&#xff0c;要systemctl daemon-reload下 &#xff0c;然后docker info 下看下镜像地址是否是自己已配置的 docker run --privilegedtrue --name mytomcat -p 8080…

利用QT画图像的直方图

1.什么是直方图 直方图是一种图形化展示数据频率分布的方式。它将样本数据分成一系列相邻的区间&#xff0c;统计每个区间内数据所占比例或数量&#xff0c;并用矩形条形图表现出来。直方图可以反映样本数据的分布情况&#xff0c;例如它们的集中趋势、对称性和离散程度等。 …

2011年03月17日 Go生态洞察:探索Go与C的交互——Cgo

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

【深度学习】手写数字识别

文章目录 一、步骤1.导包2.查看数据集图片3.多层感知器4.结果 总结 一、步骤 1.导包 #导入需要的包 import numpy as np import paddle as paddle import paddle.fluid as fluid from PIL import Image import matplotlib.pyplot as plt import os from paddle.fluid.dygraph…

Linux awk命令

除了使用 sed 命令&#xff0c;Linux 系统中还有一个功能更加强大的文本数据处理工具&#xff0c;就是 awk。 曾有人推测 awk 命令的名字来源于 awkward 这个单词。其实不然&#xff0c;此命令的设计者有 3 位&#xff0c;他们的姓分别是 Aho、Weingberger 和 Kernighan&#x…

第十八章Swing程序设计总结

例题18.1&#xff1a;第一个窗体程序 例题18.2&#xff1a;在窗体中弹出对话框 例题18.3&#xff1a;弹出会话框&#xff0c;问用户准备好了吗&#xff1f; 例题18.4&#xff1a;弹出会话框&#xff0c;询问用户是否离开 例题18.5&#xff1a;弹出会话框&#xff0c;让用户输入…

[LeetCode]-160. 相交链表-141. 环形链表-142.环形链表II

目录 160.相交链表 题目 思路 代码 141.环形链表 题目 思路 代码 142.环形链表II 题目 思路 代码 160.相交链表 160. 相交链表 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 题目 给你两个…