C语言--单链表的创建及使用详解

C语言--单链表的创建及使用详解

  • 1. 单链表定义
    • 1.1 工作原理
    • 1.2 优点
  • 2. 单链表的创建
    • 2.1 文件创建
    • 2.2 节点创建
    • 2.3 链表显示
  • 3. 链表操作
    • 3.1 尾插
    • 3.2 头插
    • 3.3 尾删
    • 3.4 头删
    • 3.5 指定数据寻找
    • 3.6 指定位置前插入
    • 3.7 指定位置删除
  • 4. 单链表总内容
    • 4.1 test.c文件
    • 4.2 SList.h文件
    • 4.3 SList.c文件

1. 单链表定义

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
每个节点只能访问其后继节点，而无法访问前驱节点。链表的头节点是第一个节点，尾节点是最后一个节点，尾节点的指针指向空值。

1.1 工作原理

其工作原理如下图，它每个模块有两个部分组成，前面存放数据，最后存放下一个数据的地址。当我们想要访问下一个节点中的数据的时候，只需要通过前一个数据存放的下一个数据的地址就可以直接进行访问数据。
在数单链表的最前端有一个 plist 的指针，它会一直记录着链表第一个数据的地址，当我们想要访问链表中的数据的时候，只要通过 plist 就可以成功进入到链表当中。而刚开始创建链表的时候，头数据不存在，因而创建的 plist 要初始化为NULL，形式如下：
SLTNode* plist = NULL; //plist为头数据的地址
在这里插入图片描述

1.2 优点

与顺序表相比，单链表内存空间利用率更高，单向链表的每个节点只需要存储数据和指向下一个节点的指针，不需要预先分配固定大小的内存空间，因此可以灵活地利用内存空间，避免了顺序表需要预留固定大小的问题。

2. 单链表的创建

2.1 文件创建

为方便代码管理，将文件内容分为三个文件来共同组成单链表，如下：

test.c //用于⽂件中单链表的逻辑测试  
SList.c //⽂件中写单链表中函数的实现等 
SList.h //⽂件中写单链表需要的数据类型和函数声明等

为了方便后期对单链表中数据及数据类型的修正，可以将数据类型等信息进行宏定义，如下所示：

typedef int SLTDataType;//定义数据类型
struct  SListNode//创建单链表
{
	SLTDataType data;//保存数据
	struct SListNode* next;//指向下一个数据的位置
};

typedef struct SListNode SLTNode;//定义结构体名称

SLTNode* plist = NULL;//plist为头数据的地址

在数据放入创建的链表之前，单链表的所有内容为空，在物理意义上是不存在的，其首地址的数据地址是不存在的，只有当放入数据之后，才会存在地址。因而，头数据的地址的创建如下所示：

SLTNode* plist = NULL;//plist为头数据的地址

2.2 节点创建

如果要插入数据，要么首先要开辟一块新的链表数据块，也就是创建一个结构体类型的数据，用一个 newnode 的指针保存其起始位置的地址，其指向下一个数据的指针置空，此时只是创建，并无下一个数据的链接。

在这里插入图片描述
代码实现如下：

SLTNode* BuySListNode(SLTDataType x)
{

	SLTNode* newcode = (SLTNode*)malloc(sizeof(SLTNode));
	newcode->data = x;
	newcode->next = NULL;
	return newcode;
}

先用 malloc 开辟一个结构体类型的空间，用 newnode 来接收其起始位置，之后将需要保存的数据放到newnode 的 data 当中，next 置空，然后再返回 newnode 的地址，这样，一个链表块就创建完毕。

需要注意的是，因为我们要返回的是 newnode 的地址，因而创建的开辟函数的数据类型是 SLTNode* 类型，即结构体指针类型。

2.3 链表显示

用形参 phead 来接收整个链表的头地址 plist 的值，通过 phead 来访问显示链表中的数据。
代码如下：

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

