数据结构--单链表（图文）

单链表的概念

在单链表中，每个元素（称为节点）包含两部分：一部分是存储数据的数据域，另一部分是存储下一个节点地址的指针域。这里的“单”指的是每个节点只有一个指向下一个节点的指针。
在这里插入图片描述

  1. 节点：链表中的基本单元，通常由数据域和指针域组成。数据域用于存储实际的数据，而指针域用于指向链表中的下一个节点。

  2. 链：通过节点中的指针链接形成的序列。在单链表中，这种链接是单向的，即只能从一个节点指向下一个节点。

  3. 头节点：链表的第一个节点，用于标识链表的开始。有时，头节点仅作为链表的头部标识，不存储实际数据。

  4. 尾节点：链表的最后一个节点，其指针域通常为空（NULL），表示链表的结束。

  5. 非连续性：与数组不同，单链表的节点在内存中不必连续存储。每个节点的位置由其前一个节点的指针决定。

  6. 动态性：单链表的大小是动态的，可以在运行时通过增加或删除节点来改变链表的长度。

单链表的主要特点是其灵活性和动态性，它可以有效地进行插入和删除操作，尤其是在不知道数据数量的情况下，或者当数据量变化较大时。但是，由于需要通过指针进行遍历，单链表在访问特定元素时可能不如数组高效。以下是其在各种操作中的优势：

  • 插入和删除：在单链表中插入或删除节点只需要O(1)的时间，前提是已经有了指向要操作节点的指针。
  • 空间利用：单链表不需要预分配固定的存储空间，它可以根据需要动态地分配内存。

单链表的实现

首先创建三个文件：

  • SList.h —— 用于声明函数的头文件
  • SList.c —— 单链表主要函数的实现
  • test.c——测试单链表。

创建单链表

typedef int SLTDataType;//方便后续使用更改类型

//创建一个节点
typedef struct SListNode
{
	SLTDataType data;//该节点储存的数据
	struct SListNode* next;//指向下一个节点的指针
}SListNode;

销毁链表

从前向后依次释放节点，最后将头节点置为NULL 。

void SListDesTroy(SListNode** pphead)//销毁链表
{
	assert(pphead && *pphead);
	SListNode* pcur = *pphead;
	while (pcur)
	{
		SListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

打印节点数据

遍历依次打印即可。

void SLTPrint(SListNode* phead)//打印节点数据
{
	assert(phead);
	SListNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

申请一块节点

在进行插入节点时，我们需要先申请一块节点来进行插入，所以我们将申请节点单独封装成一个函数。

SListNode* SLTBuyNode(SLTDataType x)//增加节点(空间)
{
	//开辟一个节点空间
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//设置数据并返回该节点地址
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

尾插数据

两种情况

  • 情况一：链表为空直接申请新节点给头节点；
  • 情况二：链表不为空，遍历找到尾节点，再将新节点接入即可。

在这里插入图片描述

void SLTPushBack(SListNode** pphead, SLTDataType x)//尾插数据
{
	assert(pphead);//不能为空，否则就会对空指针解引用
	if (*pphead == NULL)//指向头节点的指针为空，也就是链表为空
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* newnode = *pphead;
		while (newnode->next)
		{
			newnode = newnode->next;
		}
		newnode->next = SLTBuyNode(x);
	}
}

头插数据

两种情况

  • 情况一：链表为空直接申请新节点给头节点。
  • 情况二：链表不为空，先将pphead（头节点）保存起来，然后让pphead指向新插入的节点，在让*pphead->next指向刚才保存好的原本的头节点。
    在这里插入图片描述
void SLTPushFront(SListNode** pphead, SLTDataType x)//头插数据
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* pcur = *pphead;
		*pphead = SLTBuyNode(x);
		(*pphead)->next = pcur;
	}
}

尾删数据

两种情况

  • 情况一：链表只有一个数据，直接释放该节点并将头节点置为空。
  • 情况二：链表有多个数据节点，遍历找到尾节点的前一个节点，释放该节点的next节点，再将该节点的next置为空。
    在这里插入图片描述
void SLTPopBack(SListNode** pphead)//尾删数据
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next->next)
		{
			pcur = pcur->next;
		}
		free(pcur->next);
		pcur->next = NULL;
	}
}

