单链表的实现(单链表的增删查改)

在顺序表中实现数据的增删的操作时,都要把操作位置之后的数据全部移动一遍,操作效率低下。其次是容量固定(静态顺序表),虽然在动态顺序表中容量可变,但也会造成空间上的浪费。

单链表就完美解决了上述缺点。

这里要说明一点,单链表与顺序表没有哪个比哪个更好,只有哪个更适应场合。

介绍完上述后,现在开始单链表的实现,实现单链表需要用到结构体指针。

链表中的节点都是动态开辟的空间,是在堆上的,并不会出了作用域就销毁,如果在链表中找到值为1的节点,那就把这个节点的地址返回(将体现在指定位置插入删除的操作,解决了为什么没有传址而传值的疑惑)

创建结构体:

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

结构体指针SLTNode*储存下一个节点,可以理解为一条链条或套娃。直到最后一个节点的next指向空(NULL)时

需要注意的是这里SLTNode我进行了前置声明因此可以直接用转换后的语句。

如果没有前置声明,STLNode不会被识别出来,这里需要说一下,操作系统在找SLTNode时只会向上找不会向向下找,这也就是为什么有许多代码中会有前置声明的函数或者像当先操作的转换一样。

能直观的看到前置声明的重要性。

创建一个头文件SListNode.h用来放需要实现的函数(声明)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode SLTNode;
typedef struct SListNode
{
	SLTDataType data;
	SLTNode* next;
}SLTNode;


void SLTPrint(SLTNode* phead);

//头部插入删除/尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

创建SListNode.c文件用来实现头文件的函数

首先是尾插

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    newnode->data = x;
    newnode->next = NULL;
    //不能直接这样用*pphead->next = NULL;加括号(*pphead)->next,  优先级问题
    //链表为空
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    //链表不为空,找尾节点
    SLTNode* node = *pphead;
    while (node->next)
    {
        node = node->next;
    }
    node->next = newnode;
}

使用SLTNode** pphead接收,传递的phead是SLTNode*类型,而我们需要改变phead的内容,因此要传址而非传值,故用二级指针接收。

在这里我想用*pphead->next可是会报错,这是为什么呢,因为优先级,->的优先级比*的优先级高,pphead先与->结合,因此报错。

首先创建 节点(结构体指针newnode)保存需要插入的值,然后要判断两种情况,一种是*pphead为空时,直接让*pphead等于newnode。第二种*pphead不为空,创建一个node等于*pphead,循环向后找,找到node->next为空时,node->next = newnode。

头插的实现

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    newnode->data = x;
    if (*pphead == NULL)
    {
        *pphead = newnode;
        newnode->next = NULL;
    }
    else
    {
        SLTNode* ret = *pphead;
        newnode->next = ret;
        *pphead = newnode;
    }
}

头插跟尾插一样需要判断两种情况,当*pphead为空和不为空的两种情况。为空直接等于,不为空创建临时的ret保存*pphead,然后让*pphead(头节点)等于newnode。

尾删的实现

//尾删
void SLTPopBack(SLTNode** pphead)
{
    assert(*pphead);
    assert(pphead);
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLTNode* node = *pphead;
        SLTNode* ret = node->next;

        while (ret->next)
        {
            node = node->next;
            ret = ret->next;
        }
        free(ret);
        ret = NULL;
        node->next = NULL;
    }
}

删除涉及到空间的释放。因此要判断*ppead和ppead是否为空,不能传递一个空值来删除释放吧,所以要用assert断言。

也是要判断两种情况,一种是只有一个节点时,另一种是多个节点时。当为一个节点时,直接释放后置空即可,当为多个节点时需要遍历到最后一个节点后进行删除。

头删的实现

//头删
void SLTPopFront(SLTNode** pphead)
{
    assert(*pphead);
    assert(pphead);
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLTNode* node = (*pphead)->next;
        free(*pphead);
        *pphead = node;
    }
}

头删和尾删还是差不多,需要判断两种情况,是否是一个节点或多个节点。一个节点直接删除即可,多个节点,将头节点指向第二个节点。

查找的实现

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

void SLTfind(SLTNode* phead, SLTDataType x)
{
    SLTNode* ret = SLTFind(phead, x);
    if (ret)
    {
        printf("找到了%d\n", ret->data);
    }
    else
    {
        printf("没找到%d\n", x);
    }
}