注意以下几点：

  1. 创建临时变量 cur 接收 phead 的地址（也可以直接通过 phead 进行操作）
  2. 因为最后一个数据的指针是置空的，因而结束的标志是访问的数据块里面 next 指向的地址为NULL。
    在这里插入图片描述
  3. cur 通过将自己的地址改为 cur 里面 next 里面保存的地址来达到指向下一个数据的目的。
  4. 最后最好打印一个 NULL,避免链表为空时，什么都不执行，不好判断是否出错。

3. 链表操作

3.1 尾插

在链表尾部插入一个数据块时，要先找到最后一个数据块，然后将最后一个数据块的 next 由置空改为指向新创建的数据块的首地址，如图所示。
在这里插入图片描述
代码如下：

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newcode=BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newcode;
	}
	else
	{
		//找尾节点的指针
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//尾节点，链接新节点
		tail->next = newcode;
	}
}

注意以下几点：

  1. 函数的变量一定要将链表的首地址的地址传递过去，也就是SLTNode** pphead是二级指针，不再是直接使用 phead 这个一级指针。因为当链表为空的时候，往链表里面放数据之后，链表首地址 plist 应该改为指向新数据的首地址，而不再应该是被置空。而函数中是对形参 phead 进行操作，出函数之后，phead 的内容将被清除，实参 pliast 将依然指向NULL。如果不考虑数据为空的情况，那依然可以只传递 phead 过去，只对其所指的内容进行修改。以上情况适用于后面的其他操作。
  2. 创建临时变量 newnode 来接收新开辟的数据块的起始地址.
  3. 当链表为空的时候，此时链表的头位置也为空，此时只需要直接将 newnode 的地址传递给整个链表的起始地址 plist 即可，即传递给 *pphead.
  4. 通过和链表显示一样的操作找到尾节点，将尾节点的 next 指向 newnode 便可以完成链接。

3.2 头插

头插只需要将整个链表的头地址改为新的数据块的地址，再将数据块的 next 指向之前的头地址，便可以完成链接，需要注意与尾插的注意一相同的问题即可，如下同。
在这里插入图片描述
代码如下：

void SListPushFont(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newcode = BuySListNode(x);
	newcode->next = *pphead;
	*pphead = newcode;
}

3.3 尾删

删除尾部数据块 tail 时，需要先找到倒数第二的数据块的地址 prev ，将倒数第二的数据块 prev 的 next 置空，然后将最后一个数据块 tail 释放掉，过程如下图：

void SListPophBack(SLTNode** pphead)
{
	//1、空的时候
	if (*pphead == NULL)
	{
		return;
	}
	//2、只有一个节点
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//3、一个以上的节点
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

注意以下几点：

  1. 当链表为空的时候，直接返回，不做任何操作。
  2. 当判断链表只有一个节点的时候，直接释放链表数据，然后置空。
  3. 当链表有多个数据的时候，找到倒数第二个数据，改变链接，释放最后一个数据。
  4. 注意与头插注意一相同的问题。

3.4 头删

头部删除只需要将整个链表首地址改为第一块数据块指向的 next 即可，仍旧需要主要传值问题。
代码如下：
在这里插入图片描述

void SListPopFront(SLTNode** pphead)
{
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

3.5 指定数据寻找

寻找指定的数据时，我们只是对数据进行查阅，不会更改首地址 plist 的地址，因而只需要使用phead 进行操作。从第一个数据开始寻找，如果找到了，就返回数据的地址，如果到尾了仍旧没有，则直接返回NULL，表示所寻找的数据不存在。
代码如下：

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

3.6 指定位置前插入

在指定位置 pos 前面插入一个数据，需要把指定数据的位置地址传进去。考虑到链表可能为空的情况，因而要使用二级指针 pphead 。用 prev 来寻找指定位置 pos 的前一个节点,找到之后，将 prev 的 next 指向新开辟的 newnode ,将 newnode 的 next 指向 pos ，这样就i完成了链接，如下图。
在这里插入图片描述

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (pos ==* pphead)
	{
		SListPushFont(pphead,x);
	}
	else
	{
		SLTNode* newcode = BuySListNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newcode;
		newcode->next = pos;
	}
}

使用案例：

	SLTNode* pos = SListFind(plist, 3);
	if (pos)
	{
		SListInsert(&plist, pos, 30);

	}
	SListPrint(plist);

3.7 指定位置删除

在指定位置 pos 前面插入一个数据，需要把指定数据的位置地址传进去。考虑到链表可能为空的情况，因而要使用二级指针 pphead 。如果第一个数据就是指定数据，则直接使用头删，如果不是，仍旧需要找到指定数据 pos 的前一个数据，将pos 前一个数据和 pos 的后一个数据链接起来，过程与指定位置插入相似。。

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
	}
}

