数据结构之图的存储结构十字链表法

一、邻接表法回顾

邻接表法

邻接表法特点：

• 可以存储有向图和无向图
• 计算节点的出度很快（边链表数量）
• 计算节点的入度很慢（需要遍历全部节点）

二、有向图存储结构十字链表法

2.1 十字链表法定义

十字链表法定义

顶点结构：

• data：数据域可以存放节点信息
• firstin：第一个入边
• firstout：第一个出边

边结构：

• tailvex：弧尾结点
• headvex：弧头结点
• hlink：弧头相同的下一条边
• tlink：弧尾相同的下一条边
• info：信息域（可以存储边的权值）

特点：

• 仅可以表示有向图，无法表示无向图
• 计算结点的入度和出度都很快，因为都有指针，所以只需要遍历边列表即可

2.2 十字链表法示例

十字链表法示例

三、十字链表法C语言定义

十字链表法C语言定义