编辑代码

#include <stdio.h>
#include <malloc.h>

#define MaxVertexNum 10

//定义一个指向图结点ENode的指针*PtrToEode
typedef struct ENode *PtrToENode;
typedef int Vertex;
//边结点
struct ENode{
    Vertex V1,V2;  //两个顶点
    int Weight; //权重
};
typedef PtrToENode Edge;

//用顶点下标表示顶点，为整型
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
    //邻接点下标
    Vertex AdjV;
    //边权重
    int Weight;
    PtrToAdjVNode Next;
};

typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
    //存顶点的数据
    int AdjV;
}AdjList[MaxVertexNum]; //AdjList是邻接表类型

//定义一个指向图结点GNode的指针*PtrToGode
typedef struct GNode *PtrToGode;
//图结点
struct GNode{
    //顶点数
    int Nv;
    //边数
    int Ne;
    //邻接表
    AdjList G;
};
//以邻接表存储的图类型
typedef PtrToGode LGraph;

LGraph CreateGraph(int VertexNum);
void InsertEdge(LGraph Graph,Edge E);
LGraph BuildGraph();

//完整地建立一个LGraph
LGraph BuildGraph(){
    LGraph Graph;
    Edge E;
    int Nv,i;

    printf("输入结点数：\n");
    scanf("%d",&Nv);
    Graph = CreateGraph(Nv);
    printf("输入边数：\n");
    scanf("%d",&(Graph->Ne));
    if(Graph->Ne != 0){
        E = (Edge)malloc(sizeof(struct ENode));
        for(i = 0;i < Graph->Ne;i++){
            printf("输入要插入边的两个顶点以及权重：\n");
            scanf("%d %d %d",&(E->V1),&(E->V2),&(E->Weight));
            InsertEdge(Graph,E);
        }
    }

    return Graph;
}

void InsertEdge(LGraph Graph,Edge E){
    PtrToAdjVNode NewNode;

    //插入边<v1,v2>
    //为v2建立新的邻接点
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode)); 
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    //将V2插入V1的表头
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    //若是无向图，还要插入边<v2,v1>
    //为v1建立新的邻接点
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode)); 
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    //将V1插入V2的表头
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

//初始化一个有VertexNum个顶点但没有边的图
LGraph CreateGraph(int VertexNum){
    Vertex V,W;
    LGraph Graph = (LGraph)malloc(sizeof(struct GNode));
    
    Graph->Nv = VertexNum;
    Graph->Ne = 0;

    //这里默认顶点编号从0开始，到（Graph->Nv-1）
    for(V = 0;V < Graph->Nv;V++){
        //给头结点的数据赋值为指针数组的下标
        Graph->G[V].AdjV = V;
        Graph->G[V].FirstEdge = NULL;
    }
    
    return Graph;
}

int main () {
    LGraph Graph = BuildGraph();
    int i,j;

    printf("创建的图的邻接表为：\n");
    for(i = 0;i < Graph->Nv;i++){

        PtrToAdjVNode p;
        p = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));

        if(Graph->G[i].FirstEdge != NULL){
            p = Graph->G[i].FirstEdge;
            //打印头结点的数据
            printf("%d: ",Graph->G[i].AdjV);
            while(p != NULL){
                printf("%d %d ",p->AdjV,p->Weight);
                p = p->Next;
            }
        }
        printf("\n");
    }

    return 0;
}