先创建SLTFind函数返回需要查找的节点(在指定位置操作时需要用到,因此将查找节点的操作分割出来),后用SLTfind判断。

在指定位置之前插入的实现

//指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(*pphead);
    assert(pphead);
    assert(pos);
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    newnode->data = x;
    newnode->next = NULL;
    if (pos == *pphead)
    {
        SLTNode* node = (*pphead);
        *pphead = newnode;
        (*pphead)->next = node;
        return;
    }

    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
        prev = prev->next;
    }
    prev->next = newnode;
    newnode->next = pos;
}

链表中的节点都是动态开辟的空间,是在堆上的,并不会出了作用域就销毁,如果在链表中找到值为1的节点,那就把这个节点的地址返回

pos节点用SLTFind函数寻找,需要断言 pos是否为空,要判断*ppead和ppead是否为空。

判断两种情况,当插入节点为头节点时和不为头节点时。当插入节点为头节点时将头节点指向newnode。当不为头节点时创建prev使用while循环,当 prev->next=pos时退出,让prev的下个节点指向newnode,newnode的下个节点指向pos。

pos节点删除的实现

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    assert(*pphead);
    assert(pphead);
    assert(pos);

    if (pos == *pphead)
    {
        SLTNode* ret = *pphead;
        *pphead = (*pphead)->next;
        free(ret);
        ret = NULL;
        return;
    }

    SLTNode* prev = *pphead;
    while (prev->next != pos)
    {
        prev = prev->next;
    }
    SLTNode* node = pos->next;
    prev->next = node;
    free(pos);
    pos = NULL;
}

SLTFind函数寻找pos节点,判断两种情况,pos是否为头节点,然后进行删除操作。

在指定位置之后插入的实现

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    newnode->data = x;
    newnode->next = NULL;

    SLTNode* prve = pos->next;
    pos->next = newnode;
    newnode->next = prve;
}

这个更简单。

删除pos之后的节点的实现

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{

    assert(pos);
    SLTNode* prve = pos->next;
    SLTNode* node = prve;
    while (node)
    {
        node = prve->next;
        free(prve);
        prve = node;
    }
    pos->next = NULL;
}

找到pos后循环释放。

销毁链表的实现

void SListDesTroy(SLTNode** pphead)
{
    assert(*pphead);
    assert(pphead);
    SLTNode* prve = (*pphead);
    while(prve)
    {
        prve = prve->next;
        free(*pphead);
        *pphead = NULL;
        *pphead = prve;
    }
}

一样的循环释放。

下面是SListNode.c代码

#include "SListNode.h"

//打印
void SLTPrint(SLTNode* phead)
{
	while (phead)
	{
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("NULL\n");
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;
	//不能直接这样用*pphead->next = NULL;加括号(*pphead)->next,  优先级问题
	//链表为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//链表不为空,找尾节点
	SLTNode* node = *pphead;
	while (node->next)
	{
		node = node->next;
	}
	node->next = newnode;
}


//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	if (*pphead == NULL)
	{
		*pphead = newnode;
		newnode->next = NULL;
	}
	else
	{
		SLTNode* ret = *pphead;
		newnode->next = ret;
		*pphead = newnode;
	}
}


//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	assert(pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* node = *pphead;
		SLTNode* ret = node->next;

		while (ret->next)
		{
			node = node->next;
			ret = ret->next;
		}
		free(ret);
		ret = NULL;
		node->next = NULL;
	}
}


//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	assert(pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* node = (*pphead)->next;
		free(*pphead);
		*pphead = node;
	}
}



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

void SLTfind(SLTNode* phead, SLTDataType x)
{
	SLTNode* ret = SLTFind(phead, x);
	if (ret)
	{
		printf("找到了%d\n", ret->data);
	}
	else
	{
		printf("没找到%d\n", x);
	}
}


//指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(*pphead);
	assert(pphead);
	assert(pos);
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;
	if (pos == *pphead)
	{
		SLTNode* node = (*pphead);
		*pphead = newnode;
		(*pphead)->next = node;
		return;
	}

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = newnode;
	newnode->next = pos;
}


//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead);
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLTNode* ret = *pphead;
		*pphead = (*pphead)->next;
		free(ret);
		ret = NULL;
		return;
	}

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	SLTNode* node = pos->next;
	prev->next = node;
	free(pos);
	pos = NULL;
}


