线性表—单链表实现

文章目录

链表介绍

单链表介绍

创建单链表节点

销毁

打印

查找

创建节点

增加数据

尾插

头插

指定位置插入

删除数据

尾删

头删

指定位置删除

整体代码

SListNode.h

SListNode.c

 

链表介绍

     链表是一种物理存储单元上非连续、非顺序的存储结构，由一系列节点（链表中每一个元素称为节点）组成。

 

单链表介绍

     单链表是一种链式存取的结构，它由一个个节点组成。

     节点由两部分组成：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点的地址。最后一个节点的指针域指向NULL。

4d6da9fe2e3f408db26047ac595e7cbf.png

 

创建单链表节点

     由上面可知单链表节点需要用结构体定义如下：

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType date;//数据域
	struct SListNode* next;//指针域
}SLTNode;

 

销毁

     这些节点都是动态开辟的，所以一定要销毁。销毁时要一个一个销毁。绝对不可以直接头节点。

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

}

     大家可能注意到了，这里用了二级指针为什么呢？

     在创建头节点时(SLTNode* phead = NULL)，phead是指向结构体的指针，如果传的是一级指针那就相当于是传值调用并不是传址调用，所以这里要是二级指针。

打印

     遍历一遍，这里并不需要断言，因为单链表可能为空。当pcur为NULL时循环结束（这里一级指针就行这里就只是需要值）。

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

 

查找

     查找和打印很像，只是把打印换成判断是否存在。存在返回它的节点，否则返回NULL（这里一级指针就行这里就只是需要值）。

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

 

创建节点

     节点是用malloc自动创建的，在创建完后要初始化一下，然后返回创建的节点。

//创建
SLTNode* SLTCheckCapacity(SLTDataType x)
{
	SLTNode* Node = (SLTNode*)malloc(sizeof(SLTNode));
	if (Node == NULL)
	{
		perror("malloc()");
		exit(1);
	}
	Node->date = x;
	Node->next = NULL;
	return Node;
}

 

增加数据

     要断言传过来的pphead是否为NULL。

尾插

     这里要分情况讨论是空链表还是非空链表（如果不分情况就可能会对NULL解引用）。

  • 空链表：把新节点赋值给头节点。
  • 非空链表：找到最后一个节点让它的next等于新节点。

82ba0933e58e4479bf47f7d6e9bb259c.png

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* node = SLTCheckCapacity(x);//创建节点
	if (*pphead == NULL)//空链表
	{
		*pphead = node;
	}
	else//非空链表
	{
		SLTNode* pcur = *pphead;
		while (pcur->next)//找最后的节点
		{
			pcur = pcur->next;
		}
		pcur->next = node;
	}
}

 

头插

     这个并不需要分情况，让新节点的next等于头节点，在把新节点赋给头节点。

562e85f44d8e418c91d45e762e07bb5b.png

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* node = SLTCheckCapacity(x);
	node->next = *pphead;
	*pphead = node;
}

 

指定位置插入

     这里要另外判断一下链表和pos是否为空。这里要分情况讨论pos是头节点还是非头节点。

  • 头节点：相当于是头插。
  • 非头节点：找到pos的上一个节点，在它们之间插入即可。

102b87b27e644aa68b462aa434381ea7.png

//在指定位置插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* node = SLTCheckCapacity(x);
	if (*pphead == pos)//头节点
	{
		node->next = *pphead;
		*pphead = node;
	}
	else//非头节点
	{
		SLTNode* pcur = *pphead;
		while (pcur->next != pos)//找到pos的上一个节点
		{
			pcur = pcur->next;
		}
		node->next = pos;
		pcur->next = node;
	}
}

     举例：

024ee873502c4298b6bc7983ec002f63.png

 

删除数据

     要断言传过来的pphead是否为NULL，*pphead是否为空链表。

尾删

     这里要分情况讨论链表是否只有一个节点。

  • 一个节点：直接把头节点释放，并把它置为NULL。
  • 多个节点：找到倒数第二个节点，先释放最后的节点，再把倒数第二个节点的next置为NULL（如果不先释放就会找不到最后的节点）。

