文章目录
前言
路漫漫其修远兮，吾将上下而求索；
一、顺序表的缺陷
1、当空间不够的时候需要增容，增容是需要付出代价的；
增容的代价，因为增容是依靠库函数realloc 进行工作的，而realloc 的工作原理有两点：
- 一是，原地扩容，旧空间后面的空间足够（代价低）
- 二是，异地扩容，当旧空间后面的空间不够时，便会在堆上寻找一块足够大的空间，然后将旧空间中的数据拷贝放到新空间中，释放旧空间，并返回新空间的地址；（代价高）
2、顺序表要求数据从开始的位置连续存储；当我们在顺序表的头部或者中间位置插入或者删除数据的时候，需要挪动数据，在数组中一个一个地挪动数据，消耗是非常大的，故而其效率不高；
3、为了避免重复地扩容以打断操作系统地执行，所以在顺序表中扩容是以二倍地形式去扩的容，但是存在浪费空间的可能性，这也是一种消耗；
注：实际上还有一个内存池的存在；即该程序首先会向操作系统申请一块足够大地空间来动态开辟，这样少量空间地开辟并不会去频繁地打断操作系统的执行，这也是链表一个结点一个结点地动态开辟空间并不会打扰操作系统的原因
显然，利用顺序表来存放数据是非常不方便的，针对顺序表的这些缺陷，我们可以了解一下链表；
二、链表是如何设计的？
针对顺序表扩容以及数据插入删除存在的问题对应地设计出了链表，链表是由一个一个结点构成的，而一个个结点之中，存在着数值域与指针域；
当要存放一个数据地时候便开辟一块空间,此时便解决了空间的浪费问题；链表中的结点与结点之间依靠指针进行链接，像链条一样故而称之为链表；
三、链表的分类
链表有八种（下述三种特性任意组合）：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
1、其中，在单结构中，链表分为单向链表、双向链表；
- 单向链表：上一个结点存放了下一个结点的地址；
- 双向链表：前一个结点存了后一个结点的地址，后一个结点也存放了前一个结点的地址；
注：如若想在单链表中找倒数第k个结点，是非常麻烦的，因为单向链表只记录了数据与下一结点的地址，也就是说单链表中的结点不能找到自己的上一结点；但是对于双向链表来说，就完全不是事；并且在双向链表中，删除结点无需保存上一个结点的地址（相较于单链表）；
双向链表总体上优于单向链表，但是它也存在一个小缺点，会比单链表的每个结点多存一个指针变量；（实际上也没有特别大的负担）；
2、带头或者不带头
其中的“头”也就是常说的“哨兵位头节点”，哨兵位头节点并不会被用来存放有效数据.
其意义在于，当尾插、头插时会很方便，因为不用考虑链表是否为空这一情况，并且也无需传二级指针，因为此处靠哨兵位头节点中的next 去链接结点.
在操作链表的时候 plist 指向哨兵位头节点，并不会更改指针plist 中存放的数据，故而不用传其地址，也就避免了函数中形参采用二级指针来接收；
3、循环或者非循环
循环链表是一种特殊的带环链表，即该链表的尾结点中的next 指向头节点；
非循环链表：该链表中尾结点中的next 指向NULL
综上，八种链表包括：带头单向循环、带头单向不循环、不带头单向循环、不带头单向不循环、带头双向循环、带头双向不循环、不带头双向循环、不带头双向不循环。
实际中较为常用得两种链表：
不带头单向不循环链表以及带头双向循环链表
不带头单向不循环链表：结构简单，一般不会拿来单独存放数据。实际中会作为哈希桶、图的邻接表等（作为其他数据结构的子结构）;
带头双向循环链表：结构最复杂，一般会用来单独存放数据。在实际中使用的链表的数据结构基本上都是使用带头双向循环。即使这个结构很复杂，但是这个结构存在的优势非常多，（注：此结构可以看作是一个无死角结构，因为其中的两个指针prev 和next 分别记录了上一结点的地址与其下一结点的地址，删除任意位置的结点、在任意位置进行插入，它的应用场景都是一样的即无需分情况讨论链表的情况）。会使得实现这个结构的代码相较于不带头单向不循环链表简单很多；
四、链表的概念及其结构
1、链表的概念：
链表是一种物理结构上非连续、非顺序的结构，数据元素的逻辑结构时通过链表中的指针链接次序实现的.
链表的逻辑结构上呈现线性，但是其物理结构为非线性；
2、链表的结构
如下图所示：
从上图（其地址为假设的）中（以不带头单向不循环链表为例）我们可以得知
- 链式结构在逻辑结构上是线性、连续的，但是在物理上不是连续的；
- 结点需要malloc ，即结点的空间来自于堆区
- 从堆上申请的空间是按照一定给的策略进行分配的，即多次在堆上利用malloc 申请的空间可能是连续的也有可能不是连续的；
为什么链表的结点需要在堆上动态申请空间呢？为什么不利用栈上的空间？
- 链表中的结点是根据数据的多少而创建的，所以其中一个原因是因为链表的结点需要动态内存开辟的空间；其次是因为栈上的空间只有当你定义了一个空间才会有一个空间，对于链表的实现来说非常麻烦(每次想要创建一个结点便要去定义一个变量)；因动态开辟的内存空间是来自堆区，故而链表结点的空间来自于堆区；
如何将数据存储到链表中？
- 一个链表的结点会包括数值域与指针域，数值域用来存放数据，指针域用来存放下一节点的指针；利用结构体将这两个封装在一起于是便成为了链表中的结点；其结构体类型声明如下：
注：在链表中，还会利用一个指针变量(例如下面创建的变量 plist)指向其第一个结点；链表有个缺点，不能像顺序表一样访问任意位置上的数据；链表利用其链接的特点可以找到该结点的下一结点……
五、不带头单向不循环链表的实现
主要包括有以下四个步骤：
- 定义不带头单向不循环链表结点的类型
- 初始化单链表
- 功能接口函数的实现(增删查改打印)
- 一些细节的接口函数(销毁动态开辟的空间)
(一)、SList.h 的实现
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//链表中结点类型的声明
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//初始化
void SListInit(SLTNode** pphead);
//头插
void SLTNodePushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SLTNodePushBack(SLTNode** pphead, SLTDataType x);
//头删
void SLTNodePopFront(SLTNode** pphead);
//尾删
void SLTNodePopBack(SLTNode** pphead);
//向指定位置pos 前插入数据
void SLTNodeInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//向指定位置pos 后插入数据
void SLTNodeInsertAfter(SLTNode* pphead, SLTNode* pos, SLTDataType x);
//删除指定位置pos 上的数据
void SLTNodeErase(SLTNode** pphead, SLTNode* pos);
//删除指定位置pos 后的数据
void SLTNodeEraseAfter(SLTNode* ppehad, SLTNode* pos);
//查找结点
SLTNode* SLTNodeFind(SLTNode* pphead, SLTDataType x);
//打印
void SLTNodePrint(SLTNode* pphead);
//销毁
void SLTNodeDestroy(SLTNode** pphead);注：因为此处的链表为不带头单向不循环，依靠于一个指针变量plist 指向此链表，只要是这个接口和函数的实现会改变plist ，传参plist 的时候就要采用传址调用；
而不会改变plist 的接口函数既可以采用传址调用，又可以采用传值调用，本文中采取的是传值调用，例如函数：SLTNodeInsertAfter、SLTNodeEraseAfter、SLTNodeFind、SLTNodePrint.
(二)、SList.c 的实现
1、初始化
//初始化
void SListInit(SLTNode** pphead)
{
assert(pphead);//避免传参错误
(*pphead)->data = 0;
(*pphead)->next = NULL;
}注：assert(pphead) 的目的是为了避免传参的错误，因为传一个指针变量的地址形参pphead 并不会为空；相反，倘若采用传值调用，pphead 便为NULL（因为传参plist 时将plist 初始化为NULL）；
2、创建结点
}
//创建结点
SLTNode* BuySLTNode(SLTDataType x)
{
//利用malloc
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("BuySLTNode malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}注：此处就是利用malloc 对链表的结点进行动态开辟，当然也可以利用calloc、realloc(当其第一个参数为NULL的时候，其作用效果与malloc 差不多)；
并且一般malloc 均会成功（只要开辟的空间没有特别特别大），栈小，只有8M ,而1MB = 1024 KB = 1024*1024 Byte;
3、头插
//头插
void SLTNodePushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//创建结点
SLTNode* newnode = BuySLTNode(x);
//处理链接关系
newnode->next = *pphead;
*pphead = newnode;
}注：在链表中想要存放一个数据便会开辟一个空间；
处理结点之间的链接关系时：
考虑一下链表中的结点个数会不会对头插产生影响
- 表中有结点，让newnode 中的next 指向*pphead 指向的结点，然后再让*pphead 指向newnode；当链表中没有结点，即直接让让*pphead 指向newnode
- 由于空链表即*pphead为NULL；这两种情况均可以使用同一操作实现
4、尾插
//尾插
void SLTNodePushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//创建结点
SLTNode* newnode = BuySLTNode(x);
if (*pphead == NULL)//空链表
{
*pphead = newnode;
}
else//非空链表
{
//寻找尾结点
SLTNode* tail = *pphead;
while (tail->next)//到尾结点便停止
{
tail = tail->next;
}
tail->next = newnode;
}
}注：考虑一下链表中的结点个数会不会对尾插产生影响
- 当链表中有结点即不为空时，尾插->找到尾结点，让尾结点中的next 指向newnode;
- 如果链表中没有结点，相当于头插，此时也无需找尾结点
此处的循环条件有两种写法，
- 一是上述代码中的形式：tail->next
- 二是：tail->next != NULL
这两种的写法的效果都一样，均是当tail 指向尾结点时便停止；但是
这两种写法表达的语法意义不同，方式一中的 tail->next 是一个指针被隐式类型转换成了一个逻辑条件判断的值，即0为假，非0为真，当tail 为尾结点的时候，tail->next 便为NULL ,NULL的ASCII 码值为0，0为假；
方式二中 tail->next != NULL ; 为一个比较表达式，比较表达式的返回值均为一个逻辑值；
4、头删
//头删
void SLTNodePopFront(SLTNode** pphead)
{
//删除的前提是有数据可以删除
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
注：考虑一下链表中的结点个数会不会对头删产生影响
- 当链表中有两个结点及其以上的时候，利用变量next 保存头结点下一结点的地址，然后释放头节点空间，最后让*pphead 指向next 中所保存的结点
- 当链表中只有一个结点的时候，直接释放此结点，让后*pphead=NULL;
这两种情况均可以使用同一操作实现
5、尾删
//尾删
void SLTNodePopBack(SLTNode** pphead)
{
//删除的前提是有数据可以删除
assert(pphead && *pphead);
if ((*pphead)->next == NULL)//链表中只有一个结点
{
free(*pphead);
*pphead = NULL;
}
else//链表中有两个及其以上的结点
{
SLTNode* prevTail = NULL, * tail = *pphead;
while (tail->next)
{
prevTail = tail;//记录尾结点的前一个结点的地址
tail = tail->next;
}
free(tail);
prevTail->next = NULL;
}
}
注：考虑一下链表中的结点个数会不会对尾删产生影响
- 当链表中有两个及其以上的结点个数时，需要找到尾结点以及尾结点的前一个结点，释放尾结点空间，让尾结点的前一个结点中的next 置空
- 当链表中只有一个结点的时候，此时无需找尾结点，相当于头删，将此结点的空间释放，然后将*pphead 置空
另外，当单链表中的结点个数大于等于2 的时候，找尾结点的前一个结点有两种方式来找：
方法一(上述代码中的方法)：创建一个变量prevTail 在找尾的过程中，记录指针tail 的当前结点，然后再调整；当tail 指向尾结点的时候prevTail 便指向尾结点的前一个结点，代码如下：
SLTNode* prevTail = NULL, * tail = *pphead;
while (tail->next)
{
prevTail = tail;//记录尾结点的前一个结点的地址
tail = tail->next;
}方式二：尾结点的前一个结点，也就是说此节点的next 的next 为NULL,代码如下：
SLTNode* prevTail = *pphead;
while (prevTail->next->next)
{
prevTail = prevTail->next;
}6、指定pos结点前插入
//向指定位置pos 前插入数据,pos 为数据
void SLTNodeInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);//避免传参错误
//确保pos 合法，即在链表中有这个结点
assert(pos);
//创建结点
SLTNode* newnode = BuySLTNode(x);
if (pos==*pphead)//当pos 指向第一个结点的时候--头插
{
newnode->next = (*pphead)->next;
*pphead = newnode;
}
else
{
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = newnode;
newnode->next = pos;
}
}注：分情况讨论
- 当pos 指向的是链表中的第一个结点的时候，相当于头插；
- 当pos 指向其他结点的时候需要保存pos 的前一个结点的地址，让pos 的前一个结点 中的next 指向newnode, 让nownode 中的next 指向pos
7、指定pos结点后一个结点插入
//向指定位置pos 后插入数据
void SLTNodeInsertAfter( SLTNode* pos, SLTDataType x)
{
//创建结点
SLTNode* newnode = BuySLTNode(x);
SLTNode* next = pos->next;
pos->next = newnode;
newnode->next = next;
}此处并不会改变plist 所以不用传plist 的参数 ，并且新结点只需要往pos 后面插入变可以了；相当于带头单向不循环链表的头插；
注：分情况讨论--细细想来无需分情况，没有头插的情况，因为往结点后插入的
8、删除指定pos结点的数据
//删除指定位置pos 上的数据
void SLTNodeErase(SLTNode** pphead, SLTNode* pos)
{
//删除额前提是有数据可删
assert(pphead && *pphead);
if (pos == *pphead)//指向第一个结点
{
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
else
{
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);
}
}注：分情况：
- 当pos 指向链表中结点不是链表中的第一个结点的时候，需要保存pos 前一个结点的地址,然后posprev->next = pos->next ,free(pos)
- 当pos 指向第一个结点的时候，就是头删
9、删除指定pos结点后一个结点的数据
//删除指定位置pos 后的数据
void SLTNodeEraseAfter(SLTNode* pphead, SLTNode* pos)
{
assert(pphead );
assert(pphead->next);//不能只有一个结点
SLTNode* next = pos->next;
SLTNode* nextNext = next->next;
free(next);
pos->next = nextNext;
}注：
- 避免只有一个结点的情况
- 删除pos 以后的数据，不用考虑其他情况，均为尾删
10、查找
//查找结点
SLTNode* SLTNodeFind(SLTNode* pphead, SLTDataType x)
{
assert(pphead );
SLTNode* cur = pphead;
while (cur)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
11、打印
//打印
void SLTNodePrint(SLTNode* pphead)
{
assert(pphead);
SLTNode* cur = pphead;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}12、销毁
//销毁
void SLTNodeDestroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* cur = *pphead, * next = NULL;
while (cur)
{
next = cur->next;
free(cur);
cur = next;
}
}六、带头双向循环链表的实现
带头双向循环链表的结点的声明
如下：
(一)、LIst.h 的实现
代码如下：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//带头双向循环链表结点类型的声明
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
//初始化
void ListInit_1(LTNode** pphead);
LTNode* ListInit_2();
//头插
void ListPushFront(LTNode* phead, LTDataType x);
//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//头删
void ListPopFront(LTNode* phead);
//尾删
void ListPopBack(LTNode* phead);
//指定pos 位置插入(向前)
void ListInsrtt(LTNode* phead, LTNode* pos, LTDataType x);
//指定pos 位置删除(pos 指向的当前结点)
void ListPopErase(LTNode* phead, LTNode* pos);
//查找
LTNode* ListFind(LTNode* phead, LTDataType x);
//打印
void ListPrintf(LTNode* phead);
//销毁
void ListDestroy(LTNode** ppehad);在带头双向循环之中，指针plist 首先会指向哨兵位头节点，哨兵位头节点不会用来存放数据，在对此链表初始化时便创建哨兵位头节点；
初始化时，因为会改变plist 的指向，故而在初始化中采用以返回值的形式带回哨兵位头节点的地址或者采用传址调用；同理，在销毁此链表的时候，会释放所有动态开辟的空间，包括哨兵位头节点与链表中用来存放数据的结点，并将plist 置空，故而也会采用传址调用，当然，销毁时不采用传址调用也行，只不过需要使用者手动将plist 置空；
在其他接口函数中，并不会改变plist 的指向，plist 一直指向哨兵位头节点；结点之间的链接关系由哨兵位头节点中的prev 与 next 来处理，故而在其他接口函数(不包含初始化和销毁)中plist 采用传值调用；
(二)、List.c 的实现
1、初始化
返回值的形式：
//初始化--返回值的形式
LTNode* ListInit()
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if (phead == NULL)
{
perror("ListInit malloc");
exit(-1);
}
phead->prev = phead;
phead->next = phead;
return phead;
}传参的形式：
//初始化-- 创建哨兵位头节点--采用传址调用 或者返回值额形式
void ListInit(LTNode** pphead)
{
//创建哨兵位头节点--动态开辟
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if (phead == NULL)
{
perror("ListInit malloc");
exit(-1);
}
phead->prev = phead;
phead->next = phead;
*pphead = phead;
初始化：哨兵位头节点空间的开辟-- 将其prev 与next 置NULL
2、创建结点
代码如下：
// 创建结点
LTNode* BuyListNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("BuyListNode malloc");
exit(-1);
}
newnode->data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
创建结点：空间的创建+判空-->放值+初始化指针(置空) --> 返回新空间的地址
3、头插
代码如下：
//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
//创建新结点
LTNode* newnode = BuyListNode(x);
//链接关系处理
LTNode* next = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = next;
next->prev = newnode;
}处理好哨兵位头节点与newnode 之间的链接关系:
先将原本的头节点(哨兵位头节点的下一个结点)的地址保存在next 中
让 哨兵位头节点的next 指向 newnode，再让newnode中的prev 指向phead(哨兵位头节点); 最后让newnode中的next 指向next ,next 中prev 指向newnode;如下图所示：
4、尾插
代码如下：
//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
//创建新结点
LTNode* newnode = BuyListNode(x);
LTNode* tail = phead->prev;//尾结点
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
哨兵位头节点中的prev 便是指向的是链表中的尾结点，由于哨兵位头节点的存在，尾插便不用分情况讨论，如下图所示：
5、头删
代码如下：
//头删
void ListPopFront(LTNode* phead)
{
assert(phead);
//删除额前提是有数据可删，这里判断有没有结点的条件是，看哨兵位头节点指不指向自己
assert(phead->next != phead);
//头结点、头节点的下一结点
LTNode* next = phead->next;
LTNode* nextNext = next->next;
//释放、处理链接关系
phead->next = nextNext;
nextNext->prev = phead;
free(next);
}6、尾删
同理，不再作图；
代码如下：
//尾删
void ListPopBack(LTNode* phead)
{
assert(phead);
//删除额前提是有数据可删，这里判断有没有结点的条件是，看哨兵位头节点指不指向自己
assert(phead->next != phead);
//尾结点、尾结点的前一个结点
LTNode* tail = phead->prev;
LTNode* prev = tail->prev;
//释放、处理链接关系
free(tail);
prev->next = phead;
phead->prev = prev;
}7、指定pos 结点前插入数据
同理，不再作图；
代码如下：
//指定pos 位置插入(向前)
void ListInsrtt(LTNode* phead, LTNode* pos, LTDataType x)
{
assert(phead);
assert(pos);
//创建新结点
LTNode* newnode = BuyListNode(x);
//pos前后结点
LTNode* prev = pos->prev;
LTNode* next = pos;
//处理链接关系
prev->next = newnode;
newnode->prev = prev;
newnode->next = next;
next->prev = newnode;
}8、删除指定pos 结点中的数据
同理，不再作图；
代码如下：
//指定pos 位置删除(pos 指向的当前结点)
void ListPopErase(LTNode* phead, LTNode* pos)
{
assert(phead);
assert(pos);
//删除额前提是有数据可删，这里判断有没有结点的条件是，看哨兵位头节点指不指向自己
assert(phead->next != phead);
//pos 的前后结点
LTNode* prev = pos->prev;
LTNode* next = pos->next;
//释放、处理链接关系
free(pos);
prev->next = next;
next->prev = prev;
}
9、查找
代码如下：
//查找
LTNode* ListFind(LTNode* phead,LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
遍历带头双向循环链表：从哨兵位头节点指向的结点开始到哨兵位头节点结束；
10、 打印
代码如下：
//打印
void ListPrintf(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
遍历带头双向循环链表：从哨兵位头节点指向的结点开始到哨兵位头节点结束；
11、销毁
代码如下：
//销毁
void ListDestroy(LTNode** pphead)
{
assert(*pphead);
//释放所有动态开辟的空间--结点，哨兵位头节点
LTNode* cur = (*pphead)->next;
while (cur!=*pphead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
//释放哨兵位头节点
free(*pphead);
*pphead = NULL;
cur = NULL;
}释放所有动态开辟的空间(哨兵位头节点和链表中用来存放数据的节点) + 置空plist
总结
1、链表有八种（下述三种特性任意组合）：
- 单向或者双向
- 带头或者不带头
- 循环或者非循环
2、带头双向循环链表结构相较于单链表更复杂，但是实现的代码会更简单，效率更高；虽然其结点会多存放一个指针，但是总体来说，带头双向循环链表比单链表更优；
标签：pphead,结点,单链,--,pos,next,链表,phead,双链 From： https://blog.csdn.net/Distinguished_z/article/details/142674594