线性表，顺序表，链表

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列

线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线

但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储

也就是说，我们可以将线性表当作顺序表与链表的集合体 

---

顺序表

顺序表的本质是数组

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存 储

数组有一个绝对的优势：下标的随机访问

举个例子:

对于二分查找来说，只能用于数组（还有其他排序一样），就是通过数组的下标访问来实现的，由于数组的数据是连续存储的，可以通过下标按照规定的顺序来访问相对于的元素

在数组上完成数据的增删查改

---

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素

使用定长数组存储元素

//静态的顺序表#define N 10
typedef int SLDatatype;
//对SLDatatype重新赋予类型，目的是可以随意改变SLDatatype的类型struct SeqList
{SLDatatype a[N];//定义一个数组int size;//评估顺序表有多少数据
};

但是对于静态顺序表而言，它存在两个问题：

1.由于事先给定长度，当想扩容会变得非常麻烦（给小了不够用）

2.若给定过大长度，则容易造成内存空间浪费（给多了浪费）

所以我们一般使用动态顺序表

---

2. 动态顺序表：使用动态开辟的数组存储

//动态的顺序表typedef int SLdatatype;struct SeqList
{SLdatatype* a;//定义一个动态开辟的空间int size;//评估顺序表存储的有效数据个数int capacity;//评估顺序表的容量空间
};

对SeqList结构体进行初始化操作

void SLInit(SL* psl)//顺序初始化
{psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟4个SLDatatype类型的空间//将返回的无符号类型指针地址强制转换为SLDatatype*类型if (psl->a == NULL){perror("malloc fail");return;}psl->size = 0;psl->capacity = 4;
}

通过上面可以看到，对SeqList的数组a进行了动态开辟内存的操作

这样就可以弥补静态开辟内存的不足

接下来我们研究增删查改的实现

增

在上面我们进行了开辟空间的操作，接下来我们进行增加元素的操作

分为以下几种：头部增加（头插），尾部增加（尾插），任意位置增加

先来看头插

