1.链表的介绍
链表分为单链表与双链表。链表和顺序表一样，均属于顺序表，因此链表的逻辑结构是线性的。链表在内存中的存储方式是不一定连续的（因此链表的物理结构不一定是线性的），也不一定是按照顺序存储。
2、节点的介绍
a.链表是由一个一个的节点连接组成的。每一个节点存储一个数据和指向下一个节点的指针。
b.上图中指针变量plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012FFA0。
c.链表中每个结点都是独立申请的一块空间（即需要插⼊数据时才去申请⼀个结点的空间），我们需要通过指针变量来保存下⼀个结点地址才能从当前结点找到下⼀个结点。
d.结点的空间⼀般是从堆上申请的。从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续。
3.创建单链表
//创建单链表(结点)的结构
typedef struct SListNode
{DataType data;//结点中存储一个DataType类型的数据struct SListNode* next;//再存储一个指向下一个结点的指针
}SLNode;void CreateSList()//创建一个单链表(Create:创建)
{//创建了4个结点，并将4个结点的地址分别给了node1、node2、node3、node4SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));node1->data = 1;SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));node2->data = 2;SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));node3->data = 3;SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;}
用这种方式创建单链表，需要手动创建一个又一个的结点，效率太低了。下面给出效率高的方式。
4.单链表的实现
4.1实现的具体框架
需要创建SList.c、SList.h、SListTest.c三个文件。
1.SList.h文件相当于目录的功能，告诉我们这个文件中提供了哪些函数（即存放函数的声明）
2.SList.c文件是用来具体实现SList.h文件中的每个函数的功能
3.等SList.c、SList.h这两个文件写好之后，在SListTest.c文件中测试单链表的增删查改各项功能。
a.SList.h文件
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DataType;
//定义单链表(结点)的结构
typedef struct SListNode
{DataType data;//存储一个DataType类型的数据struct SListNode* next;//存储下一个结点的地址
}SLNode;//打印单链表的数据
void SLPrint(SLNode* plist);//传首结点的地址//插入结点前要申请新结点的空间,并返回新结点的地址
SLNode* SLbuyNode(DataType x);//向单链表头部插入结点
void SLpushFront(SLNode** pplist, DataType x);//两个p表示二级指针
//若单链表为空表，则头结点的地址为NULL，插入新结点后，头结点的地址将会发生变化
//因此要传指向头结点的指针的地址(采用传址调用)//向单链表尾部插入结点
void SLpushBack(SLNode** pplist, DataType x);//两个p表示二级指针
//若单链表为空表，则头结点的地址为NULL，插入新结点后，头结点的地址将会发生变化
//因此要传指向头结点的指针的地址(采用传址调用)//删除头结点
void SLpopFront(SLNode** pplist);//两个p表示二级指针
//若单链表中只有一个结点，删除头结点后，头结点的地址就变成了NULL
//因此要传指向头结点的指针的地址//删除尾结点
void SLpopBack(SLNode** pplist);//两个p表示二级指针
//若单链表中只有一个结点，则删除尾结点后，头结点的地址就变成了NULL
//因此要传指向头结点的指针的地址//查找单链表中的数据
SLNode* SLFind(SLNode* phead, DataType x);//查找数据x的过程中，不会改变头结点的地址
//因此传头结点的地址就行(传值调用)//在指定结点(pos指向的结点)之前插入结点
//会影响pos指向的结点的前一个结点
void SLInsert(SLNode** pphead, SLNode* pos, DataType x);
//若在头结点之前插入结点，则头结点的地址将会发生变化
//因此要传指向头结点的指针的地址//在指定结点(pos指向的结点)之后插入结点
//会影响pos指向的结点
void SLInsertAfter(SLNode* pos, DataType x);
//通过pos就能找到pos指向的下一个结点，因此不需要头结点的地址//删除指定的结点(pos指向的结点)
//会影响pos指向的结点与pos指向的结点的前一个结点
void SLErase(SLNode** pphead, SLNode* pos);
//若删除的是头结点，则头结点的地址会方式变化，因此要传指向头结点的指针的地址(传址调用)//删除指定的结点(pos指向的结点)的后一个结点
//会影响pos指向的结点与pos指向的结点的后一个结点
void SLEraseAfter(SLNode* pos);
//通过pos就能找到pos指向的结点的下一个结点，因此不需要传头结点的地址//单链表的销毁
void SListDestroy(SLNode** pphead);
//头结点的地址会方式变化，因此要传指向头结点的指针的地址(传址调用)
b.SList.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//打印单链表的数据
void SLPrint(SLNode* plist)//传首结点的地址
{while (plist){printf("%d->", plist->data);plist = plist->next;}printf("NULL\n");
}//插入结点前要申请新结点的空间,并返回新结点的地址
SLNode* SLbuyNode(DataType x)
{SLNode* node = (SLNode*)malloc(sizeof(SLNode));//检查新结点的空间是否申请成功assert(node);node->data = x;node->next = NULL;return node;
}//向单链表头部插入结点
void SLpushFront(SLNode** pplist, DataType x)//两个p表示二级指针
{//*pplist表示指向头结点的指针assert(pplist);//插入结点前要申请新结点的空间SLNode* NewNode = SLbuyNode(x);//判断单链表是否为空表(若指向头结点的指针为空指针，单链表就是空表)if (*pplist == NULL){//若单链表是空表，则新申请的结点就是头结点*pplist = NewNode;}else{//若单链表不是空表，则将新结点的next指针指向头结点，再将指向头结点的指针的值进行修改NewNode->next = *pplist;*pplist = NewNode;}
}//向单链表尾部插入结点
void SLpushBack(SLNode** pplist, DataType x)//两个p表示二级指针
{assert(pplist);//插入结点前要申请新结点的空间SLNode* NewNode = SLbuyNode(x);//判断单链表是否为空(若指向头结点的指针为空指针，则单链表为空表)if (*pplist == NULL){//若单链表为空表，新申请的结点就是尾结点(同时也是头结点)*pplist = NewNode;}else{//若单链表为空表，则先要找尾结点(尾结点的特征:它的next指针为空指针)，然后将尾结点的next指针指向新结点SLNode* start = *pplist;//找尾结点时，不能修改指向头结点的指针，否则就会找不到头结点了while (start->next){start = start->next;//找到尾结点之前，start指向下一个结点}start->next = NewNode;}
}//删除头结点
void SLpopFront(SLNode** pplist)//两个p表示二级指针
{//若单链表为空表，则不能删除结点(*pplist!=NULL)assert(*pplist && pplist);if ((*pplist)->next == NULL){//若单链表中只有一个结点free(*pplist);*pplist = NULL;}else{//若单链表中不止一个结点//将指向头结点的指针指向下一个结点，再释放头结点的空间SLNode* start = *pplist;*pplist = (*pplist)->next;free(start);//头结点的空间被释放后，start就变成了野指针start = NULL;}}//删除尾结点
void SLpopBack(SLNode** pplist)//两个p表示二级指针
{//若单链表为空表(*pplist!=NULL)，则不能删除结点assert(*pplist && pplist);if ((*pplist)->next == NULL){//若单链表中只有一个结点free(*pplist);*pplist = NULL;}else{//若单链表中不止一个结点//给尾结点的前一个结点的next指针赋值NULL，再释放尾结点的空间SLNode* end = *pplist;//end用于找尾结点。找尾结点的前一个结点时，不能修改指向头结点的指针，否则就找不到头结点了SLNode* prev = *pplist;//找尾结点的前一个结点while (end->next){prev = end;end = end->next;//end指向下一个结点}free(end);end = NULL;prev->next = NULL;}}//查找单链表中的数据
SLNode* SLFind(SLNode* phead, DataType x)
{//空链表无法查找数据assert(phead);SLNode* pcur = phead;//查找数据x的过程中，不希望指向头结点的指针的值发生变化，否则就找不到头结点了while (pcur)//从头结点往后遍历{if (pcur->data == x){return pcur;}pcur = pcur->next;}//如果单链表中没有x，就返回NULLreturn NULL;
}//在指定结点(pos指向的结点)之前插入新结点
void SLInsert(SLNode** pphead, SLNode* pos, DataType x)
{//若pphead==NULL，就找不到头结点了//若单链表为空表(*pphead=NULL),则单链表中不存在指定的结点//每个结点都有地址，若pos==NULL，则表示pos指向的结点不存在assert(pphead && *pphead && pos);/*插入思路:在指定结点(pos指向的结点)前插入新结点，则会影响pos指向的结点的前一个结点由于头结点没有前一个结点，因此要判断pos指向的结点是不是头结点*/if (pos == *pphead)//若pos指向的结点是头结点{SLpushFront(pphead, x);//这个函数内部会申请新结点的空间}else//若pos指向的结点不是头结点{//插入结点前要申请新结点的空间SLNode* NewNode = SLbuyNode(x);SLNode* pcur = *pphead;//pcur用于找pos指向的结点的前一个结点//p是point(指向)的缩写 cur是current(当前位置)的缩写while (pcur->next != pos){pcur = pcur->next;}pcur->next = NewNode;NewNode->next = pos;}
}//在指定结点(pos指向的结点)之后插入新结点
void SLInsertAfter(SLNode* pos, DataType x)
{//每个结点都有地址，若pos==NULL，则表示pos指向的结点不存在assert(pos);/*插入思路:在指定结点(pos指向的结点)之后插入新结点,会影响pos指向的结点*///插入结点前要申请新结点的空间SLNode* NewNode = SLbuyNode(x);/*pos->next = NewNode;NewNode->next = pos->next;这种写法是错误的*/NewNode->next = pos->next;pos->next = NewNode;
}//删除指定的结点(pos指向的结点)
void SLErase(SLNode** pphead, SLNode* pos)
{//若pphead==NULL,则找不到头结点//若*pphead==NULL，则单链表为空表，无法删除结点//每个结点都有地址，若pos==NULL，则表示pos指向的结点不存在assert(pphead && *pphead && pos);/*删除思路:删除指定的结点(pos指向的结点),会影响pos指向的结点与pos指向的结点的前一个结点由于头结点没有前一个结点，因此要判断pos指向的结点是不是头结点*/if (pos == *pphead)//若pos指向的结点是头结点{SLNode* pcur = *pphead;*pphead = (*pphead)->next;free(pcur);pcur = NULL;}else//若pos指向的结点不是头结点{//先找pos指向的结点的前一个结点//找pos指向的结点的前一个结点时，不能改变指向头结点的指针的值，否则就找不到头结点了SLNode* pcur = *pphead;//pcur用于找pos指向的结点的前一个结点while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}}//删除指定的结点(pos指向的结点)的后一个结点
//会影响pos指向的结点与pos指向的结点的后一个结点
void SLEraseAfter(SLNode* pos)
{//若pos==NULL,则表示pos指向的结点不存在//若(pos->next)==NULL，则表示pos指向的结点的下一个结点不存在assert(pos && pos->next);SLNode* temp = pos->next;pos->next = pos->next->next;free(temp);temp = NULL;
}//单链表的销毁
void SListDestroy(SLNode** pphead)
{//若pphead==NULL,则找不到头结点//若*pphead==NULL,则单链表是空表，不需要销毁assert(pphead && *pphead);SLNode* pcur = *pphead;while (pcur){//逐个释放pucr指向的结点的空间SLNode* next = pcur->next;free(pcur);pcur = next;}*pphead =NULL;
}
c.SListTest.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void test()
{//创建一个空的单链表(指向头结点的指针为空指针)SLNode* phead = NULL;/*测试插入头结点SLpushFront(&phead, 3);SLpushFront(&phead, 2);SLpushFront(&phead, 1);SLPrint(phead);SLpopFront(&phead);SLPrint(phead);SLpopFront(&phead);SLPrint(phead);SLpopFront(&phead);SLPrint(phead);*//*测试插入尾结点SLpushBack(&phead, 3);SLpushBack(&phead, 2);SLpushBack(&phead, 1);SLPrint(phead);SLpopBack(&phead);SLPrint(phead);SLpopBack(&phead);SLPrint(phead);SLpopBack(&phead);SLPrint(phead);*//*测试单链表的销毁SLpushFront(&phead, 3);SLpushFront(&phead, 2);SLpushFront(&phead, 1);SLPrint(phead);//1->2->3->NULLSListDestroy(&phead);SLPrint(phead);*/
}
int main()
{test();return 0;
}