十字链表 构造 有向图/网

#include<iostream>
#define MAX 20
using namespace std;

typedef enum{DG,DN}GraphKind;

typedef struct ArcNode{
    int tVex,hVex;
    struct ArcNode *tLink,*hLink;
    int info;
}ArcNode;

typedef struct VexNode{
    int vex;
    ArcNode *firstIn,*firstOut;
}VexNode;

typedef struct OLGraph{
    GraphKind kind;
    int vexnum,arcnum;
    VexNode vertices[MAX];
}OLGraph;

int Locate(const OLGraph &G,int vex){
    for(int i=0;i<G.vexnum;++i)
        if(G.vertices[i].vex==vex)
            return i;
    return INT_MAX;
}

bool deleteGraph(OLGraph &G){
    for(int i=0;i<G.vexnum;++i){
        ArcNode *temp=G.vertices[i].firstOut;
        G.vertices[i].firstOut=NULL;
        G.vertices[i].firstIn=NULL;
        while(temp){
            ArcNode *t=temp->tLink;//瞄准弧尾相同或者弧头相同的一个链表删，否则memory leak 
            delete temp;
            temp=t;
        }
    }
    return true;
}

bool createDG(OLGraph &G){
    cout<<"input "<<G.vexnum<<" vertex : ";
    for(int i=0;i<G.vexnum;++i){
        cin>>G.vertices[i].vex;
        G.vertices[i].firstIn=G.vertices[i].firstOut=NULL;
    }
    cout<<"input "<<G.arcnum<<" arcs : "<<endl;
    for(int i=0;i<G.arcnum;++i){
        int v1,v2;
        cin>>v1>>v2;//可以用哈希表查重
        int p=Locate(G,v1);
        int q=Locate(G,v2);
        if(p>=INT_MAX||q>=INT_MAX){
            return false;
        }
        ArcNode *temp=new ArcNode;
        temp->tVex=p;
        temp->hVex=q;
        temp->info=0;
        temp->tLink=G.vertices[p].firstOut;
        temp->hLink=G.vertices[q].firstIn;
        G.vertices[p].firstOut=G.vertices[q].firstIn=temp;
    }
    return true;
}

bool createDN(OLGraph &G){
    cout<<"input "<<G.vexnum<<" vertex : ";
    for(int i=0;i<G.vexnum;++i){
        cin>>G.vertices[i].vex;
        G.vertices[i].firstIn=G.vertices[i].firstOut=NULL;
    }
    cout<<"input "<<G.arcnum<<" arcs : "<<endl;
    for(int i=0;i<G.arcnum;++i){
        int v1,v2,w;
        cin>>v1>>v2>>w;
        int p=Locate(G,v1);
        int q=Locate(G,v2);
        if(p>=INT_MAX||q>=INT_MAX) return false;
        ArcNode *temp=new ArcNode;
        temp->tVex=p;
        temp->hVex=q;
        temp->info=w;
        temp->tLink=G.vertices[p].firstOut;
        temp->hLink=G.vertices[q].firstIn;
        G.vertices[p].firstOut=G.vertices[q].firstIn=temp;
    }
    return true;
}

bool createGraph(OLGraph &G){
    switch(G.kind){
        case DG:
            return createDG(G);
        case DN:
            return createDN(G);
        default:
            return false;
    }
}

void displayGraph(OLGraph &G){
    for(int i=0;i<G.vexnum;++i){
        cout<<"["<<G.vertices[i].vex<<"]";
        ArcNode *temp=G.vertices[i].firstOut;
        while(temp){
            cout<<"->("<<temp->tVex<<" "<<temp->hVex<<")";
            temp=temp->tLink;
        }
        cout<<endl;
    }
}

int main(){
    OLGraph graph;
    int k;
    int vexnum,arcnum;
    cout<<"vexnum = ";
    cin>>graph.vexnum;
    cout<<"arcnum = ";
    cin>>graph.arcnum;
    cout<<"\nDG=1 , UN=2"<<endl;
    cout<<"GraphKind = ";
    cin>>k;
    if(k==1){
        graph.kind=DG;
    }else if(k==2){
        graph.kind=DN;
    }else{
        cout<<"invalid kind";
        return 0;
    }
    if(createGraph(graph)){
        displayGraph(graph);
    }else cout<<"invalid input"<<endl;
    deleteGraph(graph);
}