void SLPushFront(SL* psl, SLDatatype x)//头插
{int end = psl->size - 1;int str = 0;while (end >= str){psl->a[end + 1] = psl->a[end];//令后一项等于前一项（后移前，避免覆盖数据）end--;}psl->a[str] = x;psl->size++;
}

由于我们在最前方进行数据插入的操作，为了让移动数据时不会覆盖掉数据导致bug的出现

我们应该从后往前移动数据，如上代码所示

但是对于这个代码会有什么样的问题出现呢？

若当该空间（psl->a）已全部存放数据，此时再进行插入数据操作时，会出现越界问题

所以在进行插入操作前，我们应该增加一次检查空间容量的操作

如下代码所示即为检查空间容量实现代码

void SLCheckCapacity(SL* psl)检查容量
{if (psl->size == psl->capacity){SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);//扩容到原来空间的2倍if (tmp == NULL){perror("realloc fail");return;}psl->a = tmp;psl->capacity *= 2;}
}

并需要在插入操作时加入该操作

下面看尾插

void SLPushBack(SL* psl, SLDatatype x)//尾插
{SLCheckCapacity(psl);//检查容量psl->a[psl->size] = x;//psl->a[psl->size++] = x;//先赋值，再自增psl->size++;
}

由于也是插入数据操作，我们依旧需要判断空间是否足够

在这里我们有两种表达方式

一种是psl->a[psl->size] = x;        psl->size++;

另一种是psl->[psl->size++] = x;

这两种等效（由于size++为后置自增，先使用再自增，详细查看操作符详解）

由于下标索引为psl->size指向的位置正为当前空间的最后一个元素空间

所以直接进行赋值操作，再另size++即可

最后看任意位置插入

void SLInsert(SL* psl, int pos, SLDatatype x)//任意位置插入
{SLCheckCapacity(psl);//检查容量int end = psl->size - 1;while (end >= pos){psl->a[end + 1] = psl->a[end];end--;}psl->a[pos] = x;psl->size++;
}

同上，先进行空间检查操作

由于是在任意位置插入，需要进行数据移位操作，为了不覆盖数据，需要从后往前移动

设定指针end，令其指向当前最后有效一个元素的位置，再进行移动赋值操作

直到end的位置等于pos的位置

但是对于这个代码而言，存在一个很严重的问题

当我选择插入的空间大于或者小于这个空间的范围时，会出现越界的情况

所以我们还需要在此之前增加一个判断，检测pos的值是否合法

在这里我们有两种表达方式

void SLInsert(SL* psl, int pos, SLDatatype x)//任意位置插入
{//assert(pos >= 0 && pos <= psl->size);SLCheckCapacity(psl);//检查容量if (pos > psl->size || pos < 0){printf("输入错误!\n");return;}int end = psl->size - 1;while (end >= pos){psl->a[end + 1] = psl->a[end];end--;}psl->a[pos] = x;psl->size++;
}

我么可以使用assert断言或者使用if判断语句，前者是暴力检查，后者是柔性检查

（assert断言的使用方法）

其实，对于头插和尾插，我们都可以通过引用任意位置插入的函数来实现

头插：SLInsert(psl, 0, x);（在起始位置插入）

尾插：SLInsert(psl , psl->size, x);（在结束位置插入）

---

删

对于删除操作，我们也有以下三种情况

头部删除（头删），尾部删除（尾删），任意位置删除

首先看头删

void SLPopFront(SL* psl)//头删
{int str = 0;while (str < psl->size - 1){psl->a[str] = psl->a[str + 1];//将后值赋给前值（从前往后避免覆盖）str++;}psl->size--;
}

由于是头部删除，删除之后要进行元素移动操作

为了不使数据被覆盖，这里需要从前往后移动数据避免覆盖

当删除完毕后，size需要自减

对于这里而言，我们仍然需要增加一个判断，来检查空间内是否有元素需要删除，避免越界

完整代码如下

void SLPopFront(SL* psl)//头删
{//assert(psl->size > 0);if (psl->size == 0){printf("表内无数据!\n");return;}int str = 0;while (str < psl->size - 1){psl->a[str] = psl->a[str + 1];//将后值赋给前值（从前往后避免覆盖）str++;}psl->size--;
}

再来看尾部删除

void SLPopBack(SL* psl)//尾删
{//assert(psl->size > 0);if (psl->size == 0){printf("表内无数据!\n");return;}psl->size--;
}

同理，我们仍然需要先判断空间内是否有元素

对于尾删而言，也许我们一开始会选择将最后一个有效元素赋值为0

可是当最后一个有效元素本身就为0的情况下，这种操作未免显得没有意义

所以我们可以直接选择直接令psl->size减少1，直接去除最后一个元素

最后看任意位置删除

void SLErase(SL* psl, int pos)//任意位置删除
{//assert(pos >= 0 && pos < psl->size);if (pos > psl->size || pos < 0){printf("输入错误!\n");return;}while (pos < psl->size - 1){psl->a[pos] = psl->a[pos + 1];pos++;}psl->size--;
}

老规矩，先检查空间

再进行移动赋值操作（需要从后往前移动，避免覆盖）

对于头删和尾删，可以引用任意位置删除函数来进行删除操作

头删：SLErase(psl, 0);（删除第一位元素）

尾删：SLErase(psl, psl->size - 1);（删除最后一位元素）

---

查 

代码如下

SLDatatype SLFind(SL* psl, SLDatatype x)//查
{for (int i = 0; i < psl->size; i++){if (psl->a[i] == x){return i;}elsereturn -1;}
}

非常简单，只需要一个循环遍历即可

---

改

代码如下

void SLModify(SL* psl, int pos, SLDatatype x)//改
{//assert(pos >= 0 && pos < psl->size);if (pos > psl->size || pos < 0){printf("输入错误!\n");return;}psl->a[pos] = x;
}

同样非常简单

只需要通过下标索引值找到想要修改的值，对其重新赋值即可

---

执行完上面的操作之后，下面还有几个需要注意的点

打印函数

为了可以直观地看到数据，我们需要使用一个打印函数来检查是否满足我们的需求

void SLPrint(SL* psl)//打印
{if (psl->size == 0){printf("表内无数据!\n");}for (int i = 0; i < psl->size; i++){printf("%d ", psl->a[i]);}printf("\n");
}

释放内存

由于使用malloc和relloc函数在堆中开辟空间，结束使用后需要手动释放内存

避免造成内存泄漏

void SLDestroy(SL* psl)//释放内存
{free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}

值得一提的是，我们在进行函数调用时，有时候可能会出现错误传递空指针

为了避免这样的情况，我们应该在每一个函数定义部分都加上assert断言

来判断是否有传递空指针的情况

完整代码如下

SeqList.h#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//静态的顺序表//#define N 10
//typedef int SLDatatype;
对SLDatatype重新赋予类型，目的是可以随意改变SLDatatype的类型
//
//struct SeqList
//{
//	SLDatatype a[N];
//	//定义一个数组
//	int size;
//	//评估顺序表有多少数据
//};//动态的顺序表typedef int SLDatatype;typedef struct SeqList
{SLDatatype* a;//定义一个动态开辟的空间int size;//评估顺序表存储的有效数据个数int capacity;//评估顺序表的容量空间
}SL;
//对结构体SeqList类型重命名void SLInit(SL* psl);//初始化
void SLDestroy(SL* psl);//释放内存void SLCheckCapacity(SL* psl);//检查容量空间是否足够
void SLPrint(SL* psl);//打印void SLPushBack(SL* psl, SLDatatype x);//尾插
void SLPushFront(SL* psl, SLDatatype x);//头插void SLPopBack(SL* psl);//尾删
void SLPopFront(SL* psl);//头删void SLInsert(SL* psl, int pos, SLDatatype x);//任意位置插入
void SLErase(SL* psl, int pos);//任意位置删除SLDatatype SLFind(SL* psl, SLDatatype x);//查
void SLModify(SL* psl, int pos, SLDatatype x);//改

此处是对结构体的定义，函数的声明以及#define操作

SeqList.c#include "SeqList.h"void SLInit(SL* psl)//顺序初始化
{psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟4个SLDatatype类型的空间//将返回的无符号类型指针地址强制转换为SLDatatype*类型if (psl->a == NULL){perror("malloc fail");return;}psl->size = 0;psl->capacity = 4;
}void SLCheckCapacity(SL* psl)检查容量
{assert(psl != NULL);if (psl->size == psl->capacity){SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);//扩容到原来空间的2倍if (tmp == NULL){perror("realloc fail");return;}psl->a = tmp;psl->capacity *= 2;}
}void SLPrint(SL* psl)//打印
{assert(psl != NULL);if (psl->size == 0){printf("表内无数据!\n");}for (int i = 0; i < psl->size; i++){printf("%d ", psl->a[i]);}printf("\n");
}void SLDestroy(SL* psl)//释放内存
{assert(psl != NULL);free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}void SLPushBack(SL* psl, SLDatatype x)//尾插
{assert(psl != NULL);SLCheckCapacity(psl);//检查容量psl->a[psl->size] = x;//psl->a[psl->size++] = x;//先赋值，再自增psl->size++;//SLInsert(psl , psl->size, 3);
}void SLPushFront(SL* psl, SLDatatype x)//头插
{assert(psl != NULL);SLCheckCapacity(psl);//检查容量int end = psl->size - 1;int str = 0;while (end >= str){psl->a[end + 1] = psl->a[end];//令后一项等于前一项（后移前，避免覆盖数据）end--;}psl->a[str] = x;psl->size++;//SLInsert(psl, 0, 3);
}void SLPopBack(SL* psl)//尾删
{assert(psl != NULL);//assert(psl->size > 0);if (psl->size == 0){printf("表内无数据!\n");return;}psl->size--;//SLErase(psl, psl->size - 1);
}void SLPopFront(SL* psl)//头删
{assert(psl != NULL);//assert(psl->size > 0);if (psl->size == 0){printf("表内无数据!\n");return;}int str = 0;while (str < psl->size - 1){psl->a[str] = psl->a[str + 1];//将后值赋给前值（从前往后避免覆盖）str++;}psl->size--;//SLErase(psl, 0);
}void SLInsert(SL* psl, int pos, SLDatatype x)//任意位置插入
{assert(psl != NULL);//assert(pos >= 0 && pos <= psl->size);SLCheckCapacity(psl);//检查容量if (pos > psl->size || pos < 0){printf("输入错误!\n");return;}int end = psl->size - 1;while (end >= pos){psl->a[end + 1] = psl->a[end];end--;}psl->a[pos] = x;psl->size++;
}void SLErase(SL* psl, int pos)//任意位置删除
{assert(psl != NULL);//assert(pos >= 0 && pos < psl->size);if (pos > psl->size || pos < 0){printf("输入错误!\n");return;}while (pos < psl->size - 1){psl->a[pos] = psl->a[pos + 1];pos++;}psl->size--;
}SLDatatype SLFind(SL* psl, SLDatatype x)//查
{assert(psl != NULL);for (int i = 0; i < psl->size; i++){if (psl->a[i] == x){return i;}elsereturn -1;}
}void SLModify(SL* psl, int pos, SLDatatype x)//改
{assert(psl != NULL);//assert(pos >= 0 && pos < psl->size);if (pos > psl->size || pos < 0){printf("输入错误!\n");return;}psl->a[pos] = x;
}

此处是对各个函数的定义

main.c#include "SeqList.h"void test1(SL* s)//头尾插及打印测试
{SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLPushFront(s, 1);SLPushFront(s, 2);SLPushFront(s, 3);SLPushFront(s, 4);SLPrint(s);SLDestroy(s);
}void test2(SL* s)//尾删测试
{SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLPushFront(s, 1);SLPushFront(s, 2);SLPushFront(s, 3);SLPopBack(s);SLPopBack(s);SLPopBack(s);SLPopBack(s);//SLPopBack(s);//SLPopBack(s);//测试是否有越界的问题SLPrint(s);SLDestroy(s);
}void test3(SL* s)//头删测试
{SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLPushFront(s, 1);SLPushFront(s, 2);SLPushFront(s, 3);SLPopFront(s);SLPopFront(s);SLPopFront(s);SLPopFront(s);//SLPopFront(s);//SLPopFront(s);SLPrint(s);SLDestroy(s);
}void test4(SL* s)//任意位置插与任意位置删测试
{SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLInsert(s, 2, 3);SLInsert(s, 3, 4);SLInsert(s, 4, 5);SLInsert(s, 5, 6);SLErase(s, 2);SLErase(s, 2);SLErase(s, 2);SLPrint(s);SLDestroy(s);
}void test5(SL* s)//查找与修改测试
{SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLPushBack(s, 3);SLPushBack(s, 4);SLModify(s, 1, 20);SLPrint(s);printf("%d\n", SLFind(s, 1));SLDestroy(s);
}int main()
{SL s;//test1(&s);//test2(&s);//test3(&s);//test4(&s);test5(&s);return 0;
}

此处是主函数对各个函数的测试

---

链表

链表是一种物理存储结构上非连续、非顺序的存储结构

数据元素的逻辑顺序是通过链表中的指针链接次序实现的

相比较于顺序表，链表可以做到以下几个点：

1.不需要扩容

2.可以按需求申请释放

3.解决头部/中间插入删除需要解决的移动数据的问题

---

单链表

画图来理解：

如图所示

黄色区域存放的是链表中每个结点的数据

粉色区域存放的是链表中每个结点指向下一个结点的地址

那么如何管理他们？

首先起始位置需要有一个指针指向第一个结点

通过第一个结点的指针部分找到下一个结点的地址，从而进行访问

以此类推

最后一个结点的指针指向空指针

如何定义？

typedef int SLTDataType;    //将int类型重命名为SLTDataTypetypedef struct SListNode
{SLTDataType data;    //存放数据struct SListNode* next;    //指向下一段的结构体指针
}SLTNode;    //将struct SListNode重命名为SLTNode

对于单链表，我们也需要实现不同的功能：增，删，查

但在实现这些功能之前，我们需要为链表写一个开辟空间的函数方便调用

//开辟空间
SLTNode* BuyLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//开辟一个新的SLTNode结构体的空间，将其强制转换为SLTNode*类型，并将地址传给newnodeif (newnode == NULL){perror("malloc fail");return NULL;}//判断是否开辟空间成功newnode->data = x;newnode->next = NULL;//对newnode进行初始化return newnode;
}

接收一个data数据x，用于存放在链表结点内

将开辟的空间存放在newnode结构体指针中，进行判断是否开辟成功

随后将newnode中的data赋值为x，将newnode中的next置空（防止出现悬空指针）

返回这个新开辟的结点newnode

---

 增：

对于增，有三种方法，分别是头插，尾插与任意位置前插

头插：

//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//判断是否接收到plist的地址（pphead是头指针plist的地址）SLTNode* newnode = BuyLTNode(x);assert(newnode != NULL);//判断是否开辟成功newnode->next = *pphead;//令结点指针指向原先的结点（通过pphead的地址修改）*pphead = newnode;//令phead指针指向新结点（通过pphead的地址修改,其实是改变plist）
}

