目录
线性表
线性表（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;
}
else
return -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;
}
else
return -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类型重命名为SLTDataType
typedef struct SListNode
{
SLTDataType data; //存放数据
struct SListNode* next; //指向下一段的结构体指针
}SLTNode; //将struct SListNode重命名为SLTNode对于单链表，我们也需要实现不同的功能：增，删，查
但在实现这些功能之前，我们需要为链表写一个开辟空间的函数方便调用
//开辟空间
SLTNode* BuyLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//开辟一个新的SLTNode结构体的空间，将其强制转换为SLTNode*类型，并将地址传给newnode
if (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.h
typedef 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*类型，并将地址传给newnode
if (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;
}
带哨兵位的单链表
首先看看普通的单链表与带哨兵位的单链表的区别
可以看到相比于普通的的单链表
带哨兵位的单链表只不过多了一个结点
但是对于哨兵位而言，他的黄色区域（也就是存放数据的区域）是不存放任何东西的
他仅仅是存放下一个结点的地址
那么它存在的意义是什么呢？
设置哨兵位是程序设计中常用的技巧之一，常用在线性表的处理过程中，比如查找和移动数据操作
哨兵位通常起到两个作用：
- 作为一个临时存储空间使用，
- 减少不必要的越界判断，简化算法代码复杂度
下面用一道力扣题目来举例
对这道题而言，我们的代码是这样子的
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode*list3=(struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode*p3=list3;
struct ListNode*head=list3;
while(list1!=NULL&&list2!=NULL)
{
if(list1->val<list2->val)
{
p3->next=list1;
list1=list1->next;
p3=p3->next;
p3->next=NULL;
}
else
{
p3->next=list2;
list2=list2->next;
p3=p3->next;
p3->next=NULL;
}
}
if(list1==NULL)
{
p3->next=list2;
}
else
{
p3->next=list1;
}
return head->next;
}我们可以看到，假如不使用带哨兵位的单链表来写这一道题
我们就需要通过大量的if判断语句进行插入赋值链接操作
对第一次插入与第二次插入进行区分（所处位置不同）
这样会使代码变得复杂
但是！
假如使用带哨兵位的单链表
由于哨兵位为第一位，就不需要判断是否为空
直接在tail后进行尾插操作即可
不需要对其进行判断
代码如下
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNOde* list2)
{
if(list1 == NULL)
return list2;
if(list2 == NULL)
return list1;
struct ListNode* head = NULL, *tail = NULL;
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位
while(list1 && list2)
{
if(list1->val < list2->val)
{
head = tail = list1;
tail->next = list1;
list1 = list1->next;
}
else
{
tail->next = list2;
tail = tail->next;
list2 = list2->next;
}
if(list1)
tail->next = list1;
if(list2)
tail->next = list2;
struct ListNode* del = head;
head = head->next;
free(del);
return head;
}可能有些人会觉得可以使用哨兵位来存放链表长度
但实际上这样做不好
原因是在定义声明结构体时，若要存放结构体长度，就需要使用int类型
可事实上一般不一定定义的都是int类型，有可能是char类型，也有可能是double类型
所以对于哨兵位而言，一般不存放其他数据
循环单链表（环形单链表）
字面意思，循环单链表就是首尾相接的链表
画图来理解
可以看到链表尾结点指向的首结点，形成一个闭环
但实际上尾结点不一定要指向首结点
他可以指向链表内任意一个位置
只要形成一个闭环即可
循环单链表有一个很严重的缺陷
无法遍历链表
下面用一道力扣题目来加深对循环单链表的理解
我们要判断这个链表内是否有环，也就意味着我们要判断这个链表是否是循环链表
先看代码
struct ListNode
{
int val;
struct ListNode *next;
};
bool hasCycle(struct ListNode *head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while(fast && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast )
{
return true;
}
}
return false;
}我们可以通过快慢指针来进行判断
快指针fast一次走两步：fast = fast->next->next
慢指针slow一次走一步：slow = slow->next
由于fast速度是slow速度的2倍
所以当fast为NULL时，则代表链表无环
当fast等于slow时，则链表有环
QS：为什么fast会等于slow
AS：这里涉及到一个追击问题
假若在一个圆里，fast的速度是slow的速度的2倍，那么不管如何，fast在走一圈之后都一定会追上slow
带头双向循环链表
我们知道，单链表一般只能访问下一个结点，但是如果想要访问前一个结点，就需要用到循环链表来操作，所以衍生出了一种新的链表结构：双向链表
下面画一个图来理解：
如上图存在4个结点，每个结点内有三个元素
分别是：
指向上一个结点的指针
数据区
指向下一个结点的指针
对于这种结构的链表而言，他所用的单链表无法超越的优势：
访问上一个元素
下面用代码来实现
typedef int LTDataType;//int重命名
typedef struct ListNode//定义ListNode
{
struct ListNode* next;//指向下一个结点
struct ListNode* prev;//指向上一个结点
LTDataType data;//存储数据
}LTNode;//重命名为LTNode通过定义结构体，定义结构体指针next用于指向下一结点
定义结构体指针prev用于指向上一结点
定义data存储数据
值得一提的是：
当链表只有一个结点时，next指针指向自己，prev指针也指向自己
如下图所示：
下面具体讲解双向循环链表的几种用法
初始化，开辟空间，判空，打印
直接看代码
//初始化
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
由于这是
带哨兵位的双向循环链表
，这里开辟的第一个空间的data数据区存放-1
//开辟空间
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*) malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}//判断是否开辟成功
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
为了降低代码的冗余程度，我们单独将开辟空间封装为一个函数方便使用
//判空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;//判断phead->next是否为空
}由于在删除操作时需要多次使用到判断空间的操作，我们这里也将其封装为一个函数方便使用
//打印
void LTPrint(LTNode* phead)
{
assert(phead);
printf("Guard");
LTNode* flag = phead->next;
while (flag != phead)
{
printf(" <==> %d", flag->data);
flag = flag->next;
}
}为了方便调试时使用，单独写一个打印函数
头插
话不多说直接上代码
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}其实与上面的单链表大差不大，只不过不需要使用二级指针来操作，多了prev指针大大方便了我们去寻找其他的结点
但是需要注意的重点是：
由于当链表只有一个结点时，next与prev都是指向自身，所以不需要考虑多种情况去进行分类讨论，直接如图上所示直接操作即可
尾插
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
//链表不为空或为空都可使用
}同头插道理类似，此处我们可以直接开辟空间，随后更改指针指向完成尾插
头删
//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead)); //根据LTEmpty判断链表是否为空
LTNode* head = phead->next;
phead->next = head->next;
head->next->prev = phead;
free(phead);
}由于在删除时需要考虑到链表内是否有元素需要删除
我们可以直接调用上面实现封装的函数 LTEmpty（）来进行判空操作
随后直接删除头部结点，更改指针指向即可
尾删
//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));//根据LTEmpty判断链表是否为空
LTNode* tail = phead->prev;
tail->prev->next = phead;
phead->prev = tail->prev;
free(tail);
}同头删同理，这里就不做过多赘述
查找，任意位置前删除，删除任意位置
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
assert(!LTEmpty(phead)); //根据LTEmpty判断链表是否为空
LTNode* Find = phead->next;
while (Find != phead)
{
if (Find->data == x)
{
return Find;
}
Find = Find->next;
}
return NULL;
}该查找操作是为了方便后面两个任意位置的插入与删除使用
我们也将其单独封装成为一个函数
//任意位置前插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyLTNode(x);
pos->prev->next = newnode;
newnode->prev = pos->prev;
pos->prev = newnode;
newnode->next = pos;
}通过查找函数，我们可以很方便的找到目标结点，随后对其进行插入操作
//删除任意位置
void LTErase(LTNode* phead, LTNode* pos)
{
assert(pos);
assert(!LTEmpty(phead)); //根据LTEmpty判断链表是否为空
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
}同理，通过查找函数，我们可以很方便的找到目标结点，随后进行删除操作
值得一提的是：
前文所提到的头插尾插头删尾删
也可以通过任意位置前插入与删除任意位置来使用
如下：
LTInsert(phead, x);//用任意位置前插入实现尾插 LTInsert(phead->next, x);//用任意位置前插入实现头插 LTErase(phead->prev);//用删除任意位置实现尾删 LTErase(phead->next);//用删除任意位置实现头删
全部代码如下所示：
这是链表各个函数的实现定义
List.c
#include "List.h"
//初始化
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
//开辟空间
LTNode* BuyLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*) malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}//判断是否开辟成功
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
//判空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;//判断phead->next是否为空
}
//打印
void LTPrint(LTNode* phead)
{
assert(phead);
printf("Guard");
LTNode* flag = phead->next;
while (flag != phead)
{
printf(" <==> %d", flag->data);
flag = flag->next;
}
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = BuyLTNode(x);
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
//链表不为空或为空都可使用
//LTInsert(phead, x);//用任意位置前插入实现尾插
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyLTNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
//LTInsert(phead->next, x);//用任意位置前插入实现头插
}
//尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));//根据LTEmpty判断链表是否为空
LTNode* tail = phead->prev;
tail->prev->next = phead;
phead->prev = tail->prev;
free(tail);
//LTErase(phead->prev);//用删除任意位置实现尾删
}
//头删
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead)); //根据LTEmpty判断链表是否为空
LTNode* head = phead->next;
phead->next = head->next;
head->next->prev = phead;
//LTErase(phead->next);//用删除任意位置实现头删
}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
assert(!LTEmpty(phead)); //根据LTEmpty判断链表是否为空
LTNode* Find = phead->next;
while (Find != phead)
{
if (Find->data == x)
{
return Find;
}
Find = Find->next;
}
return NULL;
}
//任意位置前插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyLTNode(x);
pos->prev->next = newnode;
newnode->prev = pos->prev;
pos->prev = newnode;
newnode->next = pos;
}
//删除任意位置
void LTErase(LTNode* phead, LTNode* pos)
{
assert(pos);
assert(!LTEmpty(phead)); //根据LTEmpty判断链表是否为空
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
}
//释放
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* flag = phead->next;
while (flag != phead)
{
LTNode* save = flag->next;
free(flag);
flag = save;
}
free(phead);
}这是对链表的声明以及头文件的包含
List.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int LTDataType;//int重命名
typedef struct ListNode//定义ListNode
{
struct ListNode* next;//指向下一个结点
struct ListNode* prev;//指向上一个结点
LTDataType data;//存储数据
}LTNode;//重命名为LTNode
//当链表为空时，next指向自己，prev指向自己
LTNode* LTInit();//初始化
LTNode* BuyLTNode(LTDataType x);//开辟
bool LTEmpty(LTNode* phead);//判空
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);//查找(配合下面两种方法使用)
void LTInsert(LTNode* pos, LTDataType x);//任意位置前插入
void LTErase(LTNode* phead, LTNode* pos);//删除任意位置
void LTPrint(LTNode* phead);//打印
void LTDestroy(LTNode* phead);//释放这是测试链表各个功能的文件
test.c
#include "List.h"
void test1()//测试尾插
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTDestroy(plist);
}
void test2()//测试头插
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTDestroy(plist);
}
void test3()//测试尾删
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPopBack(plist);
LTPopBack(plist);
LTPrint(plist);
LTDestroy(plist);
}
void test4()//测试头删
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPopFront(plist);
LTPopFront(plist);
LTPrint(plist);
LTDestroy(plist);
}
void test5()//测试任意位置前插入
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTInsert(LTFind(plist, 3), 1);
LTInsert(LTFind(plist, 4), 5);
LTPrint(plist);
LTDestroy(plist);
}
void test6()//测试删除任意位置
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTErase(plist, LTFind(plist, 2));
LTErase(plist, LTFind(plist, 3));
LTPrint(plist);
LTDestroy(plist);
}
int main()
{
//test1();
//test2();
//test3();
//test4();
//test5();
test6();
return 0;
}