十字鏈表的應用

#include<iostream> 
#include<cstring>
#include<cstdio>
#include<cstdlib> 
#define MAX_VERTEX_NUM 20    
using namespace std;
typedef struct ArcBox{int tailVex, headVex;//該弧的尾和頭頂點的位置 struct ArcBox *hlink, *tlink;//分別為弧頭相同和弧尾相同的弧的鏈域 
    ArcBox(){hlink = NULL;tlink = NULL;}
} ArcBox; typedef struct VexNode{int data;ArcBox *firstin, *firstout;VexNode(){firstin = NULL;firstout = NULL;} 
} VexNode; typedef struct{VexNode xlist[MAX_VERTEX_NUM];int vexnum, arcnum;
} OLGraph;void buildG(OLGraph &g, int u, int v){ArcBox *p = new ArcBox;/*或者， new 方式可以調用類的構造函數 ArcBox *p = (ArcBox *)malloc(sizeof(ArcBox));p->hlink = NULL;p->tlink = NULL;    */ p->tailVex = u;p->headVex = v;if(g.xlist[u].firstout == NULL){//在弧尾的地方插入 g.xlist[u].firstout = p;} else {ArcBox *tmp = g.xlist[u].firstout;while(tmp->tlink) tmp = tmp->tlink;//找到和u節點相關的最后一個弧尾 tmp->tlink = p; }if(g.xlist[v].firstin == NULL){//在弧頭的地方插入 g.xlist[v].firstin = p;} else {ArcBox *tmp = g.xlist[v].firstin;while(tmp->hlink) tmp = tmp->hlink;//找到和u節點相關的最后一個弧頭 tmp->hlink = p; }
}void inG(OLGraph g){printf("從每一個節點出度方向遍歷弧\n");for(int i=1; i<=g.vexnum; ++i){ArcBox *tmp = g.xlist[i].firstout;//找到弧尾節點為i的第一個節點printf("節點 %d:\n");while(tmp) {printf("弧 %d %d\n", tmp->tailVex, tmp->headVex);tmp = tmp->tlink;}}
}void outG(OLGraph g){printf("每一個節點的入度方向遍歷弧\n");for(int i=1; i<=g.vexnum; ++i){ArcBox *tmp = g.xlist[i].firstin;//找到弧頭節點為i的第一個節點printf("節點 %d:\n");while(tmp) {printf("弧 %d %d\n", tmp->tailVex, tmp->headVex);tmp = tmp->hlink;}}
}int main(){printf("請輸入圖的節點的個數和圖的弧數:\n");OLGraph g;scanf("%d %d", &g.vexnum, &g.arcnum);printf("請輸入圖的弧:\n");for(int i=0; i<g.arcnum; ++i) {int u, v;scanf("%d %d", &u, &v);buildG(g, u, v);}//遍歷方式，1.從每一個節點出度方向遍歷弧 2.從每一個節點的入度方向遍歷弧 
    inG(g);printf("*****************\n");outG(g);return 0;
}/*
有向圖測試數據：
4 7
1 2
4 2
4 1
1 3
3 1
3 4
4 3 */

?