2007-d-三

#include <stdio.h>
#include <stdlib.h>

#define maxSize 100

//邻接表定义存储
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;

typedef struct VNode
{
    int data;
    ArcNode *firstarc;
}VNode;

typedef struct AGraph
{
    VNode adjlist[maxSize];
    int n,e;
} AGraph;

//邻接表建立
void create(AGraph *G)
{
    int i;
    int h,t;
    ArcNode *p;
    printf("请输入顶点数、弧数：\n");
    scanf("%d,%d",&G->n,&G->e);
    //输入顶点数、弧数
    for(i=0;i<G->n;++i)
    {
        printf("请输入第%d个顶点值\n",i);
        scanf("%d",&G->adjlist[i].data);
        G->adjlist[i].firstarc=NULL;
    }
    //输入弧
    for(i=0;i<G->e;++i)
    {
         printf("请按顺序输入弧头[h]、弧尾[t]\n");
         scanf("%d,%d",&h,&t);
         p=(ArcNode*)malloc(sizeof(ArcNode));
         p->adjvex=t;
         /*将新边表结点p 插入到顶点Vh 的边表头部*/
         p->nextarc=G->adjlist[h].firstarc;
         G->adjlist[h].firstarc=p;
    }
}

//建立逆邻接表
AGraph* produce(AGraph *G)
{
    AGraph *N;
    N=(AGraph *)malloc(sizeof(AGraph));
    ArcNode *p,*q;
    int i;
    N->e=G->e;
    N->n=G->n;
    for(i=0;i<G->n;++i)
    {
        //建立逆邻接表的顶点表
       N->adjlist[i].data=G->adjlist[i].data;
       N->adjlist[i].firstarc=NULL;
    }
    for(i=0;i<G->n;++i)
    {
       //建立逆邻接表边表
       p=G->adjlist[i].firstarc;
       while(p!=NULL)
       {
         //将新边表结点p 插入到顶点Vh 的边表头部
         q=(ArcNode *)malloc(sizeof(ArcNode));
         q->adjvex=i;
         q->nextarc=N->adjlist[p->adjvex].firstarc;
         N->adjlist[p->adjvex].firstarc=q;
         p=p->nextarc;
       }
    }
    return N;
}
/**

测试

//输出图
void printG(AGraph *G)
{
    int i;
    ArcNode *p;

    for(i=0;i<G->n;++i)
    {
       printf("%d------\n",G->adjlist[i].data);
       p=G->adjlist[i].firstarc;
       while(p!=NULL)
       {
        printf("%d->%d\n",i,p->adjvex);
        p=p->nextarc;
       }
    }
}

//主函数
int main()
{
    AGraph *G;
    G=(AGraph *)malloc(sizeof(AGraph));//必须初始化
    create(G);
    printG(G);
    printG(produce(G));
}
**/