淘先锋技术网

首页 1 2 3 4 5 6 7

一起学数据结构（3）——万字解析：链表的概念及单链表的实现

上篇文章介绍了数据结构的一些基本概念，以及顺序表的概念和实现，本文来介绍链表的概念和单链表的实现，在此之前，首先来回顾以下顺序表的特点：

1.顺序表特点回顾：

1. 顺序表是一组地址连续的存储单元依次存储的线性表的数据结构，逻辑上：顺序表中相邻的数据元素，其物理次序也是相邻的。

2. 顺序表的优点： 任一元素均可以随机存取

3.顺序表的缺点：进行插入和删除操作时，需要移动大量的元素，存储空间不灵活。

2. 链表的分类及概念：

2.1 链表的分类：

1.单链表：结点只有一个指针域的链表，称之为链式线性表或者单链表:

   

2.双链表：结点由两个指针域的链表：

3.循环链表：首尾相连的链表：

 本文将着重介绍单链表，下面给出单链表的概念及相关特点：

2.2 单链表的概念即特点：

单链表指的是链表的每个结点中只包含一个指针域，对于链表，下面给出定义：

线性表链式存储的结构是：用一组任意的存储单元 存储线性表的数据元素（这组存储单元可以连续，也可以不连续）。为了表示每个数据元素a_i与其后记数据元素^{a_{i+1}}之间的逻辑关系，所以，对于存储数据元素a_i的存储单元，还需要存储一个指示后记数据元素^{a_{i+1}}的相关信息，（即存储^{a_{i+1}}所在的地址）。这两部分信息构成了数据元素a_i的存储映像，称为结点。

对于结点，包括了两个域：存储数据元素信息的域称之为数据域，存储后记元素存储位置的域称之为指针域。指针域中存储的信息称作指针或者链。n个结点链成一个链表，即为线性表的链式存储结构

（注：对于链表更详细的定义可以参考人民邮电出版社出版的《数据结构》，本文不再过多说明）

3.单链表的代码实现：

3.1 链表的存储结构及结点的创建：

单链表的定义中提到了，链表是由n个结点构成的，每个结点中包含了两个与，一个是用于存储数据元素信息的数据域，另一个是用于存储下一个数据元素信息地址的指针域。不同类型的信息的保存，可以由结构体进行实现，所以，下面用图给出单个结点的结构：

其中，data表示存储的数据元素信息，next表示下一个数据元素信息的地址。并且，将每一个这种结点命名为newnode，对上述结点用代码表示：

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;// 对应了存储的元素信息
	struct SListNode* next; // 对应了下一个数据元素信息的地址
}SLTNode;

对于链表，也和顺序表一样，可以实现增删查改各种功能，而实现这些功能的基础，就是如何创造新的结点，为了解决这个问题，可以专门定义一个函数BySListNode来实现。前面说到，链表各个结点之间的链接是通过某个结点存储下一个结点的地址来实现的。所以，对于函数BySListNode的返回类型，应该定义为SLTNode*型，即返回结构体的地址。

对于一个结点的创建，同样可以采用在顺序表中用动态内存函数malloc动态开辟内存的方式进行实现。具体代码如下:

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
        exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

 下面给出代码来测试函数BySListNode的功能:

为了测试函数的功能，首先需要针对链表来封装一个打印函数，将打印函数命名为SLTPrint，代码如下：

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
}

在链表的定义中说过，链表取任意元素必须从头节点开始向后依次寻找。所以，为了防止头指针的值被更改，后续无法找到第一个结点，所以，在上述代码中，创建了一个新的变量cur用来存放头指针phead中的地址。

对于cur = cur->next;这一行代码，是用于让cur保存下一个结点的地址，例如下图中cur的变化所示：

 下面，封装一个函数Testlist1来测试插入结点的功能，代码初步表示如下：

void Testlist()
{
	printf("请输入想要插入的元素的个数：");
	int n = 0;
	scanf("%d", &n);
	printf("请输入插入的元素：");
	for (size_t i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);
		
	}
}
int main()
{
	Testlist1();
	return 0;
}

