1.单链表的定义和结构
单链表是一种链式的数据结构，它用一组不连续的储存单元存反线性表中的数据元素。链表中的数据是以节点的形式来表示的，节点和节点之间相互连接
一般来说节点有两部分组成 1.数据域 ：数据域用来存储各种类型的数据（浮点数，字符串，自定义类型的数据），2.指针域： 指针域用来存储的是指针，它用来指向下一个节点
2.单链表的实现
SLlist.h
//定义单链表的节点
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType Data;struct SListNode* next;//指向下一个节点的指针
}SLTNode;//增加新的节点
SLTNode* SLTBuyNode(SLTDataType x);//打印链表
void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDesTroy(SLTNode** pphead);SLlist.c
//增加新的节点
SLTNode* SLTBuyNode(SLTDataType x) {//开辟一个节点大小的空间SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->Data = x;newnode->next = NULL;return newnode;
}//打印链表
void SLTPrint(SLTNode* phead) {//循环打印，当phead指向NULL（也就是尾节点指向的下一个节点）时停止while (phead){printf("%d->", phead->Data);//让phead指向下一个节点，并赋值给pheadphead = phead->next;}printf("NULL\n");
}//尾插
//想要修改值就要传地址，不能传值。而phead是个指针，我们要拿二级指针接收
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);//*pphead说明第一个节点为NULL也就是说链表为空if (*pphead == NULL) {*pphead = SLTBuyNode(x); //直接创建一个新的节点}//链表不为NULL时尾插else{SLTNode* ptail = *pphead; //创建一个节点，从头开始遍历找尾节点//遍历链表，找到尾节点while (ptail->next) //下一个节点为NULL表达式为假，就说明已经找到了尾节点{ptail = ptail->next;}ptail->next = SLTBuyNode(x); //找到为节点，让尾节点指向新的节点，完成尾插}}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x); //创建一个新的节点准备进行头插newnode->next = *pphead; //直接让新节点指向原先的第一个节点*pphead = newnode; //让新的节点成为新的第一个节点//在是有一个节点的情况下也可以完美完成任务
}//尾删
//可能要修改第一个节点，所以得传地址，用二级指针** pphead接收
void SLTPopBack(SLTNode** pphead) {//列表不能为NULL不然删啥assert(pphead && *pphead);SLTNode* ptail; //找尾节点SLTNode* prev; //尾节点前一个节点，它将来可能是新的尾节点prev = ptail = *pphead;//只有一个节点，直接删除不用找尾节点前面的节点if (ptail->next == NULL){//改变头节点需要用到pphead，对它进行解引用得到原第一个节点free(*pphead);*pphead = NULL;}//有一个以上的节点，开始找尾节点，进行尾删else{//当 某个节点的下一个节点(指向)->NULL 时找到尾节点while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail); //找到了原尾节点直接释放ptail = NULL; prev->next = NULL; //让新的位节点（指向）->NULL}
}//头删
//肯定会修改到第一个节点，要传地址，拿二级指针** pphead接收
void SLTPopFront(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* ptail = *pphead; //记录原第一个节点//改变原第一个节点*pphead = ptail->next; //让第二个节点成为，新的第一个节点//直接释放原第一个节点free(ptail);ptail = NULL;
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {//空链表的话不用找了assert(phead);SLTNode* pcur = phead;//让pcur遍历链表，直到尾节点指向的下一个节点NULL，说明没有这个元素while (pcur){if(pcur->Data == x){return pcur; //有这个元素，直接返回这个元素所在节点的地址}pcur = pcur->next;}return NULL;
}//在指定位置之前插入数据
//可能会改变第一个节点要传地址，拿二级指针** pphead接收
//pos 为指定位置
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);//创新的节点SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead; //prev用找到pos之前的位置//如果只有一个节点，会出现prev找不到pos的情况，因为一开始这两的位置一样，prev的下一个位置永远不可能是posif (pos == prev) {SLTPushFront(pphead, x);}//有多个节点的情况，开始找pos节点并再此之前插入else {//找pos之前的节点prevwhile (prev->next != pos){prev = prev->next;}//拿1 -> 2 -> NULL 我们要在1(prev) 2(pos)之间插入3演示newnode->next = pos; //先让新的节点，指向pos 3 -> 2 ->NULLprev->next = newnode; //在让prev节点指向新的节点 1 -> 3 -> 2 ->NULL}
}//在指定位置之后插入数据
//不存在改变第一个节点的情况，传第一个节点值过来就够用
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {//指定的位置不能为NULL，要不然谁知道你想要在谁之后插入数据assert(pos);创建新的节点SLTNode* newnode = SLTBuyNode(x);SLTNode* del = pos->next; //del为pos之后的节点//如果只有一个节点，那么pos指向的下一个节点为NULL，这套逻辑依旧适用//拿1 -> 2 -> 3 -> NULL 我们要再2（pos）3（del）之间插入4newnode->next = del; //先让新的节点指向del 4 ->3 -> NULLpos->next = newnode; //在让pos指向新的节点 1 -> 2 -> 4 -> 3 -> NULL}//删除pos节点
//如果删除的是第一点，得传地址，因为第一个节点会发生变化
void SLTErase(SLTNode** pphead, SLTNode* pos) {//链表不能为NULL不然删啥assert(pphead && pos && *pphead);SLTNode* del = pos->next; //del为pos之后的节点SLTNode* prev = *pphead; //prev为pos之前的节点//如果只有一个节点，直接删即可，不用去找pos前一个节点，这样找找不到if (pos == del)//pos = del 我搞错了，这样就赋值了{//头删,传头结点的地址也就是ppheadSLTPopFront(pphead);}//不止一个节点，找pos之前的节点prevelse{while (prev->next != pos){prev = prev->next;}//把pos前一个节点prev和后一个节点del连接起来，在把pos节点释放prev->next = del;free(pos);pos = NULL;}
}//删除pos之后的节点
//第一个节点不可能被修改，因为即使只有一个节点，第一个节点后面的节点也是NULL
void SLTEraseAfter(SLTNode* pos) {//pos后面的节点不能为NULL不然删啥assert(pos && pos->next);SLTNode* del = pos->next; //del为pos之后的节点//1->2->3,让1跟3连接起来，在释放2pos->next = del->next;free(del);del = NULL;
}//销毁链表
//涉及修改第一个，需要接收头结点地址
void SListDesTroy(SLTNode** pphead) {assert(pphead && *pphead);SLTNode* pcur = *pphead; //pcur用来遍历链表，依次销毁SLTNode* next; //next为当前需销毁节点的下一个节点，不然直接销毁就找不到下一个节点了//如果pcur为NULL，说明走到了尾节点指向的NULL，链表销毁完毕while (pcur){next = pcur->next; //先保存当前需要销毁节点的下一个节点的地址free(pcur); //销毁当前节点pcur = next; //走向下一个节点}*pphead = NULL; //让第一个节点为NULL，链表销毁完毕后为NULL
}
