链表
单链表
作用：存储图和树
存储：
1
2
| int head,ne[N],e[N];
int cnt;
|
插入(头节点):
1
2
3
4
5
| void insert_h(int x){
e[++cnt]=x;
ne[cnt]=head;
head=cnt;
}
|
插入(第$k$个插入的数后):
1
2
3
4
5
| void insert(int k,int x){
e[++cnt]=x;
ne[cnt]=ne[k];
ne[k]=cnt;
}
|
删除(第$k$个插入的数的后一个数):
1
2
3
4
5
6
7
8
| void del(int k){
if(k==0){
head=ne[head];
}
else{
ne[k]=ne[ne[k]];
}
}
|
如果需要查找元素的位置，可以用一个数组$plc$,在插入时记录每个数的$cnt$即可
双链表
作用：优化某些问题
存储：
1
2
| int head,tail,l[N],r[N],e[N];
int cnt;
|
插入（头节点）:
1
2
3
4
5
6
7
8
| void insert_head(int x){
e[++cnt]=x;
l[cnt]=0;
l[head]=cnt;
r[cnt]=head;
head=cnt;
if(!tail)tail=cnt;
}
|
插入（尾节点）：
1
2
3
4
5
6
7
8
| void insert_tail(int x){
e[++cnt]=x;
l[cnt]=tail;
r[tail]=cnt;
r[cnt]=0;
if(!head)head=cnt;
tail=cnt;
}
|
插入（第$k$个数左）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void insert_l(int k,int x){
e[++cnt]=x;
if(head==k){
l[k]=cnt;
head=cnt;
l[cnt]=0;
r[cnt]=k;
}
else{
r[l[k]]=cnt;
l[cnt]=l[k];
l[k]=cnt;
r[cnt]=k;
}
}
|
插入（第$k$个数右）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void insert_r(int k,int x){
e[++cnt]=x;
if(tail==k){
r[k]=cnt;
tail=cnt;
l[cnt]=k;
r[cnt]=0;
}
else{
l[r[k]]=cnt;
r[cnt]=r[k];
r[k]=cnt;
l[cnt]=k;
}
}
|
删除（第$k$个插入的数）:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void del(int k){
if(tail==k&&head==k){
tail=0,head=0;
}
else if(head==k){
head=r[k];
l[r[k]]=0;
}
else if(tail==k){
tail=l[k];
r[l[k]]=0;
}
else{
r[l[k]]=r[k];
l[r[k]]=l[k];
}
}
|