但是对于上面给出的代码，并不能完成对多个结点的数据元素的打印，因为在创建结点后，并没有将前后的结点进行链接。同时，也并没有出现上面图中所说的头指针。

为了建立前后结点的链接。所以，在上面Testlist1函数中的代码的基础上，人为建立一个头指针，定义为plist,赋值为NULL。

（注：下面为了方便进行演示，对于结点之间建立的过程采用头插的思想，但是并不等价于后面的头插）

对于链接各个结点，需要分以下两种情况：

1.头指针为NULL，即还未链接任何结点，但是已经创建了一个结点：

为了达到链接的效果，只需要将plist中存储的地址改为新结点newnode的地址即可。 

2.头指针不为空：

 此时，plist中已经通过存储第一结点的地址达到链接第一结点的目的，为了链接第二结点，需要将plist中存储的地址改为第二结点的地址。

注释中提到，为了方便演示采用头插的思想，对于头插，可以用下图进行表示：

例如，将地址为 0x0012ffa0的结点进行头插。为了完成头插，需要进行两步操作：

1.将地址为0x0012ffa0的结点（即新结点）中存储的地址改为0x0012ffb0（插入前的第一个结点）

2.将头指针中存储的地址改为0x0012ffa0（即新结点的地址）

对上述分析进行归纳，代码如下：

void Testlist()
{
	printf("请输入想要插入的元素的个数：");
	int n = 0;
	scanf("%d", &n);
	SLTNode* plist = NULL;
	printf("请输入插入的元素：");
	for (size_t i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);
		if (plist == NULL)
		{
			plist = newnode;
		}
		else
		{
			newnode->next = plist;
			plist = newnode;
		}
		
	}
    SLTPrint(plist);
}

其中，newnode是一个结构体指针，所以需要用到->进行解引用。来改变新结点newnode中存储的下一个数据元素信息的地址。

测试效果如下：

3.2 链表功能实现——尾插： 

定义尾插函数SLTPushBack其内部参数如下面代码所示：

void SLTPushBack(SLTNode* phead, SLTDataType x);

对于尾插这一功能，首先需要找到链表的尾端。前面说到，头指针对于链表的各种功能来说都非常重要，所以，为了保证头指针不被更改，这里定义一个新的结构体指针tail来存储头指针中存储的地址。

对于如何找到尾端，下面给出一段示例的代码：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	SLTNode* tail = phead;
	while (tail != NULL)
	{
		tail = tail->next;
	}
	tail = newnode;
}

上述代码给出的思路很明确。利用while循环不断检查指针tail是否为NULL,不为空，则tail存储下一个结点的指针。看似没有错误。但是如果将上述过程用图形表示，则上述代码会引起内存泄漏这一错误，具体如下：

一开始，指针tail存储了头指针phead中的地址，此时tail\neq NULL,于是执行循环内部的代码，此时，tail中存储的地址为0x0012ffb0，效果如下图所示：

依次循环上述步骤：

 再次循环上述步骤：

 到最后一步时，指针tail中存储的地址为NULL。到这里，while循环终止。已经寻找到尾端地址。假设，在循环之前新建立的结点如下图所示：

如果按照上面给出的代码来执行，即：tail = newnode;，则，执行结束后，最后一个结点和指针tail中存储的地址如下：

此时，便会出现一个问题，即，指针tail是只存在与函数内部的一个临时变量，出函数便会销毁。但是，最后一个结点中存储的地址仍然为NULL。最后一个结点和新的结点并未建立联系。造成了内存泄露的问题。 

因为，完成尾插的标志，便是最后一个结点存储的地址被更改为新结点的地址。通过上面的错误例子。可以得出一个结论。如果想要将最后一个结点存储的地址改为新结点的地址，则，不可以让临时指针tail赋值最后一个结点中存储的地址。应该赋值最后一个结点的前一个结点的存储的地址。

再通过这个结点存储的地址，来对最后一个结点存储的地址进行修改。所以，代码可以更改为：
 

void SLTPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	SLTNode* tail = phead;
	while (tail ->next != NULL)
	{
		tail = tail->next;
	}
	tail -> next = newnode;
}

通过下面的测试来测试尾插的功能：

void Testlist1()
{
	printf("请输入想要插入的元素的个数：");
	int n = 0;
	scanf("%d", &n);
	SLTNode* plist = NULL;
	printf("\n请输入插入的元素：");
	for (size_t i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);
		if (plist == NULL)
		{
			plist = newnode;
		}
		else
		{
			newnode->next = plist;
			plist = newnode;
		}
	}
	SLTPrint(plist);
	printf("\n");
	SLTPushBack(plist, 10000);
	SLTPrint(plist);
}

结果如下：

上面关于尾插的代码，只能是在有结点的情况下运行。对于头指针为空的情况下并不适用，下面将对上面的尾插代码进行完善：

给出下列代码：

void SLTPushBack(SLTNode* phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (phead == NULL)
	{
		phead = newnode;
	}
	SLTNode* tail = phead;
	while (tail ->next != NULL)
	{
		tail = tail->next;
	}
	tail -> next = newnode;
}

这里给出的代码对比尾插，仅仅是多了一个对于头指针phead = NULL的情况的判定。中心思想就是在头指针phead = NULL时，将头指针保存的地址改为第一个结点的地址。但是这种做法并不正确。因为这里所说的头指针phead只是函数内部的一个形式参数。真正的头指针时上面定义的plist。此时，函数形式参数传递的时形参phead中保存的值，在前面关于C语言函数的文章中曾提到函数的两个传递参数的方式：传值和传址。对于传值调用，并不能改变外部变量的值。所以，这里虽然对头指针phead存储的地址进行改变。但是却没有真正的改变函数外部实际参数plist中保存的地址。

对于上面的错误，可以通过传址调用来改变头指针plist中保存的地址。在前面对于C语言函数的文章的介绍中曾写过一个用传址调用来实现交换函数。所以，通过函数来交换两个变量中的值，需要用到一级指针。相对于，对于头指针plist，想要通过函数来改变他的值，需采用二级指针。

所以，正确的尾插代码应为：

void SLTPushBack(SLTNode** phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*phead == NULL)
	{
		*phead = newnode;
	}
    else
    {
	   SLTNode* tail = *phead;
	   while (tail ->next != NULL)
	     {
		   tail = tail->next;
	     }
	   tail -> next = newnode;
    } 
}

运用下面的测试，来测试尾插的功能：

void Testlist2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);
}

结果如下：

3.3 链表功能实现——头插：

对于头插功能的实现，上面已经给出来了大体思路。但是上面的头插并不是通过函数实现的。根据刚才尾插的实现可以发现。每进行一次头插，都需要对头指针plist中存储的地址进行更改。所以。在函数传递参数时，也需要传递二级指针。

代码如下：

void SLTPushFront(SLTNode** phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *phead;
	*phead = newnode;
}

用下列代码对头插功能进行测试：

void Testlist3()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	SLTPrint(plist);
}

结果如下：

3.4 链表功能实现——尾删：

对于尾删功能的实现，需要考虑下面的三种情况：

1. 链表整体为空：

2.链表内只有一个结点

3.链表有多个结点

对第一种情况，只需要在进行尾删功能前，检查一下地址是否合法即可。

对于第三种情况，需要两步。第一步是删除处于尾部的结点。第二种情况是将前一个结点中保存的地址改为NULL即：

 第二种情况也需要分为两步，首先删除尾部结点。再把头指针中存储的地址改为NULL。与第三步不同的时，第三步更改地址的对象是结构体中的一个成员。第二步中更改的对象时头指针。所以，在进行对于第二种情况的地址改动时，需要传递二级指针。

下面先给出针对第一、第二种情况下的代码：

//尾删
void SLTPopBack(SLTNode** phead)
{
	assert(*phead);
	if ((*phead)->next == NULL)//只有一个结点的情况
	{
		free(*phead);
		*phead = NULL;
	}

}