0c295d6d483a4065a8c4afdbdf90ad33.png

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)//一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//多个节点
	{
		SLTNode* pcur = *pphead;
		while (pcur->next->next)//找倒数第二的节点
		{
			pcur = pcur->next;
		}
		free(pcur->next);
		pcur->next = NULL;
	}
}

 

头删

     这个并不需要分情况，把第二个节点赋给头节点，然后在释放头节点，并置为NULL。fab512ffdceb44bb82e18038c82d6ce4.png

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

 

指定位置删除

     这里要分情况讨论pos是否为头节点。

  • pos是头节点：相当于是头删。
  • pos不是头节点：找到pos的上一个节点，让上一个节点的next等于pos的next。最后释放pos即可。

0ce7feb6fb184074bd58c6ea9f801615.png

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (*pphead == pos)//pos是头节点
	{
		*pphead = pos->next;
	}
	else//pos不是头节点
	{
		SLTNode* pcur = *pphead;
		while (pcur->next != pos)//找pos的上一个节点
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
	}
	free(pos);
	pos = NULL;
}

     举例：

53337dfa554b4378a774f9a16e338fb0.png

 

整体代码

SListNode.h

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

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType date;//数据域
	struct SListNode* next;//指针域
}SLTNode;

//销毁链表
void SListDesTroy(SLTNode** pphead);

//打印
void SLTPrintf(SLTNode* phead);

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//创建
SLTNode* SLTCheckCapacity(SLTDataType x);

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//在指定位置插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

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

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

//删除指定位置数据
void SLTErase(SLTNode** pphead, SLTNode* pos);

SListNode.c

#include "SListNode.h"

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

}

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

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

//创建
SLTNode* SLTCheckCapacity(SLTDataType x)
{
	SLTNode* Node = (SLTNode*)malloc(sizeof(SLTNode));
	if (Node == NULL)
	{
		perror("malloc()");
		exit(1);
	}
	Node->date = x;
	Node->next = NULL;
	return Node;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* node = SLTCheckCapacity(x);
	if (*pphead == NULL)
	{
		*pphead = node;
	}
	else
	{
		SLTNode* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = node;
	}
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* node = SLTCheckCapacity(x);
	node->next = *pphead;
	*pphead = node;
}

//在指定位置插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* node = SLTCheckCapacity(x);
	if (*pphead == pos)
	{
		node->next = *pphead;
		*pphead = node;
	}
	else
	{
		SLTNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		node->next = pos;
		pcur->next = node;
	}
}

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

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

//删除指定位置数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (*pphead == pos)
	{
		*pphead = pos->next;
	}
	else
	{
		SLTNode* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
	}
	free(pos);
	pos = NULL;
}

 

     好了讲到这儿就差不多讲完了，希望你能有所收获。如果有错误的地方请及时指出，有什么不懂的地方可以私信我哈，如果觉得不错那就点点赞吧！

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

相关文章

每日OJ题_贪心算法二③_力扣1005. K 次取反后最大化的数组和

每日OJ题_贪心算法二③_力扣1005. K 次取反后最大化的数组和

目录 力扣1005. K 次取反后最大化的数组和 解析代码 力扣1005. K 次取反后最大化的数组和 1005. K 次取反后最大化的数组和 难度 简单 给你一个整数数组 nums 和一个整数 k &#xff0c;按以下方法修改该数组&#xff1a; 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。…
阅读更多...
Python根据预设txt生成“你画我猜”题目PPT（素拓活动小工具）

Python根据预设txt生成“你画我猜”题目PPT（素拓活动小工具）

Python根据预设txt生成“你画我猜”题目PPT&#xff08;素拓活动小工具&#xff09; 场景来源 去年单位内部的一次素拓活动&#xff0c;分工负责策划设置其中的“你画我猜”环节&#xff0c;网络上搜集到题目文字后&#xff0c;想着如何快速做成对应一页一页的PPT。第一时间想…
阅读更多...
机器学习笔记-20

