By Shiina Orez

Updated:

Contents
  1. 1. 数组模拟链表
    1. 1.1. Node：
    2. 1.2. Add函数：

链表作为一种数据结构，对于空间的利用率非常之高。但是对于链表没有学好的同学来说，链表难上天了。有没有一种解决方案能实现链表却又不那么难呢？

当然有：那就是：

数组模拟链表

顾名思义，通过一些特殊的方法，可以让数组具有链表的作用。

我们先放代码，然后解释原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
int head[maxn],e=0; 
struct node{
	int next;
	int to;
	int w;
}edge[maxn];
void add(int u,int v,int d){
	edge[++e].next=head[u];
	edge[e].to=v;
	edge[e].w=d;
	head[u]=e;
	return ;
}

Node：

其实我们一步步的看代码就能发现其中的端倪，究竟是怎么实现这么神奇的操作的。
最基本的元素显然是node，具有三个属性next，to和w。
为什么没有from？是因为链表都是单向的，没有回溯这一环。别和我说什么双向链表

Add函数：

add函数有三个参数：u，v，d。u、v代表两个点，d代表权值。
函数的第一行涉及到了一个量：head[u]。于是我们寻找head[u]在哪里。
我们在最后一行找到了，head[u]被上一个函数赋值为e。

e是什么？
大致看一眼就知道e代表边的总数，同时还是每条边的序号。
因此head[u]代表上一个以u为起点的边的序号。
在程序的一开始e便会++,所以e这个全局变量最终就是所有边的数量。

再一次回到函数的开始， next属性赋值为head[u]。
那个next就是指的上一个以u为起点的边的序号。

到这里就看的很清楚了吧。我们也就知道届时该如何遍历这个链表。

1
2
3
for(int i=head[p];i!=0;i=edge[i].next){
	/*...*/
}

这个循环的意义也就明白了，为什么是i！=0为判断条件，因为都是指向上一个以本节点为起点的边，那么第一条边之前没有边存在，那么就是0。

就是这样，数组模拟链表的知识讲完了。
祝各位OIer武运昌隆！！！

这里写图片描述

Contents
  1. 1. 数组模拟链表
    1. 1.1. Node：
    2. 1.2. Add函数：