1 /**********************************************************************************
  2 *Name: 邻接矩阵(无向网)
  3 *Date: 2022.01.18
  4 *Author: 吕辉
  5 *Description: 图的邻接矩阵是表示顶点之间相邻关系的矩阵，是顺序存储结构，
  6 *             因此也称为“数组表示法”。它采用两个数组分别来存储图的顶点
  7 *             和边(弧)的信息。其中，用一个一维数组来存储顶点信息，一个二维
  8 *             数组来存储边(弧)的信息。事实上，这里的邻接矩阵主要指的是这个
  9 *             二维数组。---《数据结构与算法(王曙燕)》
 10 ***********************************************************************************/
 11 #define _CRT_SECURE_NO_WARNINGS
 12 #include <stdio.h>
 13 #include <stdlib.h>
 14 
 15 #define MAXVEX 20/*最大顶点个数*/
 16 #define INFINITY 32767/*表示极大值∞*/
 17 typedef struct
 18 {
 19     int arcs[MAXVEX][MAXVEX];/*边(弧)信息*/
 20     char vex[MAXVEX];/*顶点信息，这里顶点类型设置为字符型*/
 21     int vexnum;/*顶点数目*/
 22     int arcnum;/*边(弧)数目*/
 23 }AdjMatrix;/*邻接矩阵(Adjacency Matrix)*/
 24 
 25 void Create(AdjMatrix* G);
 26 int LocateVex(AdjMatrix* G, char vex);
 27 void Print(AdjMatrix* G);
 28 
 29 int main(void)
 30 {
 31     AdjMatrix G;
 32     Create(&G);
 33     Print(&G);
 34     system("pause");
 35     return 0;
 36 }
 37 /***************************************************
 38 * Function: Create
 39 * Description: 用邻接矩阵创建无向网
 40 * Called By: main
 41 * Call: LocateVex
 42 * Parameter : G 图
 43 ****************************************************/
 44 void Create(AdjMatrix* G)
 45 {
 46     int i = 1;
 47     int j = 1;
 48     int k = 1;
 49     int weight = 0;
 50     char vex1 = '\0';
 51     char vex2 = '\0';
 52 
 53     printf("请输入无向网中的顶点数和边数(逗号分隔)：\n");
 54     scanf("%d%*c%d", &G->vexnum, &G->arcnum);
 55     for (i = 1; i <= G->vexnum; i++)
 56     {
 57         for (j = 1; j <= G->vexnum; j++)
 58         {
 59             G->arcs[i][j] = INFINITY;
 60         }
 61     }
 62     printf("请输入无向网中%d个结点：\n", G->vexnum);
 63     for (i = 1; i <= G->vexnum; i++)
 64     {
 65         printf("第%d个顶点：",  i);
 66         scanf(" %c", &G->vex[i]);/*%c前均有一个空格，用于吸收缓冲区的空白字符*/
 67     }
 68     printf("请输入无向网中%d条边：\n", G->vexnum);
 69     for (k = 1; k <= G->arcnum; k++)
 70     {
 71         printf("从顶点：");
 72         scanf(" %c", &vex1);
 73         printf("到顶点：");
 74         scanf(" %c", &vex2);
 75         printf("权值为：");
 76         scanf("%d", &weight);
 77         i = LocateVex(G, vex1);
 78         j = LocateVex(G, vex2);
 79         G->arcs[i][j] = weight;
 80         G->arcs[j][i] = weight;
 81     }
 82 }
 83 /*************************************************************
 84 * Function: LocateVex
 85 * Description: 返回输入顶点在顶点数组中的位置
 86 * Called By: Create
 87 * Parameter : G 图
 88 *                      vex 顶点
 89 * Return:    若G中存在顶点vex，则返回该顶点在顶点数组中下标
 90 *                否则返回 0
 91 **************************************************************/
 92 int LocateVex(AdjMatrix* G, char vex)
 93 {
 94     int i = 1;
 95     for (i = 1; i <= G->vexnum; i++)
 96     {
 97         if (G->vex[i] == vex)
 98         {
 99             return i;
100         }
101     }
102     return 0;
103 }
104 /*************************************************************
105 * Function: Print
106 * Description: 打印邻接矩阵
107 * Called By: main
108 * Parameter : G 图
109 **************************************************************/
110 void Print(AdjMatrix* G)
111 {
112     int i = 1;
113     int j = 1;
114     printf("邻接矩阵为：\n");
115     for (i = 1; i <= G->vexnum; i++)
116     {
117         for (j = 1; j <= G->vexnum; j++)
118         {
119             printf("%d\t", G->arcs[i][j]);
120         }
121         printf("\n");
122     }
123 }