单链表的相关操作(初阶)-CSDN博客

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6


链表的概念

        链表是线性表的一种它是⼀种物理存储结构上⾮连续、⾮顺序的存储结构数据元素的逻

辑顺序是通过链表中的指针链接次序实现的 。其实链表就相当于一列火车

        链表的结构跟⽕⻋⻋厢相似淡季⻋厢会相应减少旺季时⻋厢会额外增加减少和增加车厢并不会影响其它车厢每节⻋厢都是独⽴存在的。且每节⻋厢都有⻋⻔。
        假设每节⻋厢的⻋⻔都被锁上且打开这些车厢所需要的钥匙各不相同那么如果乘务员从第一节车厢开始向后面的车厢走去如何从⻋头⾛到⻋尾
答案每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。
而每节车厢里面肯定是有人或者货物的所以这就引申出了一条新的概念在链表⾥每节“⻋厢”是由 下一个车厢的 本节车厢中存储的“数据" 组成的。

当你对后续的链表内容有问题请重新回来仔细观看下图
当你对后续的链表内容有问题请重新回来仔细观看上图

与顺序表不同的是链表⾥的每节"⻋厢"都是独⽴申请下来的空间我们称之为“ 结点/节点 ”。
结点 =  当前节点中保存的数据data + 保存下⼀个节点地址的指针变量next
        有了车厢我们就需要有一节火车头来带动这些车厢链表中的火车头就是 头结点头结点不存储数据指向链表的第一个有效结点存储数据的地址在这里plist就为头结点
为什么需要指针变量来保存下⼀个节点的位置
        因为链表在内存空间上的存储是非连续的 就和火车车厢一样根据需求进行增加和删除通俗来讲就是用到你这块儿了我用指针火车挂钩给你连上你就得给我进链表不用你的时候把脸上你的指针火车挂钩断开你就一边闲着去。

链表的相关操作

以下链表内容为不带头单向不循环链表

链表的创建

创建链表需要经历以下操作

1、定义一个结构体来表示链表的结点SList.h文件

//定义一种链表节点的结构实际应用中有多种这里只演示最基本的结构
typedef int SLDataType; //便于切换链表中存储数据的类型
struct SListNode {   
	SLDataType data;  //存储数据
	struct SListNode* next;  //用来保存下一个节点地址的指针变量next
};
typedef struct SListNode SLNode;  //将链表结点的结构体重命名为SLNode
2、编写创建链表的函数第二点这里的 内容只是为了方便理解后续内容具体情况请看下面的实际操作有个简单的了解
该函数主要进行的操作是        
①创建新节点并为其开辟内存空间
②将新结点的next指针指向下一个结点
//申请结点函数
void slttest()
{
	SLNode* node1 = (SLNode*)malloc(sizeof(SLNode)); 
	node1->data = 1;
	SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));
	node2->data = 2;
	SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));
	node3->data = 3;
	SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));
	node4->data = 4;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	//打印链表
	SLNode* plist = node1;  
	SLPrint(plist);
}

打印链表

//用phead表示头结点它指向链表的第一个结点如果思路出现混乱一定要再看一边前面的链表图
void SLPrint(SLNode* phead) 
{	
	//循环打印
	//为了能在遍历后仍能找到刚开始的起点我们就需要利用一个临时指针pcur来存储头结点的地址
	SLNode* pcur = phead;
    //当头结点不为空时进行循环
	while (pcur)
	{
    //打印此时所处结点中的数据
		printf("%d ->", pcur->data);
    //打印结束后让pcur指向下一个结点的地址
		pcur = pcur->next;
	}
    //到最后时现有结点遍历完成空间为NULL
	printf("NULL\n");
}

申请新节点

//申请有效结点函数并在该结点中存储数据
SLNode* SLByNode(SLDataType x) 
{
    //为链表的新结点申请一个新的空间
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
    //该节点中存储的数据为x
	node->data = x;
    //将该结点的下一个结点置为空因为我们也不知道它后面到底还要不要结点了
	node->next = NULL;
    //返回申请的新结点
	return node;
}

链表的尾插

