首页 > 其他分享 >数据结构:单链表

数据结构:单链表

时间:2024-04-10 22:01:58浏览次数:21  
标签:pphead 单链 SLTNode NULL pos next 数据结构 节点

一.链表的概念及结构

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

链表的结构其实就像的火车:

车厢是独立存在的,且每节车厢都有车门。想象⼀下这样的场景,假设每节车厢的车门都是锁上的状态,需要不同的钥匙才能解锁,每次只能携带⼀把钥匙的情况下如何从车头走到车尾?最简单的做法:每节车厢里都放一把下一节车厢的钥匙。

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

与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为“结点/节点”。节点的组成主要有两个部分:当前节点要保存的数据和保存下一个节点的地址(指针变量)。

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

这就是链表的组成:

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

二.单链表的实现

先简单的定义一下链表的结构,后面的代码都是基于这个结构写出来的。

typedef int SLTDataType;

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

 1.创建一个新节点

//创建一个新的节点,data为x
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//用malloc动态开辟一块空间
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

这里创建的新节点,在后面的插入等过程需要用到

2.在链表后面插入一个节点(尾插)

先来看代码

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//assert断言,传过来的二级指针,不能是一个NULL
	//*pphead 就是指向第一个节点的指针
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;//因为要改变头结点,所以用二级指针
	}
	else
	{
		//找尾
		SLTNode* ptail = *pphead;//把头结点赋值给ptail
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail指向的就是尾结点
		ptail->next = newnode;
	}
}

这里如果第一个节点为空的话,实际上就是直接把newnode当成第一个节点了。而此时就需要改变第一个节点的地址(本来为空的)为newnode。因为我要改变第一个结点的指针,所以我们要用二级指针来改变它(如果用一级指针的话,在函数中会创建一个指针叫pphead,我们在之后给pphead赋值的时候,改变的就只是pphead,pphead指向了新节点,而不是我们真正的头结点)。

提醒一下,后面在找尾的时候,其实就不需要用到二级指针了,因为我们进行的尾插操作,不再需要改变头节点,此时我们改变的是结构体内部的数据next。

3.在链表头部插入一个新的节点(头插)

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//依然需要断言,传过来的指针不能为NULL
	SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
	//newnode *pphead
	newnode->next = *pphead;//把新节点的next指针指向头节点
	*pphead = newnode;//此时newnode为头结点,赋值给*pphead
}

这里我们依然对头结点进行了改变,所以依然需要用二级指针来接收。

4.删除尾部的节点(尾删)

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//链表不能为空
	assert(pphead && *pphead);//不仅仅需要判断传过来的pphead,还要防止链表为空的情况
	//链表只有一个节点
	if ((*pphead)->next == NULL) //-> 优先级高于*
	{
		free(*pphead);//直接把第一个节点的内存释放掉就行了
		*pphead = NULL;//避免野指针。
	}
	else
        {
		//链表有多个节点
		SLTNode* prev = *pphead;//记录尾节点的上一个节点
		SLTNode* ptail = *pphead;//用来遍历整个链表的指针
		while (ptail->next)//等ptail走到尾节点停止
		{
			prev = ptail;//prev来存储尾节点的上一个节点
			ptail = ptail->next;//一直走到末尾
		}
		//prev ptail
		free(ptail);//释放尾节点
		ptail = NULL;//置为空指针
		prev->next = NULL;//尾节点的next是NULL
	}
}

上面的*pphead=NULL的操作,如果是一级指针,我们只把pphead置为NULL了 ,而原来指向的头结点的指针没有置为NULL。

为了避免野指针,用二级指针

5.删除头部的节点(头删)

void SLTPopFront(SLTNode** pphead)
{
	//链表不能为空
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next; //把头结点的下一个节点的地址存起来
	free(*pphead);//直接释放就行了
	*pphead = next;//此时next是头结点,赋值给*pphead就行了
}

这个因为改变了指向第一个节点的指针,所以就需要用二级指针。

6.查找某个节点