对于第三种情况，假设此时有三个结点：

对于尾删功能，与尾插功能相同，第一步都是需要找到尾结点：

寻找尾结点时，采用与尾插寻找尾结点相同的方式，创建一个函数内部的指针变量SLTNode*tail来保存头指针保存的地址。当tail找到尾结点时：

如果此时就删除尾结点，还是会造成在讲解尾插原理中的错误。即，没能更改尾部结点前一个结点中存储的地址。如下图所示：

此时最后一个由malloc函数开辟的结点已经被free 。

为了解决上面的问题，可以在创建一个临时变量也用于保存phead中存储的地址。不过，这个变量的作用是用于更改尾结点前一个结点中存储的地址。这里将这个指针命名为tailprev,再有了这个指针后，当找到尾结点时，这两个指针的关系如下图所示：

先用代码表示指针tail：

SLTNode* tail = *phead;
		SLTNode* tailprev = *phead;
		while (tail->next != NULL)
		{
			tail = tail->next;

		}

 为了达到图中两个指针一前一后的关系，可以让循环中在执行tail = tail -> next之前，让tailprev存储一次tail中的地址。代码如下：

//尾删
void SLTPopBack(SLTNode** phead)
{
	assert(*phead);
	if ((*phead)->next == NULL)//只有一个结点的情况
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLTNode* tail = *phead;
		SLTNode* tailprev = NULL;
		while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;

		}
		free(tail);
		tailprev->next = NULL;
	}
}

测试功能的代码如下：
 

void Testlist3()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	SLTPrint(plist);
	printf("\n尾删");
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	printf("\n");
	SLTPrint(plist);
}

结果如下：

3.5 链表功能实现——头删：

对于头删功能，依旧分为以下三种情况：

1. 链表整体为空：

2.链表内只有一个结点

3.链表有多个结点

对于第一种情况，直接检查头指针合法性即可。对于第三种情况，即多个结点，需要分为两步来完成头删：首先将头指针存储的地址改为第二个结点的地址。再把第一个结点free。对于第二种情况，和第三种情况相同，虽然只有一个结点。但是可以将NULL看作第二个结点的地址。代码如下：

//头删
void SLTPopFront(SLTNode** phead)
{
	assert(*phead);
	SLTNode* newhead = (*phead)->next;
	free(*phead);
	*phead = newhead;
}

测试函数如下：

void Testlist4()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	printf("\n");
	printf("头删");
	printf("\n");
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	printf("\n");
	SLTPrint(plist);

}

 结果如下：

 4. 单链表的代码实现——针对某一元素对应的位置进行操作：

4.1 通过某一具体元素来找到特定位置：

例如给出下面所示的一个单链表：

如果需要找到元素2所对应的位置，只需要将整体单链表进行一次遍历，若某个结点中的元素= 想要寻找的元素。则返回这个元素对应的结点的坐标，具体代码如下：

//寻找某个元素所对应的节点的地址：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* tail = phead;
	while (phead != NULL)
	{
		if (tail->data == x)
		{
			return tail;
		}
		else
		{
			tail = tail->next;
		}
	}
	return NULL;
}

4.2 在某一特定数据对应的结点前插入新结点：

前面知道了如何找到一个特定数据对应的结点的位置后，如果需要在这个结点之前插入一个新的结点。

对于这种形式的插入，需要分为两种情况：

1. 头指针为空，此时无法插入，检查指针合法性即可

2. 链表中只有一个结点，此时的插入就等于头插

3. 链表中有多个结点

对于前两种情况，具体的代码如下：

void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
	assert(*phead);
	if (*phead == NULL)
	{
		SLTPushFront(phead, x);
	}
}

对于第三种情况，需要考虑到，上面给出的查找函数返回的地址并不是插入新结点的地址，而是在这个地址对应的结点的前面进行插入。所以，此时的插入可以分为两步：

1.将新结点存储查找函数找到的结点的地址，这里将用查找函数找到的地址用指针pos存储。即：

