链表与邻链表
0.传统的链表创建方式在运算速度上非常慢
struct ListNode{
int val;
struct ListNode* next;
};
new struct ListNode();
|
1.数组模拟单链表
数组模拟链表，也成为静态链表
链表的实现方式：
一开始用head指针存储链表头节点，head之后就是空指针
之后让head之后的指针指向新节点，以此类推，直到最后一个节点，再让下一个节点指向空指针
定义e[n]为该节点的值，ne[n]为该节点的next指针
e[0] = 3,ne[0] = 1(指节点1)
e[1] = 5,ne[1] = 2(指节点2)
…
e[3] = 9,ne[3] = -1(空节点)
如何在头节点插入一个节点（算法题常用）
链表需要数形结合
1.将所想要插入的值的next指针指向0节点
2.将head的next指针指向该值
3.存储该值
代码实现
void add_to_head(int &x)
{
ne[idx] = head;
head = idx;
e[idx] = x;
idx++;
}
|
如何在任意位置插入一个值
1.首先需要直到该位置的上一节点k
2.与头节点插入类似，先让该值的next变为k的next指针
3.让k的next指针指向该节点
4.存储该值
实现代码
void add(int& k, int& x)
{
ne[idx] = ne[k];
ne[k] = idx;
e[idx] = x;
idx++;
}
|
如何删除一个节点
链表节点的删除本质上是跳过该节点
实现代码
void remove(int& k)
{
ne[k] = ne[ne[k]];
}
|
总实现代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
const int N = 100010;
int head, e[N], ne[N];
int idx;
void Init()
{
head = -1;
idx = 0;
}
void add_to_head(int &x)
{
ne[idx] = head;
head = idx;
e[idx] = x;
idx++;
}
void add(int& k, int& x)
{
ne[idx] = ne[k];
ne[k] = idx;
e[idx] = x;
idx++;
}
void remove(int& k)
{
ne[k] = ne[ne[k]];
}
int main()
{
Init();
}
|
例题
题目描述
实现一个单链表，链表初始为空，支持三种操作：
向链表头插入一个数；
删除第 k个插入的数后面的数；
在第 k个插入的数后插入一个数。
现在要对该链表进行 M次操作，进行完所有操作后，从头到尾输出整个链表。
注意:题目中第 k个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。
|
输入格式
第一行包含整数 M，表示操作次数。
接下来 M行，每行包含一个操作命令，操作命令可能为以下几种：
H x，表示向链表头插入一个数 x。
D k，表示删除第 k个插入的数后面的数（当 k 为 0时，表示删除头结点）。
I k x，表示在第 k个插入的数后面插入一个数 x（此操作中 k 均大于 0）。
|
输出格式
共一行，将整个链表从头到尾输出。
数据范围
1≤M≤10000
|
题解
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
const int N = 10010;
int idx, e[N], ne[N];
int head;
void Init()
{
head = -1;
idx = 0;
}
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
int m;
cin >> m;
Init();
while (m--)
{
char ch;
int k, x;
cin >> ch;
if (ch == 'H')
{
cin >> x;
add_to_head(x);
}
else if (ch == 'D')
{
cin >> k;
if (!k) head = ne[head];
else remove(k-1);
}
else
{
cin >> k >> x;
add(k-1, x);
}
}
for (int i = head;i != -1;i = ne[i])
{
cout << e[i] << ' ';
}
return 0;
}
|
邻接表：
将每个单链表连接起来，就是邻接表
邻接表的应用：
存储树和图
2.数组模拟双链表
双链表有两个方向，一个指向前，另一个指向后，而单链表只能指向后
因此也可以看出单链表插入时只能插入在往后的方向
需要的数组有e[n],l[n],r[n]和下标idx
e[n]表示该点的值
l[n]表示该点左边节点的指针
r[n]表示右边节点的指针，与单链表next同理
idx表示第几次操作数
head默认为0，tail默认为1
对于插入节点和删除节点的操作与单链表相类似
插入节点
1.存储要插入节点的值（可以放在任意位置）
2.改变k的右节点和插入值的左节点，让k和idx连接
3.改变k原先右节点的左节点和插入值的右节点，让k原先的右节点和插入值连接
4.最后操作数+1
实现代码
void addr(int k,int &x)
{
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++;
}
|
如果想要在k的左边插入一个节点，可以理解为在k的左节点的后面插入一个点，也就是add( l [ k ] , x )
删除节点
让该节点的左节点所指的next直接指向该节点的右节点
让该节点的右节点所指的last直接指向该节点的左节点
实现代码
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
|
总实现代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
const int N = 10010;
int e[N], l[N], r[N], idx;
void Init()
{
r[0] = 1, l[1] = 0;
idx = 2;
}
void add(int k,int &x)
{
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++;
}
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main()
{
Init();
}
|
wechat
alipay
