【数据结构|C语言版】单链表

  • 前言
  • 1. 单链表的概念和结构
    • 1.1 单链表的概念
    • 1.2 单链表的结构
  • 2. 单链表的分类
  • 3.单链表的实现
    • 3.1 新节点创建
    • 3.2 单链表头插
    • 3.3 单链表头删
    • 3.4 单链表尾插
    • 3.5 单链表尾删
    • 3.6 链表销毁
  • 4. 代码总结
    • 4.1 SLT.h
    • 4.2 SLT.c
    • 4.3 test.c
  • 后言

在这里插入图片描述

前言

各位小伙伴大家好！时隔不久，小编来给大家讲解一下单链表的相关知识。
在这里插入图片描述

1. 单链表的概念和结构

1.1 单链表的概念

【概念】链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

  • 逻辑上连续
  • 物理上非连续

1.2 单链表的结构

链表是由一个个结点组成的

【节点】
在这里插入图片描述
【单链表雏形】
在这里插入图片描述

2. 单链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构。
在这里插入图片描述
【常见分类】
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

比较常见的是无头单向非循环链表和带头双向循环链表。
在这里插入图片描述

3.单链表的实现

3.1 新节点创建

//创建一个新节点
SListNode* BuySLTNode(SLDateType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if(newNode == NULL)
	{
		perror("malloc:");
		return;
	}
	newNode->data = x;
	newNode=>next = NULL;
	return newNode;
}

3.2 单链表头插

//头插
void SListPushFront(SListNode** pphead,SLDateType x)
{
	assert(pphead);
	SListNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

3.3 单链表头删

//头删
void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SListNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
	cur = NULL;
}

3.4 单链表尾插

//尾插
void SLTPushBack(SListNode**pphead, SLDateType x)
{
	assert(pphead);
	SListNode* newnode = BuySLTNode(x);
	//1.链表为空
	//2.链表不为空
	if (*pphead == NULL)
	{
		*pphead = newnode;
        //不需要让newnode->next=NULL,在BuySLTNode中我们就已经进行过这个操作了
	}
	else
	{
		//找到链表的尾巴tail
		SListNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

3.5 单链表尾删

//尾删
void SListPopBack(SListNode**pphead)
{
	assert(pphead);
	assert(*pphead);
	//1.链表只有一个元素
	//2.链表有两个及两个以上的元素
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;
		SListNode* prev = NULL;
		//找尾
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
		tail = NULL;
·       另一种方法
		//SListNode* tail = *pphead;
		//while (tail->next->next)
		//{
		//	tail = tail->next;
		//}
		//free(tail->next);
		//tail->next = NULL;
	}
}

3.6 链表销毁

//销毁
void SLTDestory(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

4. 代码总结

4.1 SLT.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SLTNode
{
	SLTDateType data;
	struct SLTNode* next;
}SLTNode;
//创建一个结点
SLTNode* BuyListNode(SLTDateType x);
//销毁单链表
void SLTDestory(SLTNode** pphead);
//单链表头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);
//单链表尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);
//单链表头删
void SLTPopFront(SLTNode** pphead);
//单链表尾删
void SLTPopBack(SLTNode** pphead);
//单链表结点查找
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x);
//单链表结点删除(删除pos位置的结点)
void SLTErase(SLTNode** pphead, SLTNode* pos);
//单链表结点插入(在pos之前插入)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 单链表结点插入(在pos之后插入)
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x);
// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x);
//打印单链表
void PrintSLT(SLTNode * phead);

4.2 SLT.c

#include"SLT.h"
 
//建立一个新的结点
//这是链表的缺点：经常需要使用malloc为newnode开辟空间
SLTNode* BuyListNode(SLTDateType x)
{
	//为什么要用malloc，是因为，如果在BuyListNode函数中SLTNode newnode，出了这个函数，newnode就被销毁了，
	//用malloc开辟空间，只要我们不主动释放这个空间，这个空间的数据一直存在，
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//static SLTNode newnode；
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(0);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
 
//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);//phead可能为NULL，但是pphead指向phead，不可能为空
	SLTNode* newnode = BuyListNode(x);
	//这里可不是newnode->next = (*pphead)->next;
	newnode->next = *pphead;
	*pphead = newnode;
}
 
 
//尾插
//尾插特别容易出错，当链表中没有数据，即phead=NULL时，尾插就相当于头插了，此时需要改变phead的值
void SLTPushBack(SLTNode** pphead, SLTDateType x)
{
	assert(pphead);
	SLTNode* newnode = BuyListNode(x);
	//1、空
	//2、非空
	if (*pphead == NULL)
	{
		*pphead = newnode;
		//newnode->next = NULL;这一步是不需要的，newnode在建立的时候就默认newnode->next=NULL；
	}
	else
	{
		SLTNode* cur = *pphead;
		//这是单向链表的缺点，需要去找尾
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}
 
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//温柔的检查
	if (*pphead == NULL)
		return;
	//暴力的检查
	assert(*pphead);
	SLTNode* head = *pphead;
	*pphead = (*pphead)->next;
	free(head);
	head = NULL;
}
 
