图的十字链表的存储方法并举例说明

图的十字链表（Orthogonal List）是一种常用的图的存储方法，它综合了邻接表和逆邻接表的优点，可以高效地表示有向图和有向带权图。

十字链表的存储方法使用两个链表：一个顶点链表和一个弧链表。

顶点链表中的每个节点表示一个顶点，包含了顶点的标识和指向以该顶点为起点的第一条弧的指针。

弧链表中的每个节点表示一条弧，包含了弧的起点、终点、权重（仅在有权图中使用）以及指向下一个同起点和同终点的弧的指针。

下面是一个示例：

typedef struct ArcNode {
    int tailVertex;    // 弧尾顶点
    int headVertex;    // 弧头顶点
    int weight;        // 弧的权重（仅在有权图中使用）
    struct ArcNode *tailNext;  // 指向下一个同起点的弧
    struct ArcNode *headNext;  // 指向下一个同终点的弧
} ArcNode;

typedef struct VertexNode {
    int vertex;        // 顶点
    ArcNode *firstIn;  // 指向以该顶点为终点的第一条弧
    ArcNode *firstOut; // 指向以该顶点为起点的第一条弧
} VertexNode;

typedef struct {
    VertexNode vertices[MAX_VERTICES];  // 图中所有顶点的数组
    int vertexCount;                    // 顶点数
    int arcCount;                       // 弧数
} OrthogonalList;

这个示例中，ArcNode表示弧的结构体，包含了弧的起点、终点、权重以及指向下一个同起点和同终点的弧的指针。VertexNode表示顶点的结构体，包含了顶点的标识以及指向以该顶点为起点和终点的第一条弧的指针。OrthogonalList则是整个十字链表的结构体，包含了顶点数组、顶点数和弧数。

举个例子，考虑下面这个有向图：

   1
A ---> B
^     |
|     v
|     C
+---> D

使用十字链表来表示这个有向图，对应的存储结构如下：

OrthogonalList graph;
graph.vertexCount = 4;
graph.arcCount = 4;

// 顶点链表
graph.vertices[0].vertex = 'A';
graph.vertices[0].firstOut = &arc1;
graph.vertices[0].firstIn = NULL;

graph.vertices[1].vertex = 'B';
graph.vertices[1].firstOut = &arc2;
graph.vertices[1].firstIn = &arc1;

graph.vertices[2].vertex = 'C';
graph.vertices[2].firstOut = &arc3;
graph.vertices[2].firstIn = &arc2;

graph.vertices[3].vertex = 'D';
graph.vertices[3].firstOut = NULL;
graph.vertices[3].firstIn = &arc3;

// 弧链表
ArcNode arc1;
arc1.tailVertex = 0;  // A
arc1.headVertex = 1;  // B
arc1.weight = 1;
arc1.tailNext = NULL;
arc1.headNext = &arc2;

ArcNode arc2;
arc2.tailVertex = 1;  // B
arc2.headVertex = 2;  // C
arc2.weight = 1;
arc2.tailNext = &arc1;
arc2.headNext = &arc3;

ArcNode arc3;
arc3.tailVertex = 2;  // C
arc3.headVertex = 3;  // D
arc3.weight = 1;
arc3.tailNext = &arc2;
arc3.headNext = NULL;

这样，通过十字链表的存储结构，我们可以方便地找到每个顶点的出边和入边，实现图的各种操作。