回顾：
承接上回，我们讲解数据结构中的顺序表，这种结构的表，缺点也是很明显，所以本期我们来学习链表，链表有些特性是顺序表，没有的哦
1.链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的
2.链表的分类
链表的结构非常多样，以下情况组合起来就有8种链表结构：
2.1单向或双向链表
2.2带头或不带头
2.3循环或非循环
2.4常用的结构
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
3.无头单向非循环链表的实现
3.1所需要用到的接口，vs2022环境下：
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLDatatype; typedef struct SListNode { SLDatatype data; struct SListNode* next; }SListNode; //打印 void SLPrint(SListNode* phead); //结点 SListNode* BuySListNode(SLDatatype x); //头插 void SLPushFront(SListNode** phead,SLDatatype x); //尾插 void SLPushBack(SListNode** phead, SLDatatype x); //头删 void SLPopFront(SListNode** phead); //尾删 void SLPopBack(SListNode** phead); //单链表查找 SListNode* SListFind(SListNode* phead, SLDatatype x); //在pos位置之后插入数据 void SListInsertAfter(SListNode** phead, SLDatatype x); //删除pos位置之后的数据 void SListEraseAfter(SListNode* phead); //链表销毁 void SListDestroy(SListNode* phead); //删除pos位置 void SListErase(SListNode** phead, SListNode* pos);
3.2链表结构的定义
对类型进行重命名，这样以后可以根据自己的实际需求改变数据的类型。
创建一个结构体类型，存储元素数据，然后需要一个同样类型的结构体指针，这个指针可以指向同类型的数据，这样就可以通过指针访问下一个结点的元素
typedef int SLDatatype; typedef struct SListNode { SLDatatype data; struct SListNode* next; }SListNode;
3.3结点
在堆区上开辟一个新的结点，给定结点的值，然后初始化，节点是链表较为重要的一部分，没有结点，链表就无法链接
SListNode* BuySListNode(SLDatatype x) { SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); if (newnode == NULL) { perror("BuySListNode"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
3.4打印
打印链表中的元素数据
void SLPrint(SListNode* phead) { SListNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
3.5头插
在链表前插入新结点，然后链接到原链表
void SLPushFront(SListNode** phead,SLDatatype x) { SListNode* newnode = BuySListNode(x); newnode->next = *phead; *phead = newnode; }
3.6尾插
在链表末尾插入新结点，使原链表链接到新结点
void SLPushBack(SListNode** phead, SLDatatype x) { SListNode* newnode = BuySListNode(x); if (*phead == NULL) { *phead = newnode; } else { SListNode* tail = *phead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
3.7查找
给定要查找的链表中的元素，找到并返回当前元素的地址
SListNode* SListFind(SListNode* phead, SLDatatype x) { assert(phead); SListNode* pos = phead; while (pos) { if (pos->data == x) return pos; pos = pos->next; } return NULL; }
3.8pos后一位插入
在指定位置的后一位插入元素数据
void SListInsertAfter(SListNode** phead, SLDatatype x) { assert(phead); assert(*phead); SListNode* newnode = BuySListNode(x); newnode->next = (*phead)->next; (*phead)->next = newnode; }
3.9删除pos后一位
删除指定链表中的地址的后一位数据
void SListEraseAfter(SListNode* phead) { assert(phead); assert((phead)->next); SListNode* cur = phead->next; phead->next = cur->next; free(cur); cur = NULL; }
3.10删除pos位置
还给定链表的某个结点位置，然后删除，这里的pos可以置空也可以不置空，因为这是临时变量，出了函数就销毁了，好的习惯是可以置空的
void SListErase(SListNode** phead, SListNode* pos) { assert(pos); if (pos == *phead) { SLPopFront(phead); } else { SListNode* cur = *phead; while(cur->next != pos) { cur = cur->next; } cur->next = pos->next; free(pos); //pos = NULL; } }
3.11释放链表
当链表不再使用后，我们要对其进行销毁，释放空间内存
void SListDestroy(SListNode* phead) { SListNode* current = phead; SListNode* next = NULL; while (current != NULL) { next = current->next; free(current); current = next; } }
这就是本期的全部内容了，感谢各位看官的光临！
