【数据结构】单链表（二）

🕗 发布于 2024-04-15 19:48 数据结构

1.查找数据

2.指定位置插入和删除节点

2.1 指定位置之前插入节点

我们接着上一篇【数据结构】单链表（一）-CSDN博客来继续实现单链表

1.查找数据

在SList.h中进行函数的声明

SLNode* SLfind(SLNode* pps, Type x);//查找

返回值是一个地址，如果找到，就返回这个数的地址，如果没找到，就返回NULL，参数就是链表首节点地址和要查找的数

在SList.c中进行函数的实现

首先我们可以再定义一个指针存放首节点地址，这样的话在后面的遍历链表时就不会改变pps的指向了

SLNode* SLfind(SLNode* pps, Type x)//查找
{
SLNode* pcur = pps;//新定义一个指针，指向首节点
}

然后就是循环遍历

SLNode* SLfind(SLNode* pps, Type x)//查找
{
SLNode* pcur = pps;//新定义一个指针，指向首节点
while (pcur)//pcur不能为空
{
if (pcur->data == x) //找到
return pcur;//直接返回地址
pcur = pcur->next;//没找到往后找
}
}

当跳出while循环时，证明没找到，此时pcur为空，我们直接返回NULL

SLNode* SLfind(SLNode* pps, Type x)//查找
{
SLNode* pcur = pps;//新定义一个指针，指向首节点
while (pcur)//pcur不能为空
{
if (pcur->data == x) //找到
return pcur;//直接返回地址
pcur = pcur->next;//没找到往后找
}
return NULL;//没找到
}

在test.c中测试一下

void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLNode* find = SLfind(plist, 2);
if (find == NULL)
printf("没找到\n");
else
printf("找到了\n");
}
int main()
{
//SListtest1();
//SListtest2();
SListtest3();
return 0;
}

自己测试的时候可以多测几次

2.指定位置插入和删除节点

上一篇我们说了头部尾部的插入和删除数据，现在我们来实现一下指定位置的插入和删除数据

2.1 指定位置之前插入节点

在SList.h中进行函数的声明

void SLInsert(SLNode** pps, SLNode* pos, Type x);//指定之前插

参数有三个：链表首节点的地址，指定的位置，要插入的数据

在SList.c中进行函数的实现

现在我们要在节点3前面插入一个节点，就要让节点2里面的next指向新节点，新节点里面的next指向节点3

我们先找pos的前一个结点，用循环遍历

void SLInsert(SLNode** pps, SLNode* pos, Type x)//指定之前插
{
assert(pps && *pps);
assert(pos);
SLNode* prev = *pps;//再定义一个指针变量初始指向首节点
while (prev->next != pos)
{
prev = prev->next;
}
}

跳出循环后此时prev指向pos前一个节点，然后让这些节点“手牵手”

void SLInsert(SLNode** pps, SLNode* pos, Type x)//指定之前插
{
assert(pps && *pps);
assert(pos);
SLNode* newnode = SLBuyNode(x);//插入的数据
SLNode* prev = *pps;//再定义一个指针变量初始指向首节点
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
    prev->next = newnode;
}

代码写到这里我们在分析一下pos为1时可不可行

这种情况下prev会一直往后走，直到走到最后一个节点，上面的代码在次情况下行不通

我们再分析一下pos为最后一个节点时可不可行

依旧是让节点3里面的next指向新节点，新节点里面的next指向节点4

经分析，上面的代码在这种情况下可行，所以不可行的就是pos为1的情况，我们单独把这种情况列出来，其实pos为1时也就是头插的情况

void SLInsert(SLNode** pps, SLNode* pos, Type x)//指定之前插
{
assert(pps && *pps);
assert(pos);
SLNode* newnode = SLBuyNode(x);//插入的数据
if (pos == *pps)
{
SLPushHead(pps, x);//直接调用头插代码
}
else//其他位置
{
SLNode* prev = *pps;//再定义一个指针变量初始指向首节点
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
        prev->next = newnode;
}
}

这就是完整的代码

在test.c中测试一下

