关于idx
首次接触idx的时候我也有些懵逼,这里总结一下对idx的理解。
之前的链表、trie都是用结构体、类来实现的,y总讲的是使用数组模拟的,更快。
用结构体的时候我们可以很清楚地感觉到一个结构体就是一个节点,结构体中常常有两个变量val
和next
,分别代表该节点的值与下一个节点的指针。或者我们使用类的时候,类中有量val
和next
属性,也是分别代表值与指针。
那么用数组模拟,我们用e[N]
和ne[N]
数组分别模拟值域和指针域,是割裂的,也就是是分开的两个数组,那么如何让他们产生联系呢,就是通过idx
,如idx=3
时,我们给e[N]
和ne[N]
数组分别赋了值,那么给e[3]
和ne[3]
就分别代表这个节点的值与指针。
还在评论区看到,idx
就相当于一个分配器,分配给每个新产生的节点的为idx
的下标,e[N]
和ne[N]
又通过这个下标联系起来。只有当新产生节点的时候idx
才会++
,我觉得这样可能更好理解。
下面是一些使用到idx
的插入操作,包括单链表、双链表、Trie
:
// 单链表
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = h;
h = idx;
idx++;
}
// 双向链表
// 在第k个插入的节点的左边插入x
void insert_left(int k,int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = l[k];
r[l[k]] = idx;
l[k] = idx;
idx++;
}
// trie树
void insert(char str[])
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
// 如果没有儿子就创建儿子
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
}
#
泰裤辣
# 泰酷辣
结构体就是动态分配一个指针 ,而使用idx 相当于用数组的方式在分配指针,idx++则是将指针移至下个内存域,最后我们通过 e[idx] next[idx] 存取这里的变量 也就相当于 idx->next idxt ->e操作
也可以直接理解为 idx就是对 某个地址下的变量进行解引用的操作
嗯嗯是的,可以理解为索引