首先使用断言判断是否接收到pphead传送过来的地址

调用开辟空间函数，使用newnode接收新结点的地址

判断是否开辟成功

再另新结点指针指向原先的结点，最后令phead指针指向新结点（将头指向newnode）

---

尾插（第一种）：

//尾插
void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail = phead;while (tail != NULL){tail = tail->next;}SLTNode* newnode = BuyLTNode(x);assert(newnode != NULL);//判断是否开辟成功tail = newnode;
}

 上面这种属于错误写法 

首先定义以一个结构体指针tail接收phead的地址(将tail作为头)

判断tail是否为空

之后再使用一个结构体指针newnode接收新结点的地址

判断是否开辟成功

再令tail等于新结点newnode

但是！

对于这个函数而言，其实尾插是不成功的

有两个原因：

1、本质上tail并没有与链表连接起来（局部变量出了函数销毁）

2、链表连接应该使用tail->next = newnode来连接

接下来来改进一下

尾插（第二种）：

//尾插
void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail = phead;while (tail->next != NULL){tail = tail->next;}SLTNode* newnode = BuyLTNode(x);assert(newnode != NULL);tail->next = newnode;
}

上面这种属于错误写法 

此处与上面第一种不同的点为最后连接方式是使用tail->next = newnode来建立连接的