4. 单链表总内容

4.1 test.c文件

测试文件，可根据自己需要添加内容。

//test.c文件
#define  _CRT_SECURE_NO_WARNINGS

#include "SList.h"

void TestSList1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPophBack(&plist);
	SListPopFront(&plist);
	SListPushFont(&plist, 0);
	SListPrint(plist);
}

void TestSList2()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	SLTNode* pos = SListFind(plist, 3);
	if (pos)
	{
		SListInsert(&plist, pos, 30);

	}
	SListPrint(plist);
}


int main()
{
	TestSList2();

	return 0;
}

当前 test.c 文件演示效果：
在这里插入图片描述

4.2 SList.h文件

函数声明文件，用于结构体和宏定义。

#define  _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


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

typedef struct SListNode SLTNode;

//不会改变链表的头指针，传一级指针
SLTNode* BuySListNode(SLTDataType x);

void SListPrint(SLTNode* phead);

//会改变链表的头指针，传二级指针
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPushFont(SLTNode** pphead, SLTDataType x);
void SListPopFront(SLTNode** pphead);
void SListPophBack(SLTNode** pphead);

SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);

4.3 SList.c文件

函数定义文件，用于定义函数。

#define  _CRT_SECURE_NO_WARNINGS
#include "SList.h" 

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SLTNode* BuySListNode(SLTDataType x)
{

	SLTNode* newcode = (SLTNode*)malloc(sizeof(SLTNode));
	newcode->data = x;
	newcode->next = NULL;
	return newcode;
}

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newcode=BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newcode;
	}
	else
	{
		//找尾节点的指针
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		//尾节点，链接新节点
		tail->next = newcode;
	}
}

void SListPushFont(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newcode = BuySListNode(x);
	newcode->next = *pphead;
	*pphead = newcode;
}

void SListPopFront(SLTNode** pphead)
{
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
void SListPophBack(SLTNode** pphead)
{
	//1、空的时候
	if (*pphead == NULL)
	{
		return;
	}
	//2、只有一个节点
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//3、一个以上的节点
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}


SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (pos ==* pphead)
	{
		SListPushFont(pphead,x);
	}
	else
	{
		SLTNode* newcode = BuySListNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newcode;
		newcode->next = pos;
	}
}
//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
	}
}

好了，今天的分享就到这里了，欢迎大家留言评论。

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

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

相关文章

canvas设置圆锥形渐变

canvas设置圆锥形渐变

查看专栏目录 canvas示例教程100专栏&#xff0c;提供canvas的基础知识&#xff0c;高级动画&#xff0c;相关应用扩展等信息。canvas作为html的一部分&#xff0c;是图像图标地图可视化的一个重要的基础&#xff0c;学好了canvas&#xff0c;在其他的一些应用上将会起到非常重…
阅读更多...
2024年Flag

2024年Flag

管理自己 2024年是一个科技迅速发展的时期&#xff0c;作为一个技术人员&#xff0c;我将有很多事情要做。在这一年里&#xff0c;我计划立下以下几个flag&#xff0c;来提升自己的技术能力。 学习人工智能和机器学习 首先&#xff0c;我计划深入学习人工智能和机器学习。随着…
阅读更多...
在线的货币兑换平台源码下载

在线的货币兑换平台源码下载

在线的货币兑换平台&#xff0c;可帮助全球各地的个人和企业将货币从一种货币兑换为另一种货币。该货币兑换平台是 Codecanyon 中最先进的脚本。 源码下载&#xff1a;https://download.csdn.net/download/m0_66047725/88728084
阅读更多...
js中try...catch捕捉错误

