【数据结构】单链表的增删查改

---

一、链表的定义

链表是一种物理存储结构上非连续、非顺序的存储结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

链表共有以下几种分类：
1、单向或双向链表

2、带头或者不带头链表

3、循环或非循环链表

以上几种链表一共有8中组合，但是在实际中常用的组合链表有两种：
1、无头单向非循环链表
2、带头双向循环链表

二、单链表的实现

本文我们所要实现的便是无头单向非循环链表，即单链表。

在实现单链表增删查改之前，首先应该创建一个单链表

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

2.1、动态开辟一个空间

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.2、单链表的打印

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10

2.3、单链表的插入操作

尾插

代码实现：

void SLTPushBack(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		//找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

头插

代码实现：

void SLTPushFront(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
1
2
3
4
5
6

头插和尾插为什么要有二级指针接收呢？

由于在头插和尾插函数中改变的是int*类型的参数，需要传递int**给形参，形参的改变不会改变实参，所以传过来的是链表的地址。以下运用二级指针的函数均是如此。

int main()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushFront(&plist, 200);
	return 0;
}
1
2
3
4
5
6
7

---

单链表在pos位置之后插入x

void SLTnsertAfter(SLTNode* pos, SLDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7

先是newnode的next指向d3，把d3的地址给newnode的next，再把pos的next指向newnode。这里对pos解引用，需要断言，不能为空。以下pos均要断言。

单链表在pos位置之后插入为什么用一级指针呢？

这里改变的是结构体成员，有结构体指针就可以了，不需要二级指针

---

单链表在pos位置之前插入x

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	assert(pos);
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

2.4、单链表的删除操作

尾删

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

头删

void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
1
2
3
4
5
6
7

---

删除pos后一个

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* nextNode = pos->next;
		pos->next = nextNode->next;
		free(nextNode);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

函数SLTEraseAfter中的nextNode可以置NULL，也可以不用置NULL，因为nextNode是一个局部变量，出了函数就销毁。

函数SLTEraseAfter的运用：

int main()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	printf("删除前：");
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 3);
	if (pos)
	{
		printf("找到了\n");
		SLTEraseAfter(pos);
	}
	else
	{
		printf("找不到\n");
	}
	printf("删除后：");
	SLTPrint(plist);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

运行结果：

此函数先是通过查找函数确定pos存不存在，然后再进行删除。与下面SLTErase函数一样的道理

---

删除pos位置

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

若pos==* pphead，则相当于头删，直接运用头删函数即可。

---

2.5、单链表的查找及释放操作

查找

SLTNode* SLTFind(SLTNode* phead, SLDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

查找函数的运用：

int main()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTNode* pos = SLTFind(plist, 4);
	if (pos)
	{
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

运行结果：

---

释放

void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11

在函数SLTDestroy中plist必须要置NULL。若不置空，再次使用，可能会造成野指针。

不置NULL：

int main()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTDestroy(&plist);
	SLTPrint(plist);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

运行结果：

置NULL后再次使用：

int main()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTDestroy(&plist);
	SLTPushBack(&plist, 5);
	SLTPushBack(&plist, 6);
	SLTPrint(plist);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

运行结果：