看完这篇文章还不会顺序表和链表，请寄刀片给我

发表于

小知识，大挑战！本文正在参与「程序员必备小知识」创作活动

本文已参与 「掘力星计划」 ，赢取创作大礼包，挑战创作激励金。

一、线性表

1
2
scss复制代码线性表(linear list )是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表:顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

image.png

二、顺序表

💦 顺序表的概念和结构

1
复制代码顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

❗ 静态顺序表：使用定长数组存储 ❕

    缺点就是小了不够用，大了浪费

image.png

❗ 动态顺序表：使用动态开辟的数组存储 ❕

    可根据自己的需要调整大小

image.png

💦 顺序表各接口实现 (动图分析)

1
2
3
复制代码 静态顺序表只适用于确定知道需要存多少数据的场景。
 静态顺序表的定长数组导致 N 固定了，空间开多了浪费，开少了不够用。
 所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表以及增删查改等功能

这里新建三个文件：

    1️⃣ SeqList.h文件，用于函数声明

    2️⃣ SeqList.c文件，用于函数的定义

    3️⃣ Test.c文件，用于测试函数

⭕ 接口1：定义结构体SLT

1
2
3
4
5
6
7
C复制代码typedef int SQDataType;
typedef struct SeqList
{
	SQDataType* a;//指向动态开辟的空间
	int size;//有效数据个数
	int capacity;//当前容量
}SLT;

⭕ 接口2：初始化结构体 (SeqListInit)

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
C复制代码void SeqListInit(SLT* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = psl->capacity = 0;
}

📐 测试

在这里插入图片描述

⭕ 接口3：检查容量 (SeqListCheckCapcity)

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
c复制代码void SeqListCheckCapcity(SLT* psl)
{
	//一般情况为了避免频繁插入数据而增容，或者一下开辟很大的空间，我们一般是每次增容2倍
	assert(psl);
	if (psl->size == psl->capacity)
	{
		//第一次是增容4*sizeof(SQDataType)
		size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		int* temp = (SQDataType*)realloc(psl->a, newcapacity * sizeof(SQDataType));
		if (temp != NULL)
			psl->a = temp;
		else
			return;
		psl->capacity = newcapacity;
	}
}

📐 测试

在这里插入图片描述

⭕ 接口4：指定位置插入数据 (SeqListInser)

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
c复制代码void SeqListInser(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	//因为pos是size_t类型的，所以不用断言它是否小于0了，不过还是建议加上
	assert(pos > 0 && pos <= psl->size + 1);
	//判断是否要增容
	SeqListCheckCapcity(psl);
	int start = pos - 1;
	int end = psl->size - 1;
	while (start <= end)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[pos - 1] = x;
	psl->size++;
}

📐 测试

在这里插入图片描述

⭕ 接口5：输出数据 (SeqListPrint)

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
6
7
8
9
10
c复制代码void SeqListPrint(SLT* psl)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

📐 测试

image.png

⭕ 接口6：尾插 (SeqListPushBack)

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
6
c复制代码void SeqListPushBack(SLT* psl, SQDataType x)
{
	assert(psl);
	//根据分析尾部插入的话，传size+1吻合SeqListInser函数
	SeqListInser(psl, psl->size + 1, x);
}

📐 测试

在这里插入图片描述

⭕ 接口7：头插 (SeqListPushFront)

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
c复制代码void SeqListPushFront(SLT* psl, SQDataType x)
{
	assert(psl);
	SeqListInser(psl, 1, x);//根据分析头部插入的话，传1吻合SeqListInser函数
}

📐 测试

在这里插入图片描述

⭕ 接口8：指定位置删除数据 (SeqListErase)

请添加图片描述

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
c复制代码void SeqListErase(SLT* psl, size_t pos)
{
	assert(psl);
	//因为pos是size_t类型的，所以不用断言它是否小于0了，不过还是建议加上
	assert(pos > 0 && pos <= psl->size);
	size_t start = pos - 1;
	while (start < psl->size - 1)	
	{
		psl->a[start] = psl->a[start + 1];	
		start++;
	}
	psl->size--;
}

