无哨兵位单向非循环链表

多多关注哦，谢谢支持！

1. 认识链表

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

1. 和顺序表相比，链表的优势体现在哪？

顺序表中存在扩容问题，扩容扩大了，而数据没占满，则会浪费数据，链表是一个数据占一个空间，这样就不会出来空间浪费问题

2. 无哨兵位单向非循环链表结构

一个结构存放数据和关系，那么就有如下结构：

typedef int SLLDataType;

typedef struct SingleLinkListNode 
{
	int data; //数据
	struct SingleLinkListNode* next; //指向下一个结点
}SLLNode;
1
2
3
4
5
6
7

3. 生成一个结点

SLLNode* BuySLLNode(SLLDataType x)
{
	SLLNode* newnode = (SLLNode*)malloc(sizeof(SLLNode));
	if (newnode == NULL)
	{
		perror("BuySLLNode:malloc:");
		exit(-1);
	}

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

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

• 问题一：为什么要使用malloc去申请空间，而不是用结构体类型变量？

SLLNode BuySLLnode1(SLLDataType x)
{
	SLLNode newnode;
	newnode.data = x;
	newnode.next = NULL;

	return newnode; 
}
//问什么不能使用这种方式开辟结点空间？
1
2
3
4
5
6
7
8
9

原因：malloc申请的空间是在堆区中开辟的，堆区中的空间出了函数栈帧数据仍然存在，但是用结构类型变量，出了函数栈帧就销毁了，并不能存储数据

• 问题二：为什么开始的时候要使newnode指向NULL？

原因：在后面插入时，如果起初不指向NULL，而是指向别的地址，那么最后尾部还要对其做一步指向NULL的操作

4. 打印链表

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

问题：为什么限制条件是cur != NULL而不是cur->next != NULL?

5. 创建len长度的链表

SLLNode* GreateSLLNode(int len)
{
	SLLNode* head = NULL;
	SLLNode* tail = NULL;

	for (int i = 0; i < len; ++i)
	{
		//创建一个新结点
		SLLNode* newnode = BuySLLNode(i); 

		//检查第一步head
		if (head == NULL)
		{
			head = tail = newnode;
		}
		else
		{
			//变动tail
			tail->next = newnode;
			tail = newnode;
		}
	}

	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

问题：为什么要区分第一步head == NULL?

新链表中返回的是头节点地址，不可能头节点为NULL吧，所以要区分，对其进行改变

6. 尾插

void SLLPushBack(SLLNode** pphead, SLLDataType x)
{
	SLLNode* newnode = BuySLLNode(x);

	if (*pphead == NULL)
	{
		//*phead拿到的是head
		*pphead = newnode;
	}
	else
	{
		SLLNode* tail = *pphead;

		//找尾
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		//找到尾部
		tail->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 问题一：为什么不需要断言？

空链表也可以插入数据无需断言

• 问题二：为什么是传二级指针，而不是一级指针？

考虑传二级指针是针对*pphead == NULL时，要改变head指向的位置，改变指针所指向的位置就要传指针的指针(尾插、头插、尾删、头删都需要传二级都是这个原因)

7. 尾删

void SLLPopBack(SLLNode** pphead)
{
	//写法一
	assert(*pphead);

	//如果结点只有一个要单独处理
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLLNode* pre = *pphead;
		SLLNode* tail = *pphead;

		//找尾
		while (tail->next != NULL)
		{
			pre = tail;
			tail = tail->next;
		}

		//释放
		free(tail);
		pre->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
25
26
27
28
29

void TestSLLPopBack(SLLNode** pphead)
{
	//写法二
	//链表为空不能删除
	assert(*pphead);

	//只有一个结点的时候是不能使用的，NULL不能NULL->next
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLLNode* tail = *pphead;

		//找尾
		while (tail->next->next != NULL)
		{
			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
20
21
22
23
24
25
26

问题：下面这种写法对吗？

void SLLPopBack(SLLNode* phead)
{
	SLLNode* tail = phead;

	//找尾
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	free(tail);
	tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

为什么不行？

8. 头插

void SLLPushFront(SLLNode** pphead, SLLDataType x)
{
	//创建结点
	SLLNode* newnode = BuySLLNode(x);

	//链接
	newnode->next = *pphead;

	//改变头结点指针位置,所以传二级指针
	*pphead = newnode;
}
1
2
3
4
5
6
7
8
9
10
11

9. 头删

void SLLPopFront(SLLNode** pphead)
{
	assert(*pphead);
	
	//先调整头结点指针,所以传二级指针
	SLLNode* next = (*pphead)->next;
	
	free(*pphead);

	*pphead = next;
}
1
2
3
4
5
6
7
8
9
10
11

10. 查找

SLLNode* SLLFind(SLLNode* phead, SLLDataType x)
{
	//好的习惯
	SLLNode* cur = phead;

	//找到返回结点位置，没找到返回NULL，同时如果链表为NULL，也返回NULL
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

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

11. 在pos位置之后插入数据

void SLLInsertAfter(SLLNode* pos, SLLDataType x)
{
	assert(pos);

	写法一
	//SLLNode* nextnode = pos->next;
	//SLLNode* newnode = BuySLLNode(x);
	//pos->next = newnode;
	//newnode->next = nextnode;

	//写法二
	SLLNode* newnode = BuySLLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

为什么断言？

我们没找到的话就返回NULL，所以需要断言

之后插入数据为什么可以不记录pos后面的结点？

因为单链表是单向的，可以通过pos位置找到后一个结点，所以可以不用记录

12. 在pos位置之前插入数据

void SLLInsert(SLLNode** pphead, SLLNode* pos, SLLDataType x)
{
	//可能是head链表不为空，但是pos为空的情况则需断言
	assert(pos);

	//head为空也可以插入
	//head == pos时可以插入
	if (*pphead == pos)
	{
		SLLPushFront(pphead, x);
	}
	//不是头部插入
	else
	{
		SLLNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}

		SLLNode* newnode = BuySLLNode(x);
		pre->next = newnode;
		newnode->next = pos;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

为什么传二级指针？

因为链表为NULL时头插要改变head的指向

为什么这里必须记录上一个结点？

因为单链表是单向的，通过此结点不能直接访问上一个结点，所以必须记录上一个结点连接时使用

13. 删除pos位置之后的数据

void SLLEraseAfter(SLLNode* pos)
{
	//断言pos,不然pos->next会有错误
	assert(pos);

	if (pos->next == NULL)
	{
		perror("warining:已经在尾部，不可对后面删除!");
	}
	else
	{
		SLLNode* nextnode = pos->next;
		pos->next = nextnode->next;
		free(nextnode);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

为什么free后可以无需置空？

因为nextnode是局部变量，出了函数栈帧销毁

14. 删除pos位置数据

void SLLErase(SLLNode** pphead, SLLNode* pos)
{
	assert(pos);
	//链表为空不能删除
	assert(*pphead);

	if (*pphead == pos)
	{
		SLLPopFront(pphead);
	}
	else
	{
		SLLNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		pre->next = pos->next;
		free(pos);
		//无需置空，lastnode为局部变量，出栈帧自动销毁
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

为什么传二级？

因为head = NULL时，要改变head指向

15. 销毁链表

void SLLDestroy(SLLNode** pphead)
{
	//链表为NULL时断言
	assert(*pphead);

	SLLNode* cur = *pphead;
	while (cur != NULL)
	{
		SLLNode* nextnode = cur->next;
		free(cur);
		cur = nextnode;
	}

	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

为什么要最后*pphead = NULL，可以不置空吗？

循环中已经对链表释放完了，但是* pphead依然指向的是头结点的位置，但是头节点的空间已经释放，还给操作系统了，这里的*pphead就是野指针，所以必须置空

重要的要点已经指出，感性大家支持！