但是我们仍然忽略了一个最重要的点：

局部变量出了函数自动销毁

此处我们定义了一个tail结构体指针来接收phead，也就是想通过tail来改变链表

但是tail属于局部变量，当尾插函数一结束，tail自动销毁，而他会对phead指向的链表更改吗？

答案是不会的

由于phead本身属于指针（SLTNode* phead），他指向链表的头结点

想要通过传参改变链表，就需要通过二级指针来传参，（SLTNode** pphead）

第一层*访问找到pphead的地址，第二层*通过地址在访问到pphead指向的链表头结点

只有这样才能通过传参改变链表

尾插（第三种）：

//尾插（正确写法）
void SLPushBack(SLTNode** pphead, SLTDataType x)//使用二级指针来接收plist的地址
{SLTNode* newnode = BuyLTNode(x);assert(newnode != NULL);//链表为空if (*pphead == NULL)//对pphead进行解引用来访问pphead{*pphead = newnode;//将newnode的地址赋值给pphead}//链表非空else{SLTNode* tail = *pphead;//用结构体指针tail来接收pphead的地址(拷贝)while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

对于这一种写法，我们还加入了一个判断条件（判度链表是否为空）

假如链表没有任何元素时，phead为NULL，使用上面原来的方法将无法进行插入

需要分为两种情况：链表有元素，链表无元素进行讨论

之后再用结构体指针tail来接收指向头结点pphead的地址

通过二级指针来顺利改变链表

---

任意位置前插：

//任意位置前插入
void SLInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//判断目标位置是否为空SLTNode* prev = *pphead;if (*pphead == pos)//若目标位置为起始位置{SLPushFront(pphead, x);//头插return;}while (prev->next != pos)//找到pos节点的上一个节点地址{prev = prev->next;}SLTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->next = pos;
}

