首页 > 代码库 > 构建有向图邻接表

构建有向图邻接表

2024-07-10 18:46:44   225人阅读

      建立一个有向图的邻接表，首先要构思好它的邻接表里面包含哪些结构数据，然后根据哪些数据来建立相应的结构体。但也要注意数据的输入。

 

#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 10typedef struct ArcNode             //弧节点结构体{     int adjvex;                            //该弧指向定点的位置     int data;     struct ArcNode * nextarc;    //指向下下一条弧的指针}ArcNode;typedef struct VNode             //定点结构体{     char data;     ArcNode * firstarc;              //指向第一条弧的指针}VNode, AdjList[MAX_SIZE];typedef struct                         //创建图的结构体{     AdjList vertices;                   //顶点数组     int vexnum, arcnum;           //顶点个数及弧的条数}ALGraph;int Find(ALGraph G, char ch)    //查找此节点位于顶点数组的那个位置{     int i;     for(i = 0; i<G.vexnum; i++)     {          if(ch == G.vertices[i].data)               break;     }     return i;}void Input(ALGraph & G)     //构建邻接表的输入操作{     int mark, data;               //mark是用来标记是否有下一条弧，data则用来保存要输入的数据     ArcNode * p;     char ch;     printf("请输入图的顶点数和弧的条数。\n");     scanf("%d%d", &G.vexnum, &G.arcnum);     printf("请输入顶点信息。\n");     getchar();     for(int i = 0; i<G.vexnum; i++)          {               scanf("%c", &G.vertices[i].data);               getchar();         }     printf("请按照各个顶点的顺序来输入弧节点。\n");     for(int i = 0; i<G.vexnum; i++)     {          mark = 1;          G.vertices[i].firstarc = NULL;          printf("请判断以%c为弧尾的弧。\n", G.vertices[i].data);          while(mark)          {               printf("判断是否有下一个弧，若有则输入1，无则输入0。\n");               scanf("%d", &mark);               getchar();               if(mark)               {                    p = (ArcNode *)malloc(sizeof(ArcNode));                    p->nextarc = NULL;                    printf("输入弧节点的信息：");                    scanf("%c", &ch);                    getchar();                    scanf("%d", &data);                    p->adjvex = Find(G, ch);                    p->data =http://www.mamicode.com/ data;                    p->nextarc = G.vertices[i].firstarc;                    G.vertices[i].firstarc = p;               }          }     }}void Output(ALGraph G)       //输出图的有关信息{     for(int i = 0; i<G.vexnum; i++)     {          printf("%c : ", G.vertices[i].data);          while(G.vertices[i].firstarc)                  //输出每个节点弧中所包含的数据          {               printf("%d  ", G.vertices[i].firstarc->data);               G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc ;          }          printf("\n");     }}int main(){     ALGraph G;     Input(G);     Output(G);     return 0;}

 


联系
我们