数据结构篇2—《单链表(不带头单向不循环链表)》

在这里插入图片描述

文章目录

  • 🚩前言
    • 1、单链表的内涵
      • (1) 逻辑结构
      • (2) 物理结构
    • 2、链表的分类
    • 3、单链表的具体实现
      • (1) 框架结构
      • (2) SingleLinkList.h头文件的实现
      • (3)SingleLinkList.c源文件的实现
        • ①SLTPushBack()尾插函数
        • ②SLTPushFront()头插函数
        • ③SLTPopBack()尾删函数
        • ④SLTPopFront()头删函数
        • ⑤SLTInsert()和SLTInsertAfter()指定位置之前和之后插入数据函数
        • ⑥SLTErase()和SLTDestroy()删除和销毁函数
    • 4、完整代码
    • 5、效果展示

🚩前言

在数据结构中主要的就是对数据的增删查改操作，在前面讲的顺序表就是其中一种结构，顺序表前身的数组（静态和动态）。而该结构是叫单链表，从逻辑结构上看是连续的，而在物理结构上是不连续存储的。下面就来对单链表的具体实现：

1、单链表的内涵

(1) 逻辑结构

什么叫作逻辑结构上是连续的，而物理结构上是不连续的。首先，在一个连续的空间当中就是连续存储，反之就不是，但是从我们思维结构来看可以当做是连续的，下面是单链表的逻辑结构：
在这里插入图片描述

(2) 物理结构

物理结构上就得从计算机内存中来看，就是在一个内存块中，每个节点所开辟的空间位置不是紧挨着的，存在一定距离，如下简图：
在这里插入图片描述

2、链表的分类

链表的种类比起顺序表就多了，顺序表就是静态和动态。而链表主要从带不带头、单向还是双向、循不循环三个点来分类，如下：
在这里插入图片描述

比如 ：不带头单向不循环->单链表
不带头双向循环链表
带头单向循环链表等等。最常见的就是单链表和带头双向循环链表。

3、单链表的具体实现

(1) 框架结构

在这里插入图片描述

(2) SingleLinkList.h头文件的实现

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

//创建单链表结构体
typedef int DataType;
typedef struct SingLinkListNode
{
	DataType data;
	struct SingLinkListNode *next;
}SLTNode;

//打印函数
void PrintLinkList(SLTNode *phead);

//尾插
void SLTPushBack(SLTNode **pphead,DataType data);

//头插
void SLTPushFront(SLTNode **pphead,DataType data);

//尾删
void SLTPopBack(SLTNode **pphead);

//头删
void SLTPopFront(SLTNode **pphead);

//查找
SLTNode* SLTFind(SLTNode *phead,DataType data);

//指定位置之前插入数据
void SLTInsert(SLTNode **pphead,SLTNode *pos,DataType data);

//指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, DataType data);

//删除节点函数
void SLTErase(SLTNode** pphead,SLTNode* pos);

//销毁链表函数
void SLTDestroy(SLTNode** pphead);

(3)SingleLinkList.c源文件的实现

①SLTPushBack()尾插函数
SLTNode* BuyNode(DataType x)
{
	SLTNode *NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (NewNode == NULL)
	{
		perror("BuyNode:: malloc fail!");
		exit(1);
	}
	else
	{
		NewNode->data = x;
		NewNode->next = NULL;
	}
	return NewNode;
}

void SLTPushBack(SLTNode **pphead, DataType data)
{
	assert(pphead);
	SLTNode *NewNode=BuyNode(data);
	if ((*pphead) == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		//找尾
		SLTNode *ptail = *pphead;
		while (ptail->next!=NULL)
		{
			ptail = ptail->next;
		}
		ptail->next = NewNode;
	}
}

图解：尾插数据得申请新节点BuyNode();
在这里插入图片描述

②SLTPushFront()头插函数
void SLTPushFront(SLTNode **pphead, DataType data)
{
	assert(pphead);
	SLTNode *NewNode = BuyNode(data);
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		NewNode->next = *pphead;
		*pphead = NewNode;
	}
}

图解：
在这里插入图片描述

