链式前向星实现树的存储（孩⼦表示法）c++
注意：头结点h这⾥的数组⼤⼩可以为N，但是e和ne这两个数组我们要开辟之前的两倍才⾏，因为我们要存边存的是之前的两倍的。链式前向星的本质就是⽤链表存储所有的孩⼦，其中链表是⽤数组模拟实现的。名字看起来花⾥胡哨的，但是不要被唬到。
·
名字看起来花⾥胡哨的，但是不要被唬到
链式前向星的本质就是⽤链表存储所有的孩⼦，其中链表是⽤数组模拟实现的
- 创建⼀个⾜够⼤的数组h，作为所有结点的哨兵位;
- 创建两个⾜够⼤的数组e和ne，⼀个作为数据域，⼀个作为指针域;
- ⼀个变量id，标记新来结点存储的位置
当x有⼀个孩⼦y的时候，就把y头插到x的链表中
id++; e[id] = y; ne[id] = h[x]; h[x] = id;
注意：头结点h这⾥的数组⼤⼩可以为N，但是e和ne这两个数组我们要开辟之前的两倍才⾏，因为我们要存边存的是之前的两倍的
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
//链式前向星
int h[N], e[N * 2], ne[N * 2], id;
int n;
//其实就是把b头插到a所在的链表后面
void add(int a, int b)
{
++id;
e[id] = b;
ne[id] = h[a];
h[a] = id;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
int a, b; cin >> a >> b;
//a和b之间有一条边，a有一个孩子b，b有一个孩子a
add(a, b); add(b, a);
}
return 0;
}
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
3
0- 0
已为社区贡献7条内容
所有评论(0)