数据结构——单链表的实现

呀哈喽，我是结衣。

链表的概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
这里我来解释一下什么叫做逻辑上连续而物理上补连续。
所谓逻辑上的连续，就是指你你可以通过第一个节点找到第二个节点，就行火车一样你可以从一节车厢走到另一节的车厢。
物理上的不连续是指内存地址的不连续，不想顺序表中的数组是连续的。物理的不连续我们也可以把他理解成火车，火车的车厢是可以随意地拆卸和组装的，每个车厢不一定都是同时同地生产。

节点间依靠一个指针连接。

结构体的创建

链表也是和顺序表一样要创建一个结构体来储存相应的数据。不同于顺序表，链表的结构体只有两个需要存放的数据，一个为要存放的数据，另一个为下一个结构体的地址。
用代码表示就是

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;//存放的数据
	struct SListNode* next;//下个数据的地址
}SLNode;
1
2
3
4
5
6

和顺序表差不多，写完结构体我们就要来想链表的功能，然后进行相应函数的声明。
在进行函数声明之前我还要在详细的解释一下这个结构体和链表的关系，我们来画个图来看看。

我先假设1，2，3的地址就是这些，这么看来他们在内存中肯定不是连续的，要这么把他们关联起来呢？next就起到了重要的作用，我们把2的地址存在1的next中，把3的地址存在2的next中，最后把3的next指向NULL就可以了，再画一个图就是这样的。

我还用了一个头节点来指向第一个节点，从图上来看是不是每个节点都联系了起来，这就是有了逻辑上的连续。
下面我来讲解实现链表都要哪些函数。

函数的声明

函数的声明我们要写在相应的头文件当中，前面的结构体也是写在这个头文件当中。另外封装一个头文件的好处就是代码看起来简洁明白。
为此我们也要想写顺序表一样写3个文件。就像这样.

写好文件我在把上面的结构体写进SList.h的文件里面。
做完这些就开始写函数。首先我们先写一个打印函数。

打印函数

这里我们要定义一个新的结构体叫cur用它来存放phead，然后再用cur来访问头节点。当然你或许会有疑惑，为什么不直接使用phead来访问呢，其实是可以的，但是你要想如果你用了phead，那么再使用之后不就找不到头节点了吗，万一下次补充功能时候要用呢。使用这里我建议再创建一个结构体存放phead以备不时之需。

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

尾插函数

有了打印函数我们肯定要写一个插入函数，我们就先写一个尾插函数，然后来看看打印效果。
从尾部插入要怎么插呢？在写链表问题的时候就要多画图了，可别说什么人脑计算。那么我们来画图分析：

我们先假设里面是有数据的，我们要怎么插。现在我们要把“4”插进最后面，我们要怎么办？
是不是要将3节点的nest指向4节点然后把4节点的next指向NULL啊，没错就是这样。为了做到这样，我们要遍历一遍链表。用到while循环。
这样的话我们是不是又要创建一个新的结构体命名为tail用它来找尾。具体看代码。
找尾思想大概就是这样，但是我们还少了点什么，没错我们还没有创建节点呢，为此我们还要写一个创建节点的函数

节点创建

