探索数据结构：单链表的实践和应用

🔑🔑博客主页：阿客不是客

🍓🍓系列专栏：渐入佳境之数据结构与算法

欢迎来到泊舟小课堂

😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注

​

 一、前言

前面我们学习了数据结构中的顺序表，知道了顺序表的空间是连续存储的，这与数组非常类似，为我们随机访问数据提供了便利的条件，但顺序表也有着一些不足之处：

  1. 尾部插入删除效率还不错，中部或者头部插入删除需要挪动数据，效率低下。
  2. 顺序表满了以后需要扩容，扩容本身也有一定的消耗。
  3. 扩容存在空间浪费：一次扩的多了容易造成浪费，一次扩的少了可能要频繁扩容。

这些大大增加我们的时间与空间成本。为了解决这个问题，就要学习我们今天要讲解的链表。

二、什么是链表

2.1 链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。与顺序表不同，链表的存储数据在内存是随机分布的。

链表是由一个个结点组成的，结点如下图所示：

注意：链表中的最后一个结点的next指向空，next=NULL，一个个结点串成了链表：

2.2 链表的分类

链表的种类多种多样，它们大致可以分为三类：

2.2.1 单向或双向

2.2.2 带不带头结点

2.2.3 循环不循环

三、单链表的基本操作

单链表的基本操作包括单链表的初始化、判断空链表、销毁、清空以及求表长这些较为简单的操作，还有更为重要的单链表的取值、按值查找返回元素所在地址、按值查找返回元素所对应序号、结点插入和删除以及头插法和尾插法建立单链表。目前只实现了这些操作，并进行的测试。

3.1 单链表的初始化

单链表的结点定义方式与我们以往定义的方式都不同，它是一个结构体中包含两个成员。一个是存储数值，一个存放下一个结点的地址。

typedef int SLTDataType;

typedef  struct SList
{
	SLTDataType val;
	struct SList* next;//下一个结点的地址
}SLT;

3.2 创建一个新结点

后面我们要在单链表中进行头插和尾插，此时插入的不再是像顺序表一样简单的SLDateType数据了，而是一个结点，这个结点是包括SLTDateType数据以及SLTDateType*的指针，因此，为了方便和减少代码的重复度，我们另写一个函数用来专门创建新结点。

SLT* CreateNode(SLTDataType x)
{
	SLT* newnode = (SLT*)malloc(sizeof(SLT));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	//原本指向下一个结点的指针放在插入的结点的里面
	//尾插是newnode->next = NULL
	//尾插中经过while循环，tail->next == NULL
	newnode->next = NULL;
	return newnode;
}

3.3 打印单链表

注意：链表和顺序不同的是，顺序表传过来的指针是肯定不会为空的，而链表传过来的指针是可能为空的，比如说当链表中没有元素时，头指针所指向的就是NULL，如果在第一行写上断言就会有问题。

void SLTPrint(SLT* phead)//初位置的指针
{
	SLT* tail = phead;//指向链表的第一个结点（结构体）
	//遍历链表
	while (tail != NULL)//尾结点的next为空，tail指向尾结点
	{
		printf("%d->", tail->val);
		tail = tail->next;
	}
	printf("NULL\n");
}

3.4 单链表尾插

注意：在创建结点时，已经让 结点.next=NULL，所以不需要在插入完结点后，再让新结点的next指针为NULL。

有人可能会有疑问，为什么之前打印链表的时候不用断言指针，而在尾插时就要断言指针，以及为什么函数的形参是二级指针，而不使用一级指针。

因为，尾插分为两种情况:

  1. 当链表为空时，头指针phead指向NULL，尾插相当于头插，此时要改变phead的指向，让phead指向这个新结点，此时就需要二级指针来改变一级指针的值（如果我们用一级指针做形参，形参的改变不会影响实参，那么一级指针phead就不会被改变）。
  2. 至于这个什么时候要断言指针，什么时候不用断言指针：
    • 一级指针也就是phead，当链表为空的时候，phead就是为NULL，phead存在为空的可能。
    • 而二级指针永远指向phead，phead的地址是永远存在的，那么pphead就一定不可能为空，所以需要断言pphead。
