线性表之链表
- 导航
- 1、链表的概念和结构
- 2、链表的分类
- 3、链表的实现
- 3.1 结构体定义
- 3.2 接口函数定义
- 3.3 接口函数的实现
- 4、结语
导航
1、链表的概念和结构
概念： 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素
。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素的存储映像，称为节点，它包括两个域，其中存储数据单元信息的域被称为数据域，存储直接后继存储位置的域被称为指针域，指针域中的存储信息乘坐指针或链。
结构：
从上图可以看出，链式存储结构在逻辑上是连续的，但是在物理上不一定连续；
现实中的结点一般都是从堆上申请出来的；
从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续（一般都不是连续，这里大家可以用vscode跑一边看看内存监视，这里就不演示了）。
2、链表的分类
实际中链表的结构非常多样，主要总结为以下6种特征组成的8种链表结构：
①单向或双向
②带头或不带头
③循环或者非循环
常用的两种组合结构：
无头单向非循环链表：
结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
带头双向循环链表：
结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
3、链表的实现
这篇文章先实现第一种常用的链表——无头单向非循环链表
因为学校的教材可能都是带头的，那样更容易理解，但在现实运用中，带头的并不常用，没有学过不带头的UU也不用担心，其实实现起来是类似的，而且学会不带头的，再去看带头的就简单很多了。特点：随机存储，顺序存取
3.1 结构体定义
首先我们先看看无头单向非循环链表的结构体如何实现
代码如下：
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;//存放数据struct SListNode* next;//指向下一结点的指针
}SLTNode;
3.2 接口函数定义
代码如下：
SLTNode* BuyListNode(SLTDateType x);//动态申请结点
void SListPushBack(SLTNode** pphead, SLTDateType x);//尾插
void SListPushFront(SLTNode** pphead, SLTDateType x);//头插
void SListPopBack(SLTNode** pphead);//尾删
void SListPopFront(SLTNode** pphead);//头删
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);//插入（之后）
void SListErase(SLTNode** pphead, SLTNode* pos);//删除（之后）
void SListInsertAfter(SLTNode* pos, SLTDateType x);//插入（之前）
void SListEraseAfter(SLTNode* pos);//删除（之前）
SLTNode* SListFind(SLTNode* phead, SLTDateType x);//查找
void SListPrint(SLTNode* phead);//打印
void SListDestory(SLTNode** pphead);//销毁链表
3.3 接口函数的实现
这里提一句，接口函数的命名并不是固定的，但是要有由头，不能瞎取
一个优秀程序员要有良好的代码素养
毕竟在公司里，代码不仅是写给你自己看的
动态申请结点函数（BuyListNode）
你可以理解为新增结点初始化操作
代码如下：
SLTNode* BuyListNode(SLTDateType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}
这里首先使用了一个malloc函数实现动态内存分配，令第一个元素为x，并让指向下一个节点为NULL，这里我们可以看到，和之前的顺序表对比，我们会发现，在内存分配上，链表所分配空间更合理，不会造成大量浪费内存的现象，这是链表的一个优点。
尾部插入函数（SListPushBack）
显而易见，就是在链表尾部插入新元素
代码如下：
void SListPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
在上面的代码中我们可以看到，在链表中插入元素，需要申请新的结点空间，这里我们考虑两种情况：
一种是链表为空的情况，那我们直接进行赋值插入即可；
第二种是链表中有元素的情况，我们借用另外一段临时链表空间tail进行插入（注意，这里要使用*进行赋值，否则形参无法改变实参的结果，不理解的小伙伴可以再去复习一下C语言中指针的知识）
头部插入函数（SListPushFront）
代码如下：
void SListPushFront(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}
头插的实现我们只需要借助临时链表newnode存储要插入的值x，再将x指向要插入的链表pphead，再将临时链表newnode赋回给pphead，即可完成头插操作
尾部删除函数（SListPopBack）
代码如下：
void SListPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead != NULL);//断言链表为空if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}
在这里，我们要考虑到链表是否已经为空的情况，所以在这里加上第二句断言，避免造成越界访问。
然后我们再分两种情况处理：
第一种是链表已经没元素了，next指向的就是空，那么就直接释放内存，再置空；
第二种是链表还有元素的情况，在这里我们复制原链表利用while循环进行遍历，再释放掉尾元素空间，令尾元素前一个元素指向空。
头部删除函数（SListPopBack）
代码如下：
void SListPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead != NULL);//断言链表为空SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
在这里同样考虑链表为空的情况，加一个断言，避免越界访问，头删需要先把指针指向第二个元素再进行释放内存，二者顺序不可颠倒。
插入函数——之后（SListInsertAfter）
在单链表中，一般的插入都是再某元素之后，这里涉及到单链表的一个缺点，他不能像顺序表一样通过下标直接访问某个元素，单链表查找元素都是通过遍历查找的，因为在内存中可能是不连续的，单链表仅仅是通过指针来访问下一个结点，而无法访问上一个结点，所以这里正常的插入是在某元素之后，在某个元素之前插入也可以实现，不过更复杂，对于初学者来说，这个更简单也更适合。
代码如下：
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos);SLTNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;
}
这里的第二个断言是防止找不到上一个元素pos，导致无法插入，这个在pos元素后插入是先把要插入元素x封装成一个节点指向pos的初始下一元素，再将pos指向要插入的元素结点，完成插入操作。
要注意的是，顺序不可以颠倒哦，如果先将pos指向x，那么x将无法找到下一个元素结点
删除函数——之后1（SListErase）
在这里删除函数不管是某函数之前还是之后相对都没那么复杂了，我们先看删除某个元素之后的写法。
代码如下：
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos){SListPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}
这种写法首先我们分两种情况：
第一种是只剩一个元素结点，这个我们直接调用头删就可以了；
第二种是还有多个元素结点，使用while循环遍历链表找到pos元素，将pos上一个元素结点指向pos元素的下一个元素结点，再将pos的内存释放。
插入函数——之前（SListInsertBefore）
代码如下：
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead);assert(pos);SLTNode* newnode = BuyListNode(x);if (*pphead == pos){newnode->next = *pphead;*pphead = newnode;}else{SLTNode* posPrev = *pphead;while (posPrev->next != pos){posPrev = posPrev->next;}posPrev->next = newnode;newnode->next = pos;}
}
和前面一样分两种情况讨论：
第一种情况是只有一个元素，那么我们就直接将x元素结点指向原链表pphead，再重新赋值即可；
第二种是链表中有多个元素，使用while循环遍历链表找到pos上一元素结点，使其指向要插入的元素结点x，再将x指向pos元素结点，完成插入操作。
删除函数——之后2（SListEraseAfter）
代码如下：
void SListEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* next = pos->next;pos->next = next->next;free(next);
}
这个写法看起来比前面的删除更为简洁，你觉得哪个更好，更符合实际应用，就用哪个；
查找函数（SListFind）
代码如下：
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}else{cur = cur->next;}}return NULL;
}
简单来说就是利用循环来进行遍历查找，没啥好讲的。
打印函数（SListPrint）
代码如下：
void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
同样的通过遍历链表来进行逐个打印元素，用->连接更为直观。
销毁链表函数（SListDestory）
代码如下：
void SListDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}
这里也是通过遍历链表逐个元素节点释放内存空间。
4、结语
这就是无头单向非循环链表的接口函数实现，对比一下我们会发现单链表和顺序表各自的优缺点，他们两个都不完美，因此在实际应用中，这两种线性表都是有需求的，我们都需要掌握好，才能打好基础，下一章节我们来讲讲带头双向循环链表的实现。
制作不易，如有不正之处敬请指出，感谢大家的来访，UU们的观看是我坚持下去的动力，在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！
