数据结构——单链表详解（超详细）（2）

前言：

  上一篇文章小编简单的介绍了单链表的概念和一些函数的实现，不过为了保证文章的简洁，小编把它分成了两篇来写，这一篇小编紧接上一篇文章继续写单链表函数功能的实现：

目录：

1.单链表剩余函数的编写

1.1.单链表查找数据

1.2.在指定位置之前插入数据

1.3.删除指定结点

1.4.在指定位置之后插入数据

1.5.删除指定位置之后的结点

1.6.单链表的销毁

2.完整的代码呈现

正文：

1.单链表剩余函数的编写

1.1.单链表查找数据

//查找

SLTNode* SLTFind(SLTNode* phead, SLdate x);

  对于单链表的查找数据，这就类似顺序表的查找数据，我们要遍历所有的单链表，直到找到我们想要的数据位置，加入没有我们想要的数据，那么我们可以直接返回一个空地址就好了，此时我们不必再传单链表指针的地址了，因为我们本质上并没有对头结点进行改变 ，所以我们仅需把头节点传过去就可以，在函数内部，我们想要遍历顺序表，就要采用循环，来进行一个一个结点的查找，下面是代码呈现：

SLTNode* SLTFind(SLTNode* phead, SLdate x)
{
	SLTNode* pour = phead;
	while (pour)
	{
		if (pour->date == x)
		{
			return pour;
		}
		pour = pour->next;
	}
	return NULL;
}

 1.2.在指定位置之前插入数据

    这里我们可以用到我们上面用到的查找函数，因为它是返回的结点，所以我们可以通过它来确定我们想要的指定位置，因为单链表只可以往后一步一步的走，而不能往前找数据，所以我们得先确认我们想要找的位置，下面我们涉及指定位置的时候，都要引用一下查找指定位置这个函数，下面我们来进行这个函数的讲解，这个函数其实也分为两种情况

  第一种情况是指定位置就是头结点，此时这就类似于我们之前写过的头插函数，我们直接引用头插函数就可以实现这个功能。

  第二种情况就是普通情况，我们要在指定位置之前插入数据，所以我们需要找到指定位置之前的数据，所以这里我们要用用到头结点，并且用到前面讲的创建新结点的函数（因为此文章涉及了不少插入数据的函数，所以我会把创建新结点的代码再写一遍！），我们让一个结点放入头结点数据，然后一步一步往后走，直到走到指定位置之前，之后我们可以讲新节点的下一个结点设置为指定结点，然后再把之前指定位置之前的结点的下一个结点设置为新结点，这里我们便可以完成在指定位置之后插入数据，下面小编先给上图文解释：

新结点的创建：

SLTNode* SLTbuynode(SLdate x)
{
	SLTNode* pour = (SLTNode*)malloc(sizeof(SLTNode));
	assert(pour);
	pour->date = x;
	pour->next = NULL;
	return pour;
}

头插函数： 

void SLTPushFront(SLTNode** pphead, SLdate x)
{
	assert(pphead);
	SLTNode* newnode = SLTbuynode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

函数部分：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLdate x)
{
	assert(pos && pphead && *pphead);
	if (pos == *pphead)
	{
		SLTPushFront(pphead,x);   //这个是头节点就是pos的特殊情况，我们在指定位置之前插入数据的时候，是会先找到指定位置之前的数据以及之后的，头节点的话找不到数据了
	}
	else
	{
		SLTNode* newnode = SLTbuynode(x);
		SLTNode* pour = *pphead;
		SLTNode* pur = NULL;
		while (pour != pos)
		{
			pur = pour;
			pour = pour->next;
		}
		assert(pur);
		newnode->next = pour;
		pur->next = newnode;
	}

1.3.删除指定结点

  删除指定结点的操作，同样也和上面的函数一样，我们也分为两种情况进行讨论：

  第一种情况就是我们想要删除的指定节点就是头结点，此时我们只需要调用一下头删函数就可以实现。

  第二种情况自然就是普通情况，此时我们依旧需要用到头结点，因为我们需要知道指定结点之前的结点，之后我们只需要让前一个结点的下一个结点直接指向指定结点的下一个结点，之后我们在把指定节点给释放掉，就可以实现指定节点删除操作，下面小编先给上图文解释：

头删函数：

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pour = *pphead;
	*pphead = (*pphead)->next;
	free(pour);
	pour = NULL;
}

