《数据结构：C语言实现单链表》

一、单链表

1、概念与结构

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

2、结点

单链表与顺序表不同的是，链表的每个空间是独立申请的，称为一个结点。

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

所以在动态申请空间时使用malloc函数开辟空间就可以了。

3、链表的性质

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

假设当前保存的结点为整形的结构体代码：

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

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

二、实现单链表

1、创建单链表的结构体

创建一个名为SListNode.h的头文件
向SListNode.h输入如下代码：

用typedef 给要存储的数据重命名，也给单链表结构体重命名一个简单的名字SLTNode

2、头部数据插入

创建一个test.c文件用来测试程序
创建一个SListNode.c文件完成函数的定义
把函数声明放置在SListNode.h的头文件中
在test.c文件中进行主函数调用test1()函数进行测试，在test1()中创建一个单链表结构体变量,前提包含了#include"SListNode.h"，完成创建。

test.c:

传址调用，通过地址可以完成形参改变实参

SListNode.h:

传参是一级指针的地址用二级指针接收

SListNode.c:

先断言,保存数据申请空间，在创建一个开辟空间的函数，在开辟空间把要保存的数据传过去保存，空间不连续用malloc开辟

再完成一个打印数据的函数
不是通用的，现在打印的是整形数据

测试成功

3、尾插数据

要考虑两种情况，在一个数据都没有时第一个节点就是首尾结点。
在有数据的情况下，要找到最后一个结点，最后一个结点存放的指针指向的地址为NULL，把这个节点的指针指向为新结点。

4、头删和尾删数据

头删：

尾删：

5、查找数据

使用方法：

查找功能可以返回动态内存的空间，方便我们去在任意位置之前增删，结合使用。

6、在任意位置之前增加数据

test测试：

在数据为5的结点前面插入新结点，要传三个值，第一个是首结点，第二个要在哪个结点之前插入结点，第三个插入的数据值。

代码实现：

思路在开辟新结点，需要用首结点找到插入结点之前的结点，让之前结点指向新结点，新结点指向被插入的结点。
特殊情况在被插入数据结点是首结点时，前面没有结点，直接调用头插。

7、删除结点

同样是用查询找到被删数据的结点在进行调用函数删除。

8、删除结点之后的结点

9、在结点之后插入数据

10、销毁链表

三、代码

SListNode.h

#pragma once

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

typedef int SLTDATETYPE;

typedef struct SListNode
{
	SLTDATETYPE date;//结点数据
	struct SListNode* next;//指针保存下一个结点的地址
}SLTNode;

//单链表头部插入数据
void SLTPushFornt(SLTNode** pps, SLTDATETYPE x);

//打印数据
void SLTPrint(SLTNode* ps);

//单链表尾部插入数据
void SLTPushBack(SLTNode** pps, SLTDATETYPE x);

//单链表头部删除数据
void SLTPopFornt(SLTNode** pps);

//单链表尾部删除数据
void SLTPopBack(SLTNode** pps);

//查找数据返回数组的空间
SLTNode* SLTFind(SLTNode* ps, SLTDATETYPE x);

//在任意位置之前插入数据
void SLTInsert(SLTNode** pps,SLTNode* pos, SLTDATETYPE x);

//在结点之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDATETYPE x);

//删除结点
void SLTErase(SLTNode** pps, SLTNode* pos);

//删除结点之后的结点
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SLTDestroy(SLTNode** pps);

SListNode.c

#include"SListNode.h"

//申请结点空间
SLTNode* SLTBuyNode(SLTDATETYPE x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		//申请失败
		perror("malloc full");
		exit(1);
	}
	newnode->date = x;
	newnode->next = NULL;

	return newnode;
}

//单链表头部插入数据
void SLTPushFornt(SLTNode** pps, SLTDATETYPE x)
{
	assert(pps != NULL);
	//先开辟空间
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pps;
	*pps = newnode;
}

//打印数据
void SLTPrint(SLTNode* ps)
{
	while (ps != NULL)
	{
		printf("%d->", ps->date);
		ps = ps->next;
	}
	printf("NULL\n");
}

//单链表尾部插入数据
void SLTPushBack(SLTNode** pps, SLTDATETYPE x)
{
	assert(pps != NULL);
	SLTNode* newnode = SLTBuyNode(x);
	if (*pps == NULL)
	{
		*pps = newnode;
	}
	else
	{
		SLTNode* pcur = *pps;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
	}
}

//单链表头部删除数据
void SLTPopFornt(SLTNode** pps)
{
	assert(pps != NULL);
	//如果首节点为空没有数据可删了
	assert(*pps != NULL);
	//保存下一个结点的地址
	//删除首结点后下一个结点成为首结点
	SLTNode* pcur = (*pps)->next;
	free(*pps);
	*pps = pcur;
}

//单链表尾部删除数据
void SLTPopBack(SLTNode** pps)
{
	assert(pps != NULL);
	assert(*pps != NULL);
	//如果只有一个数据就直接删除

	//找尾节点
	SLTNode* pcur = *pps;

	if (pcur->next == NULL)
	{
		free(*pps);
		*pps = NULL;
	}
	else
	{
		//保存尾结点的上一结点
		//因为尾结点被删，它成为尾结点，结点指针指向NULL
		SLTNode* prev = *pps;
		while (pcur->next)
		{
			prev = pcur;
			pcur = pcur->next;
		}
		prev->next = NULL;
	}
}

//查找数据返回数组的空间
SLTNode* SLTFind(SLTNode* ps, SLTDATETYPE x)
{
	while (ps)
	{
		if (ps->date == x)
			return ps;
		ps = ps->next;
	}
	return NULL;
}

//在任意位置之前插入数据
void SLTInsert(SLTNode** pps, SLTNode* pos, SLTDATETYPE x)
{
	assert(pps != NULL);
	assert(pos != NULL);
	if (*pps == pos)
	{
		//头结点头插
		SLTPushFornt(pps, x);
	}
	else
	{
		SLTNode* newnode = SLTBuyNode(x);
		SLTNode* pcur = *pps;

		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}

		pcur->next = newnode;
		newnode->next = pos;
	}
}

//在结点之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDATETYPE x)
{
	assert(pos != NULL);
	
	SLTNode* pcur = pos->next;
	SLTNode* newnode = SLTBuyNode(x);
	pos->next = newnode;
	newnode->next = pcur;

}

//删除结点
void SLTErase(SLTNode** pps, SLTNode* pos)
{
	assert(pps != NULL);
	assert(pos != NULL);
	if (*pps == pos)
	{
		SLTPopFornt(pps);
	}
	else
	{
		SLTNode* pcur = *pps;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//删除结点之后的结点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos != NULL && pos->next != NULL);
	SLTNode* pcur = pos->next->next;
	free(pos->next);
	pos->next = pcur;
}

//销毁链表
void SLTDestroy(SLTNode** pps)
{
	assert(pps != NULL);
	SLTNode* pcru = *pps;
	SLTNode* next = *pps;
	while (pcru)
	{
		
		next = pcru->next;
		free(pcru);
		pcru = next;
	}
	*pps = NULL;
}