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

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;
}