一. 顺序表的问题及思考
在上一节，我们学习了顺序表，但是我们还是要思考，用顺序表来存储数据行不行呢?
顺序表的问题及思考：
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
很显然，用顺序表来存储数据是不太方便的。那我们能不能引入一个向概念，将存储数据的方式优化，将时间复杂度或者空间复杂度优化呢？
解决方法很明显要有两个特点：
- 空间上，按需给空间。
- 不要求物理空间连续，那么头部和中间的插入，就不需要挪动数据。
要满足这两个条件，就需要我们引入一个新的概念：链表。
提示：为了方便引入链表，本节中先讨论单链表。
二.单链表表示和实现
1. 链表的概念及结构
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
这就好比客人去酒店开房间，如果有某几个房子是空的，服务员就可能会随机开个房子给客人(假设客人不指定房间)，这里并不能保证第一位入住的客人的房间号一定先于第二位入住的客人的房间号。
链表存储数据是随机存储的，在空间上不连续。链表就像是客人去酒店开房间，在这里，数据就像是客人，房间就像是内存，服务员就好像是操作系统，房间号就是地址。设计链表时，我们通过动态内存申请，在内存中随机申请一块空间用来存储数据，便返回一个地址指针。
2.单链表的实现
在本节中，我们先讨论链表中最简单的无头单向不循环链表
// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之前插入x
void SListInsert(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置的值
void SListErase(SListNode** pplist, SListNode* pos);
3.对各个接口函数的详细解释
1.单链表打印：SListPrint
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
2.动态申请一个节点:BuySListNode
SLTNode* BuySListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
newnode->data = x;
newnode->next = NULL;
return newnode;
}
3.单链表尾插:SListPushBack
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾节点的指针
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
// 尾节点，链接新节点
tail->next = newnode;
}
}
4.单链表的头插:SListPushFront
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
5.单链表头删:SListPopFront
void SListPopFront(SLTNode** pphead)
{
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
6.单链表的尾删:SListPopBack
void SListPopBack(SLTNode** pphead)
{
// 1、空
// 2、一个节点
// 3、一个以上的节点
if (*pphead == NULL)
{
return;
}
else if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
7.单链表查找:SListFind
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
SListNode* cur = phead;
//while (cur != NULL)
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
8.单链表在pos位置之前插入x:SListInsert
// 在pos的前面插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SLTNode* newnode = BuySListNode(x);
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = newnode;
newnode->next = pos;
}
}
9.单链表删除pos位置的值:SListErase
// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
对部分接口需穿二级指针的解释：
