数组模拟 传统结构体版 含义
h[u] head 指向第一条边的指针
ne[i] ptr->next 指向下一条边的指针
e[i] ptr->val 当前边指向的具体节点
  • 数组模拟的h数组以及ne数组存储的是指针，也可以理解为指向元素的边；只有通过e数组才能得到对象的值；idx表示用到哪个节点
  • 而传统结构体则更为直接，可直接通过->next->val操作访问下一元素的值

例如

1
2
3
4
5
6
7
//访问头节点指向元素
head->next->val//传统结构体
e[h[u]]//数组模拟
  
//访问第二个元素
head->next->next->val//传统结构体
e[ne[h[u]]]//数组模拟

头插法辨析应用

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
#include<bits/stdc++.h>
using namespace std;
const int N =1e6 + 10;
//数组模拟(邻接表为例，刚好学到这hh)
int h[N], ne[N], e[N], idx;

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}


//传统结构体(🥱)
struct Node
{
    int val;
    Node *next;

    // 构造函数x为元素值，y为指向的指针
    Node(int x, Node *y) : val(x), next(y) {};
};
Node *h1[N];
// 初始化
void init(int n)
{
    for (int i = 1; i <= n; i++)
        h1[i] = nullptr;
}
void add(int a, int b)
{
    // 创建新节点并指向h[a]
    Node *p = new Node(b, h1[a]);
    // 更新头指针
    h1[a] = p;
}
步骤描述 数组模拟 传统结构体指针版
创建新“地址” idx (自增索引) new Node (堆内存地址)
存入数据 e[idx] = b; p->val = b;
指向当前的头 ne[idx] = h[a]; p->next = h[a];
更新头指针 h[a] = idx++; h[a] = p;