头删数据

两种情况

  • 情况一：链表只有一个数据，直接释放该节点并将头节点置为空。
  • 情况二：链表有多个数据节点，先将pphead（头节点）保存起来，然后让pphead指向*pphead->next（新的头节点），然后释放刚才保存的节点（原头节点）。
    在这里插入图片描述
void SLTPopFront(SListNode** pphead)//头删数据
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* pcur = (*pphead);
		*pphead = (*pphead)->next;
		free(pcur);
	}
}

查找数据

从前向后遍历整个链表，如果 plist->data == x，就说明找到了，返回 plist 此时的值，如果plist = NULL了，就说明这个链表中没有该数据，则返回空。

SListNode* SLTFind(SListNode* phead, SLTDataType x)//查找数据
{
	assert(phead);
	SListNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

有了查找函数，就可以实现任意位置的增加数据和删除数据的操作了。

在指定位置之前插入数据

两种情况

  • 情况一：指定位置为头节点则直接头插。
  • 情况二：指定位置为其他节点，遍历找到指定节点的前一个节点，在该节点后插入新数据。
    在这里插入图片描述
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)//在指定位置之前插入数据
{
	assert(pphead&&*pphead);
	if (*pphead == pos)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		SListNode* newnode = SLTBuyNode(x);
		pcur->next = newnode;
		newnode->next = pos;
	}
}

在指定位置之后插入数据

在指定位置后直接插入即可。

void SLTInsertAfter(SListNode* pos, SLTDataType x)//在指定位置之后插入数据
{
	assert(pos);
	SListNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

删除指定位置节点

两种情况

  • 情况一：指定位置为头节点则直接头删。
  • 情况二：指定位置为其他节点，遍历找到指定位置的前一个节点，先将该节点的next指针指向指定位置的next位置，然后再释放指定位置。（不能改变顺序，否则找不到指定位置的下一个节点了）
    在这里插入图片描述
void SLTErase(SListNode** pphead, SListNode* pos)//删除pos节点
{
	assert(*pphead && pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

删除指定位置之后的数据

先将指定位置的的下一个位置保存起来，让指定位置的next指针指向保存位置的下一个位置，然后释放掉保存的位置也就是指定位置之后的数据。
在这里插入图片描述

void SLTEraseAfter(SListNode* pos)//删除pos之后的节点
{
	assert(pos && pos->next);
	SListNode* pcur = pos->next;
	pos->next = pos->next->next;
	free(pcur);
	pcur = NULL;	
}

单链表源码

SList.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLTDataType;

//创建一个节点
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;

SListNode* SLTBuyNode(SLTDataType x);//增加节点(空间)


void SLTPrint(SListNode* phead);//打印节点数据


void SListDesTroy(SListNode** pphead);//销毁链表


void SLTPushBack(SListNode** pphead, SLTDataType x);//尾插数据


void SLTPushFront(SListNode** pphead, SLTDataType x);//头插数据


SListNode* SLTFind(SListNode* phead, SLTDataType x) ;//查找数据


void SLTPopBack(SListNode** pphead);//尾删数据


void SLTPopFront(SListNode** pphead);//头删数据


void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在指定位置之前插入数据


void SLTInsertAfter(SListNode* pos, SLTDataType x);//在指定位置之后插入数据


void SLTErase(SListNode** pphead, SListNode* pos);//删除pos节点


void SLTEraseAfter(SListNode* pos);//删除pos之后的节点

SList.c

#include"SList.h"

SListNode* SLTBuyNode(SLTDataType x)//增加节点(空间)
{
	//开辟一个节点空间
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//设置数据并返回该节点地址
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SLTPrint(SListNode* phead)//打印节点数据
{
	assert(phead);
	SListNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
void SListDesTroy(SListNode** pphead)//销毁链表
{
	assert(pphead && *pphead);
	SListNode* pcur = *pphead;
	while (pcur)
	{
		SListNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

void SLTPushBack(SListNode** pphead, SLTDataType x)//尾插数据
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* newnode = *pphead;
		while (newnode->next)
		{
			newnode = newnode->next;
		}
		newnode->next = SLTBuyNode(x);
	}
}



void SLTPushFront(SListNode** pphead, SLTDataType x)//头插数据
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = SLTBuyNode(x);
	}
	else
	{
		SListNode* pcur = *pphead;
		*pphead = SLTBuyNode(x);
		(*pphead)->next = pcur;
	}
}


SListNode* SLTFind(SListNode* phead, SLTDataType x)//查找数据
{
	assert(phead);
	SListNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}


void SLTPopBack(SListNode** pphead)//尾删数据
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next->next)
		{
			pcur = pcur->next;
		}
		free(pcur->next);
		pcur->next = NULL;
	}
}