参数为头结点指针pphead，插入位置指针pos和插入元素x

老样子，先进行链表判断是否为空的操作

由于任意位置前插会出现两种情况：目标位置为起始位置、目标位置不为起始位置

对于这两种情况有不同的操作方法

起始位置：

直接进行头插即可

非起始位置：

首先要找到目标位置的上一个结点的地址，定义一个结构体指针prev来接收头结点的地址

通过while循环来自增，当prev的next指向的地址为pos的地址时

停止循环，此时prev指向的结点即为pos的上一个位置的结点

用结构体指针newnode接收开辟空间返回的新结点的地址

随后令prev->next = newnode;
           newnode->next = pos;

即完成任意位置前插的操作

注意：此种方法需要结合查的函数使用

---

删

删也分为三种方式：头删、尾删与任意位置删

头删（第一种）：

//头删
void SLPopFront(SLTNode** pphead)
{assert(pphead);if (*pphead == NULL){printf("链表内无结点！");}SLTNode* head = *pphead;if (head != NULL){if (head->next == NULL)//只有一个结点{free(head);*pphead = NULL;return;}*pphead = head->next;//有多个结点free(head);}
}

由于是删除操作，需要进行链表是否为空的判断，以免出现越界访问的问题

使用结构体指针head访问*pphead达到二级指针更改结点的目的

若只有一个结点，直接释放，并令*pphead指向空（NULL）并返回

若有多个结点，则令*pphead指向head->next的地址

释放head

对于头删，还存在另一种方法

头删（第二种）：

//头删
void SLPopFront(SLTNode** pphead)
{assert(pphead);if (*pphead == NULL){printf("链表内无结点！");}SLTNode* head = *pphead;//令结构体指针head指向起始位置if ((*pphead) != NULL){*pphead = (*pphead)->next;free(head);//释放head}
}

令起始位置指针指向next指向的位置
若只有一个元素，则(*pphead)->next为NULL,令*pphead为NULL，相同效果（妙哉）

---

尾删（第一种）：

//尾删（双指针法）
void SLPopBack(SLTNode** pphead)
{if (*pphead == NULL)//判断链表是否为空{printf("链表内无结点！");}SLTNode* tail = *pphead;SLTNode* flag = NULL;//找倒数第二个结点//while (tail->next != NULL)//{//	flag = tail;//	tail = tail->next;//}while (tail->next)//指针整型可以直接做条件逻辑判断{flag = tail;tail = tail->next;}free(tail);if (flag != NULL){flag->next = NULL;}//此处加上判断是为了防止报警告
}

令结构体指针tail指向*pphead的地址

结构体指针flag指向空

当tail->next指向非空时

令falg指向tail，tail指向tail->next（此循环步骤是为了找到倒数第二个结点）

找到以后释放tail

令flag->next指向NULL（此处加一个判断是为了避免在VS运行的时候出现警告）

但是这种方法可以更加简洁

尾删（第二种）

//尾删(直接找倒数第二个节点)
void SLPopBack(SLTNode** pphead)
{if (*pphead == NULL)//判断链表是否为空{printf("链表内无结点！");}SLTNode* tail = *pphead;while ((tail->next)->next)//两次解引用，找到tail指向的结点的next指向的结点的next{tail = tail->next;}free((tail->next));//更加巧妙tail->next = NULL;
}

相比于第一种用两个指针来操作，这种方法显得更加简洁

使用两次解引用，找到tail指向的结点的next指向的结点的next

显得更加巧妙

但是以上两种尾删的方法都是不完美的，当出现只有一个元素的情况是该如何处理呢？

尾删（第三种）：

//尾删(分两种情况)
void SLPopBack(SLTNode** pphead)
{assert(pphead);if (*pphead == NULL)//判断链表是否为空{printf("链表内无结点！");}SLTNode* tail = *pphead;if (tail != NULL){if (tail->next == NULL)//当前结点为唯一结点{free(tail);*pphead = NULL;return;}while ((tail->next)->next)//当前节点非唯一结点{tail = tail->next;}free((tail->next));tail->next = NULL;}//此处的判断是为了防止报警告
}

首先进行判断链表是否为空的操作

令结构体指针tail接收*pphead

进行判断操作：

若当前tail->next指向的为空，则代表链表只有tail这一个结点，直接释放tail，并将*pphead置空，返回

若tail并非当前唯一结点，则令tail指向tail->next，释放tail->next，并将tail->next置空，避免出现悬空指针

---

任意位置删除：

//任意位置删除
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);//判断目标位置是否为空if (pos == *pphead)//判断是否为头{SLPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

