92.【C语言】数据结构之单向链表的查找,中间插入和删除,销毁
目录
1.链表的查找函数
2.链表的修改函数
3.链表的中间插入函数
1.在pos之前插入:SLTInsertBefore函数
1.借助头指针pphead
示意图
代码示例(写入SList.c)
头文件添加SLTInsertbefore的声明
main.c的部分代码改为
1.测试中间插入
2.测试头部插入
3.测试pos为NULL的情况
2.不借助头指针pphead
代码示例
2.在pos之后插入:SLTInsertAfter函数
代码示例
错误写法
4.链表的中间删除函数
示意图(非头删)
1.在pos之前删除:SLTEraseBefore函数
1.借助头指针pphead
代码示例
头文件添加SLTErase的声明
main.c的部分代码改为
运行结果
2.不借助头指针pphead
示意图
代码示例
2.在pos之后删除:SLTEraseBeforeAfter函数
代码示例
4.链表的销毁函数
代码示例(写入SList.c)
main.c部分代码改为
运行结果
错误写法
VS2022+debug+x86环境下调试错误代码
承接91.【C语言】数据结构之链表的头删和尾删文章
这里均以单向链表做演示
1.链表的查找函数
代码示例(遍历查找)
void SLTFind(SLTNode* phead, SLTDataType find)
{SLTNode* cur = phead;//初始化cur指针while (cur){if (cur->data == find){return cur;}//找不到则将下一个节点的地址赋值给curcur = cur->next;}//从头找到尾没找到,则返回NULLreturn NULL;
}2.链表的修改函数
有了查找函数,就可以轻松实现修改函数
修改函数的策略:先查某个节点的数据,再对这个数据进行修改
代码示例(写入SList.c)
void SLTMod(SLTNode* phead, SLTDataType find, SLTDataType mod)
{//将需要修改数据的节点的地址赋值给tar_p//tar_p为目标指针(target_pointer)SLTNode* tar_p = SLTFind(phead, find);//修改目标节点的数据tar_p->data = mod;
}main.c部分代码改为
void TestSList1()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTFind(plist, 3);SLTMod(plist, 3, 5);SLTPrint(plist);
}执行结果
3.链表的中间插入函数
插入包括:在pos之前插入和在pos之后插入
1.在pos之前插入:SLTInsertBefore函数
1.借助头指针pphead
示意图
在pos之前插入,要找pos前的节点,需要参数SLTNode* phead
代码示例(写入SList.c)
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos,SLTDataType x)
{//判断pos是否为NULLassert(pos);//pphead不能为NULLassert(pphead);//判断pos是否为头指针,如果是则调用现有的函数if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//初始化新节点SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}注意:
1.一开始就要判断判断pos是否为NULL
2.将pos分是否为头指针两种情况讨论
如果不判断pos是否为头指针,直接硬插入的话,会报错
分析原因:当pos为头指针时,pos和prev指针存储的内容是一样的,第一次循环条件prev->next!=pos成立,错过了prev->next==pos的机会,则while会一直循环,直到prev为NULL(x86下存储的00 00 00 00),出现NULL->next是不合法的,因此报错
3.pphead不能为NULL(即plist存储的地址不能为NULL),plist可以为NULL(空链表)
头文件添加SLTInsertbefore的声明
main.c的部分代码改为
1.测试中间插入
void TestSList1()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTNode* pos = SLTFind(plist, 3);SLTInsertBefore(&plist, pos, 5);SLTPrint(plist);
}
2.测试头部插入
SLTNode* pos = SLTFind(plist, 1); 
3.测试pos为NULL的情况
均可以实现
2.不借助头指针pphead
只需要交换即可
代码示例
void SLTInsertBefore(SLTNode** pos, SLTDataType x)
{SLTNode* newnode = BuySLTNode(x);//用中间变量n_tmp(全称next_tmp)交换SLTDataType tmp = (*pos)->data;(*pos)->data = newnode->data;newnode->data = tmp;//找pos的下一个节点,暂存到n_tmpSLTNode* n_tmp = (*pos)->next;//变动指针(*pos)->next = newnode;newnode->next = n_tmp;
}头插和尾插均可
2.在pos之后插入:SLTInsertAfter函数
代码示例
void SLTInsertAfter(SLTNode* pos,SLTDataType x)
{assert(pos);//pos不可为NULLSLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}错误写法
void SLTInsertAfter(SLTNode* pos,SLTDataType x)
{assert(pos);//pos不可为NULLSLTNode* newnode = BuySLTNode(x);pos->next = newnode;newnode->next = pos->next;
}反过来写会出问题,比如想在d2节点后插入新节点
这样做是无效的
4.链表的中间删除函数
示意图(非头删)
1.在pos之前删除:SLTEraseBefore函数
1.借助头指针pphead
代码示例
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead == pos){SLTPopFront(pphead);}else{//找pos的前一个SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}注意:
1.断言pphead,*pphead(即plist)和pos
2.头删直接调用SLTPopFront函数
3.不采取pos = NULL;,SLTErase中的pos为形参,没有办法真正为删除的节点含有的指针置NULL,应该在main.c中操作
头文件添加SLTErase的声明
main.c的部分代码改为
void TestSList1()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTNode* pos = SLTFind(plist, 3);SLTEraseBefore(&plist,pos);pos = NULL;SLTPrint(plist);
}注意pos = NULL;
运行结果
2.不借助头指针pphead
示意图
代码示例
void SLTEraseBefore(SLTNode** pos)
{assert((*pos)->next);(*pos)->data = ((*pos)->next)->data;(*pos)->next = ((*pos)->next)->next;
}
//或写成下面这样
void SLTEraseBefore(SLTNode* pos)
{assert(pos->next);pos->data = (pos->next)->data;pos->next = (pos->next)->next;
}注意:此方法有缺陷,不能尾删,因此断言
2.在pos之后删除:SLTEraseBeforeAfter函数
代码示例
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//不为空链表assert(pos->next);//不为末尾节点SLTNode* delete = pos->next;//也可以写成pos->next = delete->next;pos->next = (pos->next)->next;free(delete);delete = NULL;
}注意:不可以不写SLTNode* delete = pos->next;,一旦pos->next被修改后,要删除的节点的指针会丢失,因此要先用结构体指针delete保存
4.链表的销毁函数
代码示例(写入SList.c)
采用双指针法
void SLTDestory(SLTNode* phead)
{SLTNode* p1 = phead;while (p1){SLTNode* p2 = p1->next;free(p1);p1 = p2;}
}注:
1.p1相当于慢指针,p2相当于快指针
2.一定先保存p1->next才能free(p1);防止p1->next值被操作系统修改从而找不到下一个节点的地址!
main.c部分代码改为
void TestSList1()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);SLTDestory(plist);plist = NULL;//不能在SLTDestory内置NULL,形参的改变不影响实参
}注:如果不想在main.c中手动为plist置空,可以修改SLTDestory(&plist);
void SLTDestory(SLTNode** pphead)
{assert(pphead);SLTNode* p1 = *pphead;while (p1){SLTNode* p2 = p1->next;free(p1);p1 = p2;}*pphead = NULL;
}运行结果
错误写法
void SLTDestory(SLTNode* phead)
{SLTNode* p1 = phead;while (p1){SLTNode* p2 = p1;free(p1);p1 = p2->next;}
}对free的本质认识不清楚,free函数是将指针所指向的内存空间的使用权交还给操作系统,操作系统会改变内存空间的值,并没有改变指针的值,因此p2->next会变成野指针
VS2022+debug+x86环境下调试错误代码
SLTNode* p2 = p1;执行后
free(p1);执行后
p1->next被操作系统修改成0xdddddddd,p1->next为野指针
第二次执行完SLTNode* p2 = p1;后
显然再次执行free(p1);肯定会报错,访问冲突,无权限修改内存
