《数据结构：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{//保存尾结点的上一结点//因为尾结点被删，它成为尾结点，结点指针指向NULLSLTNode* 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;
}