数据结构--链表的基本操作

1. 链表的概念及结构

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

链表也是线性表的一种。

链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只 需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。

⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状 态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？

最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。 

在链表⾥，每节“⻋厢”是什么样的呢？

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

节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。

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

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

链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。

结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码：

假设当前保存的节点为整型：

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

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

给定的链表结构中，如何实现节点从头到尾的打印？

思考：当我们想保存的数据类型为字符型、浮点型或者其他⾃定义的类型时，该如何修改？

补充说明：

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、节点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

2. 单链表的实现

我们和顺序表一样定义三个文件，一个头文件我们取个名字叫SList.h,两个源文件分别取名叫SList.c和text.c，我们的SList.c用来实现链表的方法，text.c用来测试。

我们把单链表的功能函数全部在头文件里面声明一下，以及我们结构体的定义，还有我们需要用到的头文件都放在.h文件里面。

.h

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

//定义节点的结构
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType date;//数据
	struct SListNode* next;//指向节点的地址

}SLTNode;

void SLTPrint(SLTNode* phead);//打印

void SLTBuyBode(SLTNode** pphead, SLTDataType x);//尾插

void SLPushFront(SLTNode** pphead, SLTDataType x);//头插

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

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

SLTNode* SLFind(SLTNode* phead, SLTDataType x);//查找

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

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

void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos节点

void SLTEreaseAfter(SLTNode* pos);//删除pos之后的节点

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

以上就是我们的声明了，要注意我们的类型，我们这里用typedef 定义了一个int类型给它取了个名字叫SLTDataType，当我们需要改类型的时候直接把int改成我们想要的类型就行。

我们和顺序表一样先来实现尾插，我们插入数据的时候需要申请节点，所以我们先来实现申请节点的函数。

节点的申请

SList.c
SLTNode* SLBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

申请空间可能导致申请失败所以我们需要判断一下，x是我们节点里面的数据。

现在来实现尾插

//尾插
void SLTBuyBode(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//*pphead就是指向第一个节点的指针
	
	//空链表和非空链表
	SLTNode* newnode = SLBuyNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail指向的就是尾节点
		ptail->next = newnode;
	}
}

如果我们传过来一个NULL，我们可以对他解引用吗？那肯定是不行的，所以我们加个断言。

我们要插入数据那肯定是需要申请节点的，我们把需要插入的数据x传过去，然后进行找尾找到后让我们的尾节点的next指向我们的新节点。

这里我们创建了一个指针变量让它进行找尾的操作，如果用我们的头节点不断往后最后会指向我们的尾节点。

尾插实现好了我们用测试文件来测试一下

text.c

打印怎么实现的我们上面已经说了。我把打印的代码直接放这了(SList.c)

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->date);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

头插的实现

//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头插的实现其实就是把我们申请好的节点让它的next指向我们的头节点。 

测试一下：

尾删的实现

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	//链表只有一个节点
	if ((*pphead)->next == NULL)//-->优先级*
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//链表有多个节点
		SLTNode* prev = *pphead; //尾节点的前一个节点
		SLTNode* ptail = *pphead;//尾节点
		while (ptail->next)
		{
			prev = ptail;//尾节点的前一个节点
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;//让我的尾节点指向空指针
	}
}

既然我们要删除节点那么节点不能为空，所以需要断言一下。

当链表只有一个节点的时候我们直接把它释放就行了。

有多个节点的时候我们需要用一个指针变量用来保存我们的前一个节点。 

测试一下：

头删的实现

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

我们要把头节点给释放掉，所以我们先把头节点的next指向下一个节点的地址给保存起来。

测试一下：

查找的实现

//查找
SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->date == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return  NULL;
}

如果找到了我们就直接返回找到的节点，没找到返回NULL。

测试一下：

指定位置之前插入数据的实现

