数据结构之单链表（超详解）

一.链表的概念及结构

1.概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。

2.链表的分类

1.无头单向链表

2.带头双循环链表

二.链表的定义

用typedef给int重命名，后面修改数据类型更方便

data为链表的数据域，next是链表的指针域

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
1
2
3
4
5
6
7

三.链表的结点的创建

在插入操作或者创建链表时，都要先创建一个链表的结点，所以封装一个函数，来创建结点

//创建新节点
SLTNode* CreateNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

	assert(newnode);

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

四.链表的插入操作

1.头插

如果是空表就直接将newnode赋给phead，不是就先把他的next指向head，再把他赋给head，顺序反了，他就自己指向自己了。

//头插法
void ListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = CreateNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.尾插

如果是空表就直接将newnode赋给phead，不是就先找到链表的尾结点，然后尾结点指向newnode就行

//尾插法
void ListPushBack(SLTNode** pphead, SLTDataType x)
{

	SLTNode* newnode = CreateNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;

		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.任意位置插入

如果链表为空，可以直接调用上面的两个接口，不是利用函数指针调用find函数，找到想找的结点，将newnode的next指向cur的next，cur的nex再指向newnode，顺序不能反。

//任意位置插入
void ListInsert(SLTNode** pphead, SLTNode* (*SListFind)(SLTNode* phead),
	SLTDataType x)
{
	if (*pphead == NULL)
	{
		ListPushFront(pphead, x);
	}
	else
	{
		SLTNode* cur = SListFind(*pphead);
		SLTNode* newnode = CreateNode(x);
		newnode->next = cur->next;
		cur->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

五.链表的删除操作

1.头删

先将头部的next保存起来，然后把头部的内容用free释放，再把next赋给头指针。

//头删法
void ListPopFront(SLTNode** pphead)
{
	assert(*pphead);

	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
1
2
3
4
5
6
7
8
9

不释放头，会造成内存泄露的问题。

2.尾删

首先判断链表是否为空或者链表是否只有一个结点，不是就找到尾部的前一个结点，用free(cur->next)释放尾结点，再将next置为NULL。

//尾删法
void ListPopBack(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		printf("链表为空！\n");
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead == NULL;
	}
	else
	{
		SLTNode* cur = *pphead;

		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.任意位置删除

首先判断链表是否为空，不是利用函数指针调用find函数，找到想找的结点，再遍历链表找到该节点的前驱，将前驱的next赋为cur的next，再将cur的内容用free释放。

//任意位置删除
void ListErase(SLTNode** pphead, SLTNode* (*SListFind)(SLTNode* phead))
{
	assert(*pphead);

	if (*pphead == NULL)
	{
		printf("链表为空！\n");
	}
	else
	{
		SLTNode* cur = SListFind(*pphead);
		SLTNode* pre = *pphead;
		while (pre->next != cur)
		{
			pre = pre->next;
		}
		pre->next = cur->next;
		free(cur);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

六.链表元素的查找

找到值为x的结点并返回该结点，找不到就返回空指针。

//查找链表中的元素
SLTNode* SListFind(SLTNode* phead)
{
	assert(phead);
	SLTDataType x;
	printf("请输入你要查找的元素:");
	scanf("%d", &x);

	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return [添加链接描述](https://gitee.com/Tang-CMer/c-language-examples/tree/master/Linked%20list/Linked%20list)cur;
		cur = cur->next;
	}

	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

七.链表的销毁

直接将头结点free，再把头结点置为空就行

//链表销毁
void ListDestory(SLTNode** pphead)
{
	free(*pphead);
	*pphead = NULL;
}
1
2
3
4
5
6

八.链表的源代码

单链表