数据结构——单链表专题

目录

    • 1. 链表的概念及结构
    • 2. 实现单链表
      • 初始化
      • 尾插
      • 头插
      • 尾删
      • 头删
      • 查找
      • 在指定位置之前插入数据
      • 在指定位置之后插入数据
      • 删除指定位之前的节点
      • 删除指定位置之后pos节点
      • 销毁链表
    • 3. 完整代码
      • test.c
      • SList.h
    • 4. 链表的分类

1. 链表的概念及结构

在顺序表中存在一定的问题:

  1. 顺序表的中间/头部插入、删除需要挪动数据
  2. 扩容存在性能的消耗
  3. 会有空间的浪费

而链表是独立的节点组成

链表概念:链表是一种物理存储结构上非连续、非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表、顺序表都是线性表

逻辑结构一定是线性的
物理结构不一定是线性的

在这里插入图片描述

图中指针变量plist保存的是第一个节点的地址,我们称plist此时“指向”第一个节点,如果我们希望plist“指向第二个节点时,只需要修改plist保存的内容为0x0012FFA0

为什么还需要指针变量来保存下一个节点的位置?

链表中每个节点都是独立申请的(即需要插入数据时才去申请一块节点的空间),我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

链表是由一个一个的节点组成的
一个节点由两部分组成:要存储的数据+指针

int a = 1;
int* pa = &a;

节点结构的定义

struct SListNode{
int data;
struct SListNode* next;
}

在这里插入图片描述

链表结构体的打印方式:

在这里插入图片描述

补充说明:

  1. 链式机构在逻辑上是连续的,在物理结构上不一定连续
  2. 节点一般是从堆上申请的
  3. 从堆上申请来的空间,是按照一定策略分配出来的,每次申请的空间可能连续,可能不连续

2. 实现单链表

初始化

typedef int SLTDataType;
//链表是由节点组成的
typedef struct SListNode
{
	SLTDataType data;//节点数据
	struct SListNode* next;//指针变量保存下一个节点的地址
}SLTNode;

尾插

//公共部分,开辟一个新的节点
SLTNode* SLBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

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

	SLTNode* newnode = SLBuyNode(x);

	//链表为空,新节点作为phead
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//链表不为空,找尾结点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//ptril就是尾结点,将尾结点指向newnode
	ptail->next = newnode;
}

在这里插入图片描述

在这里插入图片描述

头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = SLBuyNode(x);

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

在这里插入图片描述

尾删

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);

	//链表不能为空
	assert(*pphead);//指向第一个节点的地址

	//链表不为空
	//链表只有一个节点/多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	
	prev->next = NULL;
	//销毁尾结点
	free(ptail);
	ptail = NULL;
}

在这里插入图片描述

头删

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);

	//链表不能为空
	assert(*pphead);

	//让第二个节点称为新的头
	SLTNode* next = (*pphead)->next;//->优先级高于*
	//把旧的头节点释放掉
	free(*pphead);
	*pphead = next;
}

在这里插入图片描述

查找

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(*pphead);

	//遍历链表
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到当前数据
	return NULL;
}

在这里插入图片描述

在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	//链表不能为空
	assert(*pphead);

	//pos刚好是头结点
	if (pos == *pphead)
	{
		//头插
		SLTPushFront(pphead, x);
		return;
	}

	//pos不是头结点的情况
	SLTNode* newnode = SLBuyNode(x);
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//找到了
	prev->next = newnode;
	newnode->next = pos;
}

在这里插入图片描述

在指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = SLBuyNode(x);

	newnode->next = pos->next;
	pos->next = newnode;
}

在这里插入图片描述

删除指定位之前的节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//pos刚好是头结点,没有前驱节点,执行头删
	if (*pphead == pos)
	{
		//头删
		SLTPopFront(pphead);
		return;
	}

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

}

在这里插入图片描述

删除指定位置之后pos节点

//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

	//pos  pos->next  pos->next->next
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}

}

在这里插入图片描述

销毁链表

