一 概述

十字鏈表是有向圖的一種鏈式存儲結構，在十字鏈表中，對應于有向圖中的每條弧有一個結點，對應于每個頂點也有一個結點。

二 十字鏈表

十字鏈表的結構分為弧結點和頂點結點，其中弧結點中有5個域，頂點結點有3個域。

弧結點的5個域：尾域和頭域分別指示弧尾和弧頭這兩個頂點在圖中的位置；鏈域hlink指向弧頭相同的下一條弧；鏈域tlink指向弧尾相同的下一個條弧；info域指向該弧的相關信息。這樣，弧頭相同的弧在同一個鏈表上，弧尾相同的弧也在同一個鏈表上。

頂點結點中有3個域：data域存頂點相關的數據信息，如頂點名稱；firstin和firstout兩個域分別指向以該頂點為弧頭或弧尾的第一個弧結點。

有向圖的十字鏈表表示法中，頂點結點之間是通過順序存儲方式存儲。

在十字鏈表中，既容易找到Vi為尾的弧，又容易找到Vi為頭的弧，因而容易求得頂點的出度和入度，圖的十字鏈表表示不是唯一的，但一個十字鏈表表示確定一個圖。

總結

以上是生活随笔為你收集整理的图存储之十字链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。