2. 将原来pos对应的结点的前一个结点中存储的地址，改为存储新结点的地址，即：

 用代码表示上述过程，即：

void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
	assert(*phead);
	if (*phead == NULL)
	{
		SLTPushFront(phead, x);
	}
	else
	{
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;

	}
}

用下面的函数测试前插的功能：

void Testlist5()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	int x = 0;
	printf("请输入想要查找的值");
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	printf("插入后：");
	SLTInsert(&plist, pos, x*10);
	SLTPrint(plist);
}

结果如下：

4.3 在某一特定数据对应的结点后插入新结点：

原理与前插相似，这里不再叙述，只给出图形表示：

对应代码如下：

void SLTInsertafter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

测试函数如下：

void Testlist5()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	int x = 0;
	int y = 0;
	printf("请输入想要查找的值");
	scanf("%d %d", &x,&y);
	SLTNode* pos = SLTFind(plist, x);
	printf("插入后：");
	SLTInsert(&plist, pos, x*10);
	SLTPrint(plist);
	printf("\n");
	printf("前插\n");
	SLTInsertafter(pos, y * 10);
	SLTPrint(plist);
}

结果如下：

4.4 删除某一特定元素对应位置的结点：

对于删除结点，也要分三种情况：

1. 链表整体为空，检查指针合法性即可

2.链表内只有一个结点，相当于头删 

3.链表有多个结点。

对于第三种情况。与前插相同，也需要创建一个指针来改变pos前面的结点中存储的地址，具体对应的代码如下：

void SLTErase(SLTNode** phead, SLTNode* pos)
{
	assert(pos);
	if (pos == *phead)
	{
		SLTPopFront(phead);
	}
	else
	{
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

测试函数如下：

void Testlist6()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	printf("请输入想要查找的值");
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	SLTErase(&plist,pos);
	printf("\n");
	SLTPrint(plist);
}

结果如下：

 4.5删除某一特定元素对应位置后一个结点：

随机给出一个链表：

通过观察不难发现： 对于删除某一特定元素对应结点的后一个结点这个功能，对于两种情况是没有意义的：

1. 链表中没有结点。

2. 对应元素的结点恰好是最后一个结点。

所以，在进行删除之前，应该针对这两种情况进行地址的检查。

而对于删除，也需要创建一个新的指针，用来保存pos->nxet这个地址。如果不保存，则删除结点和链接结点之间会出现矛盾，例如：

如果不保存pos->nxet，若选择直接链接数据元素为3的结点，此时没有指针保存数据为2的结点的地址。如果先删除pos->nxet，也无法得到数据元素为3的结点的地址。所以应该创建一个新的指针，pos->nxet，用指针变量posNext保存这个地址。在进行链接数据元素为1,3这两个结点时，可以pos->next = posNext -> next来实现。删除数据元素为2的结点时，直接free(posNext)，代码如下：

//删除对应位置后一个结点：
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);//检查是否是最后一个结点
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
}

测试函数如下：

void Testlist6()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	printf("请输入想要查找的值");
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	/*SLTErase(&plist,pos);
	printf("\n");
	SLTPrint(plist);*/
	SLTEraseAfter(pos);
	printf("\n");
	SLTPrint(plist);

}

结果如下：

 5.总体代码：

5.1 头文件 SList.h:

#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//创建结点
SLTNode* BuySListNode(SLTDataType x);

//打印各节点的信息
void SLTPprint(SLTNode* phead);

//尾插
void SLTPushBack(SLTNode** phead, SLTDataType x);

//头插
void SLTPushFront(SLTNode** phead, SLTDataType x);

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

//头删
void SLTPopFront(SLTNode** phead);

//寻找某个元素所对应的节点的地址：
SLTNode* SLTFind(SLTNode* phead,SLTDataType x);

//对应位置前插入
void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);

//对应位置后插入：
void SLTInsertafter(SLTNode* pos, SLTDataType x);

//对应位置前删除
void SLTErase(SLTNode** phead, SLTNode* pos);