//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//1、一个结点
	//2、两个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next->next)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
}
//打印单向链表
void PrintSLT(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL");
	printf("\n");
}
 
//单链表查找某个结点
SLTNode* SLTNodeFind(SLTNode* phead, SLTDateType x)
{
	SLTNode* find = phead;
	//别忘记分析找不到结点的情况
	while (find)
	{
		if (find->data == x)
		{
			return find;
		}
		find = find->next;
	}
	return NULL;
}
 
//删除pos位置的结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			//如果prev->next已经为空了，说明链表已经查完了，还没有查到pos
			//证明pos传入有误
			assert(prev->next);
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;这个没必要，改变不了pos
	}
}
//单链表结点前插
//一般插入结点都是在pos之前插入，但单链表在实现前插是比较困难的
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(pphead);
	//头插
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	//非头插
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			assert(prev->next);
		}
		SLTNode* newnode = BuyListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
//单链表结点后插
void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	SLTNode* cur = *pphead;
	while (cur != pos)
	{
		cur = cur->next;
		//防止pos传错了
		assert(cur);
	}
	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
 
// 单链表结点修改
void SLTModify(SLTNode* phead, SLTNode* pos, SLTDateType x)
{
	SLTNode* cur = phead;
	while (cur != pos)
	{
		cur = cur->next;
		assert(cur);
	}
	pos->data = x;
}
//销毁链表
void SLTDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	//比cur->next!=NULL更好一些
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

4.3 test.c

#include"SLT.h"
void test1()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 0);
	SLTPushFront(&plist, -1);
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	PrintSLT(plist);
	SLTPopFront(&plist);
	SLTPopBack(&plist);
	PrintSLT(plist);
	SLTNode* pos = SLTNodeFind(plist, 0);
	SLTInsert(&plist, pos, -2);
	PrintSLT(plist);
	SLTInsert(&plist, pos, -1);
	PrintSLT(plist);
	SLTInsertBack(&plist, pos, 3);
	PrintSLT(plist);
	SLTModify(plist, pos, 4);
	PrintSLT(plist);
}
int main()
{
	test1();
}

后言

以上就是小编对单链表的一些初步认识。
如果觉得小编讲的还可以，还请一键三连。互三必回！
持续更新中~，下周见！
在这里插入图片描述

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

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

相关文章

百科不全书之 docker记录

百科不全书之 docker记录

docker记录 1.参考文件2. Docker简介与虚拟机的区别 3. 安装Docker注意 Windows家庭版的要额外设置 4.使用5.docker与ROS 1.参考文件 参考视频&#xff1a;B站【GeekHour】Docker入门教程: 【GeekHour】30分钟Docker入门教程 2. Docker简介 Docker是一个用于构建运行 传送…
阅读更多...
The C programming language (second edition,KR) exercise（CHAPTER 4）

The C programming language (second edition,KR) exercise（CHAPTER 4）

E x c e r c i s e 4 − 1 Excercise\quad 4-1 Excercise4−1&#xff1a; #include <stdlib.h> #include <stdio.h> #include <string.h> int strindex(char s[],char t[]); int strrindex(char s[],char t[]);int main(void) {char s[100]"qwoulddf…
阅读更多...
Java | Leetcode Java题解之第41题缺失的第一个正数

Java | Leetcode Java题解之第41题缺失的第一个正数

题目&#xff1a; 题解&#xff1a; class Solution {public int firstMissingPositive(int[] nums) {int n nums.length;for (int i 0; i < n; i) {while (nums[i] > 0 && nums[i] < n && nums[nums[i] - 1] ! nums[i]) {int temp nums[nums[i] …
阅读更多...
yolov8实战第七天——pyqt5-yolov8实现车牌识别系统（参考论文（约7000字）+环境配置+完整部署代码+代码使用说明+训练好的模型）

