链表之“无头单向非循环链表”

目录

​编辑

1.顺序表的问题及思考

2.链表

2.1链表的概念及结构

2.2无头单向非循环链表的实现

1.创建结构体

2.单链表打印

3.动态申请一个节点

3.单链表尾插

4.单链表头插

5.单链表尾删

6.单链表头删

7.单链表查找

8.单链表在pos位置之前插入x

9.单链表删除pos位置的值

10.单链表在pos位置之后插入x

11.单链表删除pos位置之后的值

12.单链表销毁

3.源码


1.顺序表的问题及思考

🌻问题:

  • 顺序表在尾部插入删除效率还不错,但是在头部或者中间位置插入删除,就需要挪动数据,时间复杂度为O(N),效率低下。
  • 空间满了以后只能增容,增容需要申请新的空间,拷贝数据,释放旧空间,会有一定的消耗。
  • 增容一般是呈2倍的增长,势必会有一定的空间浪费。假设当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。也就是说,一次增的越多,可能浪费越多;一次增的少了,那么就会频繁增容。

🌻思考:

  • 如何解决以上问题呢?下面让我们一起来看看链表的结构:

2.链表

2.1链表的概念及结构

🌴概念: 

  • 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
  • 简单来说,就是链表中的每一个数据元素都是单独存储的,我们把这个数据元素又叫做节点。当需要存储下一个数据元素的时候就申请一块新的内存用来存储数据,每一个节点又通过地址链接起来,当前节点存放的是下一个节点的地址。所以,一个节点里边就包含数据元素和下一个节点的地址这两部分。

🌴结构:

注意:

  1. 从上图可以看出,链式结构在逻辑上是连续的,但是在物理上不一定连续。
  2. 现实中的节点一般都是从堆上申请出来的。
  3. 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续。

假设在32位系统上,节点中值域为int类型,则一个节点的大小为8个字节,则也可能有下述链表:

2.2无头单向非循环链表的实现

1.创建结构体

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType val;        //数据域
	struct SListNode* next; //指针域
}SLNode;

2.单链表打印

  • phead是一个指针变量,占4个字节,它指向第一个节点,即存的是第一个节点的地址。而在其它节点中,每个节点里边分别又有两个数据域,其中一个保存val,另一个保存下一个节点的地址,在32位环境下,一个节点占8个字节。
  • 遍历链表时,担心phead会发生意外,所以我们先将phead的值赋给cur,看cur等不等于NULL,如果不等于NULL,就进入循环,打印第一个节点的值,然后将第二个节点的地址再赋给cur,看它等不等于NULL,如果不等于NULL,再打印第二个节点的值,再将第三个节点的地址赋给cur,以此循环,直到cur等于NULL,就跳出循环。