📐 测试

在这里插入图片描述

⭕ 接口9：尾删 (SeqListPopBack)

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
c复制代码void SeqListPopBack(SLT* psl)
{
	assert(psl);
	SeqListErase(psl, psl->size);
}

📐 测试

在这里插入图片描述

⭕ 接口10：头删 (SeqListPopFront)

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
c复制代码void SeqListPopFront(SLT* psl)
{
	assert(psl);
	SeqListErase(psl, 1);
}

📐 测试

在这里插入图片描述

⭕ 接口11：查找 (SeqListFind)

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
c复制代码//找到返回下标，找不到返回-1
int SeqListFind(SLT* psl, SQDataType x)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

📐 测试

在这里插入图片描述

⭕ 接口12：统计 (SeqListSize)

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
c复制代码size_t SeqListSize(SLT* psl)
{
	assert(psl);
	return psl->size;
}

📐 测试

在这里插入图片描述

⭕ 接口13：修改 (SeqListAt)

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
6
c复制代码size_t SeqListAt(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos > 0 && pos <= psl->size);
	psl->a[pos - 1] = x;	
}

📐 测试

在这里插入图片描述

⭕ 接口14：销毁 (SeqListDestory)

函数原型

在这里插入图片描述

函数实现

1
2
3
4
5
6
7
8
9
10
c复制代码void SeqListDestory(SLT* psl)	
{
	assert(psl);
	if (psl->a)
	{
		free(psl->a);
		psl->a = NULL;
	}
	psl->size = psl->capacity = 0;
}

📐 测试

在这里插入图片描述

📝 完整代码

     ❗ SeqList.h ❕

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
c复制代码#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SQDataType;
typedef struct SeqList
{
	SQDataType* a;//指向动态开辟的空间
	int size;//有效数据个数
	int capacity;//当前容量
}SLT;

