数据结构（一）

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N=1e5+10;
int head,e[N],ne[N],idx;//head表示头结点的指针,ne[]里记录下标

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

void insert_head(int x)//链表头插入
{
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}

void insert_k(int k,int x)//第k个元素之后插入
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N=1e5+10;
int l[N],r[N],e[N],idx;
//偷懒一点，直接把编号0的节点作为头节点，编号为1的节点作为尾节点
void init()
{
    r[0]=1,l[1]=0;
    idx=2;//第k个插入的数下标为k+1
}
void insert(int k,int x)
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[idx]]=idx;
    r[k]=idx;
    idx++;
}
void remove(int k)//删除第k个结点
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}