void SLTpushback(SLT** pphead, SLTDataType x)
{
	assert(pphead);
	SLT* newnode = CreateNode(x);//新结点的地址
 	if (*pphead == NULL)//改变结构体的指针（二级指针）
	{
		*pphead = newnode; 
	}
	else
	{
		SLT* tail = *pphead;
		while (tail->next != NULL)//tail->next,当链表为空会解引用空指针
		{
			tail = tail->next;
		}
		//下一个结构体的指针被存放在结构体成员里面
		//可以使用一级指针访问结构体的成员来间接访问下一个结构体的指针
		//第一个结点的结构体的指针没有存放，所以要用二级指针
		tail->next = newnode;//修改结构体的内容（一级指针）
	}
}

3.5 单链表头插

头插没什么好说的，记住要断言*pphead，保证链表内容不为空，头删也同理。

void SLTpushfront(SLT** pphead, SLTDataType x)
{
	assert(pphead);
	SLT* newnode = CreateNode(x);
	newnode->next  = *pphead;
	*pphead = newnode;
}

3.6 单链表尾删

要想删除链表中的元素，就必须保证原链表就有元素，因此要断言assert(*pphead)。

尾删需要分情况去讨论：

void SLTpopback(SLT** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLT* tail = *pphead;
	if (tail->next == NULL)//只有一个结点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		while (tail->next->next != NULL)//tail指向的结点后面第二个不为空
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

3.7 单链表头删

void SLTpopfront(SLT** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLT* tail= *pphead;
	*pphead = tail->next;
	free(tail);
	tail = NULL;
}

3.8 单链表的查找

这个函数返回值不再是void，而是SListNode*，把找到的结点的地址返回去，这个函数一般会跟结点插入删除之类的函数一起使用。

SLT* SLTfind(SLT* phead, SLTDataType x)
{
	SLT* cur = phead;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

3.9 单链表任意位置插入

void SLTInsert(SLT** pphead, SLT* pos, SLTDataType x)
{
	assert(pphead);
	//pphead 是二级指针，不会为空
	//*pphead == NULL 链表为空
	//要么都为空，要么都不为空
	assert((pos && *pphead)||(!pos && !(*pphead)));

	if (*pphead == NULL)
	{
		SLTpushfront(pphead, x);
	}
	else
	{
		SLT* prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		SLT* newnode = CreateNode(x);
		prve->next = newnode;
		newnode->next = pos;
	}
}

3.10 单链表任意位置删除

这里我要提醒一下，千万不要忘记判断pos是否正确，不要只单单断言pos是否为NULL，还要判断能不能在链表中找到pos这个地址。

void SLTErase(SLT** pphead, SLT* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTpopfront(pphead);
	}
	else
	{
		SLT* prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		prve->next = pos->next;
		free(pos);
	}
}

3.11 单链表的销毁

销毁链表这一块，咱可不敢直接free(phead)，因为链表在物理结构上是不连续存储的，销毁链表必须要一个结点一个结点去销毁！！！！最后不要忘记把phead置为NULL。

void SLTDestory(SLT** pphead)
{
	assert(pphead);
	SLT* cur = *pphead;
	while (cur)
	{
		//方法一：
		//cur = cur->next;
		//free(*pphead);//释放掉了phead的空间
		//*pphead = cur;

		SLT* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

四、完整代码

4.1 SLT.h

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

typedef int SLTDataType;

typedef  struct SList
{
	int val;
	struct SList* next;//下一个结点的地址
}SLT;

void SLTPrint(SLT* phead);//打印链表

SLT* CreateNode(SLTDataType x, SLT* tail);//创建一个新结点

void SLTpushback(SLT** pphead, SLTDataType x);//尾插
void SLTpushfront(SLT** pphead, SLTDataType x);//头插
void SLTpopback(SLT** pphead);
void SLTpopfront(SLT** phead);

SLT* SLTfind(SLT* phead, SLTDataType x);

//与find函数结合使用
//在pos前面插入
void SLTInsert(SLT** pphead, SLT* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLT** pphead, SLT* pos);

void SLTDestory(SLT** pphead);//销毁

4.2 SLT.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"

SLT* CreateNode(SLTDataType x)
{
	SLT* newnode = (SLT*)malloc(sizeof(SLT));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	//原本指向下一个结点的指针放在插入的结点的里面
	//尾插是newnode->next = NULL
	//尾插中经过while循环，tail->next == NULL
	newnode->next = NULL;
	return newnode;
}

void SLTPrint(SLT* phead)//初位置的指针
{
	SLT* tail = phead;//指向链表的第一个结点（结构体）
	//遍历链表
	while (tail != NULL)//尾结点的next为空，tail指向尾结点
	{
		printf("%d->", tail->val);
		tail = tail->next;
	}
	printf("NULL\n");
}


void SLTpushback(SLT** pphead, SLTDataType x)
{
	assert(pphead);
	SLT* newnode = CreateNode(x);//新结点的地址
 	if (*pphead == NULL)//改变结构体的指针（二级指针）
	{
		*pphead = newnode; 
	}
	else
	{
		SLT* tail = *pphead;
		while (tail->next != NULL)//tail->next,当链表为空会解引用空指针
		{
			tail = tail->next;
		}
		//下一个结构体的指针被存放在结构体成员里面
		//可以使用一级指针访问结构体的成员来间接访问下一个结构体的指针
		//第一个结点的结构体的指针没有存放，所以要用二级指针
		tail->next = newnode;//修改结构体的内容（一级指针）
	}
}

void SLTpushfront(SLT** pphead, SLTDataType x)
{
	assert(pphead);
	SLT* newnode = CreateNode(x);
	newnode->next  = *pphead;
	*pphead = newnode;
}

void SLTpopback(SLT** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLT* tail = *pphead;
	if (tail->next == NULL)//只有一个结点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		while (tail->next->next != NULL)//tail指向的结点后面第二个不为空
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

void SLTpopfront(SLT** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLT* tail= *pphead;
	*pphead = tail->next;
	free(tail);
	tail = NULL;
}

SLT* SLTfind(SLT* phead, SLTDataType x)
{
	SLT* cur = phead;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

void SLTInsert(SLT** pphead, SLT* pos, SLTDataType x)
{
	assert(pphead);
	//pphead 是二级指针，不会为空
	//*pphead == NULL 链表为空
	//要么都为空，要么都不为空
	assert((pos && *pphead)||(!pos && !(*pphead)));

	if (*pphead == NULL)
	{
		SLTpushfront(pphead, x);
	}
	else
	{
		SLT* prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		SLT* newnode = CreateNode(x);
		prve->next = newnode;
		newnode->next = pos;
	}
}

void SLTErase(SLT** pphead, SLT* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SLTpopfront(pphead);
	}
	else
	{
		SLT* prve = *pphead;
		while (prve->next != pos)
		{
			prve = prve->next;
		}
		prve->next = pos->next;
		free(pos);
	}
}

void SLTDestory(SLT** pphead)
{
	assert(pphead);
	SLT* cur = *pphead;
	while (cur)
	{
		//方法一：
		//cur = cur->next;
		//free(*pphead);//释放掉了phead的空间
		//*pphead = cur;

		SLT* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

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

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

相关文章

前端JS必用工具【js-tool-big-box】学习，获取全球重点城市时间

前端JS必用工具【js-tool-big-box】学习，获取全球重点城市时间

我们去住一些旅馆的时候&#xff0c;或者一些国际性网站&#xff0c;经常可以看见他们的钟表会展示一些国家地区的时间&#xff0c;这个就是很常用的功能。但如果不常接触这个功能的开发网站呢&#xff0c;大家就看自己电脑右下角的时间展示&#xff0c;就是自己当前的具体时间…
阅读更多...
2024年【G2电站锅炉司炉】免费试题及G2电站锅炉司炉复审考试

2024年【G2电站锅炉司炉】免费试题及G2电站锅炉司炉复审考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年【G2电站锅炉司炉】免费试题及G2电站锅炉司炉复审考试&#xff0c;包含G2电站锅炉司炉免费试题答案和解析及G2电站锅炉司炉复审考试练习。安全生产模拟考试一点通结合国家G2电站锅炉司炉考试最新大纲及G2电站锅…
阅读更多...
新手必看！TikTok视频0播放的5大原因及解决方法

新手必看！TikTok视频0播放的5大原因及解决方法

很多刚起步的TikTok卖家常会遇到一个烦心事&#xff1a;发布的视频播放量少得可怜&#xff0c;甚至有时是0播放。这确实让人挺沮丧的。到底如何突破TikTok视频总是播放量为0的瓶颈&#xff1f;别担心&#xff0c;今天为大家总结了tiktok视频播放量上不去的5种原因和相应的解决方…
阅读更多...
以JVM新特性看Java的进化之路：从Loom到Amber的技术篇章

以JVM新特性看Java的进化之路：从Loom到Amber的技术篇章

引言&#xff1a; JVM的最新特性通过在效率、功能和易用性方面的创新&#xff0c;对Java的未来发展产生了深远的影响。以下是几个关键特性如何塑造了Java的未来&#xff1a; 正文&#xff1a; 轻量级并发 - 项目Loom&#xff1a; 项目Loom通过引入虚拟线程&#xff08;也被称为…
阅读更多...
使用vue,mybatis,mysql,tomcat,axios实现简单的登录注册功能

使用vue,mybatis,mysql,tomcat,axios实现简单的登录注册功能

目录 第一步环境搭建 后端&#xff1a; 前端&#xff1a; 第二步画流程图 web: service: dao层&#xff1a; 第三步前端代码的实现 这是开始的页面&#xff0c;接下来我们要到router路由下书写#login的路径 路由中的component在我们自己创建的views书写vue文件…
阅读更多...
某安全厂商外包安服工程师面试

某安全厂商外包安服工程师面试

写在前面&#xff1a;本篇帖子出现的厂商and面试问题皆为up实际面试情况&#xff0c;厂商信息不透露&#xff0c;仅供师傅们参考。 背景 某知名安全厂商外包 岗位&#xff1a;安全服务工程师&#xff08;偏售后&#xff09; 薪资条件&#xff1a;7~9k&#xff08;up所在二线…
阅读更多...
Moto和Inter字节序

Moto和Inter字节序

inter: 低地址按照start_bit位放低字节依次往高字节填充 MotoLsb: 低地址按照start_bit位放高字节&#xff0c;依次往低字节填充MotoMsb&#xff1a;高字节按照start_bit位放低地址&#xff0c;依次往高字节填充
阅读更多...
光纤跳纤，这篇文章值得一看

光纤跳纤，这篇文章值得一看

光纤跳线作为光网络布线最基础的元件之一&#xff0c;被广泛应用于光纤链路的搭建中。 如今&#xff0c;光纤制造商根据应用场景的不同推出众多类型的光纤跳线&#xff0c;如 MPO / LC / SC / FC / ST 光纤跳线&#xff0c;单工/双工光纤跳线&#xff0c;单模/多模光纤跳线等&…
阅读更多...
一文带你学会如何部署个人博客到云服务器，并进行域名备案与解析！

一文带你学会如何部署个人博客到云服务器，并进行域名备案与解析！

哈喽&#xff0c;大家好呀&#xff01;这里是码农后端。之前我给大家介绍了如何快速注册一个自己的域名&#xff0c;并创建一台自己的阿里云ECS云服务器。本篇将介绍如何将个人博客部署到云服务器&#xff0c;并进行域名备案与解析。 1、域名备案 注册了域名并购买了云服务器之…
阅读更多...
bootstrap实现天平效果

bootstrap实现天平效果

之前提到了&#xff0c;最近&#xff0c;孩子的幼儿园让家长体验“半日助教活动”&#xff0c;每个家长需要讲授15-20分钟的课程。作为一名程序员&#xff0c;实在没有能教的课程&#xff0c;只能做了一个小游戏&#xff0c;带着小朋友们熟悉数字。 在上一章博客中&#xff0c…
阅读更多...
探索AI变现新模式：搭建小程序，畅享换脸写真、趣测音乐多重乐趣

探索AI变现新模式：搭建小程序，畅享换脸写真、趣测音乐多重乐趣

一、AI创作系统介绍、 AI变现小程序是一种利用人工智能技术为用户提供服务&#xff0c;并通过某种方式实现盈利的小程序。这种小程序可以应用于多个领域&#xff0c;如AI动漫推文、AI绘画、AI换脸等。 AI小说生动漫推文&#xff1a;是一种利用AI技术和动漫制作技术&#xff0…
阅读更多...
苹果WWDC 2024或将推出AI生成的表情符号并宣布与OpenAI的合作｜TodayAI

苹果WWDC 2024或将推出AI生成的表情符号并宣布与OpenAI的合作｜TodayAI

苹果正在为即将到来的WWDC&#xff08;全球开发者大会&#xff09;做准备&#xff0c;并将展示其生成式AI技术。根据Mark Gurman在Bloomberg的《Power On》通讯中的报道&#xff0c;苹果将在2024年的WWDC上讲述自己的AI故事&#xff0c;但这可能不会像Google、Microsoft或OpenA…
阅读更多...
宝藏功能：teamOS的文件信息总览，太好用了吧

宝藏功能：teamOS的文件信息总览，太好用了吧

在日常工作中&#xff0c;我们时常需要处理大量的文件和协作任务。有时&#xff0c;过多的信息和工具可能会让我们感到混乱和困扰。 但可道云的teamOS文件信息总览窗口却为我们提供了一个清晰、高效的解决方案。 一、一站式信息展示&#xff0c;让工作更透明 这个面板集成了许…
阅读更多...
55页PDF｜人工智能通用大模型（ChatGPT）的进展、风险与应对（附下载）

55页PDF｜人工智能通用大模型（ChatGPT）的进展、风险与应对（附下载）

&#x1f449;获取方式&#xff1a; &#x1f61d;有需要的小伙伴&#xff0c;可以保存图片到wx扫描二v码免费领取【保证100%免费】&#x1f193;
阅读更多...
OrangePi AIpro上手初体验：

OrangePi AIpro上手初体验：

OrangePi AIpro上手初体验&#xff1a; 1.基本外观及功能接口简介2.点亮OrangePi AIpro开发板3.OrangePi AIpro功能体验3.1.目标检测3.2.OCR文字识别3.3.图像的曝光增强3.4.系统的整体性能(运行ROS) 4.OrangePi AIpro体验总结4.1.硬件及软件生态&#xff1a;4.2.使用体验及性能…
阅读更多...
医学图像分割--U-net变种

医学图像分割--U-net变种

参考&#xff1a;医学图像分割综述:U-Net系列_医学图像 实例分割-CSDN博客 2D Unet 收缩路径&#xff1a;每个块包含两个连续的3 3卷积&#xff0c;后面是一个ReLU激活函数和最大池化层&#xff08;下采样&#xff09;扩展路径&#xff1a;该路径包括一个2 2转置卷积层(上采…
阅读更多...
苹果手机突然白屏无反应怎么办？白屏修复办法分享！

苹果手机突然白屏无反应怎么办？白屏修复办法分享！

苹果手机突然白屏无反应怎么办&#xff1f;下面小编就来给大家分享苹果手机突然白屏的原因和修复办法。 一般造成苹果手机出现白屏的原因如下&#xff1a; 系统问题&#xff1a;iOS系统的故障是导致苹果设备白屏无反应最常见的原因之一。例如&#xff0c;系统更新失败、应用冲…
阅读更多...
OpenHarmony如何切换横竖屏？

OpenHarmony如何切换横竖屏？

前言 在日常开发中&#xff0c;大多APP可能根据实际情况直接将APP的界面方向固定&#xff0c;或竖屏或横屏。但在使用过程中&#xff0c;我们还是会遇到横竖屏切换的功能需求&#xff0c;可能是通过物理重力感应触发&#xff0c;也有可能是用户手动触发。所以本文主要带大家了…
阅读更多...
ESP32入门：1、VSCode+PlatformIO环境搭建

ESP32入门：1、VSCode+PlatformIO环境搭建

文章目录 背景安装vscode安装配置中文 安装Platform IO安装PIO 新建ESP32工程参考 背景 对于刚接触单片机的同学&#xff0c;使用vscodeplatformIO来学习ESP32是最方便快捷的&#xff0c;比IDF框架简单&#xff0c;且比arduino文件管理性能更好。但是platformIO安装较为麻烦&a…
阅读更多...
小苯的九宫格,小苯的好数组(排序),小苯的数字合并(字典树，前缀和）

小苯的九宫格,小苯的好数组(排序),小苯的数字合并(字典树，前缀和）

小苯的九宫格 题目描述 运行代码 #include<iostream> using namespace std; int main(){int a[10];for(int i1;i<9;i){cin>>a[i];} string b;cin>>b;for(int i0;i<b.size();i){int pb[i]-0;cout<<a[p];} } 代码思路 定义数组&#xff1a;首先…
阅读更多...
最新文章

Copyright @ 2022~2023