//初始化
void SeqListInit(SLT* psl);
//检查容量
void SeqListCheckCapcity(SLT* psl);
//尾部插入
void SeqListPushBack(SLT* psl, SQDataType x);
//头部插入
void SeqListPushFront(SLT* psl, SQDataType x);
//尾部删除
void SeqListPopBack(SLT* psl);
//头部删除
void SeqListPopFront(SLT* psl);
//显示
void SeqListPrint(SLT* psl); 
//查找
int SeqListFind(SLT* psl, SQDataType x);	
//从某个值的位置插入
void SeqListInser(SLT* psl, size_t pos, SQDataType x);
//从某个值的位置删除	
void SeqListErase(SLT* psl, size_t pos);
//统计当前有多少数据 - 不要认为这样没必要，这是规范的操作
size_t SeqListSize(SLT* psl);
//修改
size_t SeqListAt(SLT* psl, size_t pos, SQDataType x);
//销毁
void SeqListDestory(SLT* psl);

     ❗ SeqList.c ❕

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
c复制代码#include"SeqList.h"
//初始化
void SeqListInit(SLT* psl)
{
	assert(psl);
	psl->a = NULL;
	psl->size = psl->capacity = 0;
}
//检查容量
void SeqListCheckCapcity(SLT* psl)
{
	assert(psl);
	//检查容量以决定要不要增容 - 2倍增容(一般情况为了避免频繁插入数据增容，或者一下开辟很大的空间，我们一般是每次增容2倍
	if (psl->size == psl->capacity)
	{
		size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		int* temp = (SQDataType*)realloc(psl->a, newcapacity * sizeof(SQDataType));
		if (temp != NULL)
			psl->a = temp;
		else
			return;
		psl->capacity = newcapacity;
	}
}
//尾部插入
void SeqListPushBack(SLT* psl, SQDataType x)
{
	/*assert(psl);
	SeqListCheckCapcity(psl);
	psl->a[psl->size] = x;
	psl->size++;*/
	assert(psl);
	SeqListInser(psl, psl->size + 1, x);//根据分析尾部插入的话，传size+1吻合SeqListInser函数
}
//头部插入
void SeqListPushFront(SLT* psl, SQDataType x)
{
	//assert(psl);
	//SeqListCheckCapcity(psl);
	////挪动数据
	//int end = psl->size - 1;
	//while (end >= 0)
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	--end;
	//}
	//psl->a[0] = x;
	//psl->size++;

	assert(psl);
	SeqListInser(psl, 1, x);//根据分析头部插入的话，传1吻合SeqListInser函数

}
//尾部删除
void SeqListPopBack(SLT* psl)
{
	//assert(psl);
	//assert(psl->size > 0);//如果没有数据就报错
	//psl->size--;

	assert(psl);
	SeqListErase(psl, psl->size);
}
//头部删除
void SeqListPopFront(SLT* psl)
{
	//assert(psl);
	//assert(psl->size > 0);//如果没有数据就报错
	//int start = 0;
	//while (start < psl->size - 1)
	//{
	//	psl->a[start] = psl->a[start + 1];
	//	start++;
	//}
	//psl->size--;	 

	assert(psl);
	SeqListErase(psl, 1);
}
//显示数据
void SeqListPrint(SLT* psl)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}
//销毁
void SeqListDestory(SLT* psl)	
{
	assert(psl);
	if (psl->a)
	{
		free(psl->a);
		psl->a = NULL;
	}
	psl->size = psl->capacity = 0;
}
//查找 - 找到返回下标，找不到返回-1
int SeqListFind(SLT* psl, SQDataType x)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//从某个位置插入，但是区间只能在第1个元素之前1个元素到最后1个元素之后1个元素
void SeqListInser(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos > 0 && pos <= psl->size + 1);//因为pos是size_t类型的，所以不用断言它是否小于0了，不过还是建议加上
	SeqListCheckCapcity(psl);
	int start = pos - 1;
	int end = psl->size - 1;
	while (start <= end)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[pos - 1] = x;
	psl->size++;
}
//从某个位置的值删除	
void SeqListErase(SLT* psl, size_t pos)
{
	assert(psl);
	assert(pos > 0 && pos <= psl->size);//因为pos是size_t类型的，所以不用断言它是否小于0了，不过还是建议加上
	size_t start = pos - 1;
	while (start < psl->size - 1)	
	{
		psl->a[start] = psl->a[start + 1];	
		start++;
	}
	psl->size--;
}
//统计当前有多少数据 - 其实不要认为这样没必要，这是一些规范的基本操作
size_t SeqListSize(SLT* psl)
{
	assert(psl);
	return psl->size;
}
//修改
size_t SeqListAt(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos > 0 && pos <= psl->size);
	psl->a[pos - 1] = x;	
}

     ❗ Test.c ❕

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
c复制代码#include"SeqList.h"
void TestSeqList1()
{
	SLT s;
	//初始化
	SeqListInit(&s);
	//尾插
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPushBack(&s, 6);
	SeqListPrint(&s);//显示数据
	//头插
	SeqListPushFront(&s, -1);
	SeqListPushFront(&s, -2);
	SeqListPushFront(&s, -3);
	SeqListPrint(&s);//显示数据
	//从某个值的位置插入
	SeqListInser(&s, 1, -4);
	SeqListPrint(&s);//显示数据
	//尾删
	SeqListPopBack(&s);
	SeqListPrint(&s);//显示数据
	//头删
	SeqListPopFront(&s);
	SeqListPrint(&s);//显示数据
	////从某个值的位置删除	
	SeqListErase(&s, 8);
	SeqListPrint(&s);//显示数据
	//修改
	SeqListAt(&s, 1, 3);	
	SeqListPrint(&s);//显示数据
	//查找 - 找到返回下标，找不到返回-1
	printf("%d\n", SeqListFind(&s, 2));
	//统计
	printf("%d\n", SeqListSize(&s));
	//销毁
	SeqListDestory(&s);
}

int main()
{
	//当然也可以写一个菜单，这里就不写了。但这里有几个注意的点：建议先写函数模块，测试完后没有问题再写菜单是最合适的
	TestSeqList1();
	return 0;
}