//链表的尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{
    //判断传入的头结点plist是否为空
	assert(pphead);
	//如果存在头结点则进行后续操作
    //先申请一个新的有效结点
	SLNode* node = SLByNode(x);
    //如果第一个有效结点为空则令*pphead指向新创建的有效结点
	if (*pphead == NULL)
	{
		*pphead = node;
		return;
	}
    //如果第一个有效结点不为空则通过循环读取至链表的结尾
    //先定义一个临时的指针变量pcur令pcur指向第一个有效结点
	SLNode* pcur = *pphead;
    //然后利用pcur->next遍历至链表的末尾
	while (pcur->next)
	{
		pcur = pcur->next;
	}
    //当遍历至链表的末尾时让pcur指向新的有效结点
	pcur->next = node;
}

 对于传参中二级指针的解释

//pphead是一个二级指针通过判断它的非空情况可以得到整个链表是否存在
&plist 获取的是plist这个指针的地址==  pphead

//对于pphead的解引用
plist头结点的地址 == *pphead
如果第一个结点为空那么该结点的地址为空

//对于*pphead的解引用得到头节点中的地址
*plist第一个结点的内存块== **pphead

链表的头插

//链表的头插
void SLPushFront(SLNode** pphead, SLDataType x)//相当于两个互相赋值
{
    //判断传入的头结点plist是否为空
	assert(pphead);
	SLNode* node = SLByNode(x);
    //下面两条进行的其实就是简单的交接工作
	//先将当前头指针指向的结点交给了node->next
	node->next = *pphead;
	//然后让头指针指向新节点的地址
	*pphead = node;
}

链表的尾删 

//链表的尾删链表为空的情况下不能尾删
void SLPopBack(SLNode** pphead)
{    
	//判断传入的头结点plist是否为空
	assert(pphead);
    //判断第一个有效结点是否为空链表为空不能进行尾删
	assert(*pphead);

	//当有且只有一个有效结点时
	if ((*pphead)->next == NULL)
	{
		free(*pphead)
		*pphead = NULL;
	}
    else
    {
    //当不止一个有效结点时
    //未防止删除后空指针的出现在寻找尾节点的时候我们也要找到尾节点的前一个节点
	//找尾结点和尾结点的前一个结点
    //定义prev为尾结点的前一个结点
	SLNode* prev = NULL;
    //定义ptai为用于找尾结点的指针先让它接收第一个有效结点的地址
	SLNode* ptail = *pphead;
	while (ptail->next != NULL)
	{
        //先令prev将ptail保存下来当ptail->next为空时此时到达尾指针就不会进入循环将ptail    
        //存入prev中此时prev保存的就是尾结点的前一个结点
		prev = ptail;
		ptail = ptail->next;
	}
	//此时prev尾结点的前一个结点的next指针不再指向ptail尾结点而是指向ptail的下一个结点
	prev->next = ptail->next;
	free(ptail);
	ptail = NULL;
    }
}

链表的头删

//链表的头删
void SLPopPront(SLNode** pphead)
{
	//判断传入的头结点plist是否为空
	assert(pphead);
    //判断第一个有效结点是否为空链表为空不能进行尾删
	assert(*pphead);

	//当有且只有一个有效结点时
	if ((*pphead)->next == NULL)
	{
		//直接把头结点删除
		free(*pphead);
		*pphead = NULL;
	}
    //当整个链表
	//使用临时指针指向头结点
	SLNode* del = *pphead;
	//令头结点指向新的头结点
	*pphead = (*pphead)->next;
	//将临时指针指向的结点头结点释放掉
	free(del);
	del = NULL;
}

寻找结点

//查找结点
SLNode* SLFind(SLNode** pphead, SLDataType x)
{
	//判断传入的头结点plist是否为空
	assert(pphead);
	SLNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//该函数需要与在指定位置插入删除结合返回的结果使用一个指针来接收在test.c文件中的使用情况如下
SLNode* find = SLFind(&plist,2);//查找数据为2的结点
SLInsert(&plist,find,x)//在find数据为2的结点前插入含有数据x的新节点

在完成以下代码后需要考虑的三种情况

1、pos是头结点

2、pos是中间结点

3、pos是最后一个结点

在链表的指定位置前插入

//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
	//判断传入的头结点plist是否为空
	assert(pphead);
    //约定链表不能为空pos也不能为空
	assert(pos);
	assert(*pphead);
	SLNode* node = SLByNode(x);

	//有且只有一个有效结点此时在该有效结点前进行插入操作就相当于头插
	if(pos == *pphead)
	{
		node->next = *pphead;
		*pphead = node;
		return;
	}

	//当不只有一个有效结点的时候先通过循环找到pos的前一个结点
	SLNode* prev = *pphead; 
    //当prev->next指向pos的时候跳出循环
	while (prev->next != pos)
	{
		prev = prev->next;
	}
    //此时循环结束prev指向pos

    //最后处理插入位置两边的结点与新结点三者之间的关系prve node pos
    //此时下面的两个操作顺序可以交换
	node->next = pos;
	prev->next = node;
}

