首页 > 代码库 > 构建有向图邻接表
构建有向图邻接表
建立一个有向图的邻接表,首先要构思好它的邻接表里面包含哪些结构数据,然后根据哪些数据来建立相应的结构体。但也要注意数据的输入。
#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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。