删除指定结点函数：

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead && pos <= *pphead);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* pour = *pphead;
		SLTNode* pur = NULL;
		while (pour != pos)
		{
			pur = pour;
			pour = pour->next;
		}
		assert(pur);
		pur -> next = pur->next -> next;
		free(pour);
		pour = NULL;
	}
}

1.4.在指定位置之后插入数据

  小编在上面已经讲述了指定位置之前如何插入数据了，那么现在可以讲述在指定位置之后插入数据了，这个其实比上面那个简单多了，因为此时我们不需要用到指定位置之前的结点了，所以我们不必在使用头结点了，此时我们依然需要先创建一个新节点，之后我们在讲新结点之后的结点变为我们指定位置之后的结点，指定位置之后的结点·在指向新节点，这里就可以实现在指定位置之后插入新数据了，下面小编先给上图文解释，再给上代码呈现： 

void SLTInsertAfter(SLTNode* pos, SLdate x)
{
	assert(pos);
	SLTNode* newnode = SLTbuynode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

1.5.删除指定位置之后的结点

  有插入必会有删除，下面我们将要讲述最后一个重要的函数，那么就是删除指定位置之后的结点，这个，同样也是非常的简单，我们只需要把指定结点的下一个结点变为下一个的下一个的结点，再把原来指定位置之后的结点释放掉就好了，下面我们直接给出图像说明：

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* pour = pos -> next;
	pos->next = pos->next->next;
	free(pour);
	pour = NULL;
}

1.6.单链表的销毁

  单链表有创建，自然就会有销毁，单链表的销毁也不算很难，毕竟难的部分都在上面，轻舟已过万重山，对于单链表的销毁其实就是把每个结点给free掉，我们可以设置一个指针作为头结点，在设置一个指针用来给予上一个指针，每销毁完一个结点，我们把第二个指针的内容给予第一个指针，然后让第二个指针继续往后走，这样我们通过循环的知识可以做到每个结点的删除，循环结束完以后，别忘了对头结点进行销毁，这样我们便可以完成对于单链表的销毁了，下面直接给上代码：

void SListDestroy(SLTNode** pphead)
{
	assert(*pphead && pphead);
	SLTNode* pour = *pphead;
	while (pour)
	{
		SLTNode* next = pour->next;
		free(pour);
		pour = next;
	}
	*pphead = NULL;
}

2.完整的代码呈现

  现在，小编已经把单链表大部分内容给讲完了，但单链表实现的功能远不止这些，感兴趣的读者朋友可以再继续探索，小编这里给上大家单链表的完整代码：

SList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLdate;   //方便后面整体类型的改变


//创立一个单链表
typedef struct Slist {
	//先设置一个类型
	SLdate date;
	struct Slist* next;   //存放下一个节点的地址
}SLTNode;



//链表的打印
void SLTprintf(SLTNode* phead);

//开始正式环节了
//尾插
void SLTPushBack(SLTNode** pphead, SLdate x);

