#include<iostream>
using namespace std;
#include<string>
#define Max_Vertex_Num 20
typedef char elemtype;
typedef struct ArcNode
{
    int tailvex,headvex;
    ArcNode *hlink,*tlink;
}ArcBox;
struct VexNode
{
    elemtype data;
    ArcBox *firstin,*firstout;
};
struct OLGarph
{
    VexNode hlist[Max_Vertex_Num];
    int vexnum,arcnum;
};

int Locate(OLGarph &G,elemtype v)//顶点位置定位
{
    for(int i=0;i<G.vexnum;i++)
        if(G.hlist[i].data==v)
            return i;
    exit(0);
}

void Create_OLG( OLGarph &G)//以十字链表方式建立图
{
    cout<<"请输入有向图的顶点数：";
    cin>>G.vexnum;
    cout<<"请输入有向图的边数：";
    cin>>G.arcnum;
    int i;
   
    for(i=0;i<G.vexnum;i++)
    {
        cout<<"请输入各顶点的data值:";
        cin>>G.hlist[i].data;
        G.hlist[i].firstin=G.hlist[i].firstout=NULL;
    }
    cout<<"输入边时弧尾在前弧头之后.\n";\
    for(i=0;i<G.arcnum;i++)
    {
        cout<<"请输入各有向边所依附的顶点：";
        elemtype v1,v2;
        cin>>v1>>v2;
        int m,n;
        m=Locate(G,v1);
        n=Locate(G,v2);
        ArcNode *p=new ArcNode;
        p->tailvex=m;
        p->headvex=n;
        p->hlink=G.hlist[n].firstin;
        p->tlink=G.hlist[m].firstout;
        G.hlist[m].firstout=G.hlist[n].firstin=p;
    }
}

void InitNULL_1(OLGarph &G,int m,int n)
{
    ArcNode *p1,*p2;
    p1=G.hlist[m].firstin;
    while(p1->tailvex!=n)
    {
        p2=p1;
        p1=p1->hlink;
    }
    p2->hlink=p1->hlink;
}

void InitNULL_2(OLGarph &G,int m,int n)
{
    ArcNode *p1,*p2;
    p1=G.hlist[m].firstout;
    while(p1->headvex!=n)
    {
        p2=p1;
        p1=p1->tlink;
    }
    p2->tlink=p1->tlink;
}

void deleteout(OLGarph &G,int i)//删除以此顶点为弧尾的边
{
    ArcNode *p1,*p2;
    p1=G.hlist[i].firstout;
    while(p1)
    {
        p2=p1;
        p1=p1->tlink;
        InitNULL_1(G,p2->headvex,i);
        delete p2;
        G.arcnum--;   
    }

}

void deletein(OLGarph &G,int i)//删除以此顶点为弧头的边
{
    ArcNode *p1,*p2;
    p1=G.hlist[i].firstin;
    while(p1)
    {
        p2=p1;
        p1=p1->hlink;
        InitNULL_2(G,p2->tailvex,i);
        delete p2;
        G.arcnum--;
    }
}
void Delete_OLG(OLGarph &G)
{
    ArcNode *p,*q;
    elemtype key;
    cout<<"请输入您要删除的结点的data值:";
    cin>>key;
    int i=Locate(G,key);
    deleteout(G,i);//删除以此顶点为弧尾的边
    deletein(G,i);//删除以此顶点为弧头的边
    for(int j=i;i<G.vexnum;j++)
    {
       G.hlist[j]=G.hlist[j+1];
       for(p=G.hlist[j].firstin;p;p=p->hlink)
          p->headvex--;
       for(p=G.hlist[j].firstout;p;p=p->tlink)
           p->tailvex--;
    }
    G.vexnum--;
}

void Print_OLG(OLGarph G)
{
    cout<<"该图所有的顶点为:\n";
    for(int i=0;i<G.vexnum;i++)
        cout<<G.hlist[i].data<<' ';
    cout<<"该图所有的边为：\n";
     for(i=0;i<G.vexnum;++i)
    {   
        ArcNode *p=G.hlist[i].firstout;
        while(p)
        {
            cout<<G.hlist[i].data << "-->";
            cout<<G.hlist[p->headvex].data << endl;
            p = p->tlink;
        }
    }         
}

int main()
{
    OLGarph G;
    Create_OLG( G）;
    Print_OLG(G);
    Delete_OLG(G);
    Print_OLG(G);
    cout<<endl;
    return 0;
}