C/C++自带的数据结构-数组很好用,但是无法在任意位置插入或删除元素,所以我们就需要另外一种数据结构来实现这种操作,于是链表就诞生了,链表支持在任意位置插入或删除,但只能按顺序依次访问其中的元素。我们可以用一个 struct 表示链表的节点,其中可以储存任意数据,然后我们可以用 prev 和 next 两个指针指向前后两个节点,构成一个常见的双向链表结构。此外为了防止左右两端或者空链表中访问越界,我们通常建立额外的两个节点 head 和 tail 代表链表的头尾。
const int maxn=100100; struct Node{ int value; int prev,next; }node[maxn]; int tot,head,tail; int q; int initialize(){ tot=2; head=1; tail=2; node[head].next=tail; node[tail].prev=head; } int insert(int p,int val){ q=++tot; node[q].value=val; node[node[p].next].prev=q; node[q].next=node[p].next; node[q].next=q; node[q].prev=p; } void remove(int p){ node[node[p].prev].next=node[p].next; node[node[p].next].prev=node[p].prev; }
在与链表相关的诸多结构中,邻接表是相当重要的一个。它是树与图结构的一般储存方式。
实际上,邻接表可以看成“带有索引数组的多个数据链表”构成的结构集合。在这样的结构中存储的数据被分为若干类,每一类的数据构成一个链表。每一类还有一个代表元素,称为该类对应的链表的“表头”。所有“表头”构成一个表头数组,作为一个可以随机访问的索引,从而可以通过表头数组定位到某一类数据对应的链表。
当需要插入新的数据节点时,我们可以通过表头数组 head 定位到新的数据节点所属类别的链表表头,将新数据在表头位置插入。
在一个具有 n 个点 m 条边的有向图结构中,我们可以把每条边所属的“类别”定义为该边的起点标号。这样所有边被分为 n 类,其中第 x 类就由“从 x 出发的所有边”构成。通过表头 head[x],我们很容易定位到第 x 类对应的链表,从而访问从点 x 出发的所有边。
我画个图让大家更好理解一些。(字丑勿喷~)
具体代码实现如下:
void add(int x,int y,int z){//加入有向边 x ,y 权值为z ver[++tot]=y; edge[tot]=z; next[tot]=head[x]; head[x]=tot; } //访问从 x 出发的所有边 for(int i=head[x];i;i=next[i]){ int y=ver[i]; int z=edge[i]; }
对于无向图,我们把每条无向边看作两条有向边插入即可。
同样的我们可以用 struct 来实现,这样我们还可以记录点,更好用一些。
代码示例如下:
#include<iostream> #include<cmath> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct Edge{ int next; int edge; int ver; }t[100100]; int tot,head[100100]; void add(int x,int y,int z){ t[++tot].ver=y; t[tot].edge=z; t[tot].next=head[x]; head[x]=tot; } int main(){ int n; cin>>n; int x,y,z; for(int i=1;i<=n;i++){ cin>>x>>y>>z; add(x,y,z); } for(int i=1;i<=n;i++){ cout<<"point:"<<i<<endl; for(int j=head[i];j;j=t[j].next){ y=t[j].ver; z=t[j].edge; cout<<y<<" "<<z<<endl; } } } /* 5 1 2 5 1 3 1 2 3 4 3 4 3 4 5 2 */
样例输入:
5
1 2 5
1 3 1
2 3 4
3 4 3
4 5 2
样例输出:
point:1
3 1
2 5
point:2
3 4
point:3
4 3
point:4
5 2
point:5
<--(这里应该是没输出的)
然后我们就可以快乐的去写图论题了哦