数组结构-单链表删除+查找

举报
芒果_Mango 发表于 2022/02/26 21:32:37 2022/02/26
【摘要】 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++;
	}
}

image-20211025210651416


找到之后,还可以修改结点对应的值

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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。