void SLTPopFront(SListNode** pphead)//头删数据
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* pcur = (*pphead);
		*pphead = (*pphead)->next;
		free(pcur);
	}
}


void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)//在指定位置之前插入数据
{
	assert(pphead&&*pphead);
	if (*pphead == pos)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		SListNode* newnode = SLTBuyNode(x);
		pcur->next = newnode;
		newnode->next = pos;
	}
}


void SLTInsertAfter(SListNode* pos, SLTDataType x)//在指定位置之后插入数据
{
	assert(pos);
	SListNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


void SLTErase(SListNode** pphead, SListNode* pos)//删除pos节点
{
	assert(*pphead && pphead);
	assert(pos);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SListNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}


void SLTEraseAfter(SListNode* pos)//删除pos之后的节点
{
	assert(pos && pos->next);
	SListNode* pcur = pos->next;
	pos->next = pos->next->next;
	free(pcur);
	pcur = NULL;	
}

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

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

相关文章

java-数据结构与算法-02-数据结构-01-数组

java-数据结构与算法-02-数据结构-01-数组

文章目录 1. 概述2. 动态数组3. 二维数组4. 局部性原理5. 越界检查6. 习题 1. 概述 定义 在计算机科学中&#xff0c;数组是由一组元素&#xff08;值或变量&#xff09;组成的数据结构&#xff0c;每个元素有至少一个索引或键来标识 In computer science, an array is a dat…
阅读更多...
如何与精益管理咨询公司进行有效的沟通？

如何与精益管理咨询公司进行有效的沟通？

在现代企业管理中&#xff0c;精益管理咨询公司发挥着不可或缺的作用&#xff0c;它们通过提供专业的精益管理咨询服务&#xff0c;帮助企业优化运营流程&#xff0c;提升生产效率&#xff0c;降低成本&#xff0c;实现可持续发展。然而&#xff0c;与精益管理咨询公司进行有效…
阅读更多...
软件测评中心▏软件安全测试的测试方法和注意事项介绍

软件测评中心▏软件安全测试的测试方法和注意事项介绍

软件安全测试是一种重要的测试活动&#xff0c;旨在评估和验证软件系统中潜在的安全风险&#xff0c;并提供可行的解决方案。通过对软件系统进行系统化的测试&#xff0c;可以及时发现和修复安全漏洞&#xff0c;保护软件系统的安全性。 软件安全测试的测试方法可以帮助测试人…
阅读更多...
深度学习500问——Chapter11：迁移学习（4）

深度学习500问——Chapter11：迁移学习（4）

文章目录 11.3.8 流形学习方法 11.3.9 什么是finetune 11.3.10 finetune为什么有效 11.3.11 什么是网络自适应 11.3.12 GAN在迁移学习中的应用 参考文献 11.3.8 流形学习方法 什么是流行学习&#xff1f; 流行学习自从2000年在Science上被提出来以后&#xff0c;就成为了机器…
阅读更多...
ASP.NET Core 中使用 Dapper 的 Oracle 存储过程输出参数

ASP.NET Core 中使用 Dapper 的 Oracle 存储过程输出参数

介绍 Oracle 数据库功能强大&#xff0c;在企业环境中使用广泛。在 ASP.NET Core 应用程序中使用 Oracle 存储过程时&#xff0c;处理输出参数可能具有挑战性。本教程将指导您完成使用 Dapper&#xff08;适用于 . NET 的轻量级 ORM&#xff08;对象关系映射器&#xff09;&am…
阅读更多...
Python数据分析-对驾驶安全数据进行了预测

Python数据分析-对驾驶安全数据进行了预测

一、研究背景和意义 随着汽车保有量的不断增加&#xff0c;交通事故已成为全球范围内的重大公共安全问题。每年因交通事故造成的人员伤亡和财产损失给社会带来了巨大的负担。为了提高驾驶安全&#xff0c;减少交通事故的发生&#xff0c;许多研究致力于探索影响驾驶安全的因素…
阅读更多...
模式分解的概念（上）-分解、无损连接性、保持函数依赖特性

模式分解的概念（上）-分解、无损连接性、保持函数依赖特性

一、分解的概念 1、分解的定义 2、判断一个关系模式的集合P是否为关系模式R的一个分解 只要满足以下三个条件&#xff0c;P就是R的一个分解 &#xff08;1&#xff09;P中所有关系模式属性集的并集是R的属性集 &#xff08;2&#xff09;P中所有不同的关系模式的属性集之间…
阅读更多...
如何通过自定义模块DIY出专属个性化的CSDN主页？一招教你搞定！

如何通过自定义模块DIY出专属个性化的CSDN主页？一招教你搞定！

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 &#x1f4af;如何通过HTMLCSS自定义模板diy出自己的个性化csdn主页&#x…
阅读更多...
本地快速部署大语言模型开发平台Dify并实现远程访问保姆级教程

本地快速部署大语言模型开发平台Dify并实现远程访问保姆级教程

文章目录 前言1. Docker部署Dify2. 本地访问Dify3. Ubuntu安装Cpolar4. 配置公网地址5. 远程访问6. 固定Cpolar公网地址7. 固定地址访问 前言 本文主要介绍如何在Linux Ubuntu系统使用Docker快速部署大语言模型应用开发平台Dify,并结合cpolar内网穿透工具实现公网环境远程访问…
阅读更多...
解决element-plus没有导出的成员FormInstance

解决element-plus没有导出的成员FormInstance

使用element-plus的el-form时&#xff0c;报错“"element-plus"”没有导出的成员“FormInstance”。你是否指的是“FooterInstance”? 解决方法&#xff1a; 引入ElForm类型&#xff0c;在外重新定义FormInstance的类型为ElForm的实例类型 示例&#xff1a; import…
阅读更多...
记录keras库中导入函数找不到的问题

记录keras库中导入函数找不到的问题

1 . keras.preprocessing.text import Tokenizer 将最右边的点 " . " 修改成 " _ " : 2 . 相应函数/库找不到&#xff0c;在keras后面加一个api :
阅读更多...
基于AT32_Work_Bench配置AT32工程

基于AT32_Work_Bench配置AT32工程

基于AT32_Work_Bench配置AT32工程 ✨AT32_Work_Bench工具是用来给AT32 MCU快速构建外设初始化工程软件&#xff0c;类似STM32的STM32CubeMX工具软件。 &#x1f4cd;AT32 TOOL系列工具下载地址&#xff1a;https://www.arterytek.com/cn/support/index.jsp?index4&#x1f3f7…
阅读更多...
C# WPF入门学习主线篇（二十八）—— 使用集合（ObservableCollection）

C# WPF入门学习主线篇（二十八）—— 使用集合（ObservableCollection）

C# WPF入门学习主线篇&#xff08;二十八&#xff09;—— 使用集合&#xff08;ObservableCollection&#xff09; 在WPF中&#xff0c;数据绑定是构建动态和响应式用户界面的关键。ObservableCollection是一个特别有用的集合类型&#xff0c;它不仅支持数据绑定&#xff0c;还…
阅读更多...
基于Elementui组件，在vue中实现多种省市区前端静态JSON数据展示并支持与后端交互功能，提供后端名称label和id

基于Elementui组件，在vue中实现多种省市区前端静态JSON数据展示并支持与后端交互功能，提供后端名称label和id

基于Elementui组件&#xff0c;在vue中实现多种省市区前端静态数据&#xff08;本地JSON数据&#xff09;展示并支持与后端交互功能&#xff0c;提供后端名称label和id 话不多说&#xff0c;先上图 1.支持传递给后端选中省市区的id和名称&#xff0c;示例非常完整&#xff0c…
阅读更多...
【Java】线程池技术（二）ThreadPoolExecutor的基本定义

【Java】线程池技术（二）ThreadPoolExecutor的基本定义

线程池初始化与定义 public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, TimeUnit unit,BlockingQueue<Runnable> workQueue,ThreadFactory threadFactory,RejectedExecutionHandler handler)线程池构造方法的入参含义分别如下&…
阅读更多...
C++的动态内存分配

