数据结构——单链表专题

前言

本篇我们继续来介绍数据结构的知识——链表，这与顺序表是一个类别的知识，同样也非常重要，所以大家需要掌握好链表的内容，这对我们后面数据结构的学习也很重要，如果你对本篇的内容感兴趣，希望大佬可以一键三连，多多支持；下面进入正文部分。

1. 链表的概念

这里大家首先要明确线性表的概念，线性表是具有相同特性的一类数据的集合，它在逻辑结构上一定是线性的，而在物理结构上不一定连续；前面我已经学过一类线性表——顺序表，我们知道顺序表在物理结构和逻辑结构上都是线性的；而今天我们所说的链表在物理结构上是非线性的。

链表是一种在物理结构上非线性非连续的存储结构，由一个个节点组成。

大家仔细来看上面的图，观察节点是由什么组成的，很明显大家可以发现节点是由存储的数据和指向下一个节点的指针组成的。

这里大家可能发现了它们之间的关系了，我们定义链表实际上就是在定义链表节点的结构，那么下面我们就要来讨论节点的定义方法了。

这里大家可以看到，我们声明了一个结构体，结构体中的内容就是前面我们所说的节点的组成元素，包括节点自身存储的数据，以及指向下一个节点的指针(这是一个结构体指针)，因为下一个节点依然是一个结构体。

2. 链表的实现

上面铺垫了关于链表的基础，下面我们来实现一下链表；

首先我们要在VS中创建一个项目，来表示链表项目；其次，根据前面我们介绍顺序表的逻辑，我们要创建链表头文件和实现文件，以及测试文件。

这里我们就创建好了 

2.1 链表的打印

首先我们要在头文件中进行声明；

void SLTPrint(SLTNode* phead);

在实现打印方法之前。我们要先在test.c文件中创建好一个链表；

void SListTest01()
{
	//创建好了4个节点
	SLTNode* node1 =(SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;
	//下面将节点连接起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLTNode* plist = node1;
	SLTPrint(plist);
}

上面就是创建链表的代码，链表的每个节点是由数据和指向下一个节点的指针组成，所以我们要按照这个规则来创建链表的正确结构。

下面在Slist.c文件写打印的代码；

​
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

​

大家来看打印代码，代码并不复杂，我们通过while循环去遍历链表的内容，每打印一次，我们就让pcur指向下一个节点，通过这样的方式去遍历每一个节点，当遍历到最后一个节点时，循环停止。

这里不知道大家有没有发现，我们遍历链表的方法和之前我们遍历数组和顺序表的方法有所不同，之前我们可以连续地遍历，那是因为数组和顺序表在物理结构上是连续的；而链表不满足这一特点，所以我们不能使用原来的方法去对链表进行遍历。只能通过指针的方式一个个遍历。

 2.2 链表的尾插

第一步在头文件中声明：

void SLTPushBack(SLTNode** pphead, SLTDataType x);

在前面介绍顺序表的插入时，我们需要判断空间大小够不够，在链表这里也类似，我们要为新节点申请空间，下面我们先来写申请空间的代码：

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

这里我们创建新指针，使用malloc来申请空间，注意申请完后一定要进行判断，保证申请成功后再使用。

接下来我们来看尾插的实现方法：

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//空链表和非空链表
	if (*pphead == NULL)//
	{
		*pphead = newnode;//空链表
	}
	else//非空链表
	{
		//找尾节点
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}

		ptail->next = newnode;
	}
}

这里大家要注意，我们一定要采用传址调用，上来我们先断言，pphead不能为NULL，我们要分两种情况进行讨论，如果传过去的是空链表，那我们直接将申请好的节点给phead这个头节点；如果传过来的不是空链表，因为我们要完成尾插，所以我们就需要找到原本链表的最后一个节点，上面代码中ptail就是尾节点，我们将新节点和尾节点连接在一起即可。

下面我们进行测试：

这里我们经过测试，可以成功地将数据插入到链表中，这里大家一定要注意在尾插代码中的一些坑点。

2.3 链表的头插

首先我们还是先在头文件中声明：
 

void SLTPushFront(SLTNode** pphead, SLTDataType x);

下面我们在SList文件中写头插代码：

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

这里大家发现，头插代码是比较简单的，上来还是先断言，然后为新插入的节点申请空间，然后我们要让原本的首节点成为新节点中指向下一个位置的节点，最后再让新节点成为新的首节点，这样就完成了头插的任务。

下面我们来对头插进行测试：

这里大家就可以清楚地看到头插的效果，证明我们上面的头插实现代码是正确的。

2.4 链表的尾删 

第一步还是先进行声明：

void SLTPopBack(SLTNode** pphead);

下面我们进行方法的实现：

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//链表不能为空
	//只有一个节点
	if ((*pphead)->next == NULL)//->优先级高于括号
	{
		free(*pphead);
		*pphead = NULL;
	}
	//有多个节点
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* ptail = *pphead;
		while (ptail->next)//找尾节点
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//prev是尾节点的前一个节点
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

这里大家注意来看，我们还是要分两种情况，第一种情况是当链表中只有一个节点时，我们直接释放它就可以达到删除的效果；第二种情况是链表中有多个节点，那么我们先要找到尾节点，然后将尾节点释放掉，并将其置为NULL，最后将尾节点的前一个节点中的指针置为NULL，这里是防止其成为野指针。