//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;

	SLTNode* prve = pos->next;
	pos->next = newnode;
	newnode->next = prve;
}


//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{

	assert(pos);
	SLTNode* prve = pos->next;
	SLTNode* node = prve;
	while (node)
	{
		node = prve->next;
		free(prve);
		prve = node;
	}
	pos->next = NULL;
}

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

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

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

相关文章

微服务架构与Dubbo

一、微服务架构 微服务架构是一种架构概念&#xff0c;旨在通过将功能分解到各个离散的服务中以实现对解决方案的解耦。 分布式系统式若干独立系统的集合&#xff0c;但是用户使用起来好像是在使用一套系统。 和微服务对应的是单体式开发&#xff0c;即所有的功能打包在一个WAR…

No spring.config.import property has been defined

运行Springcloud项目出现下面错误&#xff1a; Description: No spring.config.import property has been defined Action: Add a spring.config.importnacos: property to your configuration. If configuration is not required add spring.config.importoptional:nac…

C 排序算法

冒泡排序 冒泡排序&#xff08;英语&#xff1a;Bubble Sort&#xff09;是一种简单的排序算法。它重复地走访过要排序的数列&#xff0c;一次比较两个元素&#xff0c;如果他们的顺序&#xff08;如从大到小、首字母从A到Z&#xff09;错误就把他们交换过来。 过程演示&…

校园综合服务平台V3.9.2 源码修复大部分已知BUG

校园综合服务平台&#xff0c;版本更新至V3.9.1 &#xff0c;源码功能强大&#xff0c;ui 精美&#xff0c; 功能包含但不限于校园跑腿&#xff0c;外卖&#xff0c;组局&#xff0c;圈子&#xff0c;商城&#xff0c;抽奖&#xff0c;投票&#xff0c;团购&#xff0c;二手市场…

ROS学习笔记(12)AEB和TTC的实现

0.前提 在自动驾驶领域有许多关于驾驶安全的措施AEB和TTC就是为了驾驶安全而设计出来的。在这篇文章中我会讲解我对AEB和TTC算法的一些理解。本期ROS学习笔记同时也是ros竞速小车的学习笔记&#xff0c;我会将我的部分代码拿出来进行讲解&#xff0c;让大家更好的理解ttc和aeb…

Zabbix监控系统

一.监控软件的作用: 作为一个运维&#xff0c;需要会使用监控系统查看服务器状态以及网站流量指标&#xff0c;利用监控系统的数据去了解上线发布的结果和网站的健康状态 利用一个优秀的监控软件&#xff0c;我们可以&#xff1a; 对系统不间断实时监控实时反馈系统当前状态…

挣钱新玩法,一文带你掌握流量卡推广秘诀

手机流量卡推广项目是什么&#xff1f;听名字我相信大家就已经猜出来了&#xff0c;就是三大运营商为了开发新用户&#xff0c;发起的有奖推广活动&#xff0c;也是为了长期黏贴用户。在这个活动中&#xff0c;用户通过我们的渠道&#xff0c;就能免费办理低套餐流量卡&#xf…

链表OJ - 7(链表的回文结构)

题目描述&#xff08;来源&#xff09; 对于一个链表&#xff0c;请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法&#xff0c;判断其是否为回文结构。 给定一个链表的头指针A&#xff0c;请返回一个bool值&#xff0c;代表其是否为回文结构。保证链表长度小于等于900。…

【SVG】从零开始绘制条形图