js中try...catch捕捉错误

文章目录 一、前言二、场景2.1、setTimeout2.2、Promise 三、最后 一、前言 说到try...catch都觉得非常熟悉了&#xff0c;不就是用来捕捉代码块中的错误嘛&#xff0c;平时也用得比较多的 二、场景 try...catch只能捕捉到同步执行代码块中的错误 2.1、setTimeout try {setT…
阅读更多...
【LabVIEW FPGA入门】没有CompactRIO时进行编程测试

【LabVIEW FPGA入门】没有CompactRIO时进行编程测试

1.新建一个空白项目。 2.新建cRIO终端。 要添加仿真的远程实时目标&#xff0c;请选择项目名称&#xff0c;右击并选择新建>>目标和设备(Targets and Devices)。 3.新建终端和设备&#xff0c;选一个cRIO型号 接下来&#xff0c;当添加目标和设备窗口出现时&#xff0c;请…
阅读更多...
第 2 课 ROS 系统安装和环境搭建

第 2 课 ROS 系统安装和环境搭建

第 2 课 ROS 系统安装和环境搭建 1.版本选择 不同的 Ubuntu 安装的 ROS 版本不同&#xff0c;其中 Ubuntu18.04 的 ROS 对应版本为Melodic。 Ubuntu版本ROS版本Ubuntu16.04KineticUbuntu18.04MelodicUbuntu20.04Noetic 2.检查 Ubuntu 的软件和更新源 找到系统中的“软件和…
阅读更多...
Python+Django+MySQL的图书馆管理系统【附源码，运行简单】

Python+Django+MySQL的图书馆管理系统【附源码，运行简单】

PythonDjangoMySQL的图书馆管理系统【附源码&#xff0c;运行简单】 总览 1、《图书馆管理系统》1.1 方案设计说明书设计目标需求分析工具列表 2、详细设计2.1 登录2.2 注册2.3 程序主页面2.4 图书新增界面2.5 图书信息修改界面2.6 其他功能贴图 3、下载 总览 自己做的项目&am…
阅读更多...
mysql从入门到放弃之数据库体系结构与管理

mysql从入门到放弃之数据库体系结构与管理

文章目录 前言一、体系结构1、mysql c/s结构介绍2、mysql实例组成3、mysqld程序运行原理3.1、mysqld守护进程结构3.2、 引入sql语句结构化的查询语言3.3、探索一条SQL语句的执行过程 二、mysql逻辑存储结构三、mysql物理存储结构3.1、innodb存储引擎的段、区、页之间的关系 四、…
阅读更多...
YZ虚拟资源下载源码-支持对接公众号-对接支付

YZ虚拟资源下载源码-支持对接公众号-对接支付

这款系统内置的模板是电脑系统下载站的类型&#xff0c;当然你也可以用作其他类型&#xff0c;例如软件下载&#xff0c;其他类型的资源下载&#xff0c;知识付费下载等&#xff0c;改下文字内容即可。 支持商城系统&#xff0c;后台可配置支付。青狐修改增加了很多可用性。 …
阅读更多...
C++学习笔记（十九）

C++学习笔记（十九）

一、vector容器 1. vector基本概念 功能&#xff1a;vector数据结构和数组非常相似&#xff0c;也称为单端数组 vector与普通数组区别&#xff1a;不同之处在于数组是静态空间&#xff0c;而vector可以动态扩展 动态扩展&#xff1a;并不是在原空间之后续接新空间&#xff…
阅读更多...
VMware 安装及创建一个 CentOS Stream 的详细指南

VMware 安装及创建一个 CentOS Stream 的详细指南

文章目录 1. 简介2. 下载和安装1&#xff09;通过官网安装2&#xff09;通过电脑管家安装 3. 下载操作系统镜像包4. 创建虚拟机结语 1. 简介 在过去&#xff0c;服务器通常是运行单一操作系统和应用程序的物理设备。这就导致了硬件资源浪费和管理复杂性的增加。为了解决这些问…
阅读更多...
注册中心--zookeeper 安装并启动

