[数据结构与算法]数据机构----线性表之单向链表

前言💬

在上一篇博客中我写到了数据结构中的线性表的第一种表示结构----顺序表，而本次则介绍第二种线性结构----链表中的单向链表！

1.链表💬

在上一篇博客中我提到线性表在逻辑上是一种线性结构，因此链表也具有这种性质，如图所示就是链表的图形表示。

上图就是链表中的结点，而结点通常有两部分组成，一部分是用户需要的实时数据，另一部分就是下一个节点的地址。因此将这些节点相互之间构建联系就可以形成链表，而在链表的最后一个结点里，该节点的next是指向NULL的，这一点很重要！

下面如顺序表一致，实现对数据的增删改查等操作！

2.相关功能接口💬

实现链表，我们首先需要创建结构体去开辟结点；

typedef int SListData;
typedef struct SListNode
{
	SListData data;
	struct SListData* next;
}SListNode;

data是实时数据，另一部分就是下一个结点的地址

2.1结点的创造与销毁

1??结点的创造

SListNode* BuyNewNode(SListData x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("%s", strerror(errno));
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

分析:在创造结点时首先对结点申请空间，将data传递给新创造的结点中的data，将新结点的指向地址值为NULL；而创造结点就需要去返回结点，因此函数类型也就是自定义的结构体类型，也就意味着返回的数据是一个结构体指针！

2??结点的销毁

void DestorySListNode(SListNode** pphead)
{
	SListNode* cur = *pphead;
	while (cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

分析：结点存在动态内存开辟同理也就存在着动态内存的回收，当cur不等于NULL时，对其进行释放并且使cur指向下一个结点，从而对整个链表就可以进行内存释放，最后对头指针置NULL。

2.2头插与头删

2.2.1头插

void PushSListFront(SListNode** pphead, SListData x)
{
	assert(pphead);
	SListNode* newnode = BuyNewNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

分析：头插的逻辑很简单，就是将头指针的内容传递给newnode的中的next，再将newnode的地址重新赋值给头指针即可完成头插！

而上述代码中关于函数参数为什么传递二级指针呢？

在通篇的介绍中我一直提到过头指针，头指针中存储的是第一个结点的地址，我在进行头插时，需要改变头指针中的值，也就是不断更新改变指针中地址；同普通参数进行函数传参一致，如果只是简单的值传递的话，是不能将函数内部的改变反映到函数外部的，因此在这需要址传递；在调用头插函数时，我需要传递的参数是头指针的地址，指针的地址，那我就需要用指针的指针进行接收，也就是利用二级指针进行接收才可以将函数内部的变化反映到函数外去，这也就是函数参数时二级指针的原因，后面的接口函数的参数传递二级指针的原理与上述一致，下来就不在进行解释了！

2.2.2头删

void PopSListNodeFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead!=NULL);
	SListNode* temp = *pphead;
	*pphead = (*pphead)->next;
	free(temp);
	temp = NULL;
}

分析：删除时首先需要保证的就是链表不为空，因此进行断言；*pphead就是plist的内容，pphead即是plist的地址；让头指针指向头指针所指向的那块空间的next指向的空间；也就是指向第二个结点。

2.3尾插和尾删

2.3.1尾插

void PushSListBack(SListNode** pphead, SListData x)
{
	assert(pphead);
	SListNode* newnode = BuyNewNode(x);
	//空时
	if (*pphead == NULL)
	{
		newnode->next = *pphead;//无意义的
		*pphead = newnode;
	}
	else
	{
		SListNode* temp = *pphead;
		while (temp->next != NULL)
		{
			temp = temp->next;
		}
		temp->next = newnode;
	}
}

分析：首先，如果链表为空时，尾插就相当于首插，在此不进行赘述。而链表不为空时，此时我需要找到最后一个结点，让该节点的next指向新结点的空间即插入成功！

2.3.2尾删

void PopSListNodeBack(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead != NULL);
	SListNode* tail = *pphead;
	SListNode* prev = NULL;
	while (tail->next != NULL)
	{
		prev = tail;
		tail = tail->next;
	}
	prev->next = NULL;
	free(tail);
}

分析：尾删就相对比较麻烦，需要找到最后一个结点的前一个节点，对前一个结点的next置为NULL，然后对最后一个结点进行内存释放即可，所以prev就是最后一个结点的前一个结点，对prev->next置为NULL，然后释放tail即可！

2.4查找

SListNode* FindNode(SListNode* phead, SListData x)
{
	assert(phead);
	SListNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

函数的类型是结构体指针，也就是当查找成功时返回查找的结点，因此也就与函数的类型对应起来了！

2.5插入

2.5.1在pos之前插入

插入函数的实现是离不开查找函数的，因此在实际应用中，调用插入函数时应先调用插入函数。

void InsertPosBefore(SListNode** pphead, SListData x, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	if (*pphead == NULL)
	{
		PushSListFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		//prev时pos的前一个
		while (prev->next != pos)
		{
			prev = prev->next;

			//一直向后寻找，当找不到时继续向后，当pos不在链表中时，此时prev为NULL
			//为NULL时进行断言
			assert(prev);
		}

		SListNode* newnode = BuyNewNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

当prev的next与pos相等时，此时就意味着找到了pos的前一个结点，然后创造新结点，使pos的前一个结点prev的next指向新结点，让新结点的next指向pos即可实现插入!

2.5.2在pos之后插入

void InsertPosAfter(SListNode* pos, SListData x)
{
	assert(pos);
	SListNode* newnode = BuyNewNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

分析：在pos之后插入，就直接传递pos即可，将pos->next赋给newnode->next,也就意味着将新结点插入到pos与pos后一个结点之间；然后在使pos的next指向newnode即可；这个顺序是不能颠倒的，否则就是自己指向自己这样一种情况！

2.6删除

2.6.1删除pos的位置

void DelSListNode(SListNode** pphead, SListNode* pos)
{
	assert(pos);
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur->next != pos)
	{
		cur = cur->next;
		assert(cur);//找到末尾也找不到的话报错
	}
	cur->next = pos->next;
	free(pos);
}

删除直接找到pos的前一个结点，通过前一个结点的next锁定pos，然后将pos的下一位的地址给pos前一位的地址，如cur->next = pos->next;，最后对pos进行释放即可！

2.6.2删除pos之后的位置

void DelPosAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

这个函数比较简单，将pos之后的元素的next赋给pos的next即可！

3.完整代码💬

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<errno.h>
#include<stdlib.h>

typedef int SListData;
typedef struct SListNode
{
	SListData data;
	struct SListData* next;
}SListNode;
//创造新结点
SListNode* BuyNewNode(SListData x);
//头插
void PushSListFront(SListNode** pphead, SListData x);
//尾插
void PushSListBack(SListNode** pphead, SListData x);
//头删
void PopSListNodeFront(SListNode** pphead);
//尾删
void PopSListNodeBack(SListNode** pphead);
//查找
SListNode* FindNode(SListNode* phead, SListData x);
//在pos之前插入
void InsertPosBefore(SListNode** pphead, SListData x, SListNode* pos);
//在pos之后插入
void InsertPosAfter(SListNode* pos, SListData x);
//打印
void PrintSList(SListNode* phead);
//删除
void DelSListNode(SListNode** pphead, SListNode* pos);
//删除pos之后的结点
void DelPosAfter(SListNode* pos);
//销毁
void DestorySListNode(SListNode** pphead);


//创造新结点
SListNode* BuyNewNode(SListData x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("%s", strerror(errno));
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//头插
void PushSListFront(SListNode** pphead, SListData x)
{
	assert(pphead);
	SListNode* newnode = BuyNewNode(x);
	newnode->next = *pphead;
	*pphead = newnode;

}
//尾插
void PushSListBack(SListNode** pphead, SListData x)
{
	assert(pphead);
	SListNode* newnode = BuyNewNode(x);
	//空时
	if (*pphead == NULL)
	{
		newnode->next = *pphead;//无意义的
		*pphead = newnode;
	}
	else
	{
		SListNode* temp = *pphead;
		while (temp->next != NULL)
		{
			temp = temp->next;
		}
		temp->next = newnode;
	}
}

//头删
void PopSListNodeFront(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead!=NULL);
	SListNode* temp = *pphead;
	*pphead = (*pphead)->next;
	free(temp);
	temp = NULL;
}

//尾删
void PopSListNodeBack(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead != NULL);
	SListNode* tail = *pphead;
	SListNode* prev = NULL;
	while (tail->next != NULL)
	{
		prev = tail;
		tail = tail->next;
	}
	prev->next = NULL;
	free(tail);
}

//查找
SListNode* FindNode(SListNode* phead, SListData x)
{
	assert(phead);
	SListNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//在pos之前插入
void InsertPosBefore(SListNode** pphead, SListData x, SListNode* pos)
{
	assert(pphead);
	assert(pos);
	if (*pphead == NULL)
	{
		PushSListFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		//prev时pos的前一个
		while (prev->next != pos)
		{
			prev = prev->next;

			//一直向后寻找，当找不到时继续向后，当pos不在链表中时，此时prev为NULL
			//为NULL时进行断言
			assert(prev);
		}

		SListNode* newnode = BuyNewNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
//在pos之后插入
void InsertPosAfter(SListNode* pos, SListData x)
{
	assert(pos);
	SListNode* newnode = BuyNewNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//打印
void PrintSList(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur!= NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
//删除
void DelSListNode(SListNode** pphead, SListNode* pos)
{
	assert(pos);
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur->next != pos)
	{
		cur = cur->next;
		assert(cur);//找到末尾也找不到的话报错
	}
	cur->next = pos->next;
	free(pos);
}
//删除pos之后的结点
void DelPosAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}
//销毁
void DestorySListNode(SListNode** pphead)
{
	SListNode* cur = *pphead;
	while (cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
//测试函数
void test1()
{
	SListNode* plist = NULL;
	PushSListFront(&plist, 1);
	PushSListFront(&plist, 2);
	PushSListFront(&plist, 3);
	PushSListFront(&plist, 4);
	PrintSList(plist);

	PushSListBack(&plist, 10);
	PushSListBack(&plist, 20);
	PushSListBack(&plist, 30);
	PrintSList(plist);

	/*PopSListNodeFront(&plist);
	PrintSList(plist);

	PopSListNodeBack(&plist);
	PrintSList(plist);*/

	SListNode*pos=FindNode(plist,10);
	if (pos)
	{
		InsertPosBefore(&plist, 66, pos);
		InsertPosAfter(pos, 88);
	}
	PrintSList(plist);

	SListNode* pos1 = FindNode(plist, 88);
	DelSListNode(&plist, pos1);
	SListNode* pos2 = FindNode(plist, 10);
	DelSListNode(&plist, pos2);
	PrintSList(plist);

	SListNode* pos3 = FindNode(plist, 1);
	DelPosAfter(pos3);
	PrintSList(plist);

	DestorySListNode(&plist);
}
int main()
{
	test1();
}

Ending💬

链表中的单向链表也就更新完成了，其中二级指针传参或许比较麻烦、难以理解，而结合普通函数传参就可以很好的解决这个问题；其次，还有一种办法可以将参数是二级指针的函数设计成返回类型是结构体指针的这样一种函数，但是，这种函数使用很不方便，因此本文中并没有将其写出来；

好了，就这样吧🙋?♂?