效果图 定义背景色和坐标轴颜色 :root {--cord-color: #2be7ca; }body {background-color: #000;}画坐标轴 画X轴 <!-- 坐标轴 --> <g id"cordinate"><!-- x轴 --><line x1"50" y1"600" x2"900" y2"600&q…

同城货运系统的开发与货运搬家软件的技术性探讨和市场分析

一、市场前景展望 随着城市化进程的加快和电商物流的蓬勃发展&#xff0c;同城货运市场展现出了巨大的潜力。尤其是在快节奏的生活环境中&#xff0c;个人和企业对于快速、便捷、可靠的货运搬家服务需求日益增长。同城货运系统与货运搬家软件作为连接货主与货运司机的桥梁&…

Opengl 坐标系统概述

1.谈到opengl 坐标系统 首先要知道三个坐标转换矩阵&#xff0c;模型矩阵&#xff0c;观察矩阵&#xff0c;投影矩阵。 模型矩阵作用在将以物体中心为原点的坐标系统&#xff0c;转换到世界坐标。 观察矩阵作用在将世界坐标系统转换到观察坐标系统 投影矩阵作用在将观察坐标…

2024年苹果审核4.3相关问题综述

苹果审核中的4.3问题是开发者关注的焦点之一&#xff0c;本文对此进行了综述&#xff0c;总结了不同情况下的处理方式和优化策略。 第一种4.3 该类问题常见于代码或UI的重复率过高&#xff0c;苹果会直接拒绝应用。开发者需注意避免此类情况的发生&#xff0c;特别是在更新应…

亚信安全数据安全运营平台DSOP新版本发布 注入AI研判升维

在当今快速发展的数字经济时代&#xff0c;企业对于数据的依赖日益加深&#xff0c;数据安全已成为企业的生命线。亚信安全推出数据安全运营平台DSOP全新版本&#xff0c;正是为满足企业对数据安全的高度需求而设计。这款平台以其卓越的能力和技术优势&#xff0c;为企业的数据…

逆向案例二十七——某笔网登录接口非对称加密算法RSA,涉及全扣代码,浏览器断点调试,和补环境

网址&#xff1a;aHR0cHM6Ly93d3cuZmVuYmkuY29tL3BhZ2UvaG9tZQ 点击账号密码登录&#xff0c;找到登陆的包&#xff0c;发现password进行了加密。 顿时&#xff0c;老生常谈&#xff0c;开始搜索&#xff0c;找到最有嫌疑的加密代码。进行搜索&#xff0c;进入js文件后&#x…

云计算:Linux 部署 OVS 集群(服务端)实现VXLAN

目录 一、实验 1.环境 2.Linux 部署 OVS 集群&#xff08;服务端&#xff09; 3.Linux 部署VXLAN 一、实验 1.环境 (1) 主机 表1 宿主机 主机架构软件IP备注ovs_controller控制端192.168.204.63 1个NAT网卡 &#xff08;204网段&#xff09; ovs_server01服务端 Openv…

康谋技术 | 深入探讨:自动驾驶中的相机标定技术

随着自动驾驶技术的快速发展&#xff0c;多传感器的数据采集和融合可以显著提高系统的冗余度和容错性&#xff0c;进而保证决策的快速性和正确性。在项目开发迭代过程中&#xff0c;传感器标定扮演着至关重要的角色&#xff0c;它位于数据采集平台与感知融合算法之间&#xff0…

Python学习之-typing详解

前言&#xff1a; Python的typing模块自Python 3.5开始引入&#xff0c;提供了类型系统的扩展&#xff0c;能够帮助程序员定义变量、函数的参数和返回值类型等。这使得代码更易于理解和检查&#xff0c;也方便了IDE和一些工具进行类型检查&#xff0c;提升了代码的质量。 typ…

Unity之OpenXR+XR Interaction Toolkit快速监听手柄任意按键事件

前言 当我们开发一个VR时,有时希望监听一个手柄按键的点击事件,或者一个按钮的Value值等。但是每次有可能监听的按钮有不一样,有可能监听的值不一样,那么每次这么折腾,有点累了,难道就没有一个万能的方法,让我可以直接监听我想要的某个按钮的事件么? 答案是肯定的,今…

【结构型模式】代理模式

一、代理模式概述 代理模式的定义-意图&#xff1a;给某一个对象提供一个代理或占位符&#xff0c;并由代理对象来控制来原对象的访问(对象结构型模式)。某个客户端不能直接操作到某个对象&#xff0c;但又必须和那个对象有所互动。 代理模式分析&#xff1a; 1.引入一个新的代…

Flutter 之 HTTP3/QUIC 和 Cronet 你了解过吗?

虽然 HTTP3/QUIC 和 cronet 跟 Flutter 没太大关系&#xff0c;只是最近在整理 Flutter 相关资料时发现还挺多人不了解&#xff0c;就放到一起聊聊。 本篇也是主要将现有资料做一些简化整合理解。 前言 其实为什么会有 HTTP3/QUIC &#xff1f;核心原因还是现有协议已经无法满…