数组结构-单链表删除+查找
【摘要】 05.尾删尾删可能要改变plist(如果删完了,plist要置空),传二级指针尾删:找到尾结点然后释放掉,为了防止野指针问题,还要找到上一个结点,把它的next指针置空。由于如果只有一个结点的时候,没有前一个结点。所以要单独判断只有一个结点时:释放掉第一个结点,然后把头指针置空 (注意优先级问题 *pphead就是第一个结点)多个结点时:01.使用两个指针变量,一个先走,一个后走,02....
05.尾删
尾删可能要改变plist(如果删完了,plist要置空),传二级指针
尾删:找到尾结点然后释放掉,为了防止野指针问题,还要找到上一个结点,把它的next指针置空。由于如果只有一个结点的时候,没有前一个结点。所以要单独判断
- 只有一个结点时:释放掉第一个结点,然后把头指针置空 (注意优先级问题 *pphead就是第一个结点)
- 多个结点时:01.使用两个指针变量,一个先走,一个后走,02.当前一个指向尾时,后一个指向尾的前一个结点。 **03.**然后释放掉尾结点,然后把上一个结点的next置空
//尾删
void SListPopBack(SLTNode** pphead)
{
assert(pphead); //这样只是保证传plist地址传成了空指针
//不仅要保证pphead不为空,还要保证链表不为空
assert(*pphead!= NULL);
//情况1:只有一个结点
//注意优先级问题: *pphead ->next == NULL //ERR
//要用括号括起来
if( (*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else //多个结点
{
//找到尾结点释放掉,并且还要把它的前一个结点的next置空,防止造成野指针
SLTNode* tail = *pphead;
SLTNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
//释放掉尾结点,然后把它的前一个结点置空
free(tail);
tail = NULL; //这条语句有没有都没关系,因为tail是函数内的局部变量,出了函数即销毁了
prev->next = NULL;
//使用一个指针
//SLTNode* tail = *pphead;
//如果tail的下一个结点的next为空:说明此时tail->next指向的就是尾结点
//while (tail->next->next != NULL)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
}
}
06.头删
头删要改变plist,所以要传二级指针
头删:先找到第二个结点,然后释放第一个结点,然后头指针指向第二个结点
如果只有一个结点上述思路也满足 此时第二个结点为NULL,此时头删相当于释放掉第一个结点后置空
//头删
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
//保证链表不为空 //保证链表不为空是*pphead != NULL 而不是(*pphead)->next !=NULL
//*pphead == plist头指针指向的就是第一个结点
assert(*pphead!=NULL);
//找到第二个结点,释放掉第一个结点,第二个结点成为新的头
//注意优先级问题: *pphead->next 要写成(*pphead)->next
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
//只有一个结点上述代码也符合
}
07.查找某个值在链表对应位置
遍历链表进行比较查找,找到了返回对应的结构体指针
由于查找不改变plist,所以可以传一级指针
//查找函数 找到了返回结点的地址 ->查找并不改变头指针,所以传值传址都可以
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
//链表为空,直接返回NULL
if (phead == NULL)
{
printf("链表为空,查找失败\n");
return NULL;
}
//遍历查找
SLTNode* cur = phead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
//找不到
return NULL;
}
假设查找的是多个重复数据
==思路==:找到了第一个位置之后,从该位置继续往后找,知道遍历完链表找不到了
void Test3()
{
SLTNode* plist = NULL; //头指针先置空
SListPushBack(&plist, 1);
SListPushBack(&plist, 3);
SListPushFront(&plist, 3);
SListPushFront(&plist, 4);
SListPushFront(&plist, 3);
SListPushFront(&plist, 3);
SListPrint(plist);//3 3 4 3 1 3
//假设要查找的是3
SLTNode* pos = SListFind(plist, 3);
//pos位置就是值为3的结点
int i = 1;
while (pos)
{
printf("%d个结点为2的地址为:%p\n", i, pos);
//从pos的下一个位置开始再次寻找,这样就不用担心重复,
//直到找不到了,pos为空,跳出循环
pos = SListFind(pos->next, 3);
i++;
}
}
找到之后,还可以修改结点对应的值
SLTNode* pos = SListFind(plist, 2);
//如果pos不为空,说明找到了
if (pos)
{
//查找还可以修改
pos->data = 30;
SListPrint(plist);
}
else
{
printf("找不到\n");
}
08.在pos位置后插入
思路:
//在pos位置后插入
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{
//相当于在pos位置尾插
SLTNode* newnode = BuyList(x);
//找到pos位置的下一个结点
SLTNode* next = pos->next;
//pos的next链接新结点 新结点的next链接pos的下一个位置
pos->next = newnode;
newnode->next = next;
}
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)