## 链表的概念 ##

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

1.概念及定义

1.1单链表的概念

单链表是一种链式存取的数据结构，，链表中的数据是以结点来表示的，每个结点的构成：元素 + 指针(指向后继元素存储位置)。

1.2定义结点

不同类型的集合用结构体，单链表结点中有元素和指针，就像顺序表中有元素和有效元素个数和空间大小一样，类比着就可以定义出来结点：

typedef int SLDataType;

//不知道元素类型，重命名数据类型，方便修改

typedef struct SListNode
{
	SLDataType data;         //元素
	struct SListNode* next;  //指向下一个元素的地址
}SListNode;

//SListNode为重命名结构类型

2.手动创建一个单链表

定义了结点，那我们就可以轻松手动创建一个单链表：1 2 3 4 5

创建多个结点，进行赋值，将指针指向下一个结点地址，最后一个结点的指针为空时则返回。

void TestSList3()
{
    //定义一个头结点
	SListNode* slist = NULL;
	SListNode* n1 = malloc(sizeof(SListNode));
	SListNode* n2 = malloc(sizeof(SListNode));
	SListNode* n3 = malloc(sizeof(SListNode));
	SListNode* n4 = malloc(sizeof(SListNode));
	SListNode* n5 = malloc(sizeof(SListNode));
	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;
    //链表创建完毕
    //头结点指向第一个结点
	slist = n1;
    //打印，可视化
	SListPrint(slist);
}

打印函数：

单链表手动创建完成，为了检验效果，我们接下来创建一个打印函数：

//打印
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

效果展示：

3.单链表尾部操作

3.1尾插

创建结点

尾部插入元素时，我们要知道插入的是一个结点，这时候就要创建一个结点来存放元素，指针我们置为空。

SListNode* BuySListNode(SLDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    //记得判断是否开辟成功
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
    //直接将要操作的元素放进新节点里
    //后面只需要操作指针
	return newnode;
}

进行尾插

尾插时，原末尾结点的指针指向NULL，我们需要改变，令原末尾结点指针指向新节点就可以了。

//单链表尾插
void SListPushBack(SListNode** phead, SLDataType x)
{
    //创建新结点
	SListNode* newnode = BuySListNode(x);
    //判断链表头结点是否为空
	if (*phead == NULL)
	{
		*phead = newnode;
	}
    
	else
	{
		//遍历找最后一个节点（找尾）
		SListNode* tail = *phead;
		while (tail->next!=NULL)
		{
			tail = tail->next;
		}

		//(尾插)
		tail->next = newnode;
	}
}

注：

这里要特别注意函数传参问题，函数类型为void，那么不进行返回，但是我们要改变结点的指针，所以在使用函数时，应该传的是指针的地址，头结点为slist，使用时应传（&slist），接收时应该用双指针接收。

记住一句话：函数传参时，想要改变什么，就传什么的地址。

3.2尾删

这里要判断三种情况：

1.链表为空时 2.链表只有一个结点时 3.多个结点

我们要释放最后一个结点，还要将前一个结点的next置空。

//2.单链表尾删
void SListPopBack(SListNode** phead)
{
	assert(phead);
	//1.空
	//2.一个
	//3.多个
	if (*phead==NULL)
	{
		return;
	}
	else if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		//遍历找最后一个节点（找尾）
		SListNode* tail = *phead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}

}

4.单链表头部操作

4.1头插

头插很简单，只需要创建新结点，令新结点的next指向原头结点，将头结点移到新结点位置即可。

//单链表头插
void SListPushFront(SListNode** phead, SLDataType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *phead;
	*phead = newnode;
}

4.2头删

令头结点指向头结点的next，释放原头结点即可。

//单链表头删
void SListPopFront(SListNode** phead)
{
	assert(phead);
	if (*phead == NULL)
	{
		return;
	}

    //保存头结点的next
	SListNode* next = (*phead)->next;
	free(*phead);
	*phead = next;
}

5.固定位置操作

5.1固定位置插入

要判断固定位置是否为空(超出链表范围)，为第一个时，相当于头插

其他情况下，先要遍历找到pos，开辟新结点，pos前结点next指向newnode newnode的next指向pos。

//单链表pos位置插入
void SListInsert(SListNode** phead, SListNode* pos, SLDataType x)
{
	assert(phead);
	assert(pos);

	//1.pos是第一个节点,相当于头插
	//2.pos不是第一个节点
	if (pos == *phead)
	{
		SListPushFront(phead,x);
	}
	else
	{
		SListNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SListNode* newnode = BuySListNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

5.2固定位置删除

将pos位置前结点的next指向pos的下一个结点，即pos的next，释放pos位置即可

也是先遍历，判断条件与4.1过程相同。

//单链表固定位置删除
void SListErase(SListNode** phead, SListNode* pos)
{
	assert(phead);
	assert(pos);
	if (pos == *phead)
	{
		SListPopFront(phead);
	}
	else
	{
		SListNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}

}

6.查找及修改

需要遍历，若结点data等于要查找的值，返回结点地址即可，因为无指针的改变，传参时不需要传入指针地址，接收时不需要二级指针。

//查找
SListNode* SListfind(SListNode* phead, SLDataType x)
{
	SListNode* cur = phead;
	while (cur!=NULL)
	{
		if (cur->data==x)
		{
			return cur;
		}
		
		cur = cur->next;
	}
	return NULL;
}

若要修改，应先找，查找函数返回的是指针，直接用指针修改对应的data即可

例子：

void TestSList2()
{
    //创建链表
	SListNode* slist = NULL;
	for (int i = 0;i<4;i++)
	{
		SListPushBack(&slist, i);
	}
	SListPrint(slist);
    
    //查找要修改的值
	SListNode* pos = SListFind(slist,3);
	if (pos)
	{
		printf("找到了:%p\n",pos);
		//修改
		pos->data *= 10;
	}
	SListPrint(slist);
}

7.固定位置后的插入删除

插入，先保存pos的next为next，将pos的next指向新结点，新节点的next指向刚刚保存的next，这样就将新结点连接在pos位置后了。

//单链表pos位置后插入
void SListInsertAfter(SListNode* pos, SLDataType x)
{
	assert(pos);
	SListNode* next = pos->next;
	SListNode* newnode = BuySListNode(x);
	pos->next = newnode;
	newnode->next = next;
}

删除，保存pos的next为next，判断next是否为空，不为空则将pos的next直接指向next的next，释放掉第一次保存的next，即刚开始的pos的next，next置空即可。

//单链表pos位置后删除
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	SListNode* next = pos->next;
	if (next)
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

8.销毁

预先保存头结点的下一个结点，要不然头结点释放后找不到下一个结点。

//销毁
void SListDestory(SListNode** phead)
{
	assert(phead);
	SListNode* cur = *phead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*phead = NULL;
}

这样单链表的定义及功能就完成了，只需要根据自身需求写主函数和菜单就可以了。

单链表的实现