单链表（二）

3.打印单链表

void SLTPrint(SLTNode* phead)
{
	SLTNode* tail = phead;
    //遍历链表
	while (tail)
	{
		printf("%d ", tail->val);
		tail = tail->next;
	}
	printf("\n");
}

4.尾插

//必须传二级指针，这样当头节点为空时能够改变头节点
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	SLTNode* tail = *pphead; 
	SLTNode* newnode = BuySLTNode(x); //申请新结点
	if (*pphead == NULL) //如果链表为空
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

尾插时，要注意当单链表的头结点为空的时候，要先将新结点作为头结点。因为当头结点为空时，需要改变头指针，所以传过来的为二级指针（也可以使用一级指针，不过此时要有返回值），要想改变SLTNode*的值，就要传递它的地址即SLTNode**类型，如果只传SLTNode*指针无法改变头节点，因为形参的改变不会影响到实参。

5.尾删

//传二级指针，如果只剩头节点时能够有效删除头节点
void SLTPopBack(SLTNode** pphead)//尾删
{
	assert(*pphead);//判断链表不为空
	if ((*pphead)->next==NULL)
	{
		free(*pphead);//释放空间
		*pphead = NULL;//置空
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
        //遍历找到最后一个结点
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);//将最后一个结点的空间释放
		prev->next = NULL;//置空
	}
}

尾删时也要注意区分是否为头结点；同时注意删除后，要将其置空prev->next = NULL。

6.头插

//头插时也要注意是不是头节点为空，传二级指针
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
	SLTNode* newnode = BuySLTNode(x);//申请新节点
	newnode->next = *pphead;
	*pphead = newnode;
}

7.头删

void SLTPopFront(SLTNode** pphead)//头删
{
	assert(*pphead);//断言
	SLTNode* nextnode = (*pphead)->next;//记录头节点的下一个结点
	free(*pphead);//释放空间
	*pphead = nextnode;//头节点为下一个结点
}

头插和头删是单链表的优势，尾插和尾删是顺序表的优势。同时在尾删时注意将*pphead加上括号用来区分优先级，否则会报错。

8.查找某个结点

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某个数并返回所在位置
{
	SLTNode* tail = phead;
    //遍历
	while (tail)
	{
		if (tail->val == x)
		{
			return tail;
		}
		tail = tail->next;
	}
	return NULL;
}

注意循环条件，当循环条件写为while(tail->next)时，会有空指针的风险，同时还会漏掉最后一个结点。

9.在某个结点后面插入

void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某个结点的后面插入某个数
{
	assert(pos);//断言
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* tail = pos->next;
    //插入新节点
	pos->next = newnode;
	newnode->next = tail;
}

10.在某个结点前面插入

void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)//在某个结点的前面插入某个数
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
    //如果pos是头节点，调用头插函数
	if (pos == *pphead)
	{
		/*newnode->next = *pphead;
		*pphead = newnode;*/
		SLTPushBack(pphead, x);
	}
	else
	{
        //遍历然后插入结点
		SLTNode* tail = *pphead;
		while (tail->next != pos)
		{
			tail = tail->next;
		}
        //插入结点
		tail->next = newnode;
		newnode->next = pos;
	}
}

11.删除某个位置后面的结点

void SLTEraseAfter(SLTNode* pos)//删除pos位置之后的那个位置
{
	assert(pos);
    //结点后面为空结点，直接返回
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
        //删除
		SLTNode* tail = pos->next;
		pos->next = tail->next;
		free(tail);//释放空间
	}
}

12.删除某个结点

void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
{
	assert(pos);
	SLTNode* tail = *pphead;
	if (pos == *pphead)
	{
		SLTNode* nextNode = (*pphead)->next;
		free(*pphead);
		*pphead = nextNode;
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = pos->next;
		free(pos);
	}
}

13.销毁单链表

void SLTDestroy(SLTNode** pphead)//销毁
{
	assert(*pphead);
	SLTNode* tail = *pphead;
	
    //遍历，一个一个销毁
	while (tail)
	{
		SLTNode* next = tail->next;
		free(tail);
		tail = next;
	}
	*pphead = NULL;
}

注意最后要将头结点置空。