首页 > 其他分享 >【数据结构】单链表专题

【数据结构】单链表专题

时间:2024-09-08 12:25:15浏览次数:13  
标签:pphead 单链 SLTNode pos next 链表 专题 数据结构 节点

链表的概念及结构

概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表的结构跟火车车厢相似,淡季时车次的车厢会相应减少,旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上,不会影响其他车厢,每节车厢都是独立存在的。
车厢是独立存在的,且每节车厢都有车门。想象一下这样的场景,假设每节车厢的车门都是锁上的状态,需要不同的钥匙才能解锁,每次只能携带一把钥匙的情况下如何从车头走到车尾?
最简单的做法:每节车厢里都放一把下一节车厢的钥匙。
在链表里,每节“车厢”是什么样的呢?
在这里插入图片描述
与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为“结点/节点”。

节点的组成主要有两个部分:当前节点要保存的数据和保存下一个节点的地址(指针变量)。

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

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

链表中每个节点都是独立申请的(即需要插⼊数据时才去申请一块节点的空间),我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。
结合前面学到的结构体知识,我们可以给出每个节点对应的结构体代码:
假设当前保存的节点为整型:

struct SListNode
{
 int data; //节点数据
 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
};

当我们想要保存一个整型数据时,实际是向操作系统申请了一块内存,这个内存不仅要保存整型数据,也需要保存下一个节点的地址(当下一个节点为空时保存的地址为空)。
当我们想要从第一个节点走到最后一个节点时,只需要在前一个节点拿上下一个节点的地址(下一个节点的钥匙)就可以了。

给定的链表结构中,如何实现节点从头到尾的打印?
在这里插入图片描述

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

SList.h

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

typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//typedef struct SListNode 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* pos);

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

SList.c

#include"SList.h"
void SLTPrint(SLTNode* phead) {
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

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

	return newnode;
}

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

	SLTNode* newnode = SLTBuyNode(x);

	//链表为空,新节点作为phead
	if (*pphead == NULL) {
		*pphead = newnode;
		return;
	}
	//链表不为空,找尾节点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//ptail就是尾节点
	ptail->next = newnode;
}
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(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) //等价于pcur != NULL
	{
		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);

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

	//pos不是头结点的情况
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev -> newnode -> pos
	prev->next = newnode;
	newnode->next = pos;
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);

	//pos newnode pos->next
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos节点
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 pos pos->next
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	//pos->next不能为空
	assert(pos->next);

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

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

标签:pphead,单链,SLTNode,pos,next,链表,专题,数据结构,节点
From: https://blog.csdn.net/Sakura_ding/article/details/142024363

相关文章

  • 数据结构基础讲解(二)——线性表之单链表专项练习
    本文数据结构讲解参考书目:通过网盘分享的文件:数据结构 C语言版.pdf链接: https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e 提取码:ze8e 上一节我讲了线性表中顺序表的定义以及常用的算法,那么这节我将继续讲解顺序表中的链式结构以及常见的算法。数据......
  • 数据结构基础讲解(一)——线性表之顺序表专项练习
     本文数据结构讲解参考书目:通过网盘分享的文件:数据结构 C语言版.pdf链接:https://pan.baidu.com/s/159y_QTbXqpMhNCNP_Fls9g?pwd=ze8e提取码:ze8e目录前言一.线性表的定义二.线性表的基本操作三.线性表的顺序存储和表示四.顺序表中基本操作的实现1.顺序表......
  • 马老师浑元十三刀本质是DDD程序=算法+数据结构:浑元形意太极的本质是领域驱动设计(02)
    浑元形意太极的本质是领域驱动设计(01)在软件开发的旅程中,领域驱动设计就是我们的指路明灯。它照亮了我们前进的道路,驱散了迷茫的阴霾。有了领域驱动设计的指引,我们不再畏惧未知,不再害怕挑战。我们知道,无论前方有多么艰难的障碍,都有领域驱动设计为我们指明方向。领域驱动设计就......
  • 【数据结构】18.图(Graph)
    一、图的基本概念图是由顶点集合及顶点间的关系组成的一种数据结构:G=(V,E),其中:V={x|x属于某个数据对象集}是有穷非空集合;E={(x,y)|x,y属于V}或者E={<x,y>|x,y属于V&&Path(x,y)}是顶点间关系的有穷集合,也叫做边的集合。注意:线性表可以是空表,树可以是空树,但图......
  • 【电池专题】软包电池封装工序
    铝塑膜成型工序冲坑        铝塑膜成型工序,软包电芯可以根据客户的需求设计成不同的尺寸,当外形尺寸设计好后,就需要开具相应的模具,使铝塑膜成型。        成型工序也叫作冲坑,顾名思义,就是用成型模具在加热的情况下,在铝塑膜上冲出一个能够装卷芯的坑,具体的见......
  • (36)时序收敛专题--->原则三六
    1.1.1本节目录1)本节目录;2)本节引言;3)FPGA简介;4)时序收敛原则三六5)结束语。1.1.2本节引言“不积跬步,无以至千里;不积小流,无以成江海。就是说:不积累一步半步的行程,就没有办法达到千里之远;不积累细小的流水,就没有办法汇成江河大海。1.1.3FPGA简介FPGA(FieldProgrammableG......
  • (35)时序收敛专题--->原则三五
    1.1.1本节目录1)本节目录;2)本节引言;3)FPGA简介;4)时序收敛原则三五5)结束语。1.1.2本节引言“不积跬步,无以至千里;不积小流,无以成江海。就是说:不积累一步半步的行程,就没有办法达到千里之远;不积累细小的流水,就没有办法汇成江河大海。1.1.3FPGA简介FPGA(FieldProgrammableG......
  • Java-数据结构-栈和队列-Stack和Queue (o゚▽゚)o
    文本目录:❄️一、栈(Stack):  ▶1、栈的概念: ▶ 2、栈的使用和自实现:   ☑1)、Stack():   ☑2)、push(Ee):   ☑3)、empty():     ☑4)、peek(Ee):     ☑5)、pop(Ee):    ☑6)、size(Ee): ▶3、栈自实现的总代码:......
  • 数据结构--二叉树(C语言实现,超详细!!!)
    文章目录二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码二叉树的概念二叉树(BinaryTree)是数据结构中一种非常重要的树形......
  • 【愚公系列】2023年10月 GDI+绘图专题 DrawString
    ......