第二章 数据结构

链表与邻接表

【一般实现方式:指针+结构体——动态链表(工程中常用)】

1
2
3
4
5
6
7
struct Node
{
int val;
Node *next;
}

new Node(); // 非常慢,若要使用可以初始化n个节点

这里介绍用数组模拟【静态链表】该数据结构的方式——速度快!

单链表

单链表中用的最多的是邻接表——n个单链表:将每个点(共有n个点)的所有邻边存下来

邻接表应用:存储图和树(e.g. 最短路问题、最小生成树问题、……)

单链表基本结构:从头指针开始依次指向若干个节点,每个节点存储一个数值val和一个next指针,沿着next指针不断访问后续数据,直到指向空指针

单链表基本结构

数组模拟链表存储需要定义(均为整数型数组):

  • e[N]:存储各点数值val
  • ne[N]:存储各点next指针——空节点下标用-1表示

二者通过下标关联 :

数组模拟单链表

事实上,同一下标i对应的e[i]与ne[i]表示一个节点的数值val及其next指针,将其看作一个结构体会更好理解,但在代码实现过程中,为使得代码尽量简洁,选择直接对数组下标进行操作

1
2
3
4
5
6
7
8
9
10
11
12
// 结构体写法
struct Node
{
int e, ne;
}nodes[N];

// 以删除为例:删除下标是k的节点“后面”的一个节点
void remove(int k)
{
// 直接让k节点指向的节点变成其后的节点指向的节点
nodes[k].ne = nodes[nodes[k].ne].ne;
}

需要注意:一个下标代表一个节点,各节点之间的指向关系仅由next指针(即ne[i]的值)决定

单链表的性质:顺序(单向)访问——可以在O(1)的时间复杂度内找到指定节点的后一个节点(包括完成插入等操作),但如果要找到指定节点之前的节点,则只能从头指针head开始遍历


例题:826. 单链表 - AcWing题库

实现一个单链表,链表初始为空,支持三种操作:

  1. 向链表头插入一个数;
  2. 删除第 k 个插入的数后面的一个数;
  3. 在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作,进行完所有操作后,从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。

输入格式

第一行包含整数 M,表示操作次数。

接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:

  1. H x,表示向链表头插入一个数 x。
  2. D k,表示删除第 k 个插入的数后面的数(当 k 为 0 时,表示删除头结点)。
  3. I k x,表示在第 k 个插入的数后面插入一个数 x(此操作中 k 均大于 0)。

输出格式

共一行,将整个链表从头到尾输出。

数据范围

1≤M≤100000 所有操作保证合法。

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
#include <iostream>

using namespace std;

const int N = 100010;

// head 表示头节点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少(i的下一个点的下标)
// idx 用于存储当前已经用到了哪个节点(存入新数据时将数据存入idx所在下标,并将idx往后移动一个下标)
int head, e[N], ne[N], idx;

// 需要注意:idx仅表示当前链表中有多少组节点(数值val+next指针),e[]和ne[]数组会随着idx的增加向后存储,这意味着这两个数组中的数据顺序与链表表示的数据顺序不一致

// 初始化
void init()
{
head = -1;
idx = 0;
}

// 将x插入到头节点
// 这里采用头插入方式,若采用尾插入方式,可以基于后续的add函数并结合实时存储链表的尾端指针tail实现
void add_to_head(int x)
{
e [idx] = x; // 第一步:将新数据x存入到数组e[]中
ne [idx] = head; // 第二步:让新数据x所在节点中的next指针指向原来的头节点
head = idx; // 第三步:让新数据x所在的节点变成新的头节点
idx ++ ; // 数组中存入了一组新的数据(开辟了一个新节点)
}

// 注意:下述所谓“前/后”的概念是针对链表中的存储顺序,而非在数组模拟实现中数组内的位置关系

// 将x插入到下标是k的节点(k节点)“后面”
void add(int k, int x)
{
e [idx] = x; // 第一步:将新数据x存入到数组e[]中
ne [idx] = ne[k]; // 第二步:让新数据x所在节点中的next指针指向原来k节点指向的节点
ne[k] = idx; // 第三步:让k节点指向新数据x所在的节点
idx ++ ; // 数组中存入了一组新的数据(开辟了一个新节点)
}

// 删除节点:删除下标是k的节点“后面”的一个节点
// 动态链表【工程用】中删除节点(地址)时采取直接释放内存的方式;这里只是让该节点脱离链表结构,但并未释放该节点的存储
void remove(int k)
{
// 直接让k节点指向的节点变成其后的节点指向的节点
ne[k] = ne[ne[k]];
}

int main()
{
int M;
cin >> M;

init(); // 链表初始化

char flag;
int k, x;

while (M -- )
{
cin >> flag;
if (flag == 'H')
{
// 向链表头插入一个数
cin >> x;
add_to_head(x);
}
else if (flag == 'D')
{
// 删除第 k 个插入的数后面的一个数:由于idx已经存储了插入节点的数量,因此该操作实际意味着将下标是k - 1的节点(即插入的第k个节点)指向的下一个节点从链表中删去
cin >> k;
if (k != 0)
remove(k - 1);
else
head = ne[head]; // 当 k 为 0 时,表示删除头结点
}
else if (flag == 'I')
{
// 在第 k 个插入的数后插入一个数:与删除同理,于链表中,在下标是k - 1的节点(即插入的第k个节点)后插入一个新的节点
cin >> k >> x;
add(k - 1, x);
}
}

int ptr = head;

while (ptr != -1)
{
cout << e[ptr] << " ";
ptr = ne[ptr];
}

return 0;
}