③SLTPopBack()尾删函数
void SLTPopBack(SLTNode **pphead)
{
	assert(pphead&&(*pphead)->data);
	SLTNode* prev = NULL;
	SLTNode* ptail = *pphead;
	//当只有一个节点的时候
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾节点
		while ((ptail->next)!=NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

图解：
在这里插入图片描述

④SLTPopFront()头删函数
void SLTPopFront(SLTNode **pphead)
{
	assert(pphead && *pphead);
	SLTNode *pcur = (*pphead)->next;
	free(*pphead);
	*pphead = pcur;
}

图解：头删很简单。
在这里插入图片描述

⑤SLTInsert()和SLTInsertAfter()指定位置之前和之后插入数据函数
void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType data)
{
	assert(pphead && pos);
	SLTNode* NewNode = BuyNode(data);
	SLTNode* prev = *pphead;
	//当插入的数据节点是头节点时就调用头插
	if (pos == *pphead)
	{
		SLTPushFront(pphead,data);
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = NewNode;
		NewNode->next = pos;
	}
}

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, DataType data)
{
	assert(pphead && pos);
	//SLTNode* pcur = *pphead;
	SLTNode* NewNode = BuyNode(data);
	//pcur = pos->next;
	//pos->next = NewNode;
	//NewNode->next = pcur;
	NewNode->next = pos->next;
	pos->next = NewNode;
}

图解：
在这里插入图片描述

⑥SLTErase()和SLTDestroy()删除和销毁函数
//删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && pos);
	SLTNode* prev = *pphead;
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//销毁
void SLTDestroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

在销毁的时候得注意，因为节点是一个一个创建的，所以也得一个一个的销毁。

4、完整代码

1、头文件

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

//创建单链表结构体
typedef int DataType;
typedef struct SingLinkListNode
{
	DataType data;
	struct SingLinkListNode *next;
}SLTNode;

//打印函数
void PrintLinkList(SLTNode *phead);

//尾插
void SLTPushBack(SLTNode **pphead,DataType data);

//头插
void SLTPushFront(SLTNode **pphead,DataType data);

//尾删
void SLTPopBack(SLTNode **pphead);

//头删
void SLTPopFront(SLTNode **pphead);

//查找
SLTNode* SLTFind(SLTNode *phead,DataType data);

//指定位置之前插入数据
void SLTInsert(SLTNode **pphead,SLTNode *pos,DataType data);

//指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, DataType data);

//删除节点函数
void SLTErase(SLTNode** pphead,SLTNode* pos);

//销毁链表函数
void SLTDestroy(SLTNode** pphead);

2、源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SingleLinkList.h"


void PrintLinkList(SLTNode *phead)
{
	// assert(phead&&phead->next);
	SLTNode *pcur = phead;
	while (pcur != NULL)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL");
}

SLTNode* BuyNode(DataType x)
{
	SLTNode *NewNode = (SLTNode*)malloc(sizeof(SLTNode));
	if (NewNode == NULL)
	{
		perror("BuyNode:: malloc fail!");
		exit(1);
	}
	else
	{
		NewNode->data = x;
		NewNode->next = NULL;
	}
	return NewNode;
}

void SLTPushBack(SLTNode **pphead, DataType data)
{
	assert(pphead);
	SLTNode *NewNode=BuyNode(data);
	if ((*pphead) == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		//找尾
		SLTNode *ptail = *pphead;
		while (ptail->next!=NULL)
		{
			ptail = ptail->next;
		}
		ptail->next = NewNode;
	}
}

void SLTPushFront(SLTNode **pphead, DataType data)
{
	assert(pphead);
	SLTNode *NewNode = BuyNode(data);
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		NewNode->next = *pphead;
		*pphead = NewNode;
	}
}

