## 链表的概念 ##
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
1.1单链表的概念
单链表是一种链式存取的数据结构，，链表中的数据是以结点来表示的，每个结点的构成：元素 指针(指向后继元素存储位置)。
1.2定义结点
不同类型的集合用结构体，单链表结点中有元素和指针，就像顺序表中有元素和有效元素个数和空间大小一样，类比着就可以定义出来结点：
typedef int sldatatype;
//不知道元素类型，重命名数据类型，方便修改
typedef struct slistnode
{
sldatatype data; //元素
struct slistnode* next; //指向下一个元素的地址
}slistnode;
//slistnode为重命名结构类型定义了结点，那我们就可以轻松手动创建一个单链表：1 2 3 4 5
创建多个结点，进行赋值，将指针指向下一个结点地址，最后一个结点的指针为空时则返回。
void testslist3()
{
//定义一个头结点
slistnode* slist = null;
slistnode* n1 = malloc(sizeof(slistnode));
slistnode* n2 = malloc(sizeof(slistnode));
slistnode* n3 = malloc(sizeof(slistnode));
slistnode* n4 = malloc(sizeof(slistnode));
slistnode* n5 = malloc(sizeof(slistnode));
n1->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
n5->data = 5;
n1->next = n2;
n2->next = n3;
n3->next = n4;
n4->next = n5;
n5->next = null;
//链表创建完毕
//头结点指向第一个结点
slist = n1;
//打印，可视化
slistprint(slist);
}打印函数：
单链表手动创建完成，为了检验效果，我们接下来创建一个打印函数：
//打印
void slistprint(slistnode* phead)
{
slistnode* cur = phead;
while (cur != null)
{
printf("%d->",cur->data);
cur = cur->next;
}
printf("null\n");
}效果展示：
3.1尾插
创建结点
尾部插入元素时，我们要知道插入的是一个结点，这时候就要创建一个结点来存放元素，指针我们置为空。
slistnode* buyslistnode(sldatatype x)
{
slistnode* newnode = (slistnode*)malloc(sizeof(slistnode));
//记得判断是否开辟成功
if (newnode == null)
{
printf("malloc fail\n");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = null;
}
//直接将要操作的元素放进新节点里
//后面只需要操作指针
return newnode;
}进行尾插
尾插时，原末尾结点的指针指向null，我们需要改变，令原末尾结点指针指向新节点就可以了。
//单链表尾插
void slistpushback(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;
}
}注：
这里要特别注意函数传参问题，函数类型为void，那么不进行返回，但是我们要改变结点的指针，所以在使用函数时，应该传的是指针的地址，头结点为slist，使用时应传（&slist），接收时应该用双指针接收。
记住一句话：函数传参时，想要改变什么，就传什么的地址。
3.2尾删
这里要判断三种情况：
1.链表为空时 2.链表只有一个结点时 3.多个结点
我们要释放最后一个结点，还要将前一个结点的next置空。
//2.单链表尾删
void slistpopback(slistnode** phead)
{
assert(phead);
//1.空
//2.一个
//3.多个
if (*phead==null)
{
return;
}
else if ((*phead)->next == null)
{
free(*phead);
*phead = null;
}
else
{
//遍历找最后一个节点（找尾）
slistnode* tail = *phead;
while (tail->next->next != null)
{
tail = tail->next;
}
free(tail->next);
tail->next = null;
}
}4.1头插
头插很简单，只需要创建新结点，令新结点的next指向原头结点，将头结点移到新结点位置即可。
//单链表头插
void slistpushfront(slistnode** phead, sldatatype x)
{
slistnode* newnode = buyslistnode(x);
newnode->next = *phead;
*phead = newnode;
}4.2头删
令头结点指向头结点的next，释放原头结点即可。
//单链表头删
void slistpopfront(slistnode** phead)
{
assert(phead);
if (*phead == null)
{
return;
}
//保存头结点的next
slistnode* next = (*phead)->next;
free(*phead);
*phead = next;
}5.1固定位置插入
要判断固定位置是否为空(超出链表范围)，为第一个时，相当于头插
其他情况下，先要遍历找到pos，开辟新结点，pos前结点next指向newnode newnode的next指向pos。
//单链表pos位置插入
void slistinsert(slistnode** phead, slistnode* pos, sldatatype x)
{
assert(phead);
assert(pos);
//1.pos是第一个节点,相当于头插
//2.pos不是第一个节点
if (pos == *phead)
{
slistpushfront(phead,x);
}
else
{
slistnode* prev = *phead;
while (prev->next != pos)
{
prev = prev->next;
}
slistnode* newnode = buyslistnode(x);
newnode->next = pos;
prev->next = newnode;
}
}5.2固定位置删除
将pos位置前结点的next指向pos的下一个结点，即pos的next，释放pos位置即可
也是先遍历，判断条件与4.1过程相同。
//单链表固定位置删除
void slisterase(slistnode** phead, slistnode* pos)
{
assert(phead);
assert(pos);
if (pos == *phead)
{
slistpopfront(phead);
}
else
{
slistnode* prev = *phead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = null;
}
}需要遍历，若结点data等于要查找的值，返回结点地址即可，因为无指针的改变，传参时不需要传入指针地址，接收时不需要二级指针。
//查找
slistnode* slistfind(slistnode* phead, sldatatype x)
{
slistnode* cur = phead;
while (cur!=null)
{
if (cur->data==x)
{
return cur;
}
cur = cur->next;
}
return null;
}若要修改，应先找，查找函数返回的是指针，直接用指针修改对应的data即可
例子：
void testslist2()
{
//创建链表
slistnode* slist = null;
for (int i = 0;i<4;i )
{
slistpushback(&slist, i);
}
slistprint(slist);
//查找要修改的值
slistnode* pos = slistfind(slist,3);
if (pos)
{
printf("找到了:%p\n",pos);
//修改
pos->data *= 10;
}
slistprint(slist);
}
插入，先保存pos的next为next，将pos的next指向新结点，新节点的next指向刚刚保存的next，这样就将新结点连接在pos位置后了。
//单链表pos位置后插入
void slistinsertafter(slistnode* pos, sldatatype x)
{
assert(pos);
slistnode* next = pos->next;
slistnode* newnode = buyslistnode(x);
pos->next = newnode;
newnode->next = next;
}删除，保存pos的next为next，判断next是否为空，不为空则将pos的next直接指向next的next，释放掉第一次保存的next，即刚开始的pos的next，next置空即可。
//单链表pos位置后删除
void slisteraseafter(slistnode* pos)
{
assert(pos);
slistnode* next = pos->next;
if (next)
{
pos->next = next->next;
free(next);
next = null;
}
}预先保存头结点的下一个结点，要不然头结点释放后找不到下一个结点。
//销毁
void slistdestory(slistnode** phead)
{
assert(phead);
slistnode* cur = *phead;
while (cur)
{
slistnode* next = cur->next;
free(cur);
cur = next;
}
*phead = null;
}这样单链表的定义及功能就完成了，只需要根据自身需求写主函数和菜单就可以了。