1 #include<stdio.h> 2 #include<stdlib.h> 3 #include "listGraph.cpp" 4 5 int main(void) { 6 listGraph G;//定义保存邻接矩阵结构的图 7 int i, j; 8 9 printf("请输入生成图的类型(0.无向图, 1.有向图):"); 10 scanf("%d", &G.graphType); 11 printf("请输入图的定点数量和边的数量:"); 12 scanf("%d %d", &G.vertexNum, &G.edgeNum); 13 printf("输入构成各边的两个顶点及权值: "); 14 createGraph(&G);//创建邻接表保存的图 15 printf("邻接表数据如下: "); 16 outList(&G); 17 return 0; 18 } 19 20 void createGraph(listGraph* G) { 21 int i, weight; 22 int start, end; 23 edgeNode* s; 24 25 for (i = 1; i <= G->vertexNum; i++) G->adjList[i] = NULL;//将图中的各顶点指针清空 26 for (i = 1; i <= G->edgeNum; i++) { 27 getchar(); 28 printf("第%d条边:", i); 29 scanf("%d %d %d", &start, &end, &weight);//输入边的起点和终点及权值 30 s = (edgeNode*)malloc(sizeof(edgeNode));//申请保存一个顶点的内存 31 s->next = G->adjList[start];//插入到邻接表中 32 s->vertex = end;//保存终点编号 33 s->weight = weight; 34 G->adjList[start] = s;//邻接表对应顶点指向终点 35 //如果是无向图，则需要再插入到终点的指针后 36 if (!G->graphType) { 37 s = (edgeNode*)malloc(sizeof(edgeNode)); 38 s->next = G->adjList[end]; 39 s->vertex = start; 40 s->weight = weight; 41 G->adjList[end] = s; 42 } 43 } 44 } 45 46 void outList(listGraph* G) { 47 int i; 48 edgeNode* s; 49 50 for (i = 1; i <= G->vertexNum; i++) { 51 printf("顶点%d", i); 52 s = G->adjList[i]; 53 while (s) { 54 printf("->%d(%d)", s->vertex, s->weight); 55 s = s->next; 56 } 57 printf(" "); 58 } 59 }
#include "listGraph.cpp" 如下：
1 #define vertex_max 20 2 typedef struct Node { 3 int vertex;//定点序号 4 int weight;//权值 5 struct Node* next;//指向有边的下一个顶点 6 }edgeNode; 7 8 typedef struct { 9 edgeNode* adjList[vertex_max];//指向每个顶点的指针 10 int vertexNum, edgeNum; 11 int graphType;//0表示无向图，1有向图 12 }listGraph; 13 14 void createGraph(listGraph* G);//生成图的邻接表 15 void outList(listGraph* G);//输出邻接表