數據結構：有向圖的十字鏈表存儲實現

十字鏈表結構詳解

十字鏈表是有向圖的一種鏈式存儲結構，將每條弧的弧頭和弧尾分別鏈接，便於查找頂點的入弧和出弧。核心結構體定義如下：

弧結構體

typedef struct ArcBox {
    int tailvex, headvex;           // 弧尾、弧頭頂點位置
    struct ArcBox *hlink, *tlink;   // 同弧頭、同弧尾的下一條弧
    InfoType *info;                 // 弧的相關信息指針
} ArcBox;

頂點結構體

typedef struct VexNode {
    VertexType data;                // 頂點數據
    ArcBox *firstin, *firstout;     // 第一條入弧、出弧指針
} VexNode;

圖結構體

typedef struct {
    VexNode xlist[MAX_VERTEX_NUM];  // 表頭向量
    int vexnum, arcnum;             // 頂點數、弧數
} OLGraph;

核心操作實現

創建有向圖

輸入頂點數和弧數，依次讀取弧的尾頂點和頭頂點，通過 LocateVex 定位位置，插入到對應的入弧和出弧鏈表頭部。

頂點度計算

int VexDegree(OLGraph &G, VertexType v) {
    int k = LocateVex(G, v);
    if (k < 0) exit(OVERFLOW);
    int id = 0, od = 0;
    ArcBox *pin = G.xlist[k].firstin;
    ArcBox *pout = G.xlist[k].firstout;
    while (pin) { ++id; pin = pin->hlink; }
    while (pout) { ++od; pout = pout->tlink; }
    return id + od;
}

運行結果展示

優缺點分析

• 優點：查找頂點的入度、出度非常方便，時間複雜度 O(度數)
• 缺點：結構相對複雜，內存開銷較大，不適合稠密圖