注册中心--zookeeper 安装并启动

zookeeper 安装/启动 注册中心--zookeeper安装步骤zookeeper常用命令 注册中心–zookeeper zookeeper官方下载地址 最早由雅虎开发&#xff0c;用来解决分布式系统中的一致性问题。功能&#xff1a;包括配置管理、集群的扩容和缩容、分布式锁等等。 安装步骤 1&#xff09;…
阅读更多...
C++学习笔记（二十八）：c++ 静态库及动态库的使用

C++学习笔记（二十八）：c++ 静态库及动态库的使用

静态库的使用 库的使用会很大程度减少我们的工作&#xff0c;本节对c中静态库和动态库的使用进行简单的介绍。静态链接库意味着这个库会被放到可执行文件中&#xff0c;在生成的exe中。动态链接库是在程序运行时链接的&#xff0c;可以在程序运行时调用加载库函数的方法来实现&…
阅读更多...
Java项目：07 Springboot的客户管理系统

Java项目：07 Springboot的客户管理系统

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 springboot客户管理系统 功能模块&#xff1a;登录修改密码客户列表充值列表消费记录客户类型 环境&#xff1a;IDEAjdk1.8Tomcat9MySQL5.7maven3.6…
阅读更多...
基于Matlab/Simulink开发自动驾驶的解决方案

基于Matlab/Simulink开发自动驾驶的解决方案

文章目录 处理自动驾驶数据 仿真自动驾驶场景 设计感知算法 设计规划和控制算法 生成代码和部署算法 集成和测试 参考文献 使用 MATLAB/Simulink开发自动驾驶&#xff0c;能够深入建模真实世界的行为、减少车辆测试并验证嵌入式软件的功能&#xff0c;从而推进自动驾驶感…
阅读更多...
linux安装系统遇到的问题

linux安装系统遇到的问题

这两天打算攻克下来网络编程&#xff0c;发现这也确实是很重要的一个东西&#xff0c;但我就奇了怪了&#xff0c;老师就压根没提&#xff0c;反正留在我印象的就一个tcp/ip七层网络。也说正好&#xff0c;把linux命令也熟悉熟悉&#xff0c;拿着我大一课本快速过过 连接cento…
阅读更多...
AI大模型学习笔记一

AI大模型学习笔记一

一、商业观点&#xff1a;企业借助大模型获得业务增长可能 二、底层原理&#xff1a;transformer 1&#xff09;备注 ①下面每个步骤都是自回归的过程&#xff08;aotu-regressive&#xff09;&#xff1a;已输出内容的每个字作为输入&#xff0c;一起生成下一个字 ②合起来就…
阅读更多...
服务器IP如何隐藏

服务器IP如何隐藏

说到 IP 地址&#xff0c;它足以作为服务器的定位标志&#xff0c;算是在互联网上的名片。因此&#xff0c;当一些黑客攻击服务器时&#xff0c;IP 地址便会成为首要目标。为保护服务器避免受到潜在的攻击和侦察&#xff0c;隐藏服务器的真实 IP 地址是一项重要的措施。 服务器…
阅读更多...
花了三天的时间做了一个多功能 AI 助手

花了三天的时间做了一个多功能 AI 助手

嗨&#xff01;我是团子&#xff0c;大家新年快乐呀~ 前几天看到一些好朋友在朋友圈晒自己的年度总结&#xff0c;立新年 Flag&#xff0c;看到大家一年满满的收获&#xff0c;再看看自己&#xff0c;不由得想再看看人家&#xff0c;然后再看看自己&#xff0c;然后再看看人家…
阅读更多...
Android-基础

Android-基础

Activity生命周期 1.启动Activity&#xff1a;系统会先调用onCreate方法&#xff0c;然后调用onStart方法&#xff0c;最后调用onResume&#xff0c;Activity进入运行状态。 2.当前Activity被其他Activity覆盖其上或被锁屏&#xff1a;系统会调用onPause方法&#xff0c;暂停当…
阅读更多...
最新文章

Copyright @ 2022~2023