方法实现完了，我们下面来进行测试：

 这里我们完成了尾删的操作，这里还要提醒大家一下，删除的时候一定不能删“过头”了，删除的次数不能大于链表的节点数，否则断言那里就会受到NULL，这个时程序就会报错。

2.5 链表的头删

首先还是在头文件中声明：

void SLTPopFront(SLTNode** pphead);

下面来实现头删的方法：

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);//链表不能为空
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

这里头删的代码并不难，上来先断言一下，保证链表不为空；我们只需要先创建一个指针去存储头节点的下一个节点，然后再将原本的头节点删除，最后再让刚首节点向后移动。

最后我们来对头删进行测试：

这里大家可以看到头删的效果，证明上面的头删代码是正确的。 

 2.6 链表的查找

先进行声明：

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

然后我们来写查找的方法：

SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

这里我们还是使用while来遍历链表，当所存数据与我们给的数据相等时就找到了那个对应的节点，这个时候我们直接返回pcur这个节点；如果没有找到，拿就返回NULL。

最后我们来测试查找方法：

 2.7 在链表指定位置之前插入数据

我们先在头文件中声明一下：

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

下面来实现一下这个方法：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	if (pos == *pphead)//判断是否是头插
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

这里大家要分两种情况，第一种情况，当pos就是指向首节点的指针时，那么就相当于头插；第二种情况，当pos是指向其他节点的指针时，我们需要找到pos、pos的前一个节点（prev），找到后我们需要将newnode插入在这两个节点之间。

下面。我们来进行测试：

这里大家可以看到，我们在第三个节点之前插入了指定的数据。

2.8 在链表指定位置之后插入数据

我们还是先进行声明：

void SLTInsertAfter(SLTNode* pos, SLTDataType x);

这里大家可以发现，我们在函数的参数中并没有定义二级指针去接受头节点的地址，因为我们要完成在指定位置之后插入数据，所以我们只需要找到pos和pos下一个位置的节点即可。

下面我们来实现对应方法：

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

这里大家要注意指针是怎么操作的，我们要将pos、newnode、pos->next连接起来，那么连接方式很重要，有的同学可能会将最后两行颠倒位置，这个时候代码就会出问题，换位置后相当于newnode->next=newnode，这变成自己指向自己了，所以不能更换最后两行的位置。

下面我们来测试一下这个方法：

 

2.9 删除链表指定位置的数据

首先还是先来声明：

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

下面来进行方法实现：

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

这里大家来观察代码，我们要分两种情况：第一种情况，当pos就是指向首节点的指针时，这就相当于头删，我们可以直接调用前面写好的头删方法；第二种情况，如果pos指向的不是首节点，我们就需要找到pos的前一个节点的指针(prev)，要先将prev里的指针指向pos的下一个节点，然后释放pos，实现删除的效果。

下面来测试这个方法：

 

2.10 删除链表指定位置之后的数据

这里先进行声明：

void SLTEraseAfter(SLTNode* pos);

声明完后，我们进行方法的实现：

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

方法实现这里就比较简单，我们需要创建一个临时指针来保存pos的下一个节点的地址，然后再将对应的两个节点进行连接。

下面我们进行测试：
 

2.11 链表的销毁

 先来进行声明：

void SListDestroy(SLTNode** pphead);

下面我们来实现链表的销毁：

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

我们知道，链表是由一个个节点组成的，那么销毁链表的本质就是销毁节点；所以我们要遍历链表，然后逐个删除，最后不要忘了将头节点置为NULL。

下面我们来进行测试：

 

2.12 链表完整代码

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SlistNode
{
	SLTDataType data;
	struct SlistNode* next;
}SLTNode;
void SLTPrint(SLTNode* phead);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);
void SListDestroy(SLTNode** pphead);

SList.c 

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//空链表和非空链表
	if (*pphead == NULL)//
	{
		*pphead = newnode;//空链表
	}
	else//非空链表
	{
		//找尾节点
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}

		ptail->next = newnode;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//链表不能为空
	//只有一个节点
	if ((*pphead)->next == NULL)//->优先级高于括号
	{
		free(*pphead);
		*pphead = NULL;
	}
	//有多个节点
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* ptail = *pphead;
		while (ptail->next)//找尾节点
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//prev是尾节点的前一个节点
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);//链表不能为空
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	if (pos == *pphead)//判断是否是头插
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}
void SLTInsertAfter( SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos&&pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}
void SListDestroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

test.c 

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SListTest01()
{
	//创建好了4个节点
	SLTNode* node1 =(SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;
	//下面将节点连接起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLTNode* plist = node1;
	SLTPrint(plist);
}
void SListTest02()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTPushFront(&plist, 6);
	SLTPrint(plist);
	SLTPushFront(&plist, 7);
	SLTPrint(plist);
	SLTPushFront(&plist, 8);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);	
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTNode* find = SLTFind(plist, 2);
	SLTInsert(&plist,find,11);
	SLTInsertAfter(find, 11);
	SLTErase(&plist, find);
	SLTEraseAfter(find);
	SLTPrint(plist);
	SListDestroy(&plist);
	SLTPrint(plist);
	if (find == NULL)
	{
		printf("没有找到\n");
	}
	else
	{
		printf("找到了\n");
	}
}
int main()
{
	SListTest02();
	//SListTest01();
	return 0;
}

3. 总结

本篇博客为大家介绍了链表这个数据结构，它不同于顺序表，有自己的特点；大家要理解每一个方法的实现代码，并且尝试自己写出来，链表是一种重要的线性表，希望本篇博客可以帮助大家学习，感谢阅读！