单链表所需要的头文件
重命名类型的意义在于以后还需要用到单链表时，存入的类型不一定时int类型，需要更改类型时，要一个个更改，非常麻烦，我们可以直接在这里修改，更加方便(这里的解释我上一篇也有提到)
?
单链表用到的结构体
这里我们把结构体重命名为ST
单链表需要实现的功能有 1.申请一个新节点的内存空间 2.单链表的头部，尾部的插入和删除 3.单链表的查找 4.单链表查找后的插入和删除 5.单链表的打印 6.单链表的释放
1.单链表的节点申请内存空间
申请内存空间并不是直接使用，它是作为链表需要进行插入 需要新空间的时候 才进行调用，所以返回类型不是void 而是结构体类型
?1.我们先申请一个新内存。并且存入名为?newnode的结构体类型（我们可以直接称为新节点)
?2.我们把新节点指向下一个的指针置空
?3.把x存入data
2.单链表的尾部插入
只要是插入新数据 我们都要先调用申请新内存的函数
尾部插入和头部插入可以调换 但第一次插入的函数 要先判断pplist是否为空，第一次进入的pplist指针是为空的 我们把新申请的节点内存赋值给pplist
?我们用名为tail的结构体类型存放头指针
然后开始循环 直到tail指向最后一个节点
tail=tail->next 这个就是然后tail不断的向后走（简称便利）
循环结束后 tail指向最后一个节点 然后把最后一个节点的指针指向新创建的节点，这样新创建的节点就成为了链表的最后一个节点。
3.单链表的头部插入
因为是第二次插入 pplist不为空了 那么我们就不需要判断了
还是一样 只要是插入新数据 都要调用创建新节点的内存函数
链表的头部插入的原理是
先用tail存放头节点， 再把新创建节点的指针指向头节点 那么新创建的节点就在头节点的前面，最后把指向头节点的指针再指向新创建的节点，那么新创建的节点就成为了头节点。
4.单链表尾部删除
因为是最后一个节点删除，那么我们直接找最后一个节点的上一个节点。
找最后一个节点是 的循环条件是 tail->next!=NULL?
那么找最后一个节点的上一个节点的循环条件是 tail->next->next!=NULL
依旧是遍历，便利到最后一个节点的上一个节点。
循环结束后，tail就指向了最后一个节点的上一个节点
那么上一个节点的下一个节点就是最后一个节点 我们把它释放
再把上一个节点的指针置为空 这样我们就找不到最后一个节点了，就删除成功了。
（因为最后一个节点的上一个节点无法命名 所以这里会比较绕 但是原理是简单的）
5.单链表的头部删除
?头部删除的原理比较简单，定义两个结构体类型，一个存放头，一个存放头的下一个，再把头指针指向第二个，那么头指针就从第二个开始，第二个就成为了头
?6.单链表的查找
查找的原理也很简单 对链表依次遍历 如果找到了需要的数据 就返回找到的位置，找不到就返回空
?进循环后 先判断是不是要查找的数据 ，如果不是 就跳到下一个 就此循环，直到循环结束都找不到的话，我们就返回空
返回后 我们用名为pos结构体类型接收
7.单链表查找到后的插入
首先要判断pos是否为空 如果不为空（就是找到了）那么我们才可以进行查找到后的插入
?
因为是插入数据 我们要调用申请节点内存的空间的函数
然后找到pos的前一个数据?
在pos的前一个数据指向下一个的指针不再指向pos，而是指向我们要插入的新节点（就是newnode），然后再把新插入的节点的指针指向pos，就插入了新节点
8.单链表查到到后的删除
?原理比较简单?
因为我们已经有pos的位置 （再查找函数那里 我们已经拿到了要查找的数据的位置了，存放在pos里，我们可以直接用），所以我们直接找pos的前一个数据 和pos的后一个数据 让前一个数据指向后一个数据 pos就查找不到了 就删除了
?循环条件是找到pos的上一个数据 ，然后遍历，循环结束后，tail就是指向pos的上一个数据
用end存放pos的下一个数据
让tail指向下一个数据的指针指向end，让他们连接在一起
这样pos就查找不到了 就删除成功了
最后记得要释放
9.单链表的打印
我们直接遍历单链表 然后依次打印
10.单链表的释放
直接把next的指针释放并置为空 （指针是置空）
再把存放数据的data置为0（数据是置为0）
那么单链表的全部功能就实现了！?
?接下来是代码段 需要的可以复制到编译器上自己使用
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int STDataType;
typedef struct linode
{
struct linode* next;//指向下一个节点的指针
STDataType data;//存放节点的数据
}ST;
ST* BuySListNode(STDataType x)//申请节点的动态内存
{
ST* newnode = (ST*)malloc(sizeof(ST));
newnode->next = NULL;//先把节点指向下一个节点的指针置为空
newnode->data = x;//把数据放入新节点
return newnode;
}
//链表的原理是 要存入新的节点 就申请一个内存
//不用像顺序表那样提前申请一个一定的空间 满了再继续申请
void SListPushBack(ST** pplist, STDataType x)//链表的尾部插入
{
ST* newnode = BuySListNode(x);
if (*pplist == NULL)//第一次进入pplist会为空 我们要先判断
{
*pplist = newnode;
}
else
{
ST* tail = *pplist;
while (tail->next != NULL)//一直判断到链表的最后一个节点停止
{
tail = tail->next;
}
tail->next = newnode;//让最后一个节点指向新的节点
}
}
void SListPrint(ST* plist)//链表的打印
{
ST* phead = plist;
while (phead != NULL)
{
printf("%d->", phead->data);
phead = phead->next;
}
printf("NULL\n");
}
void SListPushFront(ST** pplist, STDataType x)//链表的头部插入
{
ST* newnode = BuySListNode(x);//只要是插入数据 都要先申请一个新的内存
ST* tail = *pplist;//用一个指针存头节点
newnode->next = *pplist;//让新的节点指向头节点
*pplist = newnode;//再把指向头节点这个指针指向新节点
}
void SListPopBack(ST** pplist)//链表的尾部删除
{
ST* tail = *pplist;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
void SListPopFront(ST** pplist)//链表的头部删除
{
ST* tail = *pplist;
ST* end = tail->next;
*pplist = end;
}
void SListDesTory(ST* plist)//释放
{
free(plist->next);
plist->next = NULL;
plist->data = 0;
}
ST* SListFind(ST* plist, STDataType x)//链表的查找
{
ST* tail = plist;
while (tail != NULL)
{
if (tail->data == x)
{
return tail;
}
tail = tail->next;
}
return NULL;
}
void SListInsert(ST** pplist, ST* pos, STDataType x)//在pos前插入x
{
ST* tail = *pplist;
ST* newnode = BuySListNode(x);
while (tail->next != pos)
{
tail = tail->next;
}
tail->next = newnode;
newnode->next = pos;
}
void SListErase(ST** pplist, ST* pos)//删除pos位置的数据
{
ST* tail = *pplist;
while (tail->next != pos)
{
tail = tail ->next;
}
ST* end= pos->next;
tail->next = end;
free(pos);
}
void Intenode()
{
ST *phead = NULL;
// // 单链表尾插
SListPushBack(&phead, 1);
SListPushBack(&phead, 2);
SListPushBack(&phead, 3);
SListPushBack(&phead, 4);
// // 单链表的头插
SListPushFront(&phead, 5);
SListPushFront(&phead, 6);
SListPushFront(&phead, 7);
SListPushFront(&phead, 8);
// // 单链表的尾删
SListPopBack(&phead);
SListPopBack(&phead);
// // 单链表的头删
SListPopFront(&phead);
SListPopFront(&phead);
// // 单链表的查找
ST* pos=SListFind(&phead, 1);//用找到的位置用pos接收
if (pos)//判断是否查找到，找到才进行修改 不能直接进行修改
{
//查找到后 在pos这个位置前插入x
SListInsert(&phead, pos, 10);
}
//删除pos位置的数据
SListErase(&phead, pos);
// // 单链表打印
SListPrint(phead);
//单链表的释放
SListDesTory(phead);