参数为头结点pphead、目标位置pos

首先判断pos位置是否为头结点

是则使用头删

否则定义一个结构体指针prev接收*pphead

循环令prev指向pos的上一个结点的位置

令prev->next指向pos->next的位置

释放pos，并将pos置空

---

查

//查
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur)//遍历链表查找{if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

使用遍历链表的方法查找

定义结构体指针cur接收phead

循环遍历链表，当cur不为NULL时

cur指向cur->next的位置

若其中cur->data为目标元素，返回cur，否则返回空

---

完整代码如下：

//SList.htypedef int SLTDataType;typedef struct SListNode
{SLTDataType data;//存放数据struct SListNode* next;//指向下一段的结构体指针
}SLTNode;void SLTPrint(SLTNode* phead);//打印
SLTNode* BuyLTNode();//开辟空间void SLPushFront(SLTNode** pphead, SLTDataType x);//头插
void SLPushBack(SLTNode** pphead, SLTDataType x);//尾插void SLPopFront(SLTNode** pphead);//头删
void SLPopBack(SLTNode** pphead);//尾删SLTNode* STFind(SLTNode* phead, SLTDataType x);//查找void SLInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);//任意位置前插入
void SLInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);//任意位置后插入void SLErase(SLTNode** pphead, SLTNode* pos);//任意位置删除