既然前面都说了那么多的插入删除,此时的链表里面的数据我们就可以设计一个查找程序来查找一下。

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;//习惯:重新创建一个指向头结点的指针
	while (pcur)//等价于pcur != NULL
	{
		if (pcur->data == x)
		{
			return pcur;//找到了直接返回
		}
		pcur = pcur->next;//遍历整个链表
	}
	//pcur == NULL
	return NULL;//没有找到,返回NULL
}

因为只是查找,不需要对头结点的指针进行任何的改变,所以这里就直接把第一个节点的地址传参过去就行了,不需要用二级指针(当然如果自己搞不清楚什么时候用,那就都用就行了)。

7.在指定位置之前插入数据

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);//咱们插入的数据也不能为NULL
	SLTNode* newnode = SLTBuyNode(x);//创建一个新节点
	//若pos == *pphead;说明是头插
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);//直接调用头插函数就行了
	}
	else 
        {
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;//遍历链表,直到pos的前一个节点
		}
		//此时的prev就是pos的前一个节点
		newnode->next = pos;//把新节点的next指针指向pos
		prev->next = newnode;//把新节点放到它俩中间
	}
}

因为我们在函数里用到了头插,所以也需要用到二级指针。

8.在指定位置之后插入数据

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);//插入的节点不能为NULL

	SLTNode* newnode = SLTBuyNode(x);//创建的新节点
	//pos -> newnode -> pos->next
	newnode->next = pos->next;//把pos的下一个节点的地址赋值给新节点的next指针
	pos->next = newnode;//再把新指针的地址给pos的next指针
}

由于没有改变头结点,所以不需要用二级指针。

 关于这些函数的测试单独放在文章结尾。

9.删除指定节点

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);//要删除的节点也不能为NULL
	//分为两种情况:pos是头结点/pos不是头结点
	if (pos == *pphead)
	{
		//头删
		SLTPopFront(pphead);//头结点的话直接调用头删的函数就行了。
	}
	else 
        {
		SLTNode* prev = *pphead;//在后面的循环中,prev来存储pos的前一个节点的地址
		while (prev->next != pos)
		{
			prev = prev->next;//prev遍历到pos的前一个节点
		}
		
		prev->next = pos->next;//直接跳过pos这个节点,把prev的next指针赋值为,pos的下一个节点
		free(pos);
		pos = NULL;//也是避免野指针
	}
}

这里用到了头删,所以需要用二级指针。

10.删除指定位置之后的节点

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);//pos之后的节点也不能为NULL
	SLTNode* del = pos->next;//先存上pos之后的节点
	pos->next = del->next;//把pos后面的后面的节点赋值给pos的next指针
	free(del);//释放pos后面节点的空间
	del = NULL;//释放完空间置为NULL
}

11.销毁链表

//销毁链表
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);//头结点也不能为NULL

	SLTNode* pcur = *pphead;
	while (pcur)//等pur为NULL时结束循环
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;//遍历整个链表,经过一个节点释放一个
	}
	*pphead = NULL;//最后再把头节点置为NULL就行了
}

最后也是要把头结点置为NULL,所以需要用到二级指针传参。

三.链表的测试

void SListTest()
{
	SLTNode* plist = NULL;
	//测试尾插
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	//测试输出
	SLTPrint(plist); // 1->2->3->4->NULL
	//测试头插
	SLTPushFront(&plist, 6);
	SLTPrint(plist);
	//测试尾删
	SLTPopBack(&plist);
	SLTPrint(plist);
	//测试头删
	SLTPopFront(&plist);
	SLTPrint(plist);
	//测试查找
	SLTNode* find = SLTFind(plist, 1);
	//测试在指定位置后插入节点
	SLTInsertAfter(find, 11);
	SLTPrint(plist);
	//测试在指定位置插入节点
	SLTInsert(&plist, find, 12);
	SLTPrint(plist);
	//测试删除指定位置节点
	SLTErase(&plist, find);
	SLTPrint(plist);
	//测试删除指定位置之后位置节点
	find = SLTFind(plist, 12);
	SLTEraseAfter(find);
	SLTPrint(plist);
	//测试链表销毁
	SListDesTroy(&plist);
	SLTPrint(plist);
}
int main()
{
	SListTest();
	return 0;
}

