> 作者简介:დ旧言~,目前大一,现在学习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;
- }
💦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;
- }
- }
这里和上面的代码相似,这里主函数(Test.c)就会调用查找元素的函数,这里就简单点
- //在pos以后插入x
- void SLTInsertAfter(SLTNode* pos, SLTDataType x)
- {
- //断言
- assert(pos);
-
- //初始化
-
- SLTNode* newnode = BuySListNode(x);
- pos->next = newnode;
- newnode->next = pos->next;
- }
💦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);
- }
- }
这里和上面的代码相似,这里主函数(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;
- }
- //使用一些头文件
- #include
- #include
- #include
-
- //重匿名方法来定义数据类型
- 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);
- #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;
- }
今天内容就到这里啦,时间过得很快,大家沉下心来好好学习,会有一定的收获的,大家多多坚持,嘻嘻,成功路上注定孤独,因为坚持的人不多。那请大家举起自己的小说手给博主一键三连,有你们的支持是我最大的动力💞💞💞,回见。