SList.c
#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"void SLTPrint(SLTNode* phead)//打印链表（遍历）
{SLTNode* cur = phead;//令cur等于当前指针（拷贝）while (cur != NULL){printf("%d -> ", cur->data);cur = cur->next;//令cur指向下一段的地址}printf("NULL\n");
}//开辟空间
SLTNode* BuyLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//开辟一个新的SLTNode结构体的空间，将其强制转换为SLTNode*类型，并将地址传给newnodeif (newnode == NULL){perror("malloc fail");return NULL;}//判断是否开辟空间成功newnode->data = x;newnode->next = NULL;//对newnode进行初始化return newnode;
}//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//判断是否接收到plist的地址（pphead是头指针plist的地址）SLTNode* newnode = BuyLTNode(x);assert(newnode != NULL);//判断是否开辟成功newnode->next = *pphead;//令结点指针指向原先的结点（通过pphead的地址修改）*pphead = newnode;//令phead指针指向新结点（通过pphead的地址修改,其实是改变plist）
}/*
//尾插(错误写法1)
void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail = phead;while (tail != NULL){tail = tail->next;}SLTNode* newnode = BuyLTNode(x);assert(newnode != NULL);//判断是否开辟成功tail = newnode;
}//本质上tail并没有与链表连接起来（局部变量出了函数销毁）
*//*
//尾插（错误写法2）
void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail = phead;while (tail->next != NULL){tail = tail->next;}SLTNode* newnode = BuyLTNode(x);assert(newnode != NULL);tail->next = newnode;//假如链表没有任何元素时，phead为NULL，使用上面的方法将无法进行插入//需要分为两种情况：链表有元素，链表无元素进行讨论
}
*//*
//尾插（错误写法3）
void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = BuyLTNode(x);assert(newnode != NULL);//链表为空if (phead == NULL){phead = newnode;}//链表非空else{SLTNode* tail = phead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}//由于plist传参，phead无法改变plist（局部变量），所以需要使用地址传参来改变plist
}
*///尾插（正确写法）
void SLPushBack(SLTNode** pphead, SLTDataType x)//使用二级指针来接收plist的地址
{SLTNode* newnode = BuyLTNode(x);assert(newnode != NULL);//链表为空if (*pphead == NULL)//对pphead进行解引用来访问plist{*pphead = newnode;//将newnode的地址赋值给plist}//链表非空else{SLTNode* tail = *pphead;//用结构体指针tail来接收plist的地址(拷贝)while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}/*
//头删（方法1）
void SLPopFront(SLTNode** pphead)
{assert(pphead);if (*pphead == NULL){printf("链表内无结点！");}SLTNode* head = *pphead;if (head != NULL){if (head->next == NULL)//只有一个结点{free(head);*pphead = NULL;return;}*pphead = head->next;//有多个结点free(head);}
}
*///头删(方法2)
void SLPopFront(SLTNode** pphead)
{assert(pphead);if (*pphead == NULL){printf("链表内无结点！");}SLTNode* head = *pphead;//令结构体指针head指向起始位置if ((*pphead) != NULL){*pphead = (*pphead)->next;//令起始位置指针指向next指向的位置//若只有一个元素，则(*pphead)->next为NULL,令*pphead为NULL，相同效果free(head);//释放head}
}/*
//尾删(方法1，双指针)
void SLPopBack(SLTNode** pphead)
{if (*pphead == NULL)//判断链表是否为空{printf("链表内无结点！");}SLTNode* tail = *pphead;SLTNode* flag = NULL;//找倒数第二个结点//while (tail->next != NULL)//{//	flag = tail;//	tail = tail->next;//}while (tail->next)//指针整型可以直接做条件逻辑判断{flag = tail;tail = tail->next;}free(tail);if (flag != NULL){flag->next = NULL;}//此处加上判断是为了防止报警告
}
*//*
//尾删(方法2,直接找倒数第二个节点)
void SLPopBack(SLTNode** pphead)
{if (*pphead == NULL)//判断链表是否为空{printf("链表内无结点！");}SLTNode* tail = *pphead;while ((tail->next)->next)//两次解引用，找到tail指向的结点的next指向的结点的next{tail = tail->next;}free((tail->next));//更加巧妙tail->next = NULL;
}
*///以上两种尾删的方法都是不完美的，当出现只有一个元素的情况是该如何处理呢？//尾删(方法3，分两种情况)
void SLPopBack(SLTNode** pphead)
{assert(pphead);if (*pphead == NULL)//判断链表是否为空{printf("链表内无结点！");}SLTNode* tail = *pphead;if (tail != NULL){if (tail->next == NULL)//当前结点为唯一结点{free(tail);*pphead = NULL;return;}while ((tail->next)->next)//当前节点非唯一结点{tail = tail->next;}free((tail->next));tail->next = NULL;}//此处的判断是为了防止报警告
}//查
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur)//遍历链表查找{if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//任意位置前插入
void SLInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//判断目标位置是否为空SLTNode* prev = *pphead;if (*pphead == pos)//若目标位置为起始位置{SLPushFront(pphead, x);//头插return;}while (prev->next != pos)//找到pos节点的上一个节点地址{prev = prev->next;}SLTNode* newnode = BuyLTNode(x);prev->next = newnode;newnode->next = pos;
}//任意位置后插入
void SLInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);SLTNode* newnode = BuyLTNode(x);if (pos->next == NULL)//如果目标位置为最后一个节点{pos->next = newnode;newnode->next = NULL;return;}newnode->next = pos->next;pos->next = newnode;
}//任意位置删除
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);//判断目标位置是否为空if (pos == *pphead)//判断是否为头{SLPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