C++的动态内存分配

使用new/delete操作符在堆中分配/释放内存 //使用new操作符在堆中分配内存int* p1 new int;*p1 2234;qDebug() << "数字是&#xff1a;" << *p1;//使用delete操作符在堆中释放内存delete p1;在分配内存的同时初始化 //在分配内存的时初始化int* p2 n…
阅读更多...
chatgpt: linux 下用纯c 编写一按钮，当按钮按下在一新窗口显示hello world

chatgpt: linux 下用纯c 编写一按钮，当按钮按下在一新窗口显示hello world

用这个程序模板&#xff0c;就可以告别只能在黑框框的终端中编程了。 在 Linux 环境下使用纯 C 语言编写一个按钮&#xff0c;当按钮按下时&#xff0c;在一个新窗口显示 "Hello World"。我们可以使用 GTK 库来实现这个功能。GTK 是一个用于创建图形用户界面的跨平台…
阅读更多...
第三十三篇-Ollama+AnythingLLM基本集成

第三十三篇-Ollama+AnythingLLM基本集成

AnythingLLM AnythingLLM专属私有知识库,可以使用本地OllamaLLM模型&#xff0c;可以上传文件&#xff0c;基于文件回答问题 启动ollama 参考 第二十五篇-Ollama-离线安装 第二十四篇-Ollama-在线安装 下载安装AnythingLLM https://useanything.com/downloadAnythingLLMDe…
阅读更多...
C#使用NPOI库实现Excel的导入导出操作——提升数据处理效率的利器

C#使用NPOI库实现Excel的导入导出操作——提升数据处理效率的利器

文章目录 一、NPOI库简介二、安装与引入三、Excel的导入操作1.CSV格式导入2.XLS格式导入3. XLSX格式导入 四、Excel的导出操作1. CSV格式导出2. XLS格式导出3. XLSX格式导出 五、NPOI库的应用优势与改进方向总结 在日常工作学习中&#xff0c;我们经常需要处理Excel文件&#x…
阅读更多...
【吊打面试官系列-Mysql面试题】什么是锁？

【吊打面试官系列-Mysql面试题】什么是锁？

大家好&#xff0c;我是锋哥。今天分享关于 【什么是锁&#xff1f;】面试题&#xff0c;希望对大家有帮助&#xff1b; 什么是锁&#xff1f; 答&#xff1a;数据库是一个多用户使用的共享资源。当多个用户并发地存取数据时&#xff0c;在数据库中就会产生多个事务同时存取同一…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站