在链表的指定位置后插入

//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{
    //确定能找到该结点
	assert(pos);
	SLNode* node = SLByNode(x);
	//pos node pos->next
	node->next = pos->next;
	pos->next = pos;
}

//使用案例
//SLNode* find = SLFind(&plist,1);
//SLInsertAfter(find,100);

删除pos位置的结点

//删除pos结点
void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
    
    //当pos为第一个有效结点时
	if (pos == *pphead)
	{
		*pphead = (*pphead)->next;
		free(pos);
		return;
	}
    //当pos不为第一个有效结点时
	//先找到pos的前一个结点然后后续内容与之前的操作类似
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
    //先完成pos两边结点的交接工作然后再释放pos结点
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

删除pos位置后的结点

//删除pos结点之后的数据
void SLEraseAfter(SLNode* pos)
{
    //除了pos不为空以外还需要pos->next不为空因为pos刚好是最后一个结点你总不能删除一个NULL
	assert(pos && pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
}

销毁链表

//销毁链表
void SLDestroy(SLNode** pphead)
{
	assert(pphead);
	SLNode* pcur = *pphead;
	//循环删除
	while (pcur)
	{
		SLNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
    //此时链表所有的有效结点已经结束了最后将头结点置为空即可
	*pphead = NULL;
}

最终结果

SList.h文件

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

//定义链表节点的结构
typedef int SLDataType;
struct SListNode {   //定义一个表示链表节点的结构体
	SLDataType data;  //链表中用于存储数据的成员某个节点的数据
	struct SListNode* next;  //用来保存下一个节点地址的指针变量next
};
typedef struct SListNode SLNode;  //将指向下一个节点的指针类型重命名为SLNode

//创建几个结点组成的链表并打印链表
void SLPrint(SLNode* phead);  
//链表的尾插
void SLPushBack(SLNode** phead, SLDataType x);
//链表的头插
void SLPushFront(SLNode** phead, SLDataType x);
//链表的尾删
void SLPopBack(SLNode** pphead);
//链表的头删
void SLPopPront(SLNode** pphead);
//找结点,这里传一级指针实际上就可以了因为不改变头节点但是这里还是要写成二级指针因为要保证接口一致性
SLNode* SLFind(SLNode** pphead,SLDataType x);

//链表的在指定位置之前插入
void SLInsert(SLNode** phead, SLNode* pos,SLDataType x);
//链表的指定位置删除
void SLInsertAfter(SLNode* pos, SLDataType x);//此时不需要第一个参数
//删除pos位置的结点
void SLErase(SLNode** pphead, SLNode* pos);
//删除pos后的结点
void SLEraseAfter(SLNode* pos);
//销毁链表
void SLDestroy(SLNode** pphead);

SList.c文件

#include "SList.h"
//用phead表示头结点它指向链表的第一个结点如果思路出现混乱一定要再看一边前面的链表图
void SLPrint(SLNode* phead)
{
	//循环打印
	//为了能在遍历后仍能找到刚开始的起点我们就需要利用一个临时指针pcur来存储头结点的地址
	SLNode* pcur = phead;
	//当头结点不为空时进行循环
	while (pcur)
	{
		//打印此时所处结点中的数据
		printf("%d ->", pcur->data);
		//打印结束后让pcur指向下一个结点的地址
		pcur = pcur->next;
	}
	//到最后时现有结点遍历完成空间为NULL
	printf("NULL\n");
}

//申请有效结点函数并在该结点中存储数据
SLNode* SLByNode(SLDataType x)
{
	//为链表的新结点申请一个新的空间
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
	//该节点中存储的数据为x
	node->data = x;
	//将该结点的下一个结点置为空因为我们也不知道它后面到底还要不要结点了
	node->next = NULL;
	//返回申请的新结点
	return node;
}

//链表的尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{
	//判断传入的头结点plist是否为空
	assert(pphead);
	//如果存在头结点则进行后续操作
	//先申请一个新的有效结点
	SLNode* node = SLByNode(x);
	//如果第一个有效结点为空则令*pphead指向新创建的有效结点
	if (*pphead == NULL)
	{
		*pphead = node;
		return;
	}
	//如果第一个有效结点不为空则通过循环读取至链表的结尾
	//先定义一个临时的指针变量pcur令pcur指向第一个有效结点
	SLNode* pcur = *pphead;
	//然后利用pcur->next遍历至链表的末尾
	while (pcur->next)
	{
		pcur = pcur->next;
	}
	//当遍历至链表的末尾时让pcur指向新的有效结点
	pcur->next = node;
}

//链表的头插
void SLPushFront(SLNode** pphead, SLDataType x)//相当于两个互相赋值
{
	//判断传入的头结点plist是否为空
	assert(pphead);
	SLNode* node = SLByNode(x);
	//下面两条进行的其实就是简单的交接工作
	//先将当前头指针指向的结点交给了node->next
	node->next = *pphead;
	//然后让头指针指向新节点的地址
	*pphead = node;
}

//链表的尾删链表为空的情况下不能尾删
void SLPopBack(SLNode** pphead)
{
	//判断传入的头结点plist是否为空
	assert(pphead);
	//判断第一个有效结点是否为空链表为空不能进行尾删
	assert(*pphead);

	//当有且只有一个有效结点时
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//当不止一个有效结点时
	//未防止删除后空指针的出现在寻找尾节点的时候我们也要找到尾节点的前一个节点
	//找尾结点和尾结点的前一个结点
	//定义prev为尾结点的前一个结点
	
	else
	{
		SLNode* prev = NULL;
		//定义ptai为用于找尾结点的指针先让它接收第一个有效结点的地址
		SLNode* ptail = *pphead;
		while (ptail->next != NULL)
		{
			//先令prev将ptail保存下来当ptail->next为空时此时到达尾指针就不会进入循环将ptail    
			//存入prev中此时prev保存的就是尾结点的前一个结点
			prev = ptail;
			ptail = ptail->next;
		}
		//此时prev尾结点的前一个结点的next指针不再指向ptail尾结点而是指向ptail的下一个结点
		prev->next = ptail->next;
		free(ptail);
		ptail = NULL;
	}
}

//链表的头删
void SLPopPront(SLNode** pphead)
{
	//判断传入的头结点plist是否为空
	assert(pphead);
	//判断第一个有效结点是否为空链表为空不能进行尾删
	assert(*pphead);

	//当有且只有一个有效结点时
	if ((*pphead)->next == NULL)
	{
		//直接把头结点删除
		free(*pphead);
		*pphead = NULL;
	}
	//当整个链表
	//使用临时指针指向头结点
	SLNode* del = *pphead;
	//令头结点指向新的头结点
	*pphead = (*pphead)->next;
	//将临时指针指向的结点头结点释放掉
	free(del);
	del = NULL;
}

//查找结点
SLNode* SLFind(SLNode** pphead, SLDataType x)
{
	//判断传入的头结点plist是否为空
	assert(pphead);
	SLNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//
该函数需要与在指定位置插入删除结合返回的结果使用一个指针来接收在test.c文件中的使用情况如下
//SLNode* find = SLFind(&plist, 2);//查找数据为2的结点
//SLInsert(&plist, find, x)//在find数据为2的结点前插入含有数据x的新节点

//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
	//判断传入的头结点plist是否为空
	assert(pphead);
	//约定链表不能为空pos也不能为空
	assert(pos);
	assert(*pphead);
	SLNode* node = SLByNode(x);

	//有且只有一个有效结点此时在该有效结点前进行插入操作就相当于头插
	if (pos == *pphead)
	{
		node->next = *pphead;
		*pphead = node;
		return;
	}

	//当不只有一个有效结点的时候先通过循环找到pos的前一个结点
	SLNode* prev = *pphead;
	//当prev->next指向pos的时候跳出循环
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//此时循环结束prev指向pos

	//最后处理插入位置两边的结点与新结点三者之间的关系prve node pos
	//此时下面的两个操作顺序可以交换
	node->next = pos;
	prev->next = node;
}

//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{
	//确定能找到该结点
	assert(pos);
	SLNode* node = SLByNode(x);
	//pos node pos->next
	node->next = pos->next;
	pos->next = pos;
}