💨 输出结果

在这里插入图片描述

⚠ 关于数组越界有几个注意的点

1
2
3
4
5
6
7
8
9
10
11
c复制代码#include<stdio.h>
int main02()
{
	int a[10] = { 0 };
	a[9] = 10;
	//a[10] = 10;//err
	//a[11] = 10;//err
	a[12] = 10;//ok
	a[20] = 10;//ok
	return 0;
}

    ▶ 从以上就可以知道越界不一定报错，系统对越界的检查是抽查的形式，越界读一般是无法检查的；越界写也有可能无法检查，但是如果修改到标志位就会被检查出来

    ▶ 所谓标志位，就是如果越界写把标志位修改了，它就会报错，但是它不可能把后面的数据都设为标志位并检查，这也是为什么后面的数据无法检查的原因

❓ 为什么有了顺序表，还需要有链表这样的数据结构 ❔

    其实不难想象顺序表一定有一些缺陷，而链表恰恰可以优化缺陷

    1️⃣ 中间或头部的插入和删除，需要挪动数据，时间复杂度为O(N)

    2️⃣ 增容需要申请空间，拷贝数据，释放旧空间，会有不少的消耗

    3️⃣ 增容一般是以2倍的形式进行增长，势必会有一定的空间浪费。例如当前容量为100，增容后容量为200，我们只需要再继续插入5个数据，后面就没有数据了，那么将会浪费95个空间

三、链表

💦 链表的概念和结构

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

🎗 这里就来实现一个简单的链表(有三个文件：SList.h、SList.c、Test.c)

在这里插入图片描述

     ❗ SList.h文件 ❕

1
2
3
4
5
6
7
8
9
10
11
12
13
c复制代码#pragma once

#include<stdio.h>
#include<stdlib.h>

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void SListPrint(SLTNode* phead);

    ❗ SList.c文件 ❕

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码#include"SList.h"

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

    ❗ Test.c文件 ❕

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
c复制代码#include"SList.h"

void TestSList1()
{
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	n1->data = 1;

	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	n2->data = 2;

	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	n3->data = 3;

	SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
	n4->data = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	SLTNode* plist = n1;
	SListPrint(plist);
}
int main()
{
	TestSList1();
	return 0;
}

💨 结果

在这里插入图片描述

 
在这里插入图片描述

⚠ 注意

    1️⃣ 从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续

    2️⃣ 现实中的结点一般都是从堆上申请出来的

    3️⃣ 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表:

在这里插入图片描述

💦 链表的分类

1
2
复制代码实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
注：本章只了解单链表

1️⃣ 单向或者双向

在这里插入图片描述

2️⃣ 带头或者不带头

在这里插入图片描述

3️⃣ 循环或者非循环

在这里插入图片描述

🎗 虽然有这么多的链表结构，但是实际中最常用的只有两种结构

1️⃣ 无头单向非循环链表

在这里插入图片描述

2️⃣ 带头双向循环链表

在这里插入图片描述

⚠ 注意：

    ▶ 无头单向非循环链表:结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

    ▶ 带头双向循环链表:结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

💦 单链表各接口实现 (动图分析）

这里写了三个文件：

1️⃣ SList.h文件，用于函数声明

2️⃣ SList.c文件，用于函数的定义

3️⃣ Test.c文件，用于测试函数

⭕ 首先需要定义结构体SLTNode

1
2
3
4
5
6
c复制代码typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;//存储整型数据
	struct SListNode* next;//指向下一个节点的地址 
}SLTNode;

并定义plist变量 -> Test.c

1
c复制代码SLTNode* plist = NULL;

⭕ 接口1：开辟空间 (BuySListNode)

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
c复制代码SLTNode* BuySListNode(SLTDataType x)
{
  //每次调用开辟一个节点的空间
  SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
  if (node == NULL)
  {
  	printf("malloc fail\n");
  	exit(-1);
  }
  node->data = x;
  node->next = NULL;
  //开辟成功，返回地址
  return node;
}

