1:链表概念 

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

1：结点

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点 / 结点”.
结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。
图中指针变量 plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望
plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012FFA0。
链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

2：链表性质

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续
2、结点⼀般是从堆上申请的
3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

3：结点结构体的代码

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

2：链表的打印

void SLPrint(SLTNode* phead){
SLTNode* pcur=phead;
while(pcur){
      printf("%d -> ",pcyr);
      pcur = pcur -> next;
           }
      printf("NULL");
}

代码和图片联系一下

 

将int 重命名为SLDateType是为了将链表的元素和整型做出区分。

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

3：链表代码

我们需要在VS 2022上面创建3个文件。

1：头文件node.h（很全）

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

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

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);

// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
void SLTDestroy(SListNode** pphead);

对于链表，我们不需要进行初始化的行为。

对于链表，我们和顺序表一样，需要进行数据的增删查改。指定位置插入，指定位置删除。

2:函数实现文件node.c

#include"node.h"
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode=(SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("buy fail");
		exit(10086);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SListPrint(SListNode* plist)
{
	SListNode* pcur = plist;
	while (pcur!=NULL)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL");
}

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode*newnode = BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* ptail = *pplist;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

void SListPopBack(SListNode** pplist)
{
	assert(pplist&&*pplist);
	if ((*pplist) -> next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* pcr = *pplist;
		SListNode* pev = NULL;
		while (pcr->next)
		{
			pev = pcr;
			pcr = pcr->next;
		}
		pev->next=NULL;
		free(pcr);
		pcr = NULL;

	}
}

void SListPopFront(SListNode** pplist)
{
	assert(*pplist&& pplist);
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* pev = *pplist;
		*pplist = pev->next;
		free(pev);
		pev = NULL;
	}
}

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* pcr = plist;
	while (pcr->next)
	{
		if (pcr->data==x)
		{
			printf("%d\n", x);
			return pcr;
		}
		pcr = pcr->next;
	}
	printf("Can't find\n");
	return NULL;
}

void SListInsertAfter (SListNode* pos, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
	assert(pphead && pos);
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* newnode = BuySListNode(x);
		SListNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		newnode->next = pos;
		pre->next = newnode;
	}
}

void SListEraseAfter(SListNode* pos)
{
	assert(pos&&pos->next);
	SListNode* now = pos->next;
	pos->next = pos->next->next;
	free(now);
	now = NULL;
}

void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead&&pos);
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prc = *pphead;
		while (prc->next != pos)
		{
			prc = prc->next;
		}
		prc->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* pev = *pphead;
	while (pev)
	{
		SListNode* next = pev->next;
		free(pev);
		pev = next;
	}
	*pphead = NULL;
}

3:测试文件

#include"node.h"

void test()
{
	SListNode* node = BuySListNode(1);
	SListPushFront(&node, 4);
	SListPushFront(&node, 4);
	SListPushFront(&node, 4);
	SListNode* op = SListFind(node, 4);
	SListPushFront(&node, 2);
	SListPushFront(&node, 4);
	SListPrint(node);
	SLTErase(&node, op);
	SListPrint(node);
	SListPushFront(&node, 6);
	SListPushFront(&node, 27);
	SListPushFront(&node, 999);
	SListPushFront(&node, 56);
	SListPushFront(&node, 6);
	SListPushFront(&node, 567);
	SListNode* ret = SListFind(node, 56);
	SListPrint(node);
	SListEraseAfter(ret);
	SListPrint(node);
	SLTDestroy(&node);
}

int main()
{
	test();
	return 0;
}