//test.c#define _CRT_SECURE_NO_WARNINGS 1#include "SList.h"void test1()
{SLTNode* pplist = NULL;SLPushFront(&pplist, 1);SLPushFront(&pplist, 2);SLPushFront(&pplist, 3);SLPushFront(&pplist, 4);SLTPrint(pplist);//ps：此处需要通过pphead的地址修改
}void test2()
{SLTNode* pplist = NULL;SLPushFront(&pplist, 1);SLPushFront(&pplist, 2);SLPushFront(&pplist, 3);SLPushFront(&pplist, 4);SLPushBack(&pplist, 5);SLPushBack(&pplist, 6);SLPushBack(&pplist, 7);SLPushBack(&pplist, 8);SLTPrint(pplist);
}void test3()
{SLTNode* plist = NULL;SLPushBack(&plist, 5);SLPushBack(&plist, 6);SLPushBack(&plist, 7);SLPushBack(&plist, 8);SLTPrint(plist);
}void test4()//测试尾插
{SLTNode* pplist = NULL;SLPushBack(&pplist, 5);SLPushBack(&pplist, 6);SLPushBack(&pplist, 7);SLPushBack(&pplist, 8);SLTPrint(pplist);
}void test5()//测试尾删
{SLTNode* pplist = NULL;SLPushBack(&pplist, 5);SLPushBack(&pplist, 6);SLPushBack(&pplist, 7);SLPushBack(&pplist, 8);SLPopBack(&pplist);SLPopBack(&pplist);SLPopBack(&pplist);SLTPrint(pplist);
}void test6()//测试尾删
{SLTNode* pplist = NULL;SLPushBack(&pplist, 5);SLPushBack(&pplist, 6);SLPushBack(&pplist, 7);SLPushBack(&pplist, 8);SLPopBack(&pplist);SLPopBack(&pplist);SLPopBack(&pplist);SLPopBack(&pplist);//SLPopBack(&pplist);SLTPrint(pplist);
}void test7()//测试头删
{SLTNode* pplist = NULL;SLPushBack(&pplist, 5);SLPushBack(&pplist, 6);SLPushBack(&pplist, 7);SLPushBack(&pplist, 8);SLPopFront(&pplist);SLPopFront(&pplist);SLPopFront(&pplist);//SLPopFront(&pplist);//SLPopFront(&pplist);SLTPrint(pplist);
}void test8()//测试查找
{SLTNode* pplist = NULL;SLPushBack(&pplist, 5);SLPushBack(&pplist, 6);SLPushBack(&pplist, 7);SLPushBack(&pplist, 8);SLTNode* pos = STFind(pplist, 10);assert(pos);//判断是否为空printf("%d %p", pos->data, pos->next);
}void test9()//测试任意位置前插入
{SLTNode* pplist = NULL;SLPushBack(&pplist, 5);SLPushBack(&pplist, 6);SLPushBack(&pplist, 7);SLPushBack(&pplist, 8);SLTNode* pos1 = STFind(pplist, 5);SLInsertBefore(&pplist, pos1, 66);//在5前插入SLTNode* pos2 = STFind(pplist, 7);SLInsertBefore(&pplist, pos2, 88);//在7前插入SLTPrint(pplist);
}void test10()//测试任意位置后插入
{SLTNode* pplist = NULL;SLPushBack(&pplist, 5);SLPushBack(&pplist, 6);SLPushBack(&pplist, 7);SLPushBack(&pplist, 8);SLTNode* pos1 = STFind(pplist, 5);SLInsertAfter(&pplist, pos1, 66);//在5后插入SLTNode* pos2 = STFind(pplist, 7);SLInsertAfter(&pplist, pos2, 88);//在7后插入SLTPrint(pplist);
}void test11()//测试任意删除
{SLTNode* pplist = NULL;SLPushBack(&pplist, 5);SLPushBack(&pplist, 6);SLPushBack(&pplist, 7);SLPushBack(&pplist, 8);SLTNode* pos1 = STFind(pplist, 5);SLErase(&pplist, pos1);SLTNode* pos2 = STFind(pplist, 7);SLErase(&pplist, pos2);SLTPrint(pplist);
}//记住你要改变的是什么东西
int main()
{//test1();//test2();//test3();//test4();//test5();//test6();//test7();//test8();//test9();//test10();test11();return 0;
}