链表与邻接表：树与图的存储

链表与邻接表：树与图的存储（用数组模拟）

单链表

算法思想（静态链表）

1. 用数组模拟效率高，以为如果用结构体的话，每次要new一个节点，这样会很慢
2. 单链表–>邻接表–>存储树和图
3. 双链表–>用来优化某些题目
4. 刚开始设置头结点head为空
5. 数组表示链表，e[N]为节点存储的值，ne[N]节点指向的下一个节点，空节点的下标用-1表示
   

完整代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

//head表示头结点的下标
//e[i]表示节点i的值
//ne[i]表示节点i的next指针是多少
//idx 存储当前已经用到了哪个点

int head,e[N],ne[N],idx;

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

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

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

//将下标是k的节点的下一个节点删除
void remove(int k){
    ne[k] = ne[ne[k]];      //算法中不需要管释放空间的问题
}

int main(){
    int m;
    cin >> m;
    init();
    while(m--){
        int k,x;
        char op;

        cin >> op;
        if(op == 'H'){
            cin >> x;
            add_to_head(x);
        }else if(op == 'D'){
            cin >> k;
            if( !k ) head = ne[head];
            remove(k - 1);
        }else{
            cin >> k >> x;
            add(k - 1,x);
        }
    }

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

双链表

算法思想

与单链表类似，只是多了一个指向左边的数组，初始化不一样而已。

模板代码

//双链表
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int m;
int e[N],l[N],r[N],idx;

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

//在下标是k的点的右边插入x
void add(int k,int x){  //在下表为k的点的左边插入一个点，调用函数add(l[k],x)即可
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;      //此操作一定在r[k] = idx 之前
    r[k] = idx;
}

//删除下表为k的点
void remove(int k){
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main(){
    return 0;
}