void SLTPopBack(SLTNode **pphead)
{
	assert(pphead&&(*pphead)->data);
	SLTNode* prev = NULL;
	SLTNode* ptail = *pphead;
	//当只有一个节点的时候
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾节点
		while ((ptail->next)!=NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

void SLTPopFront(SLTNode **pphead)
{
	assert(pphead && *pphead);
	SLTNode *pcur = (*pphead)->next;
	free(*pphead);
	*pphead = pcur;
}

SLTNode* SLTFind(SLTNode *phead, DataType data)
{
	assert(phead);
	SLTNode *pcur = phead;
	while (pcur)
	{
		if (pcur->data == data)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType data)
{
	assert(pphead && pos);
	SLTNode* NewNode = BuyNode(data);
	SLTNode* prev = *pphead;
	//当插入的数据节点是头节点时就调用头插
	if (pos == *pphead)
	{
		SLTPushFront(pphead,data);
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = NewNode;
		NewNode->next = pos;
	}
}

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, DataType data)
{
	assert(pphead && pos);
	//SLTNode* pcur = *pphead;
	SLTNode* NewNode = BuyNode(data);
	//pcur = pos->next;
	//pos->next = NewNode;
	//NewNode->next = pcur;
	NewNode->next = pos->next;
	pos->next = NewNode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && pos);
	SLTNode* prev = *pphead;
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

void SLTDestroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

3、测试代码文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SingleLinkList.h"

void test()
{
	SLTNode* sl=NULL;

	//尾插函数测试
	SLTPushBack(&sl, 1);
	SLTPushBack(&sl, 2);
	SLTPushBack(&sl, 3);
	SLTPushBack(&sl, 4);
	//打印
	PrintLinkList(sl);
	printf("\n");

	//头插函数测试
	SLTPushFront(&sl, 10);
	SLTPushFront(&sl, 20);
	SLTPushFront(&sl, 30);
	//打印
	PrintLinkList(sl);
	printf("\n");

	//尾删函数测试
	SLTPopBack(&sl);
	SLTPopBack(&sl);
	//打印
	PrintLinkList(sl);
	printf("\n");


	//头删函数测试
	SLTPopFront(&sl);
	SLTPopFront(&sl);
	//打印
	PrintLinkList(sl);

	//查找函数测试
	int number = 0;
	printf("\n请输入要查找的数：");
	scanf("%d",&number);
	if (SLTFind(sl, number) == NULL)
	{
		printf("没找到！\n");
	}
	else
	{
		printf("找到了！%p\n", SLTFind(sl, number));
	}

	//在一节点之前插入数据函数测试
	int number1 = 0;
	int number2 = 0;
	printf("请输入要在那个节点之前插入数据：");
	scanf("%d",&number1);
	printf("请输入要插入的数据：");
	scanf("%d",&number2);
	SLTInsert(&sl,SLTFind(sl,number1),number2);
	//打印
	PrintLinkList(sl);
	printf("\n");

	//在一节点之后插入数据函数测试
	int number3 = 0;
	int number4 = 0;
	printf("请输入要在那个节点之后插入数据：");
	scanf("%d", &number3);
	printf("请输入要插入的数据：");
	scanf("%d", &number4);
	SLTInsertAfter(&sl, SLTFind(sl, number3), number4);
	//打印
	PrintLinkList(sl);
	printf("\n");

	//删除节点函数测试
	int number5 = 0;
	printf("请输入要删除的节点的数据：");
	scanf("%d",&number5);
	SLTErase(&sl,SLTFind(sl,number5));
	PrintLinkList(sl);
	printf("\n");

	//销毁函数测试
	SLTDestroy(&sl);
}

int main()
{
	test();
	return 0;
}

5、效果展示

在这里插入图片描述
在这里插入图片描述

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

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

相关文章

高效管理—影视管理系统_后台源码+APP源码+电影数据

高效管理—影视管理系统_后台源码+APP源码+电影数据

高效管理—影视管理系统 产品概述产品展示演示地址产品功能产品优势产品服务源码领取下期更新预报 产品概述 本产品是一个功能强大且易于使用的影视资源管理工具&#xff0c;它提供了一个集中管理和组织电影、电视剧、纪录片等影视作品的平台&#xff0c;帮助用户高效地管理和…
阅读更多...
easyExcel - 带图片导出

easyExcel - 带图片导出

目录 前言一、情景介绍二、问题分析三、代码实现1. 单图片导出2. 多图片导出3. 多图片导出&#xff08;优化&#xff09; 前言 Java-easyExcel入门教程&#xff1a;https://blog.csdn.net/xhmico/article/details/134714025 之前有介绍过如何使用 easyExcel&#xff0c;以及写…
阅读更多...
中间件之异步通讯组件RabbitMQ入门

中间件之异步通讯组件RabbitMQ入门

一、概述 微服务一旦拆分&#xff0c;必然涉及到服务之间的相互调用&#xff0c;目前我们服务之间调用采用的都是基于OpenFeign的调用。这种调用中&#xff0c;调用者发起请求后需要等待服务提供者执行业务返回结果后&#xff0c;才能继续执行后面的业务。也就是说调用者在调用…
阅读更多...
【星海随笔】windows 上跑MySQL

【星海随笔】windows 上跑MySQL

step one 使用 WSL 在 Windows 上安装 Linux wsl官方文档 在管理员模式下打开 PowerShell windows上安装wsl wsl --install查看哪些是可用的 wsl --list --onlineC:\Windows\System32\drivers\hosts docker-desktop下载官网&#xff1a;Install Docker Desktop on Windows …
阅读更多...
[ log日志画图]分割模型训练结束生成相关日志运用代码画图

[ log日志画图]分割模型训练结束生成相关日志运用代码画图

文章目录 [ log日志画图]分割模型训练结束生成相关日志运用代码画图我的log文件&#xff1a;画图&#xff1a;1.loss1.1 loss是干嘛的1.2 代码1.3 生成图 2.DICE.IOU2.1 DICE,IOU是干嘛的(常规介绍)2.2 代码2.3 生成图小白tip [ log日志画图]分割模型训练结束生成相关日志运用代…
阅读更多...
ROS1快速入门学习笔记 - 12ROS中的坐标管理系统

ROS1快速入门学习笔记 - 12ROS中的坐标管理系统

目录 一、机器人作中的坐标变换 二、海龟案例 一、机器人作中的坐标变换 TF功能包能干什么&#xff1f; 五秒钟之前&#xff0c;机器人头部坐标系相对于全局坐标系的关系是什么样子的&#xff1f;机器人夹取的物体i相对于机器人中心坐标系的位置在哪里&#xff1f;机器人中心…
阅读更多...
Linux 第十七章

Linux 第十七章

&#x1f436;博主主页&#xff1a;ᰔᩚ. 一怀明月ꦿ ❤️‍&#x1f525;专栏系列&#xff1a;线性代数&#xff0c;C初学者入门训练&#xff0c;题解C&#xff0c;C的使用文章&#xff0c;「初学」C&#xff0c;linux &#x1f525;座右铭&#xff1a;“不要等到什么都没有了…
阅读更多...
【触摸案例-控件不能响应的情况 Objective-C语言】

【触摸案例-控件不能响应的情况 Objective-C语言】

一、接下来，我们来说这个“控件不能响应的情况”， 1.素材里边，有一个“不接受用户交互的情况”，这么一个代码，把它打开， 把这个项目啊，复制过来，改一个名字，叫做“04-控件不能响应的情况”， 打开之后，command + R，运行一下， 在storyboard上，你也可以看得出来，我…
阅读更多...
Python绘制的好看统计图

Python绘制的好看统计图

代码 sx [Accent, Accent_r, Blues, Blues_r, BrBG, BrBG_r, BuGn, BuGn_r, BuPu, BuPu_r, CMRmap, CMRmap_r, Dark2, Dark2_r, GnBu, GnBu_r, Greens, Greens_r, Greys, Greys_r, OrRd, OrRd_r, Oranges, Oranges_r, PRGn, PRGn_r, Paired, Paired_r, Pastel1, Pastel1_r, P…
阅读更多...
C++ 多态详解

C++ 多态详解

文章目录 1. 多态的概念2. 多态的定义及实现2.1 多态的构成条件2.2 虚函数2.3 虚函数的重写2.3.1 虚函数重写的两个例外 2.4 C11 override 和 final2.5 重载、覆盖(重写)、隐藏(重定义)的对比 3. 多态的原理3.1 虚函数表3.2多态的原理 4. 单继承和多继承关系的虚函数表4.1 单继…
阅读更多...
C++Day 7 作业

C++Day 7 作业

1、lambda #include <iostream>using namespace std;int main() {int a 100;int b 90;int temp;auto fun [&]()mutable->int {temp a;ab;btemp;};fun();cout<<a<<endl;return 0; } 2、vector #include <iostream> #include <vector>…
阅读更多...
python安卓自动化pyaibote实践------学习通自动刷课

python安卓自动化pyaibote实践------学习通自动刷课

前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 本文是一个完成一个自动播放课程&#xff0c;避免人为频繁点击脚本的构思与源码。 加油&#xff01;为实现全部电脑自动化办公而奋斗&#xff01; 为实现摆烂躺平的人生而奋斗&#xff01;&#xff01;&#xff…
阅读更多...
python项目入门新手攻略

python项目入门新手攻略

最近工作需要接手了代码量比较大的python开发的项目&#xff0c;平时写python不多&#xff0c;记录一下如何熟悉项目。 分析调用流程-pycallgraph 因为代码量比较大&#xff0c;所以希望通过工具生成代码调用流程&#xff0c;因此用到了pycallgraph。 pycallgraph&#xff0…
阅读更多...
翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深度学习三

翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深度学习三

合集 ChatGPT 通过图形化的方式来理解 Transformer 架构 翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深度学习一翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深度学习二翻译: 什么是ChatGPT 通过图形化的方式来理解 Transformer 架构 深…
阅读更多...
56.基于SSM实现的在线教育网站系统（项目 + 论文）

56.基于SSM实现的在线教育网站系统（项目 + 论文）

项目介绍 本站是一个B/S模式系统&#xff0c;采用Java的SSM框架作为开发技术&#xff0c;MYSQL数据库设计开发&#xff0c;充分保证系统的稳定性。系统具有界面清晰、操作简单&#xff0c;功能齐全的特点&#xff0c;使得基于SSM的在线教育网站的设计与实现管理工作系统化、规范…
阅读更多...
Scikit-Learn回归树

Scikit-Learn回归树

Scikit-Learn回归树 1、决策树1.1、什么是决策树1.2、决策树学习的步骤1.3、决策树算法 1、决策树 决策树&#xff08;DTs&#xff09;是一种用于回归和分类的有监督学习方法。通常&#xff0c;决策树用于分类问题&#xff1b;当决策树用于回归问题时&#xff0c;称为回归树。回…
阅读更多...
Midjourney之绘画背景的选择

Midjourney之绘画背景的选择

hello 小伙伴们&#xff0c;我是你们的老朋友——树下&#xff0c;今天分享Midjourney提示词中绘画背景的选择&#xff0c;话不多说&#xff0c;直接开始~ 对于背景的选择&#xff0c;Midjourney中主要体现在年代和所处的环境对绘画产生不同的影响 科技的发展&#xff0c;我们…
阅读更多...
matlab学习006-使用matlab绘出系统的冲激响应和阶跃响应波形并求其冲激响应的数值解

matlab学习006-使用matlab绘出系统的冲激响应和阶跃响应波形并求其冲激响应的数值解

目录 题目 1&#xff0c;绘出系统的冲激响应和阶跃响应波形 1&#xff09;基础 2&#xff09;效果 3&#xff09;代码 2&#xff0c;求出t0.5s,1s,1.5s,2s时系统冲激响应的数值解。 1&#xff09;基础 2&#xff09;效果 ​☀ 3&#xff09;代码 题目 已知描述某连续系…
阅读更多...
【Python】Anaconda 使用笔记

【Python】Anaconda 使用笔记

文章目录 一、创建环境1.1 在任意磁盘中创建环境1.2 添加环境路径envs_dirs 二、安装和使用Python环境三、删除已有的Python环境 前言   笔者使用Python的目的主要是为了学习神经网络等深度学习算法。但是在学习之初配置环境的时候发现之前的环境配置一团乱麻&#xff0c;不仅…
阅读更多...
Mybatis进阶（动态SQL）

Mybatis进阶（动态SQL）

文章目录 1.动态SQL1.基本介绍1.为什么需要动态SQL2.基本说明3.动态SQL常用标签 2.环境搭建1.新建子模块2.删除不必要的两个文件夹3.创建基本结构4.父模块的pom.xml5.jdbc.properties6.mybatis-config.xml7.MyBatisUtils.java8.MonsterMapper.java9.MonsterMapper.xml10.测试Mo…
阅读更多...
最新文章

Copyright @ 2022~2023