⭕ 接口2：输出数据 (SListPrint)

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
c复制代码void SListPrint(SLTNode* phead)
{
  //据情况分析，此处不需要断言，因为我们想在空链表时输出NULL
  //assert(phead);

  SLTNode* cur = phead;
  //遍历
  while (cur != NULL)
  {
  	printf("%d->", cur->data);
  	cur = cur->next;
  }
  printf("NULL\n");
}

⭕ 接口3：尾插数据 (SListPushBack)，详解请看下图：

请添加图片描述

函数原型：

在这里插入图片描述

函数实现：

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
c复制代码void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	//据析，指针可能为空，但是指针的地址不可能为空，所以需要断言(pphead就是plist的地址)，且这里不能断言*pphead,因为这里空链表是可以处理的
	assert(pphead);
	//特殊情况
		//1、空链表
	if (*pphead == NULL)
	{
		//调用BuySListNode去开辟新节点
		SLTNode* newnode = BuySListNode(x);
		*pphead = newnode;
	}
		//2、非空链表
	else
	{
		SLTNode* tail = *pphead;
		//找尾 - NULL
		while(tail->next != NULL)
		{
			tail = tail->next;
		}	
		//开辟节点
		SLTNode* newnode = BuySListNode(x);
		tail->next = newnode;	
	}
}

📐 测试

在这里插入图片描述

⭕ 接口4：头插数据 (SListPushFront)，详解请看下图：

请添加图片描述

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
c复制代码void SListPushFront(SLTNode** pphead, SLTDataType x)
{
  assert(pphead);
  //对于首插来说，没有特殊情况，以下代码适用于空链表和非穿链表
  SLTNode* newnode = BuySListNode(x);
  newnode->next = *pphead;
  *pphead = newnode;
}

📐 测试

在这里插入图片描述

⭕ 接口5：尾删数据 (SListPopBack)，详解请看下图(2种方式)：

方式1：

请添加图片描述
方式2：
请添加图片描述

函数原型：

在这里插入图片描述

函数实现：

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
c复制代码void SListPopBack(SLTNode** pphead)
{
	//据析，这里需要断言plist的地址是否传成NULL了；以及没有节点的情况
	assert(pphead);
	assert(*pphead);
	//特殊情况
	//一个节点的情况
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//多个节点的情况 - 找尾 
		//1.先指向第一个节点的位置
		SLTNode* tail = *pphead;
	
		//2.删尾(错误示范) - 这样删尾会造成野指针(因为每个节点都是一个局部节点，如果这样释放掉后，则前一个节点的next就是一个野指针)
		/*while (tail->next != NULL)
		{
			tail = tail->next;
		}
		free(tail);
		tail = NULL; */
		
		//2.删尾(正确示范1)
		/*while (tail->next->next != NULL)
		{	
			tail = tail->next; 
		}
		free(tail->next);
		tail->next = NULL;*/
	
		//2.删尾(正确示范2) - 双指针
		SLTNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail->next);
		prev->next = NULL;
	}
}

📐 测试

在这里插入图片描述

⭕ 接口6：头删数据 (SListPopFront)，详解请看下图

请添加图片描述

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码void SListPopFront(SLTNode** pphead)
{
  assert(pphead);
  assert(*pphead);
  //以下代码能适用于一个节点和多个节点,如果只有一个节点的情况，先备份NULL，就将NULL赋值于*pphead
  //备份第2个节点的地址
  SLTNode* temp = (*pphead)->next;
  //释放第一个节点
  free(*pphead);
  //再将拷贝的节点链接起来
  (*pphead) = temp;	
}

📐 测试

在这里插入图片描述、

⭕ 接口7：查找数据 (SListFind)

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
c复制代码SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
  //据析，如果是空链表时，这里就无法查找，所以需要断言
  assert(phead);
  SLTNode* cur = phead;
  while (cur)
  {
  	if (cur->data == x)
  	{
  		return cur;//返回x所在节点的地址
  	}
  	else
  	{
  		cur = cur->next;
  	}
  }
  return NULL;//找不到返回空
}