输出出来的是这样: 

到这里,单链表的相关知识差不多就结束了。后面还有双向链表,循环链表什么的。先把这个单链表吃透了,再去看其他的各种链表。感谢大家的观看,如有错误,还请大家多多指出。

标签:pphead,单链,SLTNode,NULL,pos,next,数据结构,节点
From: https://blog.csdn.net/2301_81699364/article/details/137565050

相关文章

  • 初识--数据结构
    什么是数据结构?我们为什么要学习数据结构呢....一系列的问题就促使我们不得不了解数据结构。我们不禁要问了,学习C语言不就够了吗?为什么还要学习数据结构呢?这是因为:数据结构能够解决C语言解决不了的问题,比如:图形,树状图...要了解数据结构,就必须要知道:数据,数据项,数据元素,数据对象,......
  • 常用数据结构
    程序=数据结构+算法,数据结构是程序的骨架,而算法则是程序的灵魂常用的数据结构数组(Array):是一种线性数据结构,由相同类型的元素组成,可以通过索引访问元素。链表(LinkedList):是一种线性数据结构,由节点组成,每个节点包含数据和指向下一个节点的指针。栈(Stack):是一种后进先出(LIFO)的数......
  • 说说你对数据结构的理解?有哪些?区别?
    一、是什么数据结构是计算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的集合前面讲到,一个程序=算法+数据结构,数据结构是实现算法的基础,选择合适的数据结构可以带来更高的运行或者存储效率数据元素相互之间的关系称为结构,根据数据元素之间关系的......
  • 数据结构速成--数据结构和算法
            由于是速成专题,因此内容不会十分全面,只会涵盖考试重点,各学校课程要求不同,大家可以按照考纲复习,不全面的内容,可以看一下小编主页数据结构初阶的内容,找到对应专题详细学习一下。目录一、数据结构二、逻辑结构三、存储结构四、算法五、算法分析一、数......
  • NzN的数据结构--插入排序
         排序排序我要Disney,今天我们先来看看经典排序算法里的插入排序,先三连后看才是好习惯!!!目录一、排序的概念及应用1.排序的概念2.排序的应用3.常见的排序算法二、插入排序1.基本思想2.直接插入排序3.希尔排序(缩小增量排序)一、排序的概念及应用1.......
  • 大话数据结构(1)
    1线性表的链式存储结构,头指针指向每一个结点,表明,头指针不是第一个结点, 还有就是头指针可以指向头结点,头结点再指向第一个结点2 散列表(哈希表): 采用散列技术将记录存储在一块连续的存储空间中, 这块空间就称为散列表或哈希表想想链表, 这个名词就好理......
  • Python基础--python数据结构(字符串、列表和元组)
    前言!!!注意:本系列所写的文章全部是学习笔记,来自于观看视频的笔记记录,防止丢失。观看的视频笔记来自于:哔哩哔哩武沛齐老师的视频:2022Python的web开发(完整版)入门全套教程,零基础入门到项目实战数据结构1.字符串类型str1.1定义上个文件找1.2独有功能大写upper......
  • 数据结构——递增有序链表的插入
    题目:实验目的:1、掌握线性表的基本知识2、深入理解、掌握并灵活运用线性表。3、熟练掌握线性表的存储结构及主要运算的实现已知顺序表L递增有序,将X插入到线性表的适当位置上,保证线性表有序。。输入格式:第1行输入顺序表长度,第2行输入递增有序的顺序表,第3行输入要插入的数据元......
  • 【数据结构 | 并查集】维护元素分组信息,支持高效合并集合、查询元素所在集合
    文章目录并查集概述引入并查集的实现存储方式Union-Find抽象基类两种实现思路基本实现基于QuickFind思路基于QuickUnion思路优化基于size的优化基于rank的优化find优化路径压缩路径分裂路径减半总结并查集概述并查集(DisjointSetUnion,简称并查集),也叫......
  • 【数据结构与算法篇】单链表及相关OJ算法题
    【数据结构与算法篇】单链表及相关OJ算法题......