十字链表

有向图的一种链式存储结构。其有两种结点：顶点结点和边结点。 有向图中的边也叫弧，为了方便，这里采用边的概念。 入边：如果一条边$e$的终点是点$u$，则称$e$为$u$的入边。 出边：如果一条边$e$的起点是点$u$，则称$e$为$u$的出边。 对于一条从顶点$u$到顶点$v$的边$e$，$e$即是$u$的出边也是$v$的入边。

1.顶点结点

顶点结点的结构：（data,firstIn,firstOut）。 data：结点所存储的信息。 firstIn：指向该结点的第一个入边。 firstOut：指向该结点的第一个出边。

2.边结点

注：在十字链表中将点$u$所有的出边都看作是有某种特定顺序的。 边结点的结构：（info,headV,tailV,nexE,preE）。 info：该边的信息。 headV：该边的起点结点。 tailV：该边的终点结点。 nexE：headV的下一条出边（当前边的下一条边）。 preE：headV的上一条出边（当前边的上一条边）。