双链表

用于优化某些问题

基本结构与单链表一致,但每个节点会存储两个指针,一个指向前一个节点,另一个指向后一个节点

每个节点(下标)的指针存储方式:数组ne[] -> 指向前一个节点的指针数组l[] + 指向后一个节点的指针数组r[]

双链表中不再定义头节点head与尾节点tail,而是直接令0号下标对应的节点为head节点、令1号下标对应的节点为tail节点


例题:827. 双链表 - AcWing题库

实现一个双链表,双链表初始为空,支持 5 种操作:

  1. 在最左侧插入一个数;
  2. 在最右侧插入一个数;
  3. 将第 k 个插入的数删除;
  4. 在第 k 个插入的数左侧插入一个数;
  5. 在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作,进行完所有操作后,从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1 个插入的数,第 2 个插入的数,…第 n 个插入的数。

输入格式

第一行包含整数 M,表示操作次数。

接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:

  1. L x,表示在链表的最左端插入数 x。
  2. R x,表示在链表的最右端插入数 x。
  3. D k,表示将第 k 个插入的数删除。
  4. IL k x,表示在第 k 个插入的数左侧插入一个数。
  5. IR k x,表示在第 k 个插入的数右侧插入一个数。

输出格式

共一行,将整个链表从左到右输出。

数据范围

1≤M≤100000 所有操作保证合法。

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
#include <iostream>

using namespace std;

const int N = 100010;

int head, e[N], l[N], r[N], idx;

// 初始化
void init()
{
// 0表示左端点,1表示右端点
r[0] = 1;
l[1] = 0;
idx = 2; // 0号和1号节点已被占用
}

// 于链表中,在存储下标为k的节点右侧插入一个点
// 若想在存储下标为k的节点左侧插入,直接调用add(l[k], x)即可
void add(int k, int x)
{
e[idx] = x; // 第一步:将新数据x存入到数组e[]中
// 第二步:右侧指针改动
r[idx] = r[k]; // 让新数据x所在节点的右指针指向原来k节点右侧的节点
r[k] = idx; // 让k节点的右指针指向新数据x所在的节点
// 第三步:左侧指针改动
l[idx] = k; // 让新数据x所在节点的左指针指向k节点
// 注意:由于第二步已经将下标为k的节点的右指针指向转移到了插入的节点上,因此不可以再通过r[k]对原先在k节点右侧的节点进行索引!
l[r[idx]] = idx; // 让原来k节点右侧的节点的左指针指向新数据x所在的节点
idx ++ ; // 数组中存入了一组新的数据(开辟了一个新节点)
}

// 删除下标是k的节点
void remove(int k)
{
// 右指针:让k节点左侧节点的右指针指向k节点右指针指向的节点
r[l[k]] = r[k];
// 左指针:让k节点右侧节点的左指针指向k节点左指针指向的节点
l[r[k]] = l[k];
}

int main()
{
int M;
cin >> M;

init(); // 链表初始化

char flag[2]; // 注意本题涉及操作标志可能包含两个字母,需分别读入并依次判断!
int k, x;

while (M -- )
{
cin >> flag[0];
if (flag[0] == 'L')
{
// 在链表的最左端插入一个数
cin >> x;
add(0, x); // 0表示左端点;在链表的最左端插入一个数等效于在链表左端点右侧插入一个数
}
else if (flag[0] == 'R')
{
// 在链表的最右端插入一个数
cin >> x;
add(l[1], x); // 1表示右端点;在链表最右端插入一个数等效于在链表右端点左侧的节点后插入一个数
}
else if (flag[0] == 'D')
{
// 删除第 k 个插入的数:由于idx已经存储了已插入节点的数量 + 2(因为存了左端点和右端点),因此该操作实际意味着将下标是k + 1的节点(即插入的第k个节点)从链表中删去
cin >> k;
remove(k + 1);
}
else if (flag[0] == 'I')
{
cin >> flag[1];
if (flag[1] == 'R')
{
// 在第 k 个插入的数右侧插入一个数
cin >> k >> x;
add(k + 1, x); // 与删除中同理,下标+1
}
else if (flag[1] == 'L')
{
// 在第 k 个插入的数左侧插入一个数:可视为在第 k 个插入的数左侧的节点右侧插入一个数
cin >> k >> x;
add(l[k + 1], x); // 与删除中同理,下标+1
}
}
}

int ptr = r[0]; // 0表示左端点;头指针指向r[0]

while (ptr != 1) // 1表示右端点
{
cout << e[ptr] << " ";
ptr = r[ptr];
}

return 0;
}

栈与队列

【一般实现方式:C++ STL中容器】

这里介绍用数组模拟该数据结构的方式。

先进后出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 100010; 

int stk[N], tt; // stk[]为栈模拟数组;tt表示栈顶下标

// 插入
stk[ ++ tt] = x;

// 弹出
tt -- ;

// 判断栈是否为空
if (tt > 0)
// not empty
else
// empty

// 栈顶
stk[tt];

队列

先进先出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 100010; 

int q[N], hh, tt = -1; // q[]为队列模拟数组;hh为队头下标、tt为队尾下标

// 在队尾插入元素
q[ ++ tt] = x;

// 在队头弹出元素
hh ++ ;

// 判断队列是否为空
if (hh <= tt)
// not empty
else
// empty

// 取出队头元素
q[hh];

单调栈

单调队列

KMP

作者

Tim

发布于

2025-04-07

更新于

2025-04-29

许可协议

评论