void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLNode* find = SLfind(plist, 2);//找2
SLInsert(&plist, find, 11);//直接插在2前面
SLPrint(plist);//打印
}
int main()
{
SListtest3();
return 0;
}

看结果

其他情况有疑惑的话一定要自己测试运行一下

2.2 指定位置之后插入节点

在SList.h中进行函数的声明

void SLAfter(SLNode* pos, Type x);//指定之后插

这里只有两个参数，一个是指定位置，一个是要插入的值，这里我们不需要知道头节点，因为可以通过pos找到下一个节点，在指定位置之前插入数据的函数需要头节点是因为我们不能通过pos找到pos的前一个节点

在SList.c中进行函数的实现

void SLAfter(SLNode* pos, Type x)//指定之后插
{
assert(pos);
SLNode* newnode = SLBuyNode(x);//插入的数据
newnode->next = pos->next;
pos->next = newnode;
}

注意： newnode->next = pos->next; pos->next = newnode;这两句代码的顺序不可以交换，交换后是错的

在test.c中测试一下

void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLNode* find = SLfind(plist, 2);//找2
SLInsert(&plist, find, 11);//直接插在2前面
SLPrint(plist);//打印
SLAfter(find, 5);//插在2后面
SLPrint(plist);//打印
}
int main()
{
SListtest3();
return 0;
}

代码没有问题

2.3 删除指定位置节点

在SList.h中进行函数的声明

void SLErase(SLNode** pps, SLNode* pos);//删除pos节点

参数是二级指针，接收首节点地址，还有一个参数是要删除的节点

在SList.c中进行函数的实现

我们要先让pos的前一个节点指向pos的后一个节点，然后把pos这个节点销毁

既然要找pos的前一个节点，我们依旧是定义一个指针prev，初始为*pps，往后一个一个找，直到找到pos前一个节点

void SLErase(SLNode** pps, SLNode* pos)//删除pos节点
{
assert(pps && *pps);
assert(pos);
SLNode* prev = *pps;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}

如果此时链表只有一个节点，上面的代码可行吗？来分析一下

发现代码走不通，其实这种情况就是头删的情况，我们直接调用头删的代码就可以了

void SLErase(SLNode** pps, SLNode* pos)//删除pos节点
{
assert(pps && *pps);
assert(pos);
if (pos == *pps)//一个节点
{
SLPopHead(pps);
}
else//多个节点
{
SLNode* prev = *pps;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}

在test.c中测试一下

void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLNode* find = SLfind(plist, 7);//找7
SLErase(&plist, find);//删除指定位置节点
SLPrint(plist);//打印
}
int main()
{
SListtest3();
return 0;
}

删除成功

2.4 删除指定位置之后的节点

在SList.h中进行函数的声明

void SLPushAfter(SLNode* pos);//删除pos之后的节点

pos的后一个节点我们可以直接通过pos找到，就不需要头节点地址，所以一个参数就好了

在SList.c中进行函数的实现

还是先让pos这个节点找到它的下下个节点，然后再销毁pos后面的节点

这里呢我们需要一个临时变量存放pos->next的地址，然后再连接节点

我们先写一下代码，让pos和pos下下个节点相连

void SLPushAfter(SLNode* pos)//删除pos之后的节点
{
assert(pos);
assert(pos->next);
SLNode* temp = pos->next;
pos->next = temp->next;
}

然后销毁pos下一个节点并置空

void SLPushAfter(SLNode* pos)//删除pos之后的节点
{
assert(pos);
assert(pos->next);
SLNode* temp = pos->next;//临时变量
pos->next = temp->next;//连接
free(temp);//销毁
temp = NULL;//置空
}

在test.c中测试一下

void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLNode* find = SLfind(plist, 7);//找7
SLPushAfter(find);//删除指定位置后一个节点
    SLPrint(plist);//打印
}
int main()
{
SListtest3();
return 0;
}

3.销毁链表

跟顺序表一样，链表使用完之后也要销毁，链表由一个一个节点组成，所以也要一个一个销毁

在SList.h中进行函数的声明

void SLDestroy(SLNode** pps);//销毁

参数就是首节点地址

在SList.c中进行函数的实现

我们在销毁当前节点之前要把下一个节点的信息存起来

