链表

链表

八月 01, 2021

链表

单链表 多个单链表构成邻接表 ：应用：存储图，存储树

双链表 应用：优化某些题

1.单链表：

用数组模拟：
1.定义每个节点的val

e[n]定义当前点
ne[n] 定义下一个节点的位置

如下图所示

image-20210805185832865

空节点下标用-1表示

单链表：

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
#include<iostream>
using namespace std;
const int N=100010;
//head 表示头结点的下标
//e[i] 表示节点i的值
//ne[i] 表示节点i的next指针是多少
//idx存储当前已经用到了哪个点
 
void init(){
    head=-1;
    idx=0;
}

void add_to_head(int x){
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}
//将x插到头节点

void add(int x,int k){
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
//将x插到k的后面

void remove(int k){
    ne[k]=ne[ne[k]];
}

int main(){
    int m;
    cin>>m;
    while(m--){
        char op;
        int k,x;
        cin>>op;
        if(op=='H') cin>>x,add_to_head(x);
        else
            if(op=='D') cin>>k,remove(k);
        else cin>>k>>x,add(k,x);
    }
    for(int i=head&&i!=-1;i=ne[i]){
        cout<<e[i]<<" ";
    }
    return 0;
}
2.双链表

每一个点有两个指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int l[n],r[n],e[n];//l指每个点左边的点是谁

void init(){
    //l,r赋值为0表示左端点，1表示右端点
	r[0]=1;
	l[1]=0;
    idx=2;
}

//在下标是k的点的右边，插入x
void add(int k,int x){
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    r[k]=idx;
    l[r[k]]=idx++;
}

void remove(int k){
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}