链表的概念
链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的分类
链表总共有8种结构：单向有4种，双向有4种，分别与2，3中的组合即可。
单链表基本操作函数
单链表的声明
代码语言：javascript复制typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data; //存储的数据
struct SListNode* next; //指向下一个结点的指针
}SListNode;各个操作总的函数声明
代码语言：javascript复制// 动态申请一个节点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 在pos的前面插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x);
// 删除pos位置
void SListErase(SListNode** pplist, SListNode* pos);
//销毁链表
void SLTDestroy(SListNode** pplist);打印
代码语言：javascript复制void SListPrint(SListNode* plist)
{
SListNode* cur = plist;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULLn");
}创建新节点
代码语言：javascript复制SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}尾插
代码语言：javascript复制void SListPushBack(SListNode** pplist, SLTDataType x)
{
//pplist无论什么时候都不为空，因为它是plist的地址
assert(pplist);
SListNode* newnode = BuySListNode(x);
if (*pplist == NULL)
{
*pplist = newnode;
}
else
{
//找尾
SListNode* tail = *pplist;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}头插
代码语言：javascript复制void SListPushFront(SListNode** pplist, SLTDataType x)
{
assert(pplist);
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}尾删
代码语言：javascript复制void SListPopBack(SListNode** pplist)
{
assert(pplist);
assert(*pplist);
//一个节点和多个节点
if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
//找尾
SListNode* prev = NULL;
SListNode* tail = *pplist;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}头删
代码语言：javascript复制void SListPopFront(SListNode** pplist)
{
assert(pplist);
assert(*pplist);
SListNode* tmp = (*pplist)->next;
free(*pplist);
*pplist = tmp;
}单链表的查找
代码语言：javascript复制SListNode* SListFind(SListNode* plist, SLTDataType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}在pos前面插入
代码语言：javascript复制void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x)
{
//严格限定pos一定是链表里面的一个有效节点
assert(pplist);
assert(pos);
assert(*pplist);
if (*pplist == pos)
{
//头插
SListPushFront(pplist, x);
}
else
{
SListNode* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}删除pos位置
代码语言：javascript复制void SListErase(SListNode** pplist, SListNode* pos)
{
assert(pplist);
assert(*pplist);
assert(pos);
if (*pplist == pos)
{
//头删
SListPopFront(pplist);
}
else
{
SListNode* prev = *pplist;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}pos位置之后插入
代码语言：javascript复制void SListInsertAfter(SListNode* pos, SLTDataType x)
{
//为什么这里不用传**pplist?
//因为这里是往后插，不需要往前找
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}删除pos位置之后的值
代码语言：javascript复制void SListEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* tmp = pos->next;
pos->next = pos->next->next;
free(tmp);
tmp = NULL;
}销毁单链表
代码语言：javascript复制void SLTDestroy(SListNode** pplist)
{
assert(pplist);
SListNode* cur = *pplist;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pplist = NULL;
}注意：上面的函数中，有的传的是二级指针，有的是一级指针。我们可以这样理解：因为实参是一级指针，如果我们的操作需要改变实参，那么我们的实参就要传指针的地址，形参就要用二级指针接受。如果只是更改后面的结点，不涉及到头结点，我们只需要传值，因为更改后面的结点是改变结构体，因此只需用一级指针接受。