//销毁链表
void SListDesTory(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

在这里插入图片描述

3. 完整代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
#include <stdio.h>

//void SlistTest1()
//{
//	//一般不会这样去创建链表,这里只是为了给大家展示链表的打印
//	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
//	node1->data = 1;
//	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
//	node2->data = 2;
//	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
//	node3->data = 3;
//	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
//	node4->data = 4;
//
//	node1->next = node2;
//	node2->next = node3;
//	node3->next = node4;
//	node4->next = NULL;
//
//	SLTNode* plist = node1;//定一个指针指向第一个节点
//	SLTPrint(plist);
//}



void SlistTest2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 0);
	SLTPrint(plist);


	//SLTPushFront(&plist, 2);
	//SLTPushFront(&plist, 3);
	//SLTPrint(plist);


	SLTPopBack(&plist);
	SLTPrint(plist);
}

void SlistTest3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 0);
	SLTPrint(plist);

	//头删
	SLTPopFront(&plist);
	SLTPrint(plist);

	//查找
	SLTNode* FindRet = SLTFind(&plist, 0);
	if (FindRet)
	{
		printf("找到了\n");
	}
	else {
		printf("未找到\n");
	}

	SLTInsert(&plist, FindRet, 100);
	SLTPrint(plist);

	SLTInsertAfter(FindRet, 200);
	SLTPrint(plist);

	//删除指定位置的节点
	SLTErase(&plist, FindRet);
	SLTPrint(plist);

	//销毁节点
	SListDesTory(&plist);
}

int main()
{
	SlistTest3();
	//SlistTest2();
	//SlistTest1();
	return 0;
}


SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
#include <assert.h>


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


SLTNode* SLBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

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

	SLTNode* newnode = SLBuyNode(x);

	//链表为空,新节点作为phead
	if (*pphead == NULL)
	{
		*pphead = newnode;
		return;
	}

	//链表不为空,找尾结点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//ptril就是尾结点,将尾结点指向newnode
	ptail->next = newnode;
}


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

	SLTNode* newnode = SLBuyNode(x);

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


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

	//链表不能为空
	assert(*pphead);//指向第一个节点的地址

	//链表不为空
	//链表只有一个节点/多个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	
	prev->next = NULL;
	//销毁尾结点
	free(ptail);
	ptail = NULL;
}


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

	//链表不能为空
	assert(*pphead);

	//让第二个节点称为新的头
	SLTNode* next = (*pphead)->next;//->优先级高于*
	//把旧的头节点释放掉
	free(*pphead);
	*pphead = next;
}


//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(*pphead);

	//遍历链表
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到当前数据
	return NULL;
}


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

	//链表不能为空
	assert(*pphead);

	//pos刚好是头结点
	if (pos == *pphead)
	{
		//头插
		SLTPushFront(pphead, x);
		return;
	}

	//pos不是头结点的情况
	SLTNode* newnode = SLBuyNode(x);
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//找到了
	prev->next = newnode;
	newnode->next = pos;
}


//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = SLBuyNode(x);

	newnode->next = pos->next;
	pos->next = newnode;
}


//删除指定位之前的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//pos刚好是头结点,没有前驱节点,执行头删
	if (*pphead == pos)
	{
		//头删
		SLTPopFront(pphead);
		return;
	}

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

}


//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	assert(pos->next);

	//pos  pos->next  pos->next->next
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}


//销毁链表
void SListDesTory(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

SList.h

#define _CRT_SECURE_NO_WARNINGS 1

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


typedef int SLTDataType;
//链表是由节点组成的
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* 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** pphead, SLTDataType x);

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

//删除指定位置之前pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除指定位置之后pos节点
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);



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

4. 链表的分类

链表的结构非常多样,一下情况组合组合起来就有8种链表结构:

在这里插入图片描述
链表说明:

在这里插入图片描述

在单链表中,“头结点”的“头”和“带头”链表是两个概念
单链表中提到的“头结点”指的是第一个有效的节点
“带头”链表里的“头”指的是无效的节点

虽然链表的种类非常之多,但是使用比较多的只有两种:单链表(不带头单向不循环链表)和双向链表(带头双向循环链表)

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

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