机器学习笔记-20

处理大数据集的算法 1. 随机梯度下降 我们之前一直在学的梯度下降算法也叫Batch梯度下降算法&#xff0c;前面的笔记有提过一嘴。以线性回归为例子&#xff0c;随机梯度下降也适用于其他使用Batch梯度下降算法求参数的学习算法&#xff0c;随机梯度下降是对Batch梯度下降算法的…
阅读更多...
[图解]被严重污染的领域专家

[图解]被严重污染的领域专家

0 00:00:00,740 --> 00:00:04,610 今天我们来说一下领域专家 1 00:00:05,480 --> 00:00:06,920 这个概念 2 00:00:08,460 --> 00:00:13,180 这个概念现在已经被严重污染了 3 00:00:16,080 --> 00:00:21,170 你看&#xff0c;这是来自一个领域驱动设计课程的资料…
阅读更多...
数据结构与算法---树

数据结构与算法---树

数据结构可视化网址 Structure Visualization: https://www.cs.usfca.edu/~galles/visualization/Totuma: https://www.totuma.cn/Algorithm Visualizer: https://algorithm-visualizer.org/ 构建二叉树 // C#include<stdio.h> #include<stdlib.h>typedef char T…
阅读更多...
题目：线性代数

题目：线性代数

问题描述&#xff1a; 解题思路&#xff1a; 列相乘&#xff0c;然后行相加。 注意点&#xff1a;由于元素数据范围最大为1e6&#xff0c;两个元素相乘乘积最大为1e12&#xff0c;如果元素类型为int则在乘的过程中就会爆炸&#xff0c;所以需要开long long类型。 AC代码…
阅读更多...
【Linux网络】SSH服务

【Linux网络】SSH服务

目录 一、SSH概述与使用 1.1 定义 1.2 优点 1.3 原理 1.4 命令登录 1.5 跳板登录 1.6 远程控制 二、SSH配置 2.1 常用的服务端配置 2.2 ssh服务最优配置 三、免密登录 3.1 操作原理 3.2 操作步骤 一、SSH概述与使用 1.1 定义 SSH&#xff08;Secure Shell&#…
阅读更多...
【C++】滑动窗口：最大连续1的个数

【C++】滑动窗口：最大连续1的个数

1.题目 2.算法思路 其实在做这道题的时候并不需要真的把0翻转成1&#xff0c;只需要找到最长的子数组且该子数组中0的个数不大于K&#xff0c;就可以了&#xff01; 当然我们首先想到的是暴力穷举法&#xff1a; 找到所有符合题意的子数组&#xff0c;跳出最长的那个就可以了…
阅读更多...
Integer中的缓存机制

Integer中的缓存机制

先看一个示例&#xff1a; public static void main(String[] args) {Integer a127;Integer b127;System.out.println(ab);Integer c128;Integer d128;System.out.println(cd);} 输出&#xff1a; true false 为什么明明都是同一个数字进行比较&#xff0c;当数字等于127的…
阅读更多...
JVM笔记-常用命令

JVM笔记-常用命令

1、jstat jstat是一个极强的监视JVM的工具&#xff0c;可以用来监视JVM的各种堆和非堆的大小以及内存使用量。 Usage: jstat -help|-optionsjstat -<option> [-t] [-h<lines>] <vmid> [<interval> [<count>]]jstat的常用用法如图所示&#xff…
阅读更多...
Matlab各个版本介绍、区别分析及推荐

Matlab各个版本介绍、区别分析及推荐

MATLAB&#xff0c;由美国MathWorks公司出品&#xff0c;是一款广泛应用的商业数学软件。自其诞生之初&#xff0c;MATLAB便以其强大的矩阵计算能力、灵活的编程环境以及广泛的应用领域&#xff0c;赢得了全球科研工作者和工程师的青睐。本文将详细介绍MATLAB的各个版本&#x…
阅读更多...
蓝桥杯练习系统（算法训练）ALGO-950 逆序数奇偶