//删除对应位置后一个结点：
void SLTEraseAfter(SLTNode* pos);

5.1 函数功能实现——SLIst.c:

#include"SList.h"

//创建结点
SLTNode* BuySListNode(SLTDataType  x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//打印结点信息
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
}

//尾插
void SLTPushBack(SLTNode** phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	else
	{
		SLTNode* tail = *phead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

//头插：
void SLTPushFront(SLTNode** phead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *phead;
	*phead = newnode;
}

//尾删
void SLTPopBack(SLTNode** phead)
{
	assert(*phead);
	if ((*phead)->next == NULL)//只有一个结点的情况
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		SLTNode* tail = *phead;
		SLTNode* tailprev = NULL;
		while (tail->next != NULL)
		{
			tailprev = tail;
			tail = tail->next;

		}
		free(tail);
		tailprev->next = NULL;
	}
}


//头删
void SLTPopFront(SLTNode** phead)
{
	assert(*phead);
	SLTNode* newhead = (*phead)->next;
	free(*phead);
	*phead = newhead;
}


//寻找某个元素所对应的节点的地址：
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* tail = phead;
	while (phead != NULL)
	{
		if (tail->data == x)
		{
			return tail;
		}
		else
		{
			tail = tail->next;
		}
	}
	return NULL;
}


//特定位置前插入：
void SLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x)
{
	assert(*phead);
	if (*phead == NULL)
	{
		SLTPushFront(phead, x);
	}
	else
	{
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;

	}
}

//特定位置后插入新结点
void SLTInsertafter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


void SLTErase(SLTNode** phead, SLTNode* pos)
{
	assert(pos);
	if (pos == *phead)
	{
		SLTPopFront(phead);
	}
	else
	{
		SLTNode* prev = *phead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}


//删除对应位置后一个结点：
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);//检查是否是最后一个结点
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
}

5.3 函数测试文件Test.c:

#include"SList.h"


void Testlist1()
{
	printf("请输入想要插入的元素的个数：");
	int n = 0;
	scanf("%d", &n);
	SLTNode* plist = NULL;
	printf("\n请输入插入的元素：");
	for (size_t i = 0; i < n; i++)
	{
		int val = 0;
		scanf("%d", &val);
		SLTNode* newnode = BuySListNode(val);
		if (plist == NULL)
		{
			plist = newnode;
		}
		else
		{
			newnode->next = plist;
			plist = newnode;
		}
	}
	SLTPrint(plist);
	printf("\n");
	SLTPushBack(&plist, 10000);
	SLTPrint(plist);
	printf("\n");
}

void Testlist2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	printf("尾插");
	printf("\n");
	SLTPrint(plist);
	printf("\n");
}

void Testlist3()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	SLTPrint(plist);
	printf("\n尾删");
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	printf("\n");
	SLTPrint(plist);

}
void Testlist4()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPushFront(&plist, 6);
	printf("\n");
	printf("头删");
	printf("\n");
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	printf("\n");
	SLTPrint(plist);

}

void Testlist5()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	int x = 0;
	int y = 0;
	printf("请输入想要查找的值");
	scanf("%d %d", &x,&y);
	SLTNode* pos = SLTFind(plist, x);
	printf("插入后：");
	SLTInsert(&plist, pos, x*10);
	SLTPrint(plist);
	printf("\n");
	printf("前插\n");
	SLTInsertafter(pos, y * 10);
	SLTPrint(plist);
	printf("\n");
}

void Testlist6()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
	printf("\n");
	printf("请输入想要查找的值");
	int x = 0;
	scanf("%d", &x);
	SLTNode* pos = SLTFind(plist, x);
	/*SLTErase(&plist,pos);
	printf("\n");
	SLTPrint(plist);*/
	SLTEraseAfter(pos);
	printf("\n");
	SLTPrint(plist);

}
int main()
{
	/*Testlist1();*/
	/*Testlist2();*/
	/*Testlist3();
	Testlist4();*/
	/*Testlist5();*/
	Testlist6();
	return 0;
}