1. 链表

1.1 概念

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

1.2 数据结构

链表的逻辑结构

注：

• 链表在逻辑结构上是连续存储的，但是在物理结构上不一定连续存储
• 现实的节点一般是从堆上开辟出来的
• 从堆上申请的空间，是按照一定的策略进行分配的，两次申请的空间可能连续，也可能不连续。

1.3 链表的分类

• 单向或双向
  

• 带头或不带头
  

• 循环或非循环
  

最常用的两种结构

1. 无头单向非循环结构
   

2. 带头双向循环链表
   

• 无头单向非循环链表(本次实现)：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
• 带头双向循环链表(后面实现)：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

2. 链表的实现

2.1 链表的功能

• 头删（SingleListPopFront）
• 尾删（SingleListPopBack）
• 头插（SingleListPushFront）
• 尾插（SingleListPushBack）
• 删除指定位置得后面一个节点（SingleListErasetAfter）
  -在指定位置后面插入一个节点（SingleListInsertAfter）
• 查找（SingleListFind）
• 打印（SingleListPrint）
• 销毁（SingleListDestory）

SingleList.h中定义一个单向无头链表并提供函数原型

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SLTNode
{
	SLTDataType val;
	struct SLTNode* next;
}SLTNode;

//新建节点
extern SLTNode* CreatListNode(SLTDataType x);
//头插
extern void SingleListPushFront(SLTNode** pphead, SLTDataType x);
//头删
extern void SingleListPopFront(SLTNode** pphead);
//尾插
extern void SingleListPushBack(SLTNode** pphead, SLTDataType x);
//尾删
extern void SingleListPopBack(SLTNode** pphead);
//查找
extern SLTNode* SingleListFind(SLTNode* phead, SLTDataType x);
//修改
extern void SingleListModify(SLTNode* phead, SLTDataType src, SLTDataType dest);
//pos位置后插入一个节点(参数不需要头节点指针)
extern void SingleListInsertAfter(SLTNode* pos, SLTDataType
	x);
//删除pos位置后一个节点(参数不需要头节点指针)
extern void SingleListEraseAfter(SLTNode* pos);
//打印
extern void SingleListPrint(SLTNode* phead);
//销毁
extern void SingleListDestory(SLTNode** phead);

请注意在函数原型中什么时候需要传二级指针，什么时候只需要传一级指针
记住我接下来说的这句话，如果想要在函数内部改变函数外部的变量，可以让函数的参数接受该变量的地址，再在函数内部解引用该地址就可以实现函数改变函数外变量的值
所以在上面这些函数中，凡是有可能改变外部变量的值时，就需要用函数接受需改变变量的地址，如果该变量是一级指针，那么函数需要接受一级指针的地址，这就是为什么有得函数参数是二级指针了，因为它们需要改变函数外的一级指针。
那么哪些函数可能改变函数外的一级指针变量呢？
由于我们即将会在主函数中定义一个一级指针plist指向一个链表的头节点，所以凡是可能改变链表头节点的函数都可能改变plist的值，所以头插、尾插、头删、尾删函数的参数都需要接收二级指针

2.2 主函数

主函数用来测试功能写的是否正确

ps:这里有一个小技巧，主函数可以不急先写菜单，可以先测试各个函数的功能是不是达到预期了，所以主函数可以先写测试部分，如果所有逻辑都没有问题了，那么最后可以写菜单，这里我就不写菜单了，菜单写法和之前写法类似，不懂得朋友可以看看这里：
syseptember的个人博客：通讯录
syseptember的个人博客：扫雷
syseptember的个人博客：三子棋

#define _CRT_SECURE_NO_WARNINGS 1
#include "SingleLinkList.h"