//头插
void SLTPushFront(SLTNode** pphead, SLdate x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删

void SLTPopFront(SLTNode** pphead);

//查找

SLTNode* SLTFind(SLTNode* phead, SLdate x);

//在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLdate x);

//删除pos节点

void SLTErase(SLTNode** pphead, SLTNode* pos);


//在指定位置以后插入数据

void SLTInsertAfter(SLTNode* pos, SLdate x);

//删除pos之后的节点

void SLTEraseAfter(SLTNode* pos);


//销毁链表
void SListDestroy(SLTNode** pphead);

SList.c

#include"SList.h"
void SLTprintf(SLTNode* phead)
{
	SLTNode* pour = phead;    //这么做是为了保证头节点不会发生改变
	while (pour)
	{
		printf("%d->", pour->date);
		pour = pour->next;
	}
	printf("NULL\n");
}   //这个操作是打印单链表的数据


SLTNode* SLTbuynode(SLdate x)
{
	SLTNode* pour = (SLTNode*)malloc(sizeof(SLTNode));
	assert(pour);
	pour->date = x;
	pour->next = NULL;
	return pour;
}

void SLTPushBack(SLTNode** pphead, SLdate x)
{
	//首先可以先建一个函数，这个函数是来开辟一个新节点的（后面想要插入直接调用就好了）
	assert(pphead);
	SLTNode * p = SLTbuynode(x);
	if (*pphead == NULL)  //首先判断
	{
		*pphead = p;
	}
	else
	{
		SLTNode* pour = *pphead;
		while (pour -> next)
		{
			pour = pour->next;
		}
		pour->next = p;
	}
}



void SLTPushFront(SLTNode** pphead, SLdate x)
{
	assert(pphead);
	SLTNode* newnode = SLTbuynode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}



void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		*pphead = NULL;
	}
	else
	{
		SLTNode* pour = *pphead;
		SLTNode* plist = NULL;
		while (pour->next)
		{
			plist = pour;
			pour = pour->next;
		}
		plist->next = NULL;
		free(pour);
		pour = NULL;
	}
}



void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pour = *pphead;
	*pphead = (*pphead)->next;
	free(pour);
	pour = NULL;
}



SLTNode* SLTFind(SLTNode* phead, SLdate x)
{
	SLTNode* pour = phead;
	while (pour)
	{
		if (pour->date == x)
		{
			return pour;
		}
		pour = pour->next;
	}
	return NULL;
}


void SLTInsert(SLTNode** pphead, SLTNode* pos, SLdate x)
{
	assert(pos && pphead && *pphead);
	if (pos == *pphead)
	{
		SLTPushFront(pphead,x);   //这个是头节点就是pos的特殊情况，我们在指定位置之前插入数据的时候，是会先找到指定位置之前的数据以及之后的，头节点的话找不到数据了
	}
	else
	{
		SLTNode* newnode = SLTbuynode(x);
		SLTNode* pour = *pphead;
		SLTNode* pur = NULL;
		while (pour != pos)
		{
			pur = pour;
			pour = pour->next;
		}
		assert(pur);
		newnode->next = pour;
		pur->next = newnode;
	}
}



void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead && pos <= *pphead);
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* pour = *pphead;
		SLTNode* pur = NULL;
		while (pour != pos)
		{
			pur = pour;
			pour = pour->next;
		}
		assert(pur);
		pur -> next = pur->next -> next;
		free(pour);
		pour = NULL;
	}
}



void SLTInsertAfter(SLTNode* pos, SLdate x)
{
	assert(pos);
	SLTNode* newnode = SLTbuynode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}



void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* pour = pos -> next;
	pos->next = pos->next->next;
	free(pour);
	pour = NULL;
}



void SListDestroy(SLTNode** pphead)
{
	assert(*pphead && pphead);
	SLTNode* pour = *pphead;
	while (pour)
	{
		SLTNode* next = pour->next;
		free(pour);
		pour = next;
	}
	*pphead = NULL;
}

总结：

  可算快马加鞭的肝完这篇文章了，小编本来想上一篇文章就结束单链表的，但是觉得万字文章有点太多了内容，于是分装成两篇来书写，因为小编是学完了单链表就开始写的文章，有一些地方可能有错误或者文笔显得很繁琐，各位读者朋友见谅，如果有错误的话，恳请在评论区指出，小编会及时的更正，那么，我们下一篇文章见啦！