蓝桥杯练习系统（算法训练）ALGO-950 逆序数奇偶

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 老虎moreD是一个勤于思考的青年&#xff0c;线性代数行列式时&#xff0c;其定义中提到了逆序数这一概念。不过众所周知我们…
阅读更多...
力扣hot100：101. 对称二叉树（双指针以不同方式递归）

力扣hot100：101. 对称二叉树（双指针以不同方式递归）

LeetCode&#xff1a;101. 对称二叉树 看了第一个样例&#xff0c;很容易直接层序遍历看每一层的前后是否相同。但接下来这个样例告诉你&#xff0c;不能这样做。 层序遍历 仔细思考会发现&#xff0c;层序遍历不能看本结点&#xff0c;但是可以看儿子结点是否对称&#xf…
阅读更多...
RK3568平台（时间篇）看门狗

RK3568平台（时间篇）看门狗

一.看门狗原理 在产品化的嵌入式系统中&#xff0c;为了使系统在异常情况下能自动复位&#xff0c;一般都需要引入看门狗。 看门狗其实就是一个可以在一定时间内被复位的计数器。当看门狗启动后&#xff0c;计数器开始自动计数&#xff0c;经过一定时间&#xff0c;如果没有被…
阅读更多...
笔记-mathtype公式在PDF或打印出来显示不全

笔记-mathtype公式在PDF或打印出来显示不全

原文中的公式&#xff1a; 纸质版打印出来的公式有缺失 问题描述&#xff1a;mathtype公式编辑器所编辑的公式转成PDF或者打印出来有缺失 以下是解决方法的具体描述。 目录 一、准备工作二、操作步骤 一、准备工作 1、工具&#xff1a;mathtype、微软word 二、操作步骤 …
阅读更多...
概念解析 | 互补学习系统

概念解析 | 互补学习系统

注1：本文系"概念解析"系列之一，致力于简洁清晰地解释、辨析复杂而专业的概念。本次辨析的概念是：互补学习系统（Complementary Learning Systems） 概念解析：互补学习系统 Paper Summary - “Complementary Learning Systems Theory Updated” | Rylan Schaeffer…
阅读更多...
Linux下Palabos源码编译安装及使用

Linux下Palabos源码编译安装及使用

目录 软件介绍 基本依赖 其它可选依赖 一、源码下载 二、解压缩&#xff08;通过方式1下载源码.zip格式&#xff09; 三、编译安装 3.1 自带算例 ​编辑3.2 自行开发算例 四、简单使用 4.1 串行运行 4.2 并行运行 4.3 查看结果 软件介绍 Palabos是一款基于LBM&…
阅读更多...
前端面试和一些建议

前端面试和一些建议

最近公司在招前端&#xff0c;我有跟着一起参与面试。我们主要负责面试的人&#xff0c;不会问那些什么闭包&#xff0c;原型链&#xff0c;他觉得那些东西在我们日常开发中用不到&#xff0c;问的基本都是一些工作中的问题。这些问题不是每次都问&#xff0c;但也就问这些了。…
阅读更多...
[论文阅读] 测试时间自适应TTA

[论文阅读] 测试时间自适应TTA

最初接触 CVPR2024 TEA: Test-time Energy Adaptation [B站]&#xff08;1:35:00-1:53:00&#xff09;https://www.bilibili.com/video/BV1wx4y1v7Jb/?spm_id_from333.788&vd_source145b0308ef7fee4449f12e1adb7b9de2 实现&#xff1a; 读取预训练好的模型参数设计需要更…
阅读更多...
C语言写一个终端进度条

C语言写一个终端进度条

C语言写一个终端进度条 这个功能挺简单的&#xff0c;主要有以下两点&#xff1a; 如何获取终端宽度如何让字符在原地闪烁 如何获取终端宽度 这里用到了设备控制接口函数ioctl()&#xff0c;下面简单的介绍一下这个函数的用法&#xff1a; ioctl是一个在Unix和类Unix系统中…
阅读更多...
最新文章

Copyright @ 2022~2023