⭕ 接口8：指定的数之前插入数据 (SlistInser)，不支持尾插，详解请看下图

请添加图片描述

因此可以看出单链表不适合在指定的数的前面插入的，因为它需要前面一个节点的地址

函数原型：

在这里插入图片描述

函数实现：

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
c复制代码void SlistInser(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//据析，这里需要调用SlistFind函数来配合使用，所以这里不需要判断是否为空链表，因为SlistFind函数内已经断言过了
	assert(pphead);
	assert(pos);
	//特殊情况
	//1、调用头插的接口
	if (*pphead == pos)
	{
		SListPushFront(pphead, x);
	}
	//2、非头插入 - 不包含尾插
	else
	{
		//找pos位置的前一个节点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		//注意这里它们前后链接时可以颠倒
		newnode->next = pos;
		prev->next = newnode;
	}
}

📐 测试

在这里插入图片描述

⭕ 接口9：指定的数之后插入数据 (SlistInser)，不支持头插，详解请看下图

请添加图片描述

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
c复制代码void SlistInserAfter(SLTNode* pos, SLTDataType x)
{
	//据析，这里也不需要判断空链表的情况
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	//注意，必须先把pos后面节点的地址交给newnode->next，再将newnode的地址交给pos->next；两者不能颠倒
	newnode->next = pos->next;
	pos->next = newnode;	
}

📐 测试

在这里插入图片描述

⭕ 接口10：指定的数删除 (SlistErase)，详解请看下图

请添加图片描述

因此可以看出单链表不适合在删除指定的数，因为它需要前面一个节点的地址

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
c复制代码void SlistErase(SLTNode** pphead, SLTNode* pos)
{
	//据析，这里也不需要判断空链表的情况
	assert(pphead);

	//1、调用头删
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	//2、其余节点 - 包括尾删
	else
	{
		//找pos位置的前一个节点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

📐 测试

在这里插入图片描述

⭕ 接口11：指定的数之后删除 (SlistEraseAfter)，详解请看下图

请添加图片描述

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码void SlistEraseAfter(SLTNode* pos)
{
	//据析如果那个数后面为NULL，就删除不了，需要断言
	assert(pos);
	assert(pos->next);	

	//拷贝一份
	SLTNode* temp = pos->next->next;
	free(pos->next);
	pos->next = NULL;
	pos->next = temp;
}

📐 测试

在这里插入图片描述

⭕ 接口12：统计 (SListSize)

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码int SListSize(SLTNode* phead)
{
	//这里不需要断言
	int size = 0;
	SLTNode* cur = phead;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

📐 测试

在这里插入图片描述

⭕ 接口13：判空 (SListSize)

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c复制代码bool SListEmpty(SLTNode* phead)
{
	//判空，空是真，非空是假

	//写法1
	//return phead == NULL ? true : false;

	//写法2
	//if (phead == NULL)
	//{
	//	return true;
	//}
	//else
	//{
	//	return false;
	//}

	//写法3
	return phead == NULL; 
}

📐 测试

在这里插入图片描述

⭕ 接口14：销毁 (SListDestory)

函数原型：

在这里插入图片描述

函数实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
c复制代码void SListDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}

📐 测试

在这里插入图片描述

📝 完整代码

     ❗ SList.h ❕

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
c复制代码#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;//存储整型数据
	struct SListNode* next;//指向下一个节点的地址 
}SLTNode;

//只读的函数接口
void SListPrint(SLTNode* phead);
int SListSize(SLTNode* phead);
bool SListEmpty(SLTNode* phead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
SLTNode* BuySListNode(SLTDataType x);
void SListInserAfter(SLTNode* pos, SLTDataType x);
void SListEraseAfter(SLTNode* pos);
void SListDestory(SLTNode** pphead);

//读写的函数接口
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);
void SListInser(SLTNode** pphead,  SLTNode* pos, SLTDataType x);
void SListErase(SLTNode** pphead, SLTNode* pos);

    ❗ SList.c ❕

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
c复制代码#include"SList.h"


void SListPrint(SLTNode* phead)
{
	//据情况分析，此处不需要断言，因为我们想在空链表时输出NULL
	//assert(phead);

	SLTNode* cur = phead;
	//遍历
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SLTNode* BuySListNode(SLTDataType x)
{
	//每次调用开辟一个节点的空间
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	
	node->data = x;
	node->next = NULL;
	//开辟成功，返回地址
	return node;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	//据析，指针可能为空，但是指针的地址不可能为空，所以需要断言(pphead就是plist的地址)，且这里不能断言*pphead,因为这里空链表是可以处理的
	assert(pphead);
	//特殊情况
	//1、空链表
	if (*pphead == NULL)
	{
		//调用BuySListNode去开辟新节点
		SLTNode* newnode = BuySListNode(x);
		*pphead = newnode;
	}
	//2、非空链表
	else
	{
		SLTNode* tail = *pphead;
		//找尾 - NULL
		while(tail->next != NULL)
		{
			tail = tail->next;
		}	
		//开辟节点
		SLTNode* newnode = BuySListNode(x);
		tail->next = newnode;	
	}
}

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//对于首插来说，没有特殊情况，以下代码适用于空链表和非空链表
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
 
void SListPopBack(SLTNode** pphead)
{
	//据析，这里需要断言plist的地址是否传成NULL了；以及没有节点的情况
	assert(pphead);
	assert(*pphead);
	//特殊情况
	//一个节点的情况
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//多个节点的情况 - 找尾 
		//1.先指向第一个节点的位置
		SLTNode* tail = *pphead;
	
		//2.删尾(错误示范) - 这样删尾会造成野指针(因为每个节点都是一个局部节点，如果这样释放掉后，则前一个节点的next就是一个野指针)
		/*while (tail->next != NULL)
		{
			tail = tail->next;
		}
		free(tail);
		tail = NULL; */
		
		//2.删尾(正确示范1)
		/*while (tail->next->next != NULL)
		{	
			tail = tail->next; 
		}
		free(tail->next);
		tail->next = NULL;*/
	
		//2.删尾(正确示范2) - 双指针
		SLTNode* prev = NULL;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail->next);
		prev->next = NULL;
	}
}