yolov8实战第七天——pyqt5-yolov8实现车牌识别系统（参考论文（约7000字）+环境配置+完整部署代码+代码使用说明+训练好的模型）

基于 pyqt5-yolov8实现车牌识别系统，包括图片车牌识别，视频车牌识别，视频流车牌识别。 效果展示（图片检测，检测到的内容添加到历史记录）： 效果展示（视频检测，视频车辆只会添加一条记录，下文更多实际应用中的优化策略）： 基于YOLOv8和PyQt5的车牌识别系统设计与…
阅读更多...
存储竞赛，角逐未来

存储竞赛，角逐未来

随着人工智能&#xff08;AI&#xff09;和大数据驱动的海量数据需求&#xff0c;对存储技术的要求也在不断提高。在此背景下&#xff0c;各大存储芯片巨头之间的技术竞赛日益激烈。 在NAND闪存领域&#xff0c;企业关注的重点在于层数的突破。近日&#xff0c;《韩国经济日报》…
阅读更多...
linux下编译c++程序报错“undefined reference to `std::allocator＜char＞::allocator()‘”

linux下编译c++程序报错“undefined reference to `std::allocator＜char＞::allocator()‘”

问题 linux下编译c程序报错“undefined reference to std::allocator::allocator()”。 原因 找不到c标准库文件。 解决办法 开始尝试给gcc指令添加-L和-l选项指定库路径和库文件名&#xff0c;但是一直不成功&#xff0c;后来把gcc改为g就可以了。
阅读更多...
Stylus精讲：网页设计新境界【写作AI一键生成】

Stylus精讲：网页设计新境界【写作AI一键生成】

首先&#xff0c;这篇文章是基于笔尖AI写作进行文章创作的&#xff0c;喜欢的宝子&#xff0c;也可以去体验下&#xff0c;解放双手&#xff0c;上班直接摸鱼~ 按照惯例&#xff0c;先介绍下这款笔尖AI写作&#xff0c;宝子也可以直接下滑跳过看正文~ 笔尖Ai写作&#xff1a;…
阅读更多...
SWCTF

SWCTF

easy_php 源码 <?php// flag is in flag.php highlight_file(__FILE__); ini_set(display_errors, 0); error_reporting(0);if (isset($_GET[myon1]) && isset($_GET[myon2]) && isset($_GET[myon3])) {$myon1 $_GET[myon1];$myon2 $_GET[myon2];$myon…
阅读更多...
# Win10 打不开【本地组策略编辑器】解决方案

# Win10 打不开【本地组策略编辑器】解决方案

Win10 打不开【本地组策略编辑器】解决方案 段子手168 问题描述&#xff1a; 当在 WIN R 打开【运行】输入&#xff1a;gpedit.msc 打开【本地组策略编辑器】时&#xff0c;出现错误时&#xff0c; 或者在【计算机管理】中 没有【本地用户和组】这一项。 可以试一下以下方…
阅读更多...
Go 之 sync.Mutex 加锁失效现象

Go 之 sync.Mutex 加锁失效现象

我先声明一下&#xff0c;并不是真的加锁失效&#xff0c;而是我之前的理解有误&#xff0c;导致看起来像是加锁失效一样。于是乎记录一下&#xff0c;加深一下印象。 我之前有个理解误区&#xff08;不知道大家有没有&#xff0c;有的话赶紧纠正一下——其实也是因为我这块的…
阅读更多...
Spec-Gaussian：3D高斯溅射的各向异性视图相关外观

Spec-Gaussian：3D高斯溅射的各向异性视图相关外观

Spec-Gaussian: Anisotropic View-Dependent Appearance for 3D Gaussian Splatting Spec-Gaussian&#xff1a;3D高斯溅射的各向异性视图相关外观 Ziyi Yang1,3  Xinyu Gao1  Yangtian Sun2  Yihua Huang2  Xiaoyang Lyu2 杨子怡 1,3 高新宇 1 太阳扬天 2 黄宜华 2 吕晓阳…
阅读更多...
【github主页】优化简历

【github主页】优化简历

