[数据结构]----链表(无头单向非循环链表的实现)
目录
1. 顺序表的缺陷
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。
2. 链表
2.1 链表的概念
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
2.2. 链表的结构
链表结构是有一个Data存储值/数据，有一个结构体指针存放下一个结点的地址
2.3 链表的分类
1.单向链表或双向链表
2.带头（哨兵位）链表或不带头（哨兵位）链表
3.循环链表或不循环链表
每种类型都有两种不同的结构，所以一共能出8种（2*2*2）不同的结构
虽然链表的种类众多，但是我们主要用两种链表
无头单向非循环链表和带头双向循环链表
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势
3. 无头单向非循环链表
注：为什么有的函数传递二级指针
因为当链表的头结点需要被改变时，需要传递头结点的地址，以此才能改变头结点
3.1 链表的结构体定义
typedef int DataType;
typedef struct Slist
{
DataType data;
struct Slist* next;
}SL;3.2 动态创建一个链表新结点
函数声明：
SL* BuyListNode(DataType x);在VS中malloc一个内存块时，注意检查一下malloc是否成功，最后返回malloc出来的结点地址
函数定义：
SL* BuyListNode(DataType x)
{
SL* newnode = (SL*)malloc(sizeof(SL));
if (newnode == NULL)
{
printf("malloc errno\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}3.3 打印链表
函数声明：
void SlPrint(SL* phead);
注：当while循环中是cur != NULL时，最后cur会指向链表最后一个元素存储的NULL
当while循环中是cur->next !=NULL时，最后cur会指向链表的最后一个元素
函数定义：
void SlPrint(SL* ps)
{
SL* cur = ps;
//while (cur)
while (cur != NULL)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("NULL\n");
}3.4 尾插和尾删
尾插：
函数声明：
void SlPushBack(SL** pphead, DataType x);无头单向非循环链表尾插需要通过遍历才能找到链表的尾，有些麻烦
尾插时，分两种情况：
1.链表中还没有存储数据，此时链表的头结点是NULL
此时直接将malloc出来的结点给头结点
2.链表中已经有数据，此时链表的头结点不是NULL
此时需要先找到尾结点，然后再把malloc出来的结点给tail->next
函数定义：
void SlPushBack(SL** pphead, DataType x)
{
assert(pphead);
SL* newnode = BuyListNode(x);
if (*pphead == NULL)//1
{
*pphead = newnode;
}
else
{
//找尾
SL* tail = *pphead;//2
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}尾删：
函数声明：
void SlPopBack(SL** pphead);
首先需要检查传进函数的指针不为空
尾删时，分两种情况：
1.链表中只有一个结点：此时直接free掉这个结点，然后再让它为空
2.链表中不只有一个结点：
此时需要找到尾结点，同时也需要记录尾结点的前一个结点，最后让前一个节点的指向NULL
（原因：若只找到尾结点并释放掉的话，尾结点的前一个结点还指向原来的尾结点地址，如果打印时此时会造成指针的非法访问）
函数定义：
void SlPopBack(SL** pphead)
{
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SL* end = *pphead;
SL* prve = NULL;
while (end->next)
{
prve = end;
end = end->next;
}
free(end);
end = NULL;
prve->next = NULL;
}
}3.5 头插和头删
头插：
函数声明：
void SlPushFront(SL** pphead, DataType x);
只需要检查一下指针不为NULL，然后将malloc出来的结点直接插入
函数定义：
void SlPushFront(SL** pphead, DataType x)
{
assert(pphead);
SL* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}头删：
函数声明：
void SlPopFront(SL** pphead);
需要检查一下指针不为NULL，记录第二个结点地址，释放第一个结点，将第二个结点地址给头结点
函数定义：
void SlPopFront(SL** pphead)
{
assert(*pphead != NULL);
assert(pphead);
SL* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}3.6 找到x值的地址
函数声明：
SL* SlFind(SL* phead, DataType x);
遍历链表，找到返回结点地址，找不到返回NULL
函数定义：
SL* SlFind(SL* phead, DataType x)
{
assert(phead);
while (phead)
{
if (phead->data == x)
{
return phead;
}
else
{
phead = phead->next;
}
}
return NULL;
}3.7 在pos前面/后面插入一个数
在pos前面插入一个数：
函数声明：
void SlInsertBefore(SL** pphead, SL* pos, DataType x);
1.pos是头结点，此时就是头结点的前插
2.在其他位置前插一个数，需要记录pos位置的前一个结点的位置
函数定义：
void SlInsertBefore(SL** pphead, SL* pos, DataType x)
{
assert(*pphead);
assert(pos);
if (*pphead == pos)
{
SlPushFront(pphead,x);
}
else
{
SL* prev = *pphead;
while (prev->next != pos)
{
prev = (*pphead)->next;
}
SL* newnode = BuyListNode(x);
newnode->next = pos;
prev->next = newnode;
}
}在pos后面插入一个数：
函数声明：
void SlInsertAfter(SL* pos, DataType x);
只直接改变两个结点的next指针即可
函数定义：
void SlInsertAfter(SL* pos, DataType x)
{
SL* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}3.8 删除某个位置/删除某个位置的后一个位置
删除某个位置 ：
函数声明：
void SlErase(SL** pphead, SL* pos);
1. pos是头结点时，调用头删函数
2. pos是其他结点，通过遍历找到pos的前一个结点，将pos前一个结点的next指向pos的下一个结点，最后free掉pos
函数定义：
void SlErase(SL** pphead, SL* pos)
{
assert(*pphead);
assert(pos);
if(*pphead == pos)
{
SlPopFront(pphead);
}
else
{
SL* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
pos = NULL;
}
删除某个位置的后一个位置：
函数声明：
void SListEraseAfter(SL* pos);
记录pos下两个结点的地址
将pos下两个结点的地址给pos->next
函数定义：
void SListEraseAfter(SL* pos)
{
assert(pos);
assert(pos->next);
SL* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}3.9 销毁链表
函数声明：
void SlDestory(SL** pphead);通过遍历链表释放每个结点
函数定义：
void SlDestory(SL** pphead)
{
assert(pphead);
SL* cur = *pphead;
while (cur)
{
SL* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}