void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);

	//以下代码能适用于一个节点和多个节点,如果只有一个节点的情况，先备份NULL，就将NULL赋值于*pphead
	//备份第2个节点的地址
	SLTNode* temp = (*pphead)->next;
	//释放第一个节点
	free(*pphead);
	//再将拷贝的节点链接起来
	(*pphead) = temp;	
}

int SListSize(SLTNode* phead)
{
	//这里不需要断言
	int size = 0;
	SLTNode* cur = phead;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

bool SListEmpty(SLTNode* phead)
{
	//判空，空是真，非空是假

	//写法1
	//return phead == NULL ? true : false;

	//写法2
	//if (phead == NULL)
	//{
	//	return true;
	//}
	//else
	//{
	//	return false;
	//}

	//写法3
	return phead == NULL; 
}

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	//据析，如果是空链表时，这里就无法查找，所以需要断言
	assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;//返回x所在节点的地址
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;//找不到返回空
}

void SListInser(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	//据析，这里需要调用SlistFind函数来配合使用，所以这里不需要判断是否为空链表，因为SlistFind函数内已经断言过了
	assert(pphead);
	assert(pos);
	//特殊情况
	//1、调用头插的接口
	if (*pphead == pos)
	{
		SListPushFront(pphead, x);
	}
	//2、非头插入 - 不包含尾插
	else
	{
		//找pos位置的前一个节点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		//注意这里它们前后链接时可以颠倒
		newnode->next = pos;
		prev->next = newnode;
	}
}