【github主页】优化简历 写在最前面一、新建秘密仓库二、插件卡片配置1、仓库状态统计2、Most used languages&#xff08;GitHub 常用语言统计&#xff09;使用细则 3、Visitor Badge&#xff08;GitHub 访客徽章&#xff09;4、社交统计5、打字特效6、省略展示小猫 &#x1f…
阅读更多...
Java+springboot开发的医院智能导诊服务系统源码 自动兼容小程序与H5版本

Java+springboot开发的医院智能导诊服务系统源码 自动兼容小程序与H5版本

智能导诊系统 一、什么是智慧导诊系统&#xff1f; 智慧导诊系统是一种医院使用的引导患者自助就诊挂号、精准推荐科室、引导患者挂号就诊的系统。该系统结合医院挂号及就诊的HIS系统&#xff0c;为患者带来全流程的信息指引提醒&#xff0c;可以在全院区构建一个精细化、移动…
阅读更多...
react 项目路由配置（react-router-dom 版本 v6.3、v6.4）

react 项目路由配置（react-router-dom 版本 v6.3、v6.4）

根据 react-router-dom 的版本&#xff0c;有不同的方式 一、react-router-dom v6.3 用到的主要 api: BrowserRouteruseRoutesOutlet 下面是详细步骤&#xff1a; 1、index.js BrowserRouter 用来实现 单页的客户端路由使用 BrowserRouter 包裹 App放在 顶级 位置&#x…
阅读更多...
MATLAB初学者入门（7）—— 参数估计

MATLAB初学者入门（7）—— 参数估计

参数估计是利用实验数据来推断模型参数的过程&#xff0c;这在科学和工程领域中非常常见。MATLAB提供了多种工具来进行参数估计&#xff0c;尤其是当模型表现为非线性时。以下是使用MATLAB进行参数估计的一种常见方法&#xff0c;我们将通过一个具体的案例——化学动力学模型的…
阅读更多...
EI级 | Matlab实现VMD-TCN-LSTM-MATT变分模态分解卷积长短期记忆神经网络多头注意力多变量时间序列预测

EI级 | Matlab实现VMD-TCN-LSTM-MATT变分模态分解卷积长短期记忆神经网络多头注意力多变量时间序列预测

EI级 | Matlab实现VMD-TCN-LSTM-MATT变分模态分解卷积长短期记忆神经网络多头注意力多变量时间序列预测 目录 EI级 | Matlab实现VMD-TCN-LSTM-MATT变分模态分解卷积长短期记忆神经网络多头注意力多变量时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matl…
阅读更多...
手写一个Spring IOC框架

手写一个Spring IOC框架

目录 一&#xff0c;Spring IOC 二&#xff0c;流程图设计 三&#xff0c;设计思路解析 三&#xff0c;开始写代码 1.准备工作: 2.扫描并加载类信息 3.初始化bean 4.测试一下 一&#xff0c;Spring IOC Spring IoC容器是Spring框架的核心&#xff0c;它通过读取配置信息…
阅读更多...
【C语言】万字详讲操作符

【C语言】万字详讲操作符

目录 前言 一、操作符分类 二、算数操作符 三、移位操作符 四、位操作符 五、赋值操作符 六、单目操作符 6.1 逻辑反操作 6.2 负值与正值 6.3 取地址 6.4 sizeof 6.5 取反操作符 6.6 --和操作符 6.7 间接访问操作符&#xff08;解引用操作符&#xff09; 6.8 强…
阅读更多...
java导出数据到excel表中

java导出数据到excel表中

java导出数据到excel表中 环境说明项目结构1.controller层2.service层3.实现层4.工具类&#xff1a;ExcelUtil.java5.ProductModel.java类 使用的Maven依赖postman请求展示&#xff0c;返回内容需要前端接收浏览器接收说明&#xff08;如果下载下来的为zip类型&#xff0c;记得…
阅读更多...
矽塔SA8321 单通道 2.7-12.0V 持续电流 3.0A H 桥驱动芯片

矽塔SA8321 单通道 2.7-12.0V 持续电流 3.0A H 桥驱动芯片

描述 SA8321是为消费类产品&#xff0c;玩具和其他低压或者电池供电的运动控制类应用提供了一个集成的电机驱动器解决方案。此器件能够驱动一个直流无刷电机&#xff0c;由一个内部电荷泵生成所需的栅极驱动电压电路和4个功率 NMOS组成H桥驱动&#xff0c;集成了电机正转/反…
阅读更多...
最新文章

Copyright @ 2022~2023