6.2.3 十字链表

教材导航 · 第6章

原书定位

印刷页P209起,对应PDF第221页。下文为目视整理的知识提要;完整内容见原书对照。

用于有向图。每条弧只有一个弧结点,同时参加弧尾相同的出边链和弧头相同的入边链;顶点结点保存首入弧与首出弧指针。

tailvex、headvex 为弧尾与弧头,tlink 沿同弧尾找下一条出弧,hlink 沿同弧头找下一条入弧。便于同时枚举入边、出边和删除边,空间 O(n+m)O(n+m)。

十字链表结点结构

十字链表结点结构,原书P209。

有向图的十字链表

有向图的十字链表,原书P209。

对应练习

6.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P209,PDF第221页