//单链表打印
void SLTPrint(SLNode* phead)
{
	//不要动phead,否则会找不到头
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

3.动态申请一个节点

如果直接在其它函数内部申请节点的话,它的作用域就只能在那个函数内部,出了函数作用域就会销毁,所以得单独写一个函数来申请节点,让其它函数来调用它。

//动态申请一个节点
SLNode* CreateNode(SLTDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}

3.单链表尾插

单链表尾插分为有节点无节点两种情况:

  • 假设现在链表里边有节点,那我们要尾插一个数据,第一步肯定是要先找到尾。先定义一个tail,让它指向头节点,然后看tail->next等不等于NULL,如果不为NULL,让tail等于tail->next,依次循环,直到tail->next等于NULL的时候,tail刚好就是尾节点。找到尾节点后,再动态申请一个节点,让新申请的节点指向NULL,再让尾节点指向新申请的这个节点。

  • 如果链表里边没有节点,即链表为空,那我们直接让*pphead指向新节点的地址就行了。因为在主函数里边我们定义的是*plist的指针,所以要想改变外面结构体指针SLNode*,就要用二级指针SLNode**。
//单链表尾插
void SLTPushBack(SLNode** pphead, SLTDataType x)
{
    assert(pphead);
	SLNode* newnode = CreateNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

4.单链表头插

头插时比较简单,我们让新申请出来的节点newnode指向第一个节点的地址,而第一个节点的地址保存在plist里边,我们又把plist的地址赋给了pphead,所以让newnode->next指向*pphead,再将*pphead指向newnode就可以了。

//单链表头插
void SLTPushFront(SLNode** pphead, SLTDataType x)
{
    assert(pphead);

	SLNode* newnode = CreateNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

5.单链表尾删

单链表的尾删也分为两种情况:

  • 第一种是当链表里边只有一个节点的时候,我们只需要free掉这个节点,然后让plist指向空就行了。
  • 第二种是当链表里边有多个节点的时候,我们可以定义两个指针,让第一个指针prev指向NULL,第二个指针保存头节点的地址,然后通过循环找尾,当找到尾的时候,跳出循环,此时prev刚好指向了尾的前一个节点,我们再free掉尾,让前一个节点指向空就可以了。
//单链表尾删
void SLTPopBack(SLNode** pphead)
{
    assert(pphead);
	assert(*pphead);

	//1.一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//2.多个节点
	else
	{
		/*SLNode* prev = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;*/

		SLNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}

6.单链表头删

因为空链表无法删除,所以需要先断言。头删只需要将第一个节点free掉就可以了,但是free之前得先保存下一个节点的地址。

//单链表头删
void SLTPopFront(SLNode** pphead)
{
    assert(pphead);
	//空
	assert(*pphead);

	//一个或多个以上节点都可以处理
	SLNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

7.单链表查找

单链表的查找只需要遍历一遍就可以了,定义一个cur让它指向第一个节点的地址,通过循环如果cur不为空,就进入循环,进入循环后,如果cur->val等于x,则返回cur,否则,让cur指向下一个节点的地址。遍历完一遍如果没有找到,则返回NULL。可以说查找函数是为了配合修改单链表中的值而写的。

//单链表查找
SLNode* SLTFind(SLNode* phead, SLTDataType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

8.单链表在pos位置之前插入x

如果此时链表为空,那么就相当于头插;如果不为空,则只需找到pos位置的前一个节点,让前一个节点的地址指向新节点,新节点指向pos位置即可。

//单链表在pos位置之前插入x
void SLTInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{
	assert(pphead);
	//要么都为空,要么都不为空
	assert((!pos && !(*pphead)) || (pos && *pphead));

	if (*pphead == pos)
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLNode* newnode = CreateNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

9.单链表删除pos位置的值

如果链表只有一个节点,则相当于头删;如果有多个节点,则需要找到pos位置的前一个节点,然后让前一个节点指向pos位置的后一个节点,接着free掉pos即可。

//单链表删除pos位置的值
void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}

}

10.单链表在pos位置之后插入x

创建一个新节点,先让新节点的指针域存pos后一个节点的地址,然后让pos的指针域存新节点的地址。

//单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLTDataType x)
{
	assert(pos);

	SLNode* newnode = CreateNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


11.单链表删除pos位置之后的值

这个操作必须保证链表中有两个以上的数据,如果只有一个数据的话,那它后面为空,没法执行删除操作,所以得先断言一下。

//单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLNode* tmp = pos->next;
	pos->next = pos->next->next;
	free(tmp);
	tmp = NULL;
}

12.单链表销毁

//单链表销毁
void SLTDestroy(SLNode** pphead)
{
	assert(pphead);

	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

3.源码

🌻SList.h

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

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType val;
	struct SListNode* next;
}SLNode;

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

//单链表尾插
void SLTPushBack(SLNode** pphead, SLTDataType x);
//单链表头插
void SLTPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删
void SLTPopBack(SLNode** pphead);
//单链表头删
void SLTPopFront(SLNode** pphead);

//单链表查找
SLNode* SLTFind(SLNode* phead, SLTDataType x);

//单链表在pos位置之前插入x
void SLTInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//单链表删除pos位置的值
void SLTErase(SLNode** pphead, SLNode* pos);

//单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLTDataType x);
//单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos);

//单链表销毁
void SLTDestroy(SLNode** pphead);

🌻SList.c

#include "SList.h"

//单链表打印
void SLTPrint(SLNode* phead)
{
	//不要动phead,否则会找不到头
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

//动态申请一个节点
SLNode* CreateNode(SLTDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}

//单链表尾插
void SLTPushBack(SLNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLNode* newnode = CreateNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

//单链表头插
void SLTPushFront(SLNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLNode* newnode = CreateNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

//单链表尾删
void SLTPopBack(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	//1.一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//2.多个节点
	else
	{
		/*SLNode* prev = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;*/

		SLNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}

//单链表头删
void SLTPopFront(SLNode** pphead)
{
	assert(pphead);
	//空
	assert(*pphead);

	//一个或多个以上节点都可以处理
	SLNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

//单链表查找
SLNode* SLTFind(SLNode* phead, SLTDataType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

//单链表在pos位置之前插入x
void SLTInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{
	assert(pphead);
	//要么都为空,要么都不为空
	assert((!pos && !(*pphead)) || (pos && *pphead));

	if (*pphead == pos)
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLNode* newnode = CreateNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//单链表删除pos位置的值
void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		//头删
		SLTPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLTDataType x)
{
	assert(pos);

	SLNode* newnode = CreateNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLNode* tmp = pos->next;
	pos->next = pos->next->next;
	free(tmp);
	tmp = NULL;
}

//单链表销毁
void SLTDestroy(SLNode** pphead)
{
	assert(pphead);

	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

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

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

相关文章

力扣645. 错误的集合(排序,哈希表)

Problem: 645. 错误的集合 文章目录 题目描述思路复杂度Code 题目描述 思路 1.排序 1.对nums数组按从小到大的顺序排序; 2.遍历数组时若判断两个相邻的元素则找到重复元素&#xff1b; 3.记录一个整形变量prev一次置换当前位置元素并与其作差&#xff0c;若差等于2着说明缺失的…

一篇文章搞懂CDN加速原理

目录 一、什么是CDN CDN对网络的优化作用主要体现在以下几个方面&#xff1a; 二、CDN工作原理 CDN网络的组成元素&#xff1a; 三、名词解释 3.1 CNAME记录&#xff08;CNAME record&#xff09; 3.2 CNAME域名 3.3 DNS 3.4 回源host 3.5 协议回源 一、什么是CDN CD…

linux增加物理磁盘并挂载到文件系统

centos7增加物理磁盘并挂载到文件系统 1、查看所有磁盘情况 fdisk -l2、创建挂载路径 mkdir /data3、格式化磁盘 #磁盘filesystem(上图标红处) mkfs.xfs -f /dev/sda建议 与其它磁盘文件系统保持一致&#xff0c;我这里是xfs 可通过 cat /dev/sda查看 4、挂载 mount /dev/…

今日必读的9篇大模型论文

1.Customize-A-Video&#xff1a;文生视频&#xff0c;可以自由定制了 图像定制在文本到图像&#xff08;T2I&#xff09;扩散模型中已经得到了广泛的研究&#xff0c;并取得了令人印象深刻的成果和应用。随着文本到视频&#xff08;T2V&#xff09;扩散模型的兴起&#xff0c…

从零开始手写mmo游戏从框架到爆炸(二十一)— 战斗系统二

导航&#xff1a;从零开始手写mmo游戏从框架到爆炸&#xff08;零&#xff09;—— 导航-CSDN博客 上一章&#xff08;从零开始手写mmo游戏从框架到爆炸&#xff08;二十&#xff09;— 战斗系统一-CSDN博客&#xff09;我们只是完成了基本的战斗&#xff0c;速度属性并没有…

前端数据可视化:ECharts使用

可视化介绍 ​  ​  应对现在数据可视化的趋势&#xff0c;越来越多企业需要在很多场景(营销数据&#xff0c;生产数据&#xff0c;用户数据)下使用&#xff0c;可视化图表来展示体现数据&#xff0c;让数据更加直观&#xff0c;数据特点更加突出。   ​  数据可视化主要目…

读取7400MB/s!华为发布eKitStor Xtreme M.2闪存条

今日&#xff0c;华为举行数据存储新春新品发布会&#xff0c;不仅发布全新数据湖解决方案&#xff0c;华为还针对商业市场与分销市场发布了全闪存存储新品。 据介绍&#xff0c;面向游戏加速、影视编辑、户外作业等场景&#xff0c;华为发布eKitStor Xtreme系列高性能M.2闪存条…

Leetcode3035. 回文字符串的最大数量

Every day a Leetcode 题目来源&#xff1a;3035. 回文字符串的最大数量 解法1&#xff1a;哈希 排序 由于可以随意交换字母&#xff0c;先把所有字母都取出来&#xff0c;然后考虑如何填入各个字符串。 如果一个奇数长度字符串最终是回文串&#xff0c;那么它正中间的那…

一文读懂Linux内核中的Device mapper映射机制

一、 简介 本文总结Device mapper的映射机制。Device mapper是Linux2.6内核中提供的一种逻辑设备到物理设备的映射框架机制&#xff0c;在该机制下&#xff0c;用户可以很方便的根据自己的需要指定实现存储资源的管理策略&#xff0c;当前比较流行的Linux的逻辑卷管理器比如&a…

轻松打造智能化性能测试监控平台:【JMeter+Grafana+Influxdb】的优化整合方案

在当前激烈的市场竞争中&#xff0c;创新和效率成为企业发展的核心要素之一。在这种背景下&#xff0c;如何保证产品和服务的稳定性、可靠性以及高效性就显得尤为重要。 而在软件开发过程中&#xff0c;性能测试是一项不可或缺的环节&#xff0c;它可以有效的评估一个系统、应…

igolang学习3,golang 项目中配置gin的web框架

1.go 初始化 mod文件 go mod init gin-ranking 2.gin的crm框架 go get -u github.com/gin-gonic/gin 3.go.mod爆红解决

渗透测试之RCE漏洞

RCE&#xff08;remote command execute&#xff09;远程命令执行。应用程序的某些功能需要调用可以执行的系统命令的函数&#xff0c;如果这些函数或者函数的参数被用户控制&#xff0c;就可能通过命令连接符将恶意的命令拼接到函数中&#xff0c;从而执行系统命令。 常见的命…

WordPress使用

WordPress功能菜单 仪表盘 可以查看网站基本信息和内容。 文章 用来管理文章内容&#xff0c;分类以及标签。编辑文章以及设置分类标签&#xff0c;分类和标签可以被添加到 外观-菜单 中。 分类名称自定义&#xff1b;别名为网页url链接中的一部分&#xff0c;最好别设置为中文…

mybatis 集成neo4j实现

文章目录 前言一、引入jar包依赖二、配置 application.properties三、Mybatis Neo4j分页插件四、Mybatis Neo4j自定义转换器handler五、MybatisNeo4j代码示例总结 前言 MyBatis是一个基于Java语言的持久层框架&#xff0c;它通过XML描述符或注解将对象与存储过程或SQL语句进行…

【C++私房菜】面向对象中的多重继承以及菱形继承

文章目录 一、多重继承1、多重继承概念2、派生类构造函数和析构函数 二、菱形继承和虚继承2、虚继承后的构造函数和析构函数 三、has-a 与 is-a 一、多重继承 1、多重继承概念 **多重继承&#xff08;multiple inheritance&#xff09;**是指从多个直接基类中产生派生类的能力…

Open CASCADE学习|绘制砂轮

今天绘制一个砂轮&#xff0c;其轮廓由两条直线段和两段圆弧构成&#xff0c;圆弧分别与直线相切&#xff0c;两条圆弧之间相交而非相切。建模思路是&#xff1a;先给定两条直线段的起始点及长度&#xff0c;画出直线段&#xff0c;然后给定其中一圆弧的半径及圆心角&#xff0…

Elastic Stack--02--核心概念、倒排索引

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 1.核心概念1.1 索引1.2 类型1.3 文档1.4 字段 2.倒排索引此处ID是唯一标识 具体拆解的案例 1.核心概念 mysqlESDatabases 数据库索引 indicesTable 数据表类型 Type…

探索D咖智能饮品机器人的工作原理:科技、材料与设计的相互融合

智能饮品机器人是近年来随着人工智能和自动化技术的发展而崭露头角的一种创新产品。它将科技、材料和设计相互融合&#xff0c;为消费者带来了全新的饮品体验。下面D咖来探索智能饮品机器人的工作原理&#xff0c;以及科技、材料和设计在其中的作用。 首先&#xff0c;智能饮品…

抖音小店无货源真的靠谱吗?发展前景如何?2024年值得做吗?

大家好&#xff0c;我是电商花花。 我们通常说的抖音小店无货源就是利用产品之间的信息差、利润差来赚取商品的差价。 无货源模式就是即使没有货源&#xff0c;也能做抖音小店&#xff0c;前期店铺起店&#xff0c;我们需要大量的出单量和数据&#xff0c;我们才能快速把店铺…

Spring Boot应用集成Actuator端点自定义Filter解决未授权访问的漏洞

一、前言 我们知道想要实时监控我们的应用程序的运行状态&#xff0c;比如实时显示一些指标数据&#xff0c;观察每时每刻访问的流量&#xff0c;或者是我们数据库的访问状态等等&#xff0c;需要使用到Actuator组件&#xff0c;但是Actuator有一个访问未授权问题&#xff0c;…