首先需要借助三个文件 SList.h SList.c test.c
目录
SList.h ：用来建立结构体、头文件、函数声明、全局变量建立
SList.c：对头文件中声明的函数的实现
void SLTPrint(SLTNode* phead)
SLTNode* BuyLTNode(SLTDataType x)
void SLPushFront(SLTNode** pphead, SLTDataType x)
//void SLPushBack(SLTNode* phead, SLTDataType x)
void SLPushBack(SLTNode** pphead, SLTDataType x) //尾部需要用tail
void SLPopFront(SLTNode** pphead) //头删
void SLPopBack(SLTNode** pphead)
SLTNode* STFind(SLTNode* phead, SLTDataType x) //查找会返回当前节点的指针，所以如果查找不为空，可以直接进行修改
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) //pos是某个节点的指针 //前插需要pphead，后插不需要（前插需要判断pos是不是首元素！）
void SLInsertAfter(SLTNode* pos, SLTDataType x) //find之后，会返回当前的指针，传给pos使用
void SLErase(SLTNode** pphead, SLTNode* pos) //前删需要pphead，后删不需要 需要判断pos是不是首元素！
void SLEraseAfter(SLTNode* pos) //传找到的一级指针就可以
test.c
SList.h ：用来建立结构体、头文件、函数声明、全局变量建立
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
void SLPushFront(SLTNode** pphead, SLTDataType x);
void SLPushBack(SLTNode** pphead, SLTDataType x);
void SLPopFront(SLTNode** pphead);
void SLPopBack(SLTNode** pphead);
// 单链表查找
SLTNode* STFind(SLTNode* phead, SLTDataType x);
// 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos);
// 删除pos位置后面的值
void SLEraseAfter(SLTNode* pos);
SList.c：对头文件中声明的函数的实现
#include"Slist.h"
void SLTPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SLTNode* BuyLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址 //pphead 要断言 ， 因为需要对 pphead 进行解引用操作并修改 *pphead = ....
//assert(*pphead); // 不能断言， 链表为空，也需要能插入 //因为 *pphead 不需要再次解引
SLTNode* newnode = BuyLTNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//void SLPushBack(SLTNode* phead, SLTDataType x)
//{
// SLTNode* tail = phead;
// while (tail != NULL)
// {
// tail = tail->next;
// }
//
// SLTNode* newnode = BuyLTNode(x);
// tail = newnode;
//}
void SLPushBack(SLTNode** pphead, SLTDataType x) //尾部需要用tail
{
assert(pphead); // 链表为空，pphead也不为空，因为他是头指针plist的地址
//assert(*pphead); // 链表为空，可以尾插
SLTNode* newnode = BuyLTNode(x);
// 1、空链表
// 2、非空链表
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SLPopFront(SLTNode** pphead) //头删
{
//1.是否解引用 2 .看具体场景
assert(pphead); // 链表为空，pphead也永远不为空，因为他是头指针plist的地址
assert(*pphead); // 链表为空，不能头删。（当然你还可以用温柔的检查）
SLTNode* del = *pphead;
*pphead = (*pphead)->next;
free(del); //不能free *pphead ， 因为他的空间已经改变了
// 一个节点
// 多个节点
//if ((*pphead)->next == NULL)
//{
// free(*pphead);
// *pphead = NULL;
//}
//else
//{
// SLTNode* del = *pphead;
// //*pphead = del->next;
// *pphead = (*pphead)->next;
// free(del);
//}
}
void SLPopBack(SLTNode** pphead)
{
assert(pphead); // 链表为空，pphead也不为空，因为他是 头指针plist 的地址
assert(*pphead); // 链表为空，不能头删。（当然你还可以用温柔的检查）
// 没有节点(空链表)
// 暴力检查
//assert(*pphead);
// 温柔的检查
/*if (*pphead == NULL)
{
return;
}*/
// 一个节点
// 多个节点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
//SLTNode* prev = NULL;
//SLTNode* tail = *pphead;
找尾
//while (tail->next)
//{
// prev = tail;
// tail = tail->next;
//}
//free(tail);
//prev->next = NULL;
SLTNode* tail = *pphead;
// 找尾
while (tail->next->next) //为了找到前一个节点next置空，需要一个让tail为倒数第二个节点
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
SLTNode* STFind(SLTNode* phead, SLTDataType x) //查找会返回当前节点的指针，所以如果查找不为空，可以直接进行修改
{
//assert(phead);
SLTNode* cur = phead; //遍历时一般会利用一个新的指针，而不是头指针
while (cur) //直到为空指针 //不能是cur->next ，否则最后一个节点无法访问
{
if (cur->data == x) //当前cur的date
{
return cur; //返回节点的指针 （要弄清楚修改节点和修改节点的指针的区别！）
}
cur = cur->next; //通过next 连接整个链表
}
return NULL;
}
// 在pos之前插入：prev指向的新节点是新插入的节点
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) //pos是某个节点的指针 //前插需要pphead，后插不需要（前插需要判断pos是不是首元素！）
{
assert(pphead);
assert(pos); //在pos之前插入需要断言！（也可以不断言，多写一个尾插）
//assert(*pphead); //*pphead为空，那么pos也为空（*pphead为空，则说明节点不存在，那么pos这个位置，一定为空）
if (*pphead == pos) //如果是第一个元素的话，那么plist（即*pphead） == pos
{
SLPushFront(pphead, x); //那么就需要头插
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos) //找前一个节点，如果后一个是pos，那么就找到了（== pos 时停止）
{
prev = prev->next;
}
SLTNode* newnode = BuyLTNode(x);
prev->next = newnode; //newnode是堆区新开辟的空间
newnode->next = pos; //newnode—>next也是在堆区开辟的空间 //指向的是pos，不是pre—>next！
}
}
// 在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x) //find之后，会返回当前的指针，传给pos使用
{
assert(pos);
SLTNode* newnode = BuyLTNode(x);
newnode->next = pos->next; //可以为NULL；
pos->next = newnode;
}
// 删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos) //前删需要pphead，后删不需要 需要判断pos是不是首元素！
{
assert(pphead);
assert(pos); //当前元素（前删的元素）不能为空
if (pos == *pphead) //只有一个元素，头删
{
SLPopFront(pphead);
}
else //多个元素
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos); //释放pos //有pos的直接用pos
//不能置空，因为链表需要链接
}
}
void SLEraseAfter(SLTNode* pos) //传找到的一级指针就可以
{
assert(pos);
assert(pos->next); //后删的元素也不能为空
SLTNode* next = pos->next; //将next指针，指向 pos->next 这块空间
//结构体成员next 和 形参next可以共存
pos->next = next->next;
free(next); //释放空间 无需置空
}
test.c
#include"SList.h"
void TestSList1()
{
SLTNode* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
/*plist = SLPushFront(plist, 1);
plist = SLPushFront(plist, 2);
plist = SLPushFront(plist, 3);
plist = SLPushFront(plist, 4);*/
SLTPrint(plist);
SLPushBack(&plist, 5);
SLTPrint(plist);
}
void TestSList2()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTPrint(plist);
SLPopBack(&plist);
SLTPrint(plist);
SLPopBack(&plist);
SLTPrint(plist);
SLPopBack(&plist);
SLTPrint(plist);
SLPopBack(&plist);
SLTPrint(plist);
//SLPopBack(&plist);
}
void TestSList3()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = STFind(plist, 3);
if(pos)
pos->data = 30;
SLTPrint(plist);
}
void TestSList4()
{
SLTNode* plist = NULL;
SLPushBack(&plist, 1);
SLPushBack(&plist, 2);
SLPushBack(&plist, 3);
SLPushBack(&plist, 4);
SLTPrint(plist);
SLTNode* pos = STFind(plist, 3);
if (pos)
{
SLInsert(&plist, pos, 30); //插入时先查找，找到返回的地址
}
SLTPrint(plist);
pos = STFind(plist, 2);
if (pos)
{
SLInsertAfter(pos, 20); //先查找，找到返回的地址
}
SLTPrint(plist);
pos = STFind(plist, 2); //先查找，找到返回的地址
if (pos)
{
SLErase(&plist, pos);
}
SLTPrint(plist);
}
值得一提的是
1.形参的修改不会影响实参，想要修改指针的指向，需要利用二级指针传参去修改一级指针（必须有一层解引用材才可以！！！）
2.分析链表头插尾插的时候，画图，分析date 和 naxt 的指向
3.要对链表进行数据操作时，一定是通过next指针