相关文章

15.一种坍缩式的简单——组合模式详解

当曾经的孩子们慢慢步入社会才知道&#xff0c;那年味渐淡的春节就像是疾驰在人生路上的暂停键。 它允许你在隆隆的鞭炮声中静下心来&#xff0c;瞻前顾后&#xff0c;怅然若失。 也允许你在寂静的街道上屏气凝神&#xff0c;倾听自己胸腔里的那团人声鼎沸。 孩子们会明白的&am…

库的操作【数据库】

目录 一、创建数据库 二、删除数据库 ​编辑 三、数据库编码问题 四、库的改查 查 1&#xff09;查有哪些数据库&#xff1a; 2&#xff09;使用某个数据库&#xff1a; 3&#xff09;当前在哪个数据库&#xff1a; 4&#xff09;有谁在使用 改alter 五、备份和恢复 …

Shiro-02-shiro 是什么?

序言 大家好&#xff0c;我是老马。 前面我们学习了 5 分钟入门 shiro 安全框架实战笔记&#xff0c;让大家对 shiro 有了一个最基本的认识。 shiro 还有其他优秀的特性&#xff0c;今天我们就一起来学习一下&#xff0c;为后续深入学习奠定基础。 Apache Shiro 是什么&…

2.18通过字符设备驱动分步注册过程实现LED驱动的编写,编写应用程序测试

应用程序&#xff1a; #include<stdlib.h> #include<stdio.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include<unistd.h> #include<string.h> #include<sys/ioctl.h> #include"myled.h&quo…

LabVIEW智能家居控制系统

LabVIEW智能家居控制系统 介绍了一个基于LabVIEW的智能家居控制系统的开发过程。该系统利用LabVIEW软件与硬件设备相结合&#xff0c;通过无线网络技术实现家居环境的实时监控与控制&#xff0c;提升居住舒适度和能源使用效率。 项目背景&#xff1a;随着科技的发展和生活水平…

vue-router 实现路由懒加载

在现代的Web开发中&#xff0c;前端技术的发展日新月异。在构建大规模单页应用&#xff08;Single Page Application&#xff09;时&#xff0c;路由管理是一个非常重要的环节。随着用户对网页速度和性能的要求越来越高&#xff0c;有效的路由管理能够显著提升用户体验。本篇博…

【RT-DETR有效改进】利用EMAttention加深网络深度提高模型特征提取能力(特征选择模块)

一、本文介绍 本文给大家带来的改进机制是EMAttention注意力机制,它的核心思想是,重塑部分通道到批次维度,并将通道维度分组为多个子特征,以保留每个通道的信息并减少计算开销。EMA模块通过编码全局信息来重新校准每个并行分支中的通道权重,并通过跨维度交互来捕获像素级…

IT行业高含金量证书全解析:开启职业生涯新篇章

在快速发展的IT行业&#xff0c;持续学习和专业认证是提升个人竞争力的重要途径。全球范围内存在着众多的IT认证&#xff0c;它们不仅能够验证你的技术能力&#xff0c;还能在求职和职业晋升中起到关键作用。 本篇博客将深入探讨IT行业中部分高含金量的证书&#xff0c;包括中…

【IO流】IOException IO流异常

IOException IO流异常 1. 概述2. try...catch异常处理2.1 基础做法2.2 JDK7方案2.3 JDK9方案 3. 注意事项 异常 概括 1. 概述 IOException&#xff08;Input/Output Exception&#xff0c;输入/输出异常&#xff09;是 Java 编程中常见的异常类型之一。它是 java.io 包中定义的…

速看!2024年泰国国际电力能源展10月16-18日

2024年泰国&#xff08;亚洲&#xff09;国际电力能源展暨电工技术设备展 展会时间&#xff1a;2024年10月16-18日 展会地点&#xff1a;泰国.曼谷BITEC会展中心 主办单位&#xff1a;新加坡Fireworks展览集团 组织单位&#xff1a;武汉柏翰展览有限公司(Fireworks China) …

SQL Developer 小贴士:Unshared Worksheet