//指定位置之前插入数据
void SLTnsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* newnode = SLBuyNode(x);
	if (pos == *pphead)
	{
		//如果pos等于我们的头节点我们直接使用头插
		SLPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

pos是我们指定的位置，所以不能为空我们断言一下。

插入数据肯定是要申请节点的。

如果pos等于我们的头节点那么我们直接调用头插就可以了。

我们定义一个指针变量用来保存前一个节点，然后用我们申请好了的节点的next指向我们的pos，在用我们前一个节点的next指向我们申请好了的节点。

测试一下：

指定位置之后插入数据

//指定位置之后插入数据
void SLTnesertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

这里我们用不到头节点，所以只有两个参数，这里的pos是指定位置所以不能为空我们要加个断言，这里直接用申请好的节点的next指向pos的下一个节点，然后再让pos的next指向我们申请好的节点，这样就插入进去了。

 测试：

删除pos节点

/删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		//如果等于说明要删除的就是头节点，所以我们直接头删
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

删除指定pos节点的实现和我们在指定位置之前插入数据的实现有点相似。

当跳出while循序的时候说明prev->next已经等于pos了，所以我们让perv->next指向pos的下一个节点，然后把pos释放掉。

测试：

删除pos之后的节点

//删除pos之后的节点
void SLTEreaseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

删除pos之后的节点，直接把pos指向的下一个节点的地址保存起来，这里面我们定义了一个指针变量用来存放下一个节点，然后把del节点的next指向的节点给pos->next，最后释放掉del。

测试：

销毁链表

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

通过循序对节点一个一个的释放。

最后置为NULL

3.单链表的所有代码

SList.h

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

//定义节点的结构
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType date;//数据
	struct SListNode* next;//指向节点的地址

}SLTNode;

void SLTPrint(SLTNode* phead);//打印

void SLTBuyBode(SLTNode** pphead, SLTDataType x);//尾插

void SLPushFront(SLTNode** pphead, SLTDataType x);//头插

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

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

SLTNode* SLFind(SLTNode* phead, SLTDataType x);//查找

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

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

void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos节点

void SLTEreaseAfter(SLTNode* pos);//删除pos之后的节点

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

SList.c

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

//判断是否为非空链表
SLTNode* SLBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}


//尾插
void SLTBuyBode(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//*pphead就是指向第一个节点的指针
	
	//空链表和非空链表
	SLTNode* newnode = SLBuyNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail指向的就是尾节点
		ptail->next = newnode;
	}
}

//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}


//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	//链表只有一个节点
	if ((*pphead)->next == NULL)//-->优先级*
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//链表有多个节点
		SLTNode* prev = *pphead; //尾节点的前一个节点
		SLTNode* ptail = *pphead;//尾节点
		while (ptail->next)
		{
			prev = ptail;//尾节点的前一个节点
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;//让我的尾节点指向空指针
	}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

//查找
SLTNode* SLFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->date == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return  NULL;
}

//指定位置之前插入数据
void SLTnsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* newnode = SLBuyNode(x);
	if (pos == *pphead)
	{
		//如果pos等于我们的头节点我们直接使用头插
		SLPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

//指定位置之后插入数据
void SLTnesertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		//如果等于说明要删除的就是头节点，所以我们直接头删
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//删除pos之后的节点
void SLTEreaseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

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

text.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void SListText02()
{
	SLTNode* plist = NULL;
	//尾插
	SLTBuyBode(&plist, 1);
	SLTBuyBode(&plist, 2);
	SLTBuyBode(&plist, 3);
	SLTBuyBode(&plist, 4);
	SLTPrint(plist);//打印

	//测试头插
	SLPushFront(&plist, 0);
	SLTPrint(plist);

	//测试尾删
	SLTPopBack(&plist);
	SLTPrint(plist);

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

	//测试查找
	SLTNode* find = SLFind(plist,1);
	if (find == NULL)
	{
		printf("没找到\n");
	}
	else
	{
		printf("找到了\n");
	}

	//指定位置之前插入数据
	SLTnsert(&plist,find,6);
	SLTPrint(plist);

	//指定位置之后插入数据
	SLTnesertAfter(find, 7);
	SLTPrint(plist);
	
	
	//删除pos节点
	SLTErase(&plist,find);
	SLTPrint(plist);

	//删除pos之后的节点
	SLTEreaseAfter(find);
	SLTPrint(plist);

	//销毁链表
	SListDesTroy(&plist);
}
int main()
{
	SListText02();
	return 0;
}

以上就是单链表的基本操作了，如有表述不准确或理解不深刻的地方，还请各位看客不吝指正。