数组模拟＜—＞链表_使用数组模拟链表

---

---

一、单连表

数组模拟时，idx作为链条的导向（idx可以查到该位置的元素）
在加入新元素的时候，首先将新元素插到e[]，然后将该元素的位置下标存入en[]
！！！！在第k个位置 插入/删除 时，即为在k-1的位置后面操作（由于下标是从0开始的）操作时注意传入形参的位置要减一！！！！！！！

const int w=1e6+10;

int e[w],en[w],idx,head;

//初始化 
void inti(){
    head=-1;
    idx=0;
}
1
2
3
4
5
6
7
8
9
10

`让该位置的节点等于头结点，然后让头结点改为该位置的下标 `

1
2
3

//在头节点加入一个元素 
void add_to_head(int x){
    e[idx]=x;
    en[idx]=head;
    head=idx;
    idx++;
}
1
2
3
4
5
6
7

首先同样的先存入元素，让插入的链表 en[] （en[]存的是下个位置的节点） 等于第k个位置的 en[]，然后让k位置的节点等于idx

//在第 k个插入的后面插入 
void add_to_k(int k,int x){
    e[idx]=x;
    en[idx]=en[k];
    en[k]=idx;
    idx++;
}
1
2
3
4
5
6
7

删除时注意如果是首节点那么要让头结点head（本身就是节点）等于他的下一个节点
否则的话同理^_^

//删除第 k个数后面的数 
void del(int k){
    if(k+1==0) head=en[head];
    else{
        en[k]=en[en[k]];
    }
}
1
2
3
4
5
6
7

完整代码

#include<iostream>

using namespace std;
const int w=1e6+10;

int e[w],en[w],idx,head;

void inti(){
    head=-1;
    idx=0;
}

void add_to_head(int x){
    e[idx]=x;
    en[idx]=head;
    head=idx;
    idx++;
}

void add_to_k(int k,int x){
    e[idx]=x;
    en[idx]=en[k];
    en[k]=idx;
    idx++;
}

void del(int k){
    if(k+1==0) head=en[head];
    else{
        en[k]=en[en[k]];
    }
}

int main(){
    inti();

    int n;
    cin>>n;

    for(;n>0;n-- ){
        char ch;
        cin>>ch;

        if(ch=='I'){
            int k,x;
            cin>>k>>x;
            add_to_k(k-1,x);
        }
         if(ch=='D'){
            int k;
            cin>>k;
            del(k-1);
        }
         if(ch=='H'){
            int x;
            cin>>x;
            add_to_head(x);
        }
        // cout<<ch<<endl;
    }

    for(int i=head;i!=-1;i=en[i]) cout<<e[i]<<' ';
    return 0;
}

作者：blue_sky_ （不要误会，这个是本人的ID  hh）
链接：https://www.acwing.com/activity/content/code/content/5193191/
来源：AcWing

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

二、双链表

1、双链表相对于单连表比较容易理解，操作也更简单
2、初始化时，由于有了l[] r[] 数组，变使得下标idx要从2开始，这倒不是对e[]数组有什么影响，主要因为左右数组也是由idx而进行操作的，为了保持下标的不重复从2开始即可

完整代码

#include<iostream>

using namespace std;
const int w=1e5+10;

int e[w],l[w],r[w],idx;

void right_add(int k,int x){
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];
//以上是先存入元素
//然后操作插入位置的左（或左右）两边的元素
    l[r[k]]=idx;//k个数的右边的左边等于idx 
    r[k]=idx;//k个数的左边

    idx++;
}

void del(int k){
    l[r[k]] = l[k];//让k右边的左边等于k的左边
    r[l[k]] = r[k];//让k左边的右边等于k的右边
}


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

    r[0]=1,l[1]=0,idx=2;

    for(int i=1;i<=n;i++){
        string ch;
        cin>>ch;

        int k,x;
        if(ch=="L"){//最左边插入
            cin>>x;
            right_add( 0 , x ) ;
        }
        else if(ch=="R"){//最右边插入
            cin>>x;
            right_add(l[1],x);
        }
        else if(ch=="IL"){//左边插入
            cin>>k>>x;
            right_add(l[k+1],x);
        }
        else if(ch=="IR"){//右边插入
            cin>>k>>x;
            right_add ( k + 1 , x );
        }
        else if(ch=="D") {//删除
            cin>>k;
            del( k + 1 );
        }

   	for(int i = r[0] ; i != 1 ; i = r[i] ) cout<<e[i]<< ' ';
    return 0;

}

作者：blue_sky_
链接：https://www.acwing.com/activity/content/code/content/5204167/
来源：AcWing

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