什么是十字链表
发布网友
发布时间：2022-04-19 20:49
共1个回答
热心网友
时间：2022-07-12 22:36
十字链表是有向图的另一种链式存储结构，是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。
十字链表在这种结构中，每条弧的弧头结点和弧尾结点都存放在链表中，并将弧结点分别组织到以弧尾结点为头结点和以弧头结点为头结点的链表中。由此可见，图中的每条弧存在于两个链表中，一个是弧头相同的链表，一个是弧尾相同的链表，两个链表在该弧处交叉形成“十”字，因此称作十字链表。十字链表的结点结构如图7－14所示。顶点结点由2个域组成，其中data域存储和顶点相关的信息，如顶点的名称等；firstin和firstout为两个指针域，分别指向以该顶点为弧头和弧尾的第一个弧结点。弧结点有5个域，其中尾域tailve*和头域headve*分别指向弧尾和弧头这两个顶点在图中的位置，指针域hlink指向弧头相同的下一条弧，而指针域tlink指向弧尾相同的下一条弧，Info域指向该弧的相关信息。
十字链表的结点结构
