/*

     以十字链表作为图的存储结构创建图。

 */

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #define    MAX_VERTEX_NUM    20    //最大顶点数

 #define DEBUG

 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}

 typedef char InfoType;

 typedef char VertexType;

 //弧结点

 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;//有向图的当前顶点数和弧数

     GraphKind kind;//图类型

 }OLGraph;

 /*

     若G中存在顶点u，则返回该顶点在图中位置；否则返回-1。

 */

 int LocateVex(OLGraph G, VertexType v)

 {

     int i = ;

     for(i=; i<G.vexnum; i++){

         if(G.xlist[i].data == v)

             return i;

     }

     return -;

 }

 /*

     若G中存在顶点位置loc存在,则返回其顶点名称

 */

 VertexType LocateVInfo(OLGraph G, int loc)

 {

     return G.xlist[loc].data;

 }

 /*

     采用十字链表的存储结构，构造有向图

  */

 int CreateDG(OLGraph *G)

 {

     int i = , j = , k = , IncInfo = ;

     int v1 = , v2 = ;

     char tmp[] = {};

     ArcBox *p = NULL;

     printf("输入顶点数，弧数，其他信息标志位: ");

     scanf("%d,%d,%d", &G->vexnum, &G->arcnum, &IncInfo);

     for(i=; i<G->vexnum; i++){

         //输入顶点值

         printf("输入第%d个顶点: ", i+);

         memset(tmp, , sizeof(tmp));

         scanf("%s", tmp);

         //初始化指针

         G->xlist[i].data = tmp[];

         G->xlist[i].firstin = NULL;

         G->xlist[i].firstout = NULL;

     }

     //输入各弧并构造十字链表

     for(k=; k<G->arcnum; k++){

         printf("输入第%d条弧(顶点1, 顶点2): ", k+);

         memset(tmp, , sizeof(tmp));

         scanf("%s", tmp);

         sscanf(tmp, "%c,%c", &v1, &v2);

         //确定顶点v1和v2在图中的位置

         i = LocateVex(*G, v1);

         j = LocateVex(*G, v2);

         //对弧结点赋值

         p = (ArcBox *) malloc(sizeof(ArcBox));

         p->tailvex = i;

         p->headvex = j;

         p->hlink = G->xlist[j].firstin;

         p->tlink = G->xlist[i].firstout;

         p->info = NULL;

         //完成在入弧和出弧链头的插入

         G->xlist[j].firstin = p;

         G->xlist[i].firstout = p;

         //若弧有相关的信息,则输入

         if(IncInfo){

             //Input(p->info);

         }

     }

     return ;

 }

 /*

     采用十字链表的存储结构，构造图

 */

 int CreateGraph(OLGraph *G)

 {

     printf("输入图类型: +有向图(0), -有向网(1), -无向图(2), -无向网(3): ");

     scanf("%d", &G->kind);

     switch(G->kind){

         case DG:

             return CreateDG(G);

         case DN:

         case UDN:

         case UDG:

         default:

             printf("还不支持!\n");

             return -;

     }

 }

 /*

     输出图的信息

 */

 void printG(OLGraph G)

 {

     if(G.kind == DG){

         printf("类型：有向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }else if(G.kind == DN){

         printf("类型：有向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }else if(G.kind == UDG){

         printf("类型：无向图；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }else if(G.kind == UDN){

         printf("类型：无向网；顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);

     }

     int i = ;

     ArcBox *fi = NULL;

     ArcBox *fo = NULL;

     for(i=; i<G.vexnum; i++){

         printf("%c: ", G.xlist[i].data);

         fi = G.xlist[i].firstin;

         fo = G.xlist[i].firstout;

         printf("(hlink=");

         while(fi){

 #ifdef DEBUG

             printf("%c->%c; ", LocateVInfo(G, fi->tailvex), LocateVInfo(G, fi->headvex));

 #else

             printf("%d->%d; ", fi->tailvex, fi->headvex);

 #endif

             fi = fi->hlink;

         }

         printf(")\t(tlink=");

         while(fo){

 #ifdef DEBUG

             printf("%c->%c; ", LocateVInfo(G, fo->tailvex), LocateVInfo(G, fo->headvex));

 #else

             printf("%d->%d; ", fo->tailvex, fo->headvex);

 #endif

             fo = fo->tlink;

         }

         printf(")\n");

     }

     return;

 }

 int main(int argc, char *argv[])

 {

     OLGraph G;

     if(CreateGraph(&G) > -){

         printG(G);

     }

     return ;

 }