> 作者简介:დ旧言~,目前大一,现在学习Java,c,c++,Python等
> 座右铭:松树千年终是朽,槿花一日自为荣。
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言
前面我们已经学习了顺序表,顺序表可以存储动态的数据,但是一旦元素过少,而又要开辟空间,这样就造成空间的浪费,为了解决这类问题,人们发现了单链表,把一个一个元素以链子的形式存储,那单链表如何实现呢,今天咱们就实现一下--《单链表》。
🌙主体
咱们从三个方面实现单链表,动态管理,头插头删尾插尾删,增删查改。
在程序中为了实现顺序表,需要创建头文件Slist.h ,创建源文件Test.c,Slist.c。
🌠动态管理
💤初始化动态单链表
既然实现单链表,初始化动态的单链表必不可少,从两个方面实现初始化动态的单链表。
1.首先我们在Slist.h定义动态的单链表,省得我们再定义节点(单链表)。
//重匿名方法来定义数据类型 typedef int SLTDataType; //定义动态的单链表 typedef struct SListNode { //定义数据类型 SLTDataType data; //指向下一个元素 struct SListNode* next; }SLTNode;
2.对单链表进行初始化。(这里和顺序表相似)
💦这里采用malloc开辟空间
💦采用预指令判断空间是否开辟完成(没有开辟空间返回-1)
💦之后就是简单的初始数据
💦记得返回值
//初始化 SLTNode* BuySListNode(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 SLTDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; //比cur->next!=NULL更好一些 while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
🌠头插头删尾插尾删
💤打印元素
打印元素就太简单了,直接上代码
//打印数据 void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); //找到下一个地址 cur = cur->next; } printf("NULL\n"); }
💤头插
💦1.因为需要改变结构体的指针,因此需要二级指针来接收
💦2.因为头插是一个元素,因此需要初始化
💦3.指向开始
//头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { //初始化 SLTNode* newnode = BuySListNode(x); //改变地址指向 newnode->next = *pphead; //指向开始 *pphead = newnode; }
💤尾插(重点)
💦1.因为需要改变结构体的指针,因此需要二级指针来接收
💦2.因为尾插是一个元素,因此需要初始化
💦3.如果单链表没有元素,直接把头赋值给pphead
💦4.如果单链表有元素,就需要找到尾,再把开辟好的newnode赋值给tail->next
//尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { //初始化 SLTNode* newnode = BuySListNode(x); //判断pphead == NULL if (*pphead == NULL) { //改变的结构体的指针,所以要用二级指针 *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next != NULL) { //找到尾 tail = tail->next; } //改变的结构体,用结构体的指针即可(指向空指针) tail->next = newnode; } }
💤头删(重点)
头删还是比较简单的,这里就需要注意一点(单链表为空时,不为空时)
//头删 void SLTPopFront(SLTNode** pphead) { //空时 assert(*pphead); //非空时 指向下一个 SLTNode* newhead = (*pphead)->next; //释放内存 free(*pphead); *pphead = newhead; }
💤尾删(重点)
💦1.一个节点(一个元素)直接把头指向空(NULL)
💦2.一个节点以上(一个元素以上),先找到尾,再释放内存,最后尾指向空(NULL)
//尾删 void SLTPopBack(SLTNode** pphead) { //不能为空 assert(*pphead); // 1、一个节点 if ((*pphead)->next == NULL) { //释放空间 free(*pphead); //指向空 *pphead = NULL; } // 2、一个以上节点 else { //找到尾 SLTNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } //释放空间 free(tail->next); //指向空 tail->next = NULL; } }
🌠增删查改
💤查找下标
这个函数是为了增删查改服务的函数,这个函数还是比较好实现的。
//查找下标 需要给尾phead参数 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
💤在pos之前插入x
💦1.因为需要改变结构体的指针,因此需要二级指针来接收
💦2.先断言(pphead和pos)
💦3.如果只有一个元就头插
💦4.再找到pos之前的地址
💦5.初始化插入的元素
💦6.改变元素的地址
//在pos之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //断言 assert(pphead); assert(pos); //如果只有一个元素就头插 if (pos == *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //初始化 SLTNode* newnode = BuySListNode(x); //前一个元素地址指向插入的元素 prev->next = newnode; //插入的元素指向后一个元素 newnode->next = pos; } }
💤在pos之后插入x
这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点
//在pos以后插入x void SLTInsertAfter(SLTNode* pos, SLTDataType x) { //断言 assert(pos); //初始化 SLTNode* newnode = BuySListNode(x); pos->next = newnode; newnode->next = pos->next; }
💤删除pos位置
💦1.因为需要改变结构体的指针,因此需要二级指针来接收
💦2.先断言(pphead和pos)
💦3.如果只有一个元就头删
💦4.再找到pos的地址
💦5.修改pos的地址
💦6.释放内存
//删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos) { //断言 assert(pphead); assert(pos); //如果只有一个元素就头删 if (pos == *pphead) { SLTPopFront(pphead); } else { //找删除的地址 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //指向后一元素 prev->next = pos->next; //释放内存 free(pos); } }
💤删除pos的后一个位置
这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点
//删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos) { //断言 assert(pos); //检查pos是否是尾节点 assert(pos->next); //改变地址 SLTNode* posNext = pos->next; pos->next = posNext->next; //释放内存 free(posNext); posNext = NULL; }
💤单链表结点修改
其实这个函数也没啥技术含量, 这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点。
// 单链表结点修改 void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x) { SLTNode* cur = phead; while (cur != pos) { cur = cur->next; assert(cur); } pos->data = x; }
🌙代码总结
🌠主函数
//包含头文件 #include"Slist.h" void TestSList1() { int n; printf("请输入链表的长度:"); scanf("%d", &n); printf("\n请依次输入每个节点的值:"); SLTNode* plist = NULL; for (size_t i = 0; i < n; i++) { int val; scanf("%d", &val); SLTNode* newnode = BuySListNode(val); //头插 newnode->next = plist; //指向头 plist = newnode; } //打印数据 SLTPrint(plist); //这里头插本质相似 //SLTPushBack(&plist, 10000); //打印数据 SLTPrint(plist); } void TestSList2() { //初始化 SLTNode* plist = NULL; //头插 SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); //打印数据 SLTPrint(plist); SLTPushFront(&plist, 10); SLTPushFront(&plist, 20); SLTPushFront(&plist, 30); SLTPushFront(&plist, 40); //打印数据 SLTPrint(plist); } void TestSList3() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); //SLTPopBack(&plist); //SLTPrint(plist); } void TestSList4() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); SLTPrint(plist); SLTPopFront(&plist); //SLTPopFront(&plist); SLTPrint(plist); } void TestSList5() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); SLTNode* pos = SLTFind(plist, 40); if (pos) { pos->data *= 10; } SLTPrint(plist); int x; scanf("%d", &x); pos = SLTFind(plist, x); if (pos) { SLTInsert(&plist, pos, x * 10); } SLTPrint(plist); } void TestSList6() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); int x; scanf("%d", &x); SLTNode* pos = SLTFind(plist, x); if (pos) { //SLTInsertAfter(pos, x * 10); } SLTPrint(plist); } void TestSList7() { SLTNode* plist = NULL; SLTPushBack(&plist, 1); SLTPushBack(&plist, 2); SLTPushBack(&plist, 3); SLTPushBack(&plist, 4); SLTPushBack(&plist, 5); SLTPrint(plist); int x; scanf("%d", &x); SLTNode* pos = SLTFind(plist, x); if (pos) { //SLTErase(&plist, pos); //SLTEraseAfter(pos); pos = NULL; } SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); //SLTPopFront(&plist); //SLTPrint(plist); } int main() { TestSList7(); return 0; }
🌠SqList.h头文件
//使用一些头文件 #include<stdio.h> #include<stdlib.h> #include<assert.h> //重匿名方法来定义数据类型 typedef int SLTDataType; //定义动态的单链表 typedef struct SListNode { //定义数据类型 SLTDataType data; //指向下一个元素 struct SListNode* next; }SLTNode; //初始化 SLTNode* BuySListNode(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); //在pos之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在pos以后插入x void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos的后一个位置 void SLTInsertAfter(SLTNode* pos); //销毁链表 void SLTDestory(SLTNode** pphead); // 单链表结点修改 void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x);
🌠SqList.c源文件
#define _CRT_SECURE_NO_WARNINGS 1 //包含头文件 #include"Slist.h" //初始化 SLTNode* BuySListNode(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) { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); //找到下一个地址 cur = cur->next; } printf("NULL\n"); } //头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { //初始化 SLTNode* newnode = BuySListNode(x); //改变地址指向 newnode->next = *pphead; //指向开始 *pphead = newnode; } //尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { //初始化 SLTNode* newnode = BuySListNode(x); //判断pphead == NULL if (*pphead == NULL) { //改变的结构体的指针,所以要用二级指针 *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next != NULL) { //找到尾 tail = tail->next; } //改变的结构体,用结构体的指针即可(指向空指针) tail->next = newnode; } } //头删 void SLTPopFront(SLTNode** pphead) { //空时 assert(*pphead); //非空时 SLTNode* newhead = (*pphead)->next; free(*pphead); *pphead = newhead; } //尾删 void SLTPopBack(SLTNode** pphead) { //不能为空 assert(*pphead); // 1、一个节点 if ((*pphead)->next == NULL) { //释放空间 free(*pphead); //指向空 *pphead = NULL; } // 2、一个以上节点 else { //找到尾 SLTNode* tail = *pphead; while (tail->next->next) { tail = tail->next; } //释放空间 free(tail->next); //指向空 tail->next = NULL; } } //查找下标 需要给尾phead参数 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos之前插入x void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //断言 assert(pphead); assert(pos); //如果只有一个元素就头插 if (pos == *pphead) { SLTPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //初始化 SLTNode* newnode = BuySListNode(x); //前一个元素地址指向插入的元素 prev->next = newnode; //插入的元素指向后一个元素 newnode->next = pos; } } //在pos以后插入x void SLTInsertAfter(SLTNode* pos, SLTDataType x) { //断言 assert(pos); //初始化 SLTNode* newnode = BuySListNode(x); pos->next = newnode; newnode->next = pos->next; } //删除pos位置 void SLTErase(SLTNode** pphead, SLTNode* pos) { //断言 assert(pphead); assert(pos); //如果只有一个元素就头删 if (pos == *pphead) { SLTPopFront(pphead); } else { //找删除的地址 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } //指向后一元素 prev->next = pos->next; //释放内存 free(pos); } } //删除pos的后一个位置 void SLTEraseAfter(SLTNode* pos) { //断言 assert(pos); //检查pos是否是尾节点 assert(pos->next); SLTNode* posNext = pos->next; pos->next = posNext->next; free(posNext); posNext = NULL; } // 单链表结点修改 void SLTModify(SLTNode* phead, SLTNode* pos, SLTDataType x) { SLTNode* cur = phead; while (cur != pos) { cur = cur->next; assert(cur); } pos->data = x; } //销毁链表 void SLTDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; //比cur->next!=NULL更好一些 while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = NULL; }
🌟结束语
今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小说手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。