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);肯定会报错,访问冲突,无权限修改内存