🍟无头单链表

👻无头单链表的所有结点都存储有效信息
👻无头单链表相对带头单链表，在有些涉及更改头节点的函数上需要传二级指针

🍟头文件list.h

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SLTNode {SLTDataType data;struct SLTNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);
SLTNode* BuySLTNode(SLTDataType x);
void Destroy_Method1(SLTNode** pphead);
void Destroy_Method2(SLTNode** pphead);//查
SLTNode* FindBySerialNumber(SLTNode* phead, int n);
SLTNode* FindByContent(SLTNode* phead, SLTDataType x);
//改
void ModefyNodeBySerialNumber(SLTNode* phead, int n, SLTDataType x);
void ModifyNodeByContent(SLTNode* phead, SLTDataType x1, SLTDataType x2);
//增
void PushFront(SLTNode** pphead, SLTDataType x);
void PushBack(SLTNode** pphead, SLTDataType x);void InsertFrontBySerialNumber(SLTNode** pphead, int n, SLTDataType x);
void InsertFrontByAddress(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void InsertFrontByContent(SLTNode** pphead, SLTDataType x1, SLTDataType x2);void InsertBackBySerialNumber(SLTNode** pphead, int n, SLTDataType x);
void InsertBackByAddress(SLTNode* pos, SLTDataType x);
void InsertBackByContent(SLTNode* pphead, SLTDataType x1, SLTDataType x2);
//删
void PopFront(SLTNode** pphead);
void PopBack(SLTNode** pphead);void DeleteFrontNode(SLTNode** pphead, SLTNode* pos);
void DeleteNode(SLTNode** pphead, SLTNode* pos);
void DeleteAfterNode(SLTNode* pos);//测试
SLTNode* testPush_Front_Back();
void testInsertFront();
void testInsertBack();
void testPop();

🍟函数实现list.c

🥤 辅助操作函数

🍕打印链表函数

//辅助操作（打印链表，动态申请节点）
//打印链表
void SLTPrint(SLTNode* phead) {SLTNode* cur = phead;while (cur) {//当指针不为空时进入循环printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

🥤 创建节点，销毁链表函数

🍕创建节点函数

//2.动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x) {//1.用malloc动态申请一个结点的空间SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//2.判断是否申请成功，申请失败直接退出程序if (newnode == NULL) {perror("mallocfail");exit(-1);}//3.给结点的数据域赋值为x，给指针域赋值为NULLnewnode->data = x;newnode->next = NULL;//4.返回节点的地址return newnode;
}

🍕销毁链表函数

🥓法1：先保留头节点，把后面的删完，最后删头结点

//销毁链表
//法1：先保留头节点，把后面的删完，最后删头结点
void Destroy_Method1(SLTNode** pphead) {//链表为空，无需删除assert(pphead);//先删后面，最后删头while ((*pphead)->next) {SLTNode* next = (*pphead)->next;(*pphead)->next = next->next;free(next);}free(*pphead);
}

🥓法2：从头往后删，头节点的值一直更新

//法2：从头往后删，头节点的值一直更新
void Destroy_Method2(SLTNode** pphead) {assert(pphead);SLTNode* cur = *pphead;while (cur) {SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

🥤增删查改——查

🍕1.根据序号查找节点

序号：serial number

// 3.1根据序号查找节点
SLTNode* FindBySerialNumber(SLTNode* phead, int n) {SLTNode* cur = phead;for (int i = 1;i < n;i++) {cur = cur->next;//如果被查找结点不存在（超过链表范围），返回空指针if (cur == NULL) {return NULL;}}return cur;
}

🍕2.根据内容查找结点

//3.2根据内容查找结点
SLTNode* FindByContent(SLTNode* phead, SLTDataType x) {SLTNode* cur = phead;while (cur) {if (cur->data == x) {return cur;}cur = cur->next;}//查找不到返回空指针return NULL;
}

🥤增删查改——改

🍕1.改变节点内数据(通过序号找到被改节点）

//4.1改变节点内数据(通过序号找到被改节点） 
void ModefyNodeBySerialNumber(SLTNode* phead, int n, SLTDataType x) {SLTNode* cur = FindBySerialNumber(phead, n);cur->data = x;
}

🍕2.改变节点内数据(通过内容找到被改节点）

//4.2改变节点内数据(通过内容找到被改节点）
void ModifyNodeByContent(SLTNode* phead, SLTDataType x1, SLTDataType x2) {SLTNode* cur = FindByContent(phead, x1);cur->data = x2;
}

🥤增删查改——增

（头插，尾插，在指定节点前插，在指定节点后插）

🍕1.头插

//5.1头插
void PushFront(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}

👻问：为什么数据x传参时不传指针，而头结点要传二级指针?
👻因为数据x传进来就立马通过BuySLTNode函数被放到在堆区上申请的空间中了，就算不传指针出函数作用域也不会被销毁；而头结点要从原来的链表首结点变成新结点newnode，相当于头结点pphead的值发生变化了，头结点是一个一级指针，对一级指针的修改需要二级指针

🍕2.尾插

//5.2尾插
void PushBack(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL) {*pphead = newnode;//改变结构体指针，要用二级指针，一级指针只能改形参，出作用域后形参被销毁}else {SLTNode* tail = *pphead;while (tail->next != NULL) {tail = tail->next;}tail->next = newnode;}
}

🍕3.在指定结点前插入

在指定结点前插入，需要得到指定位置的前置节点。有控制循环法和前置指针法让指针停留至前置节点处，但控制循环法只能在已知插入第几个节点时用，而前置指针法可以在任何情况下用

🥓3.1通过序号指定节点

👻用到了控制for循环法

//5.3在指定结点前插入（通过序号指定节点） 
void InsertFrontBySerialNumber(SLTNode** pphead, int n, SLTDataType x) {//产生新结点并赋值SLTNode* newnode = BuySLTNode(x);SLTNode* ptmp = *pphead;//如果要在第一个结点前插入结点，就成了头插if (n == 1) {PushFront(pphead, x);return;}//将结点放入指定位置的前一个结点，指定位置不包括第一个结点for (int i = 2;i < n;i++) {ptmp = ptmp->next;if (ptmp == NULL)printf("位置不合法");}newnode->next = ptmp->next;ptmp->next = newnode;}

这个函数之所以要传二级指针是因为有头插的情况，需要调用SLTPushFront函数，但其实用一级指针，调用PushFront函数时再取一级指针的地址也行

🥓3.2内容->地址->找到结点

👻用到了while循环加前置指针法

//5.4在指定结点前插入（内容->地址->找到结点） 
//参数二pos是由test.c调用的Find函数返回的节点位置
void InsertFrontByAddress(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//头插情况if (*pphead == pos) {PushFront(pphead, x);}//非头插else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}SLTNode* newnode = BuySLTNode(x);newnode->next = pos;prev->next = newnode;//由于有两个指针分别控制被插入结点和前一个结点，因此这两句顺序随意}
}

🥓3.3通过内容指定节点

👻用到了while循环加前置指针法

//5.5在指定结点前插入（通过内容指定节点）void InsertFrontByContent(SLTNode** pphead, SLTDataType x1, SLTDataType x2) {SLTNode* cur = *pphead;//头插情况if (cur->data == x1) {PushFront(pphead, x2);}//非头插情况else {cur = FindByContent(*pphead, x1);SLTNode* prev = *pphead;while (prev->next != cur) {prev = prev->next;}//此时必须要第二个指针prevSLTNode* newnode = BuySLTNode(x2);newnode->next = cur;prev->next = newnode;}
}

当不借助FindByContent函数，只知道指定节点的内容时，需要进入每一个节点对比数据是否一致，这时只能用while训话加前置指针法，因为提前不知道指定位置，无法用通过控制for循环找到指定位置的前置节点

🍕4.在指定结点后插入

🥓4.1通过序号指定节点

//5.6 在指定结点后插入（通过序号指定节点）
void InsertBackBySerialNumber(SLTNode** pphead, int n, SLTDataType x) {//原链表为空if (*pphead == NULL) {SLTNode* newnode = BuySLTNode(x);*pphead = newnode;}//原链表不为空SLTNode* newnode = BuySLTNode(x);SLTNode* ptmp = *pphead;//将结点放入指定位置的后一个结点for (int i = 1;i < n;i++) {ptmp = ptmp->next;//指定节点超过最大长度，报错if (ptmp == NULL);assert(ptmp);}newnode->next = ptmp->next;ptmp->next = newnode;
}

🥓4.2内容->地址->找到节点

//5.7在指定结点后插入（内容->地址->找到节点）
//参数一pos是由test.c调用的SLTFind函数返回的节点位置
void InsertBackByAddress(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}

🥓4.3通过内容指定节点

不借助FindByContent函数

//5.8在指定结点后插入（通过内容指定节点）不借助FindByContent函数
void InsertBackByContent(SLTNode** pphead, SLTDataType x1, SLTDataType x2) {SLTNode* newnode = BuySLTNode(x2);SLTNode* cur = *pphead;//原链表为空，newnode就是头节点if (cur == NULL) {*pphead = newnode;}while (cur) {if (cur->data == x1) {//指定结点是尾结点if (cur->next == NULL) {cur->next = newnode;}//指定结点不是尾结点else {newnode->next = cur->next;cur->next = newnode;}}cur = cur->next;}//没找到return;
}

🥤增删查改——删

（头删，尾删，删除指定位置，删除指定位置的前一个节点，删除指定位置的后一个节点）

🍕1.头删

//6.1头删
void PopFront(SLTNode** pphead) {//头结点为空，报错assert(*pphead);//不为空SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;
}

🍕2.尾删

//6.2尾删
void PopBack(SLTNode** pphead) {//头结点为空，报错assert(*pphead);//只有一个结点if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;}//有两个及以上个结点else {SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;//指向尾节点的前置节点}free(tail->next);tail->next = NULL;}
}

🍕3.删除指定节点的前一个节点

(由于前置指针法相对于控制for循环法更普适，这里只展示前置指针法）

//删除指定节点的前一个节点
void DeleteFrontNode(SLTNode** pphead, SLTNode* pos) {//指定位置不可以是头节点if (pos == *pphead) {return;}//指定位置为第二个节点，头结点被删除，更新头结点if ((*pphead)->next == pos) {PopFront(pphead);}//定义pos的前置指针prevelse {SLTNode* prevprev = *pphead;while (prevprev->next->next != pos) {prevprev = prevprev->next;}free(prevprev->next);prevprev->next = pos;}
}

🍕4.删除指定位置节点

//删除指定位置节点
void DeleteNode(SLTNode** pphead, SLTNode* pos) {//如果删除了头结点，头删函数if (pos == *pphead) {PopFront(pphead);}else {SLTNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

🍕5.删除指定节点的后一个节点

//删除指定节点的后一个节点
void DeleteAfterNode(SLTNode* pos) {//检查pos是否为空assert(pos);//检查pos是否是尾节点assert(pos->next);SLTNode* posNext = pos->next;pos->next = posNext->next;free(posNext);posNext = NULL;
}

🍟测试函数test.c

🥤测试头插尾插

SLTNode* testPush_Front_Back() {//测试头插PushFrontprintf("请输入头插长度：");int n = 0;scanf("%d", &n);printf("请依次输入结点的值：\n");SLTNode* plist = NULL;for (int i = 0;i < n;i++) {int val = 0;scanf("%d", &val);PushFront(&plist, val);}SLTPrint(plist);//测试尾插printf("请输入尾插长度：");int m = 0;scanf("%d", &m);printf("请依次输入结点的值：\n");for (int i = 0;i < m;i++) {int val = 0;scanf("%d", &val);PushBack(&plist, val);}SLTPrint(plist);return plist;
//销毁链表Destroy_Method1(&plist);//Destroy_Method2(&plist);
}

🥤测试在指定节点前插入

void testInsertFront() {SLTNode* plist = testPush_Front_Back();//在指定结点前插入（通过序号指定节点）printf("在指定结点前插入（通过序号指定节点）\n");printf("请输入结点编号：");int input1 = 0;scanf("%d", &input1);printf("请输入插入的数据");SLTDataType data1 = 0;scanf("%d", &data1);InsertFrontBySerialNumber(&plist, input1, data1);SLTPrint(plist);//在指定结点前插入（内容->地址->找到结点）printf("在指定结点前插入（内容->地址->找到结点）\n");printf("请输入要插入位置的数据：");SLTDataType data2 = 0;scanf("%d", &data2);SLTNode* pos = FindByContent(plist, data2);printf("请输入插入的数据：");SLTDataType data3 = 0;scanf("%d", &data3);InsertFrontByAddress(&plist, pos, data3);SLTPrint(plist);//在指定结点前插入（通过内容指定节点）printf("在指定结点前插入（通过内容指定节点）\n");printf("请输入要插入位置的数据：");SLTDataType data4 = 0;scanf("%d", &data4);printf("请输入插入的数据：");SLTDataType data5 = 0;scanf("%d", &data5);InsertFrontByContent(&plist, data4, data5);SLTPrint(plist);//销毁链表Destroy_Method1(&plist);//Destroy_Method2(&plist);
}

🥤测试在指定节点后插入

void testInsertBack() {SLTNode* plist = testPush_Front_Back();//在指定结点后插入（通过序号指定节点）printf("在指定结点后插入（通过序号指定节点）\n");printf("请输入节点编号：");int input2 = 0;scanf("%d", &input2);printf("请输入插入的数据：");SLTDataType data6 = 0;scanf("%d", &data6);InsertBackBySerialNumber(&plist, input2, data6);SLTPrint(plist);//在指定结点后插入（内容->地址->找到结点）printf("在指定结点后插入（内容->地址->找到结点）\n");printf("请输入要插入位置的数据：");SLTDataType data7 = 0;scanf("%d", &data7);SLTNode* pos = FindByContent(plist, data7);printf("请输入插入的数据：");SLTDataType data8 = 0;scanf("%d", &data8);InsertBackByAddress(pos, data8);SLTPrint(plist);//在指定结点后插入（通过内容指定节点）printf("在指定结点后插入（通过内容指定节点）\n");printf("请输入要插入位置的数据：");SLTDataType data9 = 0;scanf("%d", &data9);printf("请输入插入的数据：");SLTDataType data10 = 0;scanf("%d", &data10);InsertBackByContent(&plist, data9, data10);SLTPrint(plist);//销毁链表Destroy_Method1(&plist);//Destroy_Method2(&plist);
}

🥤测试各种删除

void testPop() {SLTNode* plist = testPush_Front_Back();//测试头删printf("测试头删\n");PopFront(&plist);SLTPrint(plist);//测试尾删printf("测试尾删\n");PopBack(&plist);SLTPrint(plist);//删除指定节点的前一个节点printf("删除指定节点的前一个节点\n");printf("请输入指定节点内容：\n");SLTDataType data11 = 0;scanf("%d", &data11);SLTNode* pos1 = FindByContent(plist, data11);DeleteFrontNode(&plist, pos1);SLTPrint(plist);//删除指定位置节点printf("删除指定位置节点\n");printf("请输入指定节点内容：\n");SLTDataType data12 = 0;scanf("%d", &data12);SLTNode* pos2 = FindByContent(plist, data12);DeleteNode(&plist, pos2);SLTPrint(plist);//删除指定节点的后一个节点printf("删除指定节点的后一个节点\n");printf("请输入指定节点内容：\n");SLTDataType data13 = 0;scanf("%d", &data13);SLTNode* pos3 = FindByContent(plist, data13);DeleteAfterNode(pos3);SLTPrint(plist);//销毁链表Destroy_Method1(&plist);//Destroy_Method2(&plist);}

🥤主函数

测一个的时候其他三个注释掉，要不然会累死的O(∩_∩)O哈哈~😂

int main() {testPush_Front_Back();testInsertFront();testInsertBack();testPop();
}

🍟测试结果

🥤测试一：头插尾插

🥤测试二：在指定节点前插入节点

🥤测试三：在指定节点后插入节点

🥤测试四：各种删除

👻当前是有点小缺陷的，当通过指定内容找到节点时，如果遇到有多个相同数据的情况，会在第一个出现该数据的位置停下进行插入等操作，这是由于当前节点中的数据只是一个简单的数字，当以后节点内数据更多或每个节点都有自己的唯一标识时，就不会有这个缺陷了。

🌈把以上所有代码块连起来就是完整程序啦，最开始是头文件list.h，接下来是函数实现list.c，最后是测试文件test.c，其中分了4个函数。

🌈在插入和删除那块函数有点多，我把想到的全写上了，有点繁琐，大家主要借鉴思路哈🤣😂，如有错误请及时指正，感谢❤️