//使用案例
//SLNode* find = SLFind(&plist,1);
//SLInsertAfter(find,100);

//删除pos结点
void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	//当pos为第一个有效结点时
	if (pos == *pphead)
	{
		*pphead = (*pphead)->next;
		free(pos);
		return;
	}
	//当pos不为第一个有效结点时
	//先找到pos的前一个结点然后后续内容与之前的操作类似
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//先完成pos两边结点的交接工作然后再释放pos结点
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

//销毁链表
void SLDestroy(SLNode** pphead)
{
	assert(pphead);
	SLNode* pcur = *pphead;
	//循环删除
	while (pcur)
	{
		SLNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时链表所有的有效结点已经结束了最后将头结点置为空即可
	*pphead = NULL;
}

test.c文件

#include "SList.h"
//申请结点函数
//void slttest()
//{
//	//使用malloc函数动态分配创建链表的头节点它不包含任何数据知识用来指向链表的第一个实际节点
//	SLNode* node1 = (SLNode*)malloc(sizeof(SLNode)); 
//	//head
//	node1->data = 1;
//	SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));
//	node2->data = 2;
//	SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));
//	node3->data = 3;
//	SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));
//	node4->data = 4;
//
//	//实现四个节点的链接
//	//初始化头节点的next指针为node2指针变量
//	node1->next = node2;
//	node2->next = node3;
//	node3->next = node4;
//	node4->next = NULL;
//
//	//打印链表
//	SLNode* plist = node1;  //定义一个SLNode*类型的指针变量plist他也叫头指针我们用它指向链表的头节点
//	
//	//注意头节点和头指针的概念是不同的
//	/*在链表的上下文中通常将链表的第一个节点称为头节点Head Node但是头节点和头指针Head Pointer是不同的概念。
//	头节点是链表中的第一个实际节点它包含数据和指向下一个节点的指针。头节点是链表的起始点它可以存储实际的数据也可以只是一个占位符节点不存储实际的数据。
//	头指针是指向链表的头节点的指针。它是一个指针变量存储着头节点的地址。通过头指针我们可以访问链表中的每个节点或者进行其他链表操作。
//	因此头节点是链表中的一个节点而头指针是指向头节点的指针。它们是不同的概念但在某些情况下人们可能会将它们混用或将它们视为相同的概念因为头节点通常通过头指针来访问。*/
//	
//	SLNPrint(plist);
//}

void slttest()
{

	SLNode* plist = NULL;	
	//尾插
	SLPushBack(&plist, 1);  
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);//1->2->3->4->NULL
	SLPrint(plist);
	头插
	//SLPushFront(&plist, 1);
	//SLPushFront(&plist, 2);
	//SLPushFront(&plist, 3);
	//SLPushFront(&plist, 4);//4->3->2->1->NULL
	//SLPrint(plist);
	//尾删
	SLPopBack(&plist);
	SLPopBack(&plist);
	SLPopBack(&plist);
	头删
	//SLPopPront(&plist);
	//SLPopPront(&plist);
	//SLPopPront(&plist);
	//SLPopPront(&plist);
	//SLPopPront(&plist);
	//SLPopPront(&plist);
	指定位置插入
	//SLNode* find = SLFind(&plist, 4);
	//SLInsert(&plist, find,11);//1->11->2->3->4->NULL
	在指定位置之后插入数据
	//SLInsertAfter(find, 100);
	删除pos位置的节点
	//SLErase(&plist, find);//1->2->3->NULL
	删除pos之后的节点
	//SLEraseAfter(find);
	//
	//销毁链表
	//SLDestory(&plist);
	//检验是否成功销毁
	SLPrint(plist);
}

int main()
{
	slttest();
	return 0;
}

注意事项

1、判断条件的等号都是==

2、冒号是否写了

3、函数或者指针变量的名字是否书写正确 

4、最后的test.c文件实验时可能会存在一些多删之类的问题函数写多了请自行检查~

额外拓展

链表其实一共有八种结构

  • 带头单向不循环/循环链表
  • 带头双向不循环/循环链表
  • 不带头单向不循环/循环链表
  • 不带头双向不循环/循环链表
但是我们实际中 最常⽤还是两种结构 不带头单向不循环链表 带头双向循环链表
⽆头单向⾮循环链表
        结构简单⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构如哈希桶、图的邻接表等等。
带头双向循环链表
        结构最复杂⼀般⽤在单独存储数据。实际中使⽤的链表数据结构都是带头双向循环链表。

~over~

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6