销毁空间

pcur后移到提前保存的next处

然后next后移，把当前的pcur销毁

就这样一直往后，直到pcur为空

代码来实现一下


void SLDestroy(SLNode** pps)//销毁
{
assert(*pps && pps);
SLNode* pcur = *pps;
while (pcur)
{
SLNode* next = pcur->next;//存下节点信息
free(pcur);//释放
pcur = next;//往后走
}
*pps = NULL;//不要忘了头节点此时没有置空，要置空
}

在test.c中测试一下

void SListtest3()
{
SLNode* plist = NULL;//空链表
SLPushBack(&plist, 1);//尾插
SLPushBack(&plist, 2);
SLPushHead(&plist, 6);//头插
SLPushHead(&plist, 7);
SLPrint(plist);//打印
SLDestroy(&plist);//销毁
SLPrint(plist);//打印
}
int main()
{
SListtest3();
return 0;
}

可以自己通过调试看结果，能看到更详细，打印出来看也可以

单链表实现就分享到这里，拜拜~

原文地址：https://blog.csdn.net/2402_82757055/article/details/137613666

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：java: 警告: 源发行版 17 需要目标发行版 17，java17 无效的目标发行
下一篇：蓝桥杯备考随手记: 二分查找

网络安全入门教程（非常详细）从零基础入门到精通_网路安全教程
1.入行网络安全这是一条坚持的道路，三分钟的热情可以放弃往下看了。2.多练多想，不要离开了教程什么都不会了，最好看完教程自己独立完成技术方面的开发。3.有时多百度，我们往往都遇不到好心的大神，谁会无聊
阅读更多2024-11-13
【MySQL】MySQL中的函数之JSON_UNQUOTE
在 MySQL 中，函数用于去除 JSON 值周围的双引号，并将其转换为普通的字符串或数值。这个函数特别适用于从 JSON 文档中提取的值，因为这些值通常会被包含在双引号中。
阅读更多2024-11-13
西门子S120伺服驱动器F1910故障报警原因分析及处理
西门子S120伺服驱动器F1910故障报警原因分析及处理
阅读更多2024-11-13
(不看后悔系列二)python网络爬虫爬取网络视频
Python网络爬虫带你爬取下载网络视频
阅读更多2024-11-13
elementUI input 禁止内容两端存在空格，或者是自动去除两端空格
项目中有需求：输入框中禁止内容两端存在空格，或者是自动去除两端空格。
阅读更多2024-11-13
JavaWeb——Web入门（7/9）-Tomcat-介绍（Tomcat 的简介：轻量级Web服务器，支持Servlet/JSP少量JavaEE规范）
比如我们前面介绍的 XML，以及我们后面要学习的 JDBC，这些都是 Java EE 的规范。还有像 Servlet、JSP 这样的技术，现在基于 Servlet 进行项目开发呢，基本上已经很少很少了
阅读更多2024-11-13
就是这个样的粗爆，手搓一个计算器：存储单位换算计算器
作为程序员，没有合适的工具，就得手搓一个：在线计算器，存储单位换算计算器，PC端，移动端均可适用。废话不多说，直接上代码。
阅读更多2024-11-13
关于我、重生到500年前凭借C语言改变世界科技vlog.18——内存函数
内存函数是用于的一组函数，它们可以对内存进行复制、移动、设置和比较等操作。这些函数主要在头文件中声明，其操作对象通常是字节序列，不管这些字节代表的是字符、整数还是其他数据类型。
阅读更多2024-11-13
Warped Universe游戏即将在Sui上推出，为玩家提供多样化的游戏体验
Warped Games利用Sui实现玩家拥有的资产和多类型游戏玩法。
阅读更多2024-11-13
测试用例设计方法之场景法
场景法也叫流程图法, 使用流程图描述用户的使用场景, 然后通过覆盖流程路径来设计测试用例。
阅读更多2024-11-13

【数据结构】单链表（二）

1.查找数据

2.指定位置插入和删除节点

2.1 指定位置之前插入节点

2.2 指定位置之后插入节点

2.3 删除指定位置节点

2.4 删除指定位置之后的节点

3.销毁链表

相关文章