SLNode* Creaknode(SLTDateType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	//内存开辟失败
	if (newnode == NULL)
	{
		perror("malloc fail");
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

尾插代码分析

创建完节点后要用newnode来存放，然后就是判断链表是否为空，为空的话我们只有把头节点*pphead指向新的节点newnode就可以了，
如果不是空链表，就是按上面图里那样，把最后节点的next指向新的节点就可以了。
值得注意的是while里的判断条件别写成了tail！=NULL如果这样写了显然会出问题，你找不到最后的节点了，它变成了NULL，程序会出问题的。

void SLPushBack(SLNode** pphead, SLTDateType x)
{
	SLNode* newnode = Creaknode(x);//创建新的节点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLNode* 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

写完我们当然要来试一试了，插入1，2，3，4看看吧

没问题，但是细心的小伙伴可能就发现了我用的是双指针，为什么链表要用二级指针呢，明明顺序表就只有一级指针。问的好，因为，这里我们定义了SLNode* plist = NULL;它不就是一个一级指针吗，我们要改变它里面的内容不就要把它的地址传过去吗，我们传了一个一级指针的地址过去，不就要用二级这种接收吗，这样才可以做到修改plist里面的内容啊。

头插函数

想要实现头部插入，我们先画图。

要想吧新的节点插入头部，我们就要把，新节点的nest指向第一个节点，然后把pphead指向新的节点。就像这样：

void SLPushFront(SLNode** pphead, SLTDateType x)
{
	SLNode* newnode = Creaknode(x);//创建新的节点
	newnode->next = *pphead;
	*pphead = newnode;
}
1
2
3
4
5
6

是不是很简单，比尾插简单多了，下面就是打印看看对没对咯。

这样看就没问题了，符合头插。

尾删函数

写完插入写删除，首当其冲的当然是尾删了。

为了把最后的节点删除，我们就要把倒数第二个节点的next指向NULL然后再把最后的节点free了就可以了。

void SLPopBack(SLNode** pphead)
{
	assert(*pphead);
	SLNode* 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

目前看是没有问题的，我们再来试试删完的情况。

这么看来如果我们多删了，程序就出问题了，甚至刚好删完都不可以。

那么问题出在了哪里，我们没有考虑只有一个节点的情况，所以我们还要再加上一个判断。就像这个样子。

void SLPopBack(SLNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* 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

当然尾删不止这样一种的写法，我们在写一种写法吧

void SLPopBack(SLNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		/*SLNode* cur = *pphead;
		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;*/
		SLNode* pre = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			pre = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		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
30
31

这样也是对的。

头插函数

最后我们来写头插函数啊。

突然想到上面的图片pphead没加** * **啊，欧克，回到这里来，我们要把第一个节点删除，就要让*pphead指向第二个节点，然后把第一个节点给free了就欧克了。思路就是这个思路，我们来写写代码。

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

代码很简单的，运行起来好像也没什么问题，我们再来试试删完看看。

没问题，再多删一个看看

也没有问题，这个是我们自己写的assert断言。

结语

到这我们的基础教学就结束了，还要好几个函数没有写，就比如查找函数，指定位置的插入和删除。这些当然就和顺序表一样交给大家自己完成咯

代码

SList.h

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;//存放的数据
	struct SListNode* next;//下个数据的地址
}SLNode;
void SLNprintf(SLNode* phead);
void SLPushBack(SLNode** pphead, SLTDateType x);
void SLPushFront(SLNode** pphead, SLTDateType x);
void SLPopBack(SLNode** phead);
void
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

SList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
void SLNprintf(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
SLNode* Creaknode(SLTDateType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	//内存开辟失败
	if (newnode == NULL)
	{
		perror("malloc fail");
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SLPushBack(SLNode** pphead, SLTDateType x)
{
	SLNode* newnode = Creaknode(x);//创建新的节点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLNode* tail = *pphead;
		while (tail->next!=NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLPushFront(SLNode** pphead, SLTDateType x)
{
	SLNode* newnode = Creaknode(x);//创建新的节点
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLPopBack(SLNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		/*SLNode* cur = *pphead;
		while (cur->next->next != NULL)
		{
			cur = cur->next;
		}
		free(cur->next);
		cur->next = NULL;*/
		SLNode* pre = NULL;
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			pre = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		pre->next = NULL;
		
	}
	
}
void SLPopFront(SLNode** pphead)
{
	assert(*pphead);
	SLNode* cur = *pphead;
	*pphead = 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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

test.c

#define _CRT_SECURE_NO_WARNINGS
#include "SList.h"
void test1()
{
	SLNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLNprintf(plist);
	/*SLPushFront(&plist, 1);
	SLPushFront(&plist, 2);
	SLPushFront(&plist, 3);
	SLPushFront(&plist, 4);
	SLNprintf(plist);*/
	SLPopBack(&plist);
	SLPopBack(&plist);
	SLPopBack(&plist);
	//SLPopBack(&plist);
	SLPopBack(&plist);
	SLNprintf(plist);
}
void test2()
{
	SLNode* plist = NULL;
	SLPushBack(&plist, 1);
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLNprintf(plist);
	SLPopFront(&plist);
	SLPopFront(&plist);
	SLPopFront(&plist);
	SLPopFront(&plist);
	SLPopFront(&plist);
	SLNprintf(plist);
}
int main()
{
	test2();

	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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43