十字链表的基本概念

• 有向边又称为弧

• 假设顶点 v 指向 w，那么 w 称为弧头，v 称为弧尾
  

• 顶点节点采用顺序存储

• 顶点节点

  • data：存放顶点的信息
  • firstin：指向以该节点为终点（弧头）的弧节点
  • firstout：指向以该节点为起点（弧尾）的弧节点

• 弧节点

  • tailvex：起点（弧尾）在数组中的索引
  • headvex：终点（弧头）在数组中的索引
  • hlink：终点（弧头）相同的下一个弧节点
  • tlink：起点（弧尾）相同的下一个弧节点
  • info：存放边（弧）有关的信息

画法

示例

第 1 步

• 先画顶点节点，并在右侧标出顶点对应的索引
• 右侧的这些索引就叫它第 i 列吧，$i\in [0,3]$

第 2 步

• 遍历每个顶点，找到该顶点指向的其他顶点 i，从左到右画弧节点，弧节点的位置对应第 i 列，每一行最右侧弧节点的 tlink 置为空
• 如果索引为 i 的顶点节点没有出度，那么 firstout 置为空
  

第 3 步

• 索引为 i 的顶点节点的 firstin 指向第 i 列的第一个节点（从上到下的第一个弧节点）
• 如果第 i 列一个节点也没有，那么 firstin 置为空

第 4 步

• 遍历每一列，将 hlink 按列从上到下进行连接
• 每一列最后一个弧节点的 hlink 置为空（从上到下，最上面的是第一个，最下面的是最后一个）