在Oracle SQL Developer中&#xff0c;最常用的功能应该是SQL Worksheet&#xff0c;或Worksheet。 可以创建两类Worksheet&#xff0c;即Worksheet和Unshared Worksheets。前者是共享数据库连接的&#xff0c;后者会单独创建自己的连接。前者的快捷键是AltF10&#xff1b;后者…

趋高技术开发出超低价的视觉尺寸测量仪软件

2024年1月1日元旦节当日&#xff0c;深圳市趋高技术有限公司Fuxi实验室开发组成员成功开发出一款视觉尺寸测量仪软件。这款软件类比市场价格处于超低价。仅报三千二百元。有需要的码农或客户都可以了解一下&#xff0c;带回家。 趋高技术HITREND是深圳的一家高科技公司。 …

阅读笔记(SOFT COMPUTING 2018)Seam elimination based on Curvelet for image stitching

参考文献&#xff1a; Wang Z, Yang Z. Seam elimination based on Curvelet for image stitching[J]. Soft Computing, 2018: 1-16. 注&#xff1a;SOFT COMPUTING 大类学科小类学科Top期刊综述期刊工程技术 3区 COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE 计算机&#xf…

【论文解读】Latency-Aware Collaborative Perception

Latency-Aware Collaborative Perception 摘要引言方法SystemSyncNet 实验 摘要 协作感知最近显示出提高单智能体感知感知能力的巨大潜力。现有的协同感知方法通常考虑理想的通信环境。然而&#xff0c;在实践中&#xff0c;通信系统不可避免地存在延迟问题&#xff0c;导致安…

IO进程线程第一天

1.完成注册登录功能&#xff1a; 做个小菜单&#xff0c;功能1&#xff1a;是注册功能&#xff0c;输入注册账户和注册密码&#xff0c;将账户和密码写入文件中 功能2&#xff1a;是登录功能&#xff0c;提示并输入登录账户和登录密码&#xff0c;并用其遍历文件中的每一组账户…

应用回归分析:岭回归

岭回归&#xff0c;也称为Tikhonov正则化&#xff0c;是一种专门用于处理多重共线性问题的回归分析技术。多重共线性是指模型中的自变量高度相关&#xff0c;这种高度的相关性会导致普通最小二乘法&#xff08;OLS&#xff09;估计的回归系数变得非常不稳定&#xff0c;甚至无法…

二维码的颜色怎么改变?轻松3步修改二维码样式

怎么修改二维码的颜色呢&#xff1f;一般我们制作的二维码或者经过系统生成的二维码大多都是黑白颜色的&#xff0c;有些小伙伴会觉得不太美观无法满足自己的使用需求。那么对于想要修改二维码样式的小伙伴&#xff0c;可以使用二维码生成器的二维码美化功能来处理&#xff0c;…

力扣 第 124 场双周赛 解题报告 | 珂学家 | 非常规区间合并

前言 整体评价 T4的dp解法没想到&#xff0c;走了一条"不归路", 这个区间合并解很特殊&#xff0c;它是带状态的&#xff0c;而且最终的正解也是基于WA的case&#xff0c;慢慢理清的。 真心不容易&#xff0c;太难了。 T1. 相同分数的最大操作数目 I 思路: 模拟 c…

【机构vip教程】Charles(1):Charles的介绍及安装

Charles Charles 是在 Mac &#xff08;Charles是跨平台的 &#xff09;下常用的网络封包截取工具&#xff0c;在做移动开发、测试时&#xff0c;我们为了调试与服务器端的网络通讯协议&#xff0c;常常需要截取网络封包来分析。Charles是一个HTTP代理服务器,HTTP监视器,反转代…

白酒:制曲工艺的微生物多样性及其作用

在云仓酒庄豪迈白酒的制曲工艺中&#xff0c;微生物多样性是一个关键要素。曲是白酒生产中的重要配料&#xff0c;它由小麦、麸皮等原料制成&#xff0c;经过微生物的发酵和生长而形成。微生物的多样性和相互作用对曲的品质和白酒的口感具有重要影响。 首先&#xff0c;微生物多…