1 /********************************************************** 2 * Name: 邻接表(有向网) 3 * Data: 2022.01.19 4 * Author: 吕辉 5 * Description: 邻接表是图的链式存储结构,由边表和顶点表组成。 6 * 边表是对图中每个顶点建立一条单链表,表中存放 7 * 与该顶点邻接的相关顶点和对应权值;顶点表用于存 8 * 放图中每个顶点的信息以及指向该顶点边表的头指针。 9 ***********************************************************/ 10 #define _CRT_SECURE_NO_WARNINGS 11 #include <stdio.h> 12 #include <stdlib.h> 13 14 #define MAXVEX 20 15 typedef struct ArcNode 16 { 17 int adjvex;/*弧尾顶点在邻接表中的位置下标*/ 18 int weigth;/*权值*/ 19 struct ArcNode* next; 20 }ArcNode;/*边表结构*/ 21 22 typedef struct VertexNode 23 { 24 char vexdata;/*弧头顶点*/ 25 ArcNode* head;/*该顶点边表的头指针*/ 26 }VertexNode;/*顶点结构*/ 27 28 typedef struct 29 { 30 VertexNode vertex[MAXVEX]; 31 int vexnum;/*顶点总数*/ 32 int arcnum;/*边(弧)总数*/ 33 }AdjList;/*邻接表*/ 34 35 void Create(AdjList* G); 36 int LocateVex(AdjList* G, char vex); 37 void Print(AdjList* G); 38 39 int main(void) 40 { 41 AdjList G; 42 Create(&G); 43 Print(&G); 44 system("pause"); 45 return 0; 46 } 47 /***************************************** 48 * Name: Creat 49 * Call: LocateVex 50 * Called By: main 51 * Parameter: G 邻接表 52 * Description: 通过构建邻接表来存储图 53 ******************************************/ 54 void Create(AdjList* G) 55 { 56 int i = 1; 57 int j = 1; 58 int k = 1; 59 int weight = 0; 60 char vex1 = '\0'; 61 char vex2 = '\0'; 62 ArcNode* P = NULL; 63 ArcNode* Pre = NULL; 64 65 printf("请输入顶点数和边数(逗号分隔):"); 66 scanf("%d%*c%d", &G->vexnum, &G->arcnum); 67 for (i = 1; i <= G->vexnum; i++) 68 { 69 printf("请输入第%d个结点:", i); 70 scanf(" %c", &G->vertex[i].vexdata); 71 G->vertex[i].head = NULL; 72 } 73 for (k = 1; k <= G->arcnum; k++) 74 { 75 printf("请输入第%d条边的弧尾、弧头和权值(逗号分隔)\n", k); 76 scanf(" %c%*c%c%*c%d", &vex1, &vex2, &weight); 77 /*查找并返回顶点在邻接表中的位置*/ 78 i = LocateVex(G, vex1); 79 j = LocateVex(G, vex2); 80 /*链接边表结点*/ 81 P = (ArcNode*)calloc(1, sizeof(ArcNode)); 82 P->adjvex = j; 83 P->weigth = weight; 84 /*判断图中某顶点的指针域是否为空*/ 85 if (G->vertex[i].head == NULL) 86 { 87 G->vertex[i].head = P; 88 } 89 else 90 { 91 Pre = G->vertex[i].head; 92 while (Pre->next) 93 { 94 Pre = Pre->next; 95 } 96 Pre->next = P; 97 } 98 }/*for循环*/ 99 } 100 /********************************************************** 101 * Name: LocateVex 102 * Called By: Create 103 * Parameter: G 邻接表 104 * vex 顶点 105 * Description: 查找顶点vex在顶点表中的位置下标,并返回 106 * return: 若顶点表中存在该顶点,则返回其位置下标; 107 否则返回0; 108 **********************************************************/ 109 int LocateVex(AdjList* G, char vex) 110 { 111 int i = 1; 112 for (i = 1; i <= G->vexnum; i++) 113 { 114 if (G->vertex[i].vexdata == vex) 115 { 116 return i; 117 } 118 } 119 return 0; 120 } 121 /****************************************** 122 * Name: Print 123 * Called By: main 124 * Parameter: G 邻接表 125 * Description: 打印所有边的信息 126 *******************************************/ 127 void Print(AdjList* G) 128 { 129 int i = 1; 130 int j = 1; 131 ArcNode* P = NULL; 132 for (i = 1; i <= G->arcnum; i++) 133 { 134 P = G->vertex[i].head; 135 while (P) 136 { 137 /*弧尾顶点在邻接表中位置下标*/ 138 j = P->adjvex; 139 printf("%c--%d--%c\n", G->vertex[i].vexdata, P->weigth, G->vertex[j].vexdata); 140 P = P->next; 141 } 142 } 143 }