//测试头插尾插
void test1()
{
	SLTNode* plist = NULL;
	SingleListPushFront(&plist, 1);
	SingleListPushFront(&plist, 2);
	SingleListPushFront(&plist, 3);
	SingleListPopFront(&plist);
	SingleListPopFront(&plist);
	SingleListPopFront(&plist);
	SingleListPrint(plist);
}
//测试头删
void test2()
{
	SLTNode* plist = NULL;
	SingleListPushBack(&plist, 1);
	SingleListPushBack(&plist, 2);
	SingleListPushBack(&plist, 3);
	SingleListPopFront(&plist);
	SingleListPopFront(&plist);
	SingleListPopFront(&plist);
	SingleListPrint(plist);
}
//测试尾删
void test3()
{
	SLTNode* plist = NULL;
	SingleListPushBack(&plist, 1);
	SingleListPushBack(&plist, 2);
	SingleListPushFront(&plist, 3);
	SingleListPushFront(&plist, 4);
	SingleListPopBack(&plist);
	SingleListPopBack(&plist);
	SingleListPopBack(&plist);
	SingleListPopBack(&plist);
	SingleListPrint(plist);
}
//测试查找
void test4()
{
	SLTNode* plist = NULL;
	SingleListPushBack(&plist, 1);
	SingleListPushBack(&plist, 2);
	SingleListPushBack(&plist, 3);
	SingleListPushBack(&plist, 4);
	SLTNode* pos = SingleListFind(plist, 4);
	if (pos)
		printf("%d", pos->val);
}

//测试插入
void test5()
{
	SLTNode* plist = NULL;
	SingleListPushBack(&plist, 1);
	SingleListPushBack(&plist, 2);
	SingleListPushBack(&plist, 3);
	SingleListPushBack(&plist, 4);
	SLTNode* pos = NULL;
	pos = SingleListFind(plist, 2);
	if (pos)
		SingleListInsertAfter(pos, 6);
	pos = SingleListFind(plist, 4);
	if (pos)
		SingleListInsertAfter(pos, 7);
	pos = SingleListFind(plist, 1);
	if (pos)
		SingleListInsertAfter(pos, 0);

	SingleListPrint(plist);
}
//测试删除
void test6()
{
	SLTNode* plist = NULL;
	SingleListPushBack(&plist, 1);
	SingleListPushBack(&plist, 2);
	SingleListPushBack(&plist, 3);
	SingleListPushBack(&plist, 4);
	SingleListPushBack(&plist, 5);
	SLTNode* pos = NULL;
	pos = SingleListFind(plist, 1);
	if (pos)
		SingleListEraseAfter(pos);
	pos = SingleListFind(plist, 4);
	if (pos)
		SingleListEraseAfter(pos);
	SingleListPrint(plist);
	//不能删除最后一个节点得后面一个
	pos = SingleListFind(plist, 4);
	if (pos)
		SingleListEraseAfter(pos);
}
//测试销毁
void test7()
{
	SLTNode* plist = NULL;
	SingleListPushBack(&plist, 1);
	SingleListPushBack(&plist, 2);
	SingleListPushBack(&plist, 3);
	SingleListPrint(plist);
	SingleListDestory(&plist);
	SingleListPrint(plist);
}
int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	//test5();
	//test6();
	test7();
	return 0;
}

plist是一个指向链表头节点的指针，想要通过函数修改该指针
plist的初始值为NULL，表示最开始plist指向的链表为空

2.3 打印

由于链表没有变量记录有效数据的个数，因此无法像顺序表一样通过循环变量来控制打印的次数，但是我们可以通过判断是否遍历到最后一个节点来判断是否终止打印，到达尾节点终止打印，因此我们将尾节点的next成员置为NULL，当遍历到一个·SLTNode*·指针，它指向的next成员为NULL,找到尾节点，遍历结束。

//打印
void SingleListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

注意循环条件是cur!=NULL,不是cur->cext!=NULL，否则将无法打印尾节点处的数据

2.4 创造一个节点

每当插入时都需要创建一个节点，所以我们将创建节点封装为一个函数

//新建节点
SLTNode* CreatListNode(int x)
{
	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
	assert(newNode);
	newNode->val = x;
	newNode->next = NULL;
	return newNode;
}

2.4 尾插

尾插需要创建一个新的节点newnode
需要根据链表中是否有元素进行分情况讨论：

1. 无元素 需要将plist指针指向新增的newnode节点,将newnode的next成员赋值为NULL
   

2. 有元素 将newnode的next成员赋值为NULL,让原来的尾节点的next成员指向newnode

注：当plist指向的链表为空时，此时尾插会改变plist的值，所以需要传二级指针

//尾插
void SingleListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//链表为空
	if (*pphead == NULL)
	{
		*pphead = CreatListNode(x);
		return;
	}
	SLTNode* cur = *pphead;
	//找尾
	while (cur->next)
	{
		cur = cur->next;
	}
	//插入
	SLTNode* newTail = CreatListNode(x);
	cur->next = newTail;
}

