单链表的相关操作（初阶）

编程入门行业动态更新时间:2024-10-26 10:28:33

单<a href=https://www.elefans.com/category/jswz/34/1769662.html style= 链表的相关操作（初阶）"/>

单链表的相关操作（初阶）

链表的概念

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

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

链表的结构跟⽕⻋⻋厢相似，淡季⻋厢会相应减少，旺季时⻋厢会额外增加，减少和增加车厢并不会影响其它车厢，每节⻋厢都是独⽴存在的。且每节⻋厢都有⻋⻔。假设每节⻋厢的⻋⻔都被锁上，且打开这些车厢所需要的钥匙各不相同，那么如果乘务员从第一节车厢开始向后面的车厢走去，如何从⻋头⾛到⻋尾？

答案：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。

而每节车厢里面肯定是有人或者货物的，所以这就引申出了一条新的概念：在链表⾥，每节“⻋厢”是由 下一个车厢的🔑 和 本节车厢中存储的“数据" 组成的。

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

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“ 结点/节点 ”。

结点 = 当前节点中保存的数据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;}//到最后时现有结点遍历完成，空间为NULLprintf("NULL\n");
}

申请新节点：

//申请有效结点函数（并在该结点中存储数据）
SLNode* SLByNode(SLDataType x) 
{//为链表的新结点申请一个新的空间SLNode* node = (SLNode*)malloc(sizeof(SLNode));//该节点中存储的数据为xnode->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->nextnode->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->nextnode->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刚好是最后一个结点你总不能删除一个NULLassert(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;}//到最后时现有结点遍历完成，空间为NULLprintf("NULL\n");
}//申请有效结点函数（并在该结点中存储数据）
SLNode* SLByNode(SLDataType x)
{//为链表的新结点申请一个新的空间SLNode* node = (SLNode*)malloc(sizeof(SLNode));//该节点中存储的数据为xnode->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->nextnode->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->nextnode->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->NULLSLPrint(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;
}