链表

1. 前言

C/C++自带的数据结构-数组很好用，但是无法在任意位置插入或删除元素，所以我们就需要另外一种数据结构来实现这种操作，于是链表就诞生了，链表支持在任意位置插入或删除，但只能按顺序依次访问其中的元素。我们可以用一个 struct 表示链表的节点，其中可以储存任意数据，然后我们可以用 prev 和 next 两个指针指向前后两个节点，构成一个常见的双向链表结构。此外为了防止左右两端或者空链表中访问越界，我们通常建立额外的两个节点 head 和 tail 代表链表的头尾。

2. 代码实现

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
              <--（这里应该是没输出的）

然后我们就可以快乐的去写图论题了哦