2.5 头插

头插需要将plist指向的值变为newnode，并且需要将newnode的next成员赋值原来plist的值
注：当链表中没有节点时，头插仍然是将newnode的next成员赋值为原来plist的值NULL，因此头插不需要分类讨论

//头插
void SingleListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newNode = CreatListNode(x);
	newNode->next = *pphead;
	*pphead = newNode;
}

2.6 尾删

尾删需要讨论链表中的节点个数

1. 当链表中没有节点->不让删除,报错
2. 当链表中只有只有一个节点->将plist赋值为NULL
3. 当链表中有多个节点->尾删需要找到原来尾节点的前一个结点，将该节点的next成员赋值为NULL，并释放tail指向的空间
   

//尾删
void SingleListPopBack(SLTNode** pphead)
{
	//判断链表是否为空
	assert(pphead && *pphead);
	//链表只有一个节点
	SLTNode* cur = *pphead;
	if (cur->next == NULL)
	{
		*pphead = NULL;
		return;
	}
	//链表有多个节点
	SLTNode* prev = NULL;
	//找尾
	while (cur->next)
	{
		prev = cur;
		cur = cur->next;
	}
	//删除
	prev->next = NULL;
	free(cur);
}

2.7 头删

1. 当链表中无节点时->报错
2. 当链表中有节点时(1个或多个)->将plist指向原plist指向的next成员,释放原来plist指向的空间

//头插
void SingleListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newNode = CreatListNode(x);
	newNode->next = *pphead;
	*pphead = newNode;
}

注：这里只能先指向后释放，如果先释放就找不到应该指向的位置了

2.8 查找

在链表中查找元素很容易，将链表遍历一遍就行，找到后是返回在链表中的下标还是地址呢？
如果返回的是在链表中的下标，那么找到该元素后又该如何修改？
如果返回的是地址，可以直接通过该地址来修改该值，综合考虑，我们让查找函数返回地址

//查找（返回节点得地址）-->返回地址方便后续直接通过该地址插入/删除数据
SLTNode* SingleListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (x == cur->val)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
}

找到一个节点后，我们可以修改该节点的值

//将2的值改为x
SLTNode* pos = SingleListFind(phead, 2);
if (pos)
	pos->val = x;

2.9 指定位置后面插入

//插入->在pos位置后面插入数据	
void SingleListInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newNode = CreatListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

2.10 删除指定位置的后面一个元素

不可以删除尾节点的后一个节点

//删除
void SingleListEraseAfter(SLTNode* pos)
{
	//不能删除最后一个节点得后一个
	assert(pos && pos->next);
	SLTNode* tmp = pos->next;
	pos->next = pos->next->next;
	free(tmp);
}

思考一下为什么插入和删除的参数要这么设置？
假设现在链表是1->2->3->4->NULL,我想在2的后面插入5可以怎么处理？
可以通过SingleListFind函数找到2的位置，然后将该位置传给SingleListInsertAfter,就可以插入节点了
同理，我想删除3怎么处理？先找到2的位置，再将该位置传给SingleListEraseAfter就可以删除节点3了。
上述参数的传递不涉及头节点，无需知道头节点的位置。所以传递参数可以不用传头节点指针。
再来思考为什么选择在pos位置后面插入、删除元素？

• 如果在pos前删除元素，需要传递头节点的地址才可以做到。
• 如果像在pos前插入元素，传递头节点的地址可以做到，如果不想传递头节点的地址，那么只能实现“伪插入”
  假设原链表是1->2->3->null，在2前面插入4
  
  
  将在pos后面创造一个节点，新节点的val域和pos指向的节点一样，再将pos指向节点的val域更改为4
  虽然改变了pos指向节点的val值，但是最终链表形式上确实满足在2前面插入4，所以我将它称为伪插入

所以如果在pos前插入节点，实际上还是没有在pos位置后面插入节点容易实现，所以我们实现为pos位置后面插入、删除

总结一下：我们设计的查找、插入、删除函数是一起的，也就是通过将查找函数的返回值设置为指针可以找到该节点的位置，再只需要该位置传递给插入删除函数，就可以实现该位置后插入、删除节点了。

---

完整代码在gitee->syseptember:单链表