图的存储–邻接表法

邻接表法（顺序+链式存储）

邻接表法

总结

代码实现

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100

typedef char VertexType;        //顶点数据类型
typedef int EdgeType;           //边的权重

typedef struct EdgeNode{
    int adjVex;                 //邻接点域，存储该节点的下标
    EdgeType weigth;            //边的权重
    struct EdgeNode* next;      //指向下一条边的指针

}EdgeNode;

typedef struct VertrNode{
    VertexType data;            //顶点数据
    struct EdgeNode* firstEdge; //指向第一条边的指针
}VertrNode,AdjList[MAXVEX];

typedef struct GraphAdj{
    int numVertexes,numEdges;   //  顶点数量、边节点数量
    AdjList adjList;
}GraphAdjList;

void CreateGraphAdjList(GraphAdjList* G){
    int i,j,k,w;
    printf("请输入顶点数量与边的数量:\n");
    scanf("%d%d",&G->numVertexes,&G->numEdges);
    getchar();
    printf("请输入每个顶点的数据:\n");
    for(i = 0;i < G->numVertexes;i ++){
        scanf("%c",&G->adjList[i].data);
        G->adjList[i].firstEdge = NULL;
    }

    for(k = 0;k < G->numEdges;k ++)
    {
        printf("请输入边(vi,vj)上的顶点的下标,i,j,及权重w:\n");
        scanf("%d%d%d",&i,&j,&w);
        EdgeNode* q = (EdgeNode*)malloc(sizeof (EdgeNode));
        q->adjVex = j;
        q->weigth = w;
        q->next = G->adjList[i].firstEdge;      //头插法
        G->adjList[i].firstEdge = q;
        //有向图不需要下面操作 注释掉即可 因为无向图每次要存两次
//        q = (EdgeNode*)malloc(sizeof (EdgeNode));
//        q->adjVex = j;
//        q->weigth = w;
//        q->next = G->adjList[j].firstEdge;
//        G->adjList[j].firstEdge = q;
    }
}

int main(){
    GraphAdjList GA;
    printf("--------邻接表的创建--------");
    CreateGraphAdjList(&GA);
    return 0;
}