void SListInserAfter(SLTNode* pos, SLTDataType x)
{
	//据析，这里也不需要判断空链表的情况
	assert(pos);
	SLTNode* newnode = BuySListNode(x);
	//注意，必须先把pos后面节点的地址交给newnode->next，再将newnode的地址交给pos->next；两者不能颠倒
	newnode->next = pos->next;
	pos->next = newnode;	
}

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	//据析，这里也不需要判断空链表的情况
	assert(pphead);

	//1、调用头删
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	//2、其余节点 - 包括尾删
	else
	{
		//找pos位置的前一个节点
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
void SListEraseAfter(SLTNode* pos)
{
	//据析如果那个数后面为NULL，就删除不了，需要断言
	assert(pos);
	assert(pos->next);	

	//拷贝一份
	SLTNode* temp = pos->next->next;
	free(pos->next);
	pos->next = NULL;
	pos->next = temp;
}

void SListDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}

    ❗ Test.c ❕

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
87
88
89
90
91
92
93
c复制代码#include"SList.h"

void TestSList1()
{
	SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
	n1->data = 1;

	SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
	n2->data = 2;

	SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
	n3->data = 3;

	SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
	n4->data = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	SLTNode* plist = n1;
	SListPrint(plist);
}

void TestSList2()
{
	//定义plist变量
	SLTNode* plist = NULL;
	//尾插
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);
	//头插
	SListPushFront(&plist, 0);
	SListPushFront(&plist, -1);
	SListPushFront(&plist, -2);
	SListPrint(plist);
	//尾删
	SListPopBack(&plist);
	SListPrint(plist);
	//头删
	SListPopFront(&plist);
	SListPrint(plist);
	//查找 - 查找空链表时，断言报错；查找失败返回NULL;查找成功返回x所在的节点的地址 
	SLTNode* pos = SListFind(plist, 0);
	if (pos)
	{
		printf("找到了\n");
	}
	//指定的数之前插入数据 - 此函数实现不了尾插
	pos = SListFind(plist, -1);
	if (pos)//找到了才插入数据
	{
		SListInser(&plist, pos, -2);
	}
	SListPrint(plist);
	//指定的数之后插入数据 - 此函数实现不了头插
	pos = SListFind(plist, 3);
	if (pos)
	{
		SListInserAfter(pos, 4);
	}
	SListPrint(plist);
	//指定的数删除
	pos = SListFind(plist, 4);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
	//删除指定的数之后的数
	pos = SListFind(plist, 2);
	if (pos)
	{
		SListEraseAfter(pos);
	}
	SListPrint(plist);
	//统计
	printf("%d\n", SListSize(plist));
	//判空，空是真，非空是假
	printf("%d\n", SListEmpty(plist));
	//销毁
	SListDestory(&plist);
}

int main()
{
	TestSList2();
	return 0;
}

💨 结果

在这里插入图片描述

四、顺序表和链表的区别和联系

不同点 顺序表 链表
存储空间上 物理上一定连续 逻辑上连续，但物理上不一定连续
随机访问 支持 O(1) 不支持 O(N)
任意位置插入或删除元素 可能需要搬移元素，效率低 只需要修改指针指向
插入 动态顺序表，空间不够时需要扩容 没有容量的概念
应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁
缓存利用率、缓存命中率 高 低

💨 总结：

链表和顺序表没有谁更优，它们各有优缺点，相辅相成

备注：缓存利用率参考存储体系结构以及局部原理性

在这里插入图片描述

在这里插入图片描述

假设写了一个程序，实现分别对顺序表和链表上的每个数据+1，那么这个程序会编译成指令，然后CPU再执行
CPU运算的速度很快，那内存的速度跟不上，CPU一般就不会直接访问内存，而是把要访问的数据先加载到缓存体系，如果是 ≤ 8byte的数据 (寄存器一般是8byte)，会直接到寄存器；而大的数据，会到三级缓存，CPU直接跟缓存交互。
CPU执行指令运算要访问内存，先要取0x10 (假设) 的数据，拿0x10去缓存中找，发现没有 (不命中) ，这时会把主存中这个地址开始的一段空间都读进来 (缓存)。
如果是整型数组，下一次访问0x14、0x18… 就会命中
如果是链表，先取第1个节点0x60，不命中；再取第2个0x90，不命中…。这样会造成一定的缓存污染

相关CPU缓存博客

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%