Day6

发表于 | 更新于: | 分类于 | | 阅读数

链式前向星 && 手写Hash

链式前向星

对于图来说，链式前向星的概念就不得不提及了，其中的链表的思想也是手写Hash的重要一环

什么是链式前向星，就是利用链表的方式存图

定义一个结构体，其中包含next和to

next：表示与这个边起点相同的上一条边的编号

to：表示这条边的终点

ecnt：表示边的编号

还要定义一个head数组，head[i]表示以i为起点的最后一条边的编号

最开始head数组赋值为-1

加边操作

1
2
3
4
5
void add(int from,int to){
    e[ecnt].nex=head[from];
    e[ecnt].to=to;
    head[from]=ecnt++;
}

通过加边操作我们可以记录所有从from出去的边，然后把每条边的前面的值放入next值中。

那么我们遍历每个点的边是，只要递归地寻找head[i]，然后再往E[i].next找即可

1
2
3
4
5
for(int i=0; i<n; i++){
    for(int j=head[i]; ~j; j=e[j].nex){
        //这条边就是i->e[j].to
    }
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int maxn = 110;
struct egde{
    int nex,to;
}e[maxn<<1];
int head[maxn],ecnt;
void init(){
    memset(head,-1,sizeof head);
    memset(in,0,sizeof in);
    ecnt=0;
}
void add(int from,int to){
    e[ecnt].nex=head[from];
    e[ecnt].to=to;
    head[from]=ecnt++;
}
for(int i=0; i<n; i++){
    for(int j=head[i]; ~j; j=e[j].nex){
        //这条边就是i->e[j].to
    }
}

手写Hash

c++的STL有hash的两个函数，一个是map一个是unorder_map，都可以标记哪个数是否出现过，效率还可以$logn$，但是常数大。

我们可以直接手写Hash，利用链式前向星的思想，找一个不是特别大的质模数，然后对于每个模数相当于建立一个点，每次出现一个同模的就可以建立一条边，比如模数为$mod$，就会有$mod$个余数，每次加数的时候先求余数，然后加到那个余数集合里面，存储就用链式前向星的方法。

当数不是特别大特别多的时候，这个效率还可以。

但是这种一般题目可以用，（一般还是用unorder_map，这里只是介绍一种思想），如果卡模数就没办法了，只能更换模数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Hash{
    ll mod = 2908361;
    ll cnt = 0, Head[2908361], nxt[1000006];
    ll val[1000006], pos[1000006];
    void init(){
        memset(Head, -1, sizeof(Head)); cnt = 0;
    }
    void Insert(ll x, ll v){
        ll key = x % mod;
        pos[cnt] = x, val[cnt] = v, nxt[cnt] = Head[key];
        Head[key] = cnt++;
    }
    ll Find(ll x){
        ll key = x % mod;
        for(ll i = Head[key]; ~i; i = nxt[i]){
            if(pos[i] == x) return val[i];
        }
        return -1ll;
    }
}hs;
thanks!