邻接多重表(无向图)的抽象数据结构
1 #define MAXVEX 20/*最大顶点数*/
2 typedef struct ArcNode
3 {
4 int mark;/*访问标记*/
5 int ivex;/*该边依附的顶点的位置*/
6 int jvex;
7 struct ArcNode* inext;/*依附该顶点的下一条边*/
8 struct ArcNode* jnext;
9 }ArcNode;/*边表*/
10
11 typedef struct VexNode
12 {
13 char vexdata;
14 ArcNode* head;/*指向第一条依附该顶点的边*/
15 }VexNode;/*顶点表*/
16
17 typedef struct
18 {
19 int vexnum;/*顶点数*/
20 int arcnum;/*边数*/
21 VexNode vertex[MAXVEX];
22 }AMLGraph;/*邻接多重表(Adjacency Multilist)*/
创建邻接多重表(无向图)
1 void Create(AMLGraph* G)
2 {
3 int i = 1;
4 int j = 1;
5 int k = 1;
6 char vex1 = '\0';
7 char vex2 = '\0';
8 ArcNode* P = NULL;
9 ArcNode* Pre = NULL;
10
11 printf("请输入顶点数和边数(逗号分隔)：");
12 scanf("%d%*c%d", &G->vexnum, &G->arcnum);
13 for (i = 1; i <= G->vexnum; i++)
14 {
15 printf("请输入第%d个顶点：", i);
16 scanf(" %c", &G->vertex[i].vexdata);
17 G->vertex[i].head = NULL;
18 }
19 for (k = 1; k <= G->arcnum; k++)
20 {
21 printf("请输入第%d条边的两顶点(逗号分隔)：", k);
22 scanf(" %c%*c%c", &vex1, &vex2);
23 i = LocateVex(G, vex1);
24 j = LocateVex(G, vex2);
25 P = (ArcNode*)calloc(1, sizeof(ArcNode));
26 P->ivex = i;
27 P->jvex = j;
28 /*链接以vex1为顶点的下一条边*/
29 if (G->vertex[i].head == NULL)
30 {
31 G->vertex[i].head = P;
32 }
33 else
34 {
35 Pre = G->vertex[i].head;
36 while (Pre->inext)
37 {
38 Pre = Pre->inext;
39 }
40 Pre->inext = P;
41 }
42 /*链接以vex2为顶点的下一条边*/
43 if (G->vertex[j].head == NULL)
44 {
45 G->vertex[j].head = P;
46 }
47 else
48 {
49 Pre = G->vertex[j].head;
50 while (Pre->jnext)
51 {
52 Pre = Pre->jnext;
53 }
54 Pre->jnext = P;
55 }
56 }/*for循环*/
57 }
View Code
LocateVex函数
1 int LocateVex(AMLGraph* G, char vex)
2 {
3 int i = 1;
4 for (i = 1; i <= G->vexnum; i++)
5 {
6 if (G->vertex[i].vexdata == vex)
7 {
8 return i;
9 }
10 }
11 return 0;
12 }
View Code
源代码
1 /********************************************************************
2 * Name: 邻接多重表(无向图)
3 * Data: 2022.01.21
4 * Author: 吕辉
5 * Description: 邻接多重表(Adjacency Multilist)是无向图的一种链式存储结构，
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 mark;/*访问标记*/
18 int ivex;/*该边依附的顶点的位置*/
19 int jvex;
20 struct ArcNode* inext;/*依附该顶点的下一条边*/
21 struct ArcNode* jnext;
22 }ArcNode;/*边表*/
23
24 typedef struct VexNode
25 {
26 char vexdata;
27 ArcNode* head;/*指向第一条依附该顶点的边*/
28 }VexNode;/*顶点表*/
29
30 typedef struct
31 {
32 int vexnum;/*顶点数*/
33 int arcnum;/*边数*/
34 VexNode vertex[MAXVEX];
35 }AMLGraph;/*邻接多重表(Adjacency Multilist)*/
36
37 void Create(AMLGraph* G);
38 int LocateVex(AMLGraph* G, char vex);
39 void Print(AMLGraph G);
40
41 int main(void)
42 {
43 AMLGraph G;
44 Create(&G);
45 Print(G);
46 system("pause");
47 return 0;
48 }
49 /*****************************************************
50 * Name: Create
51 * Called By: main
52 * Call: LocateVex
53 * Parameter: G 邻接多重表
54 * Description: 创建邻接多重表
55 ******************************************************/
56 void Create(AMLGraph* G)
57 {
58 int i = 1;
59 int j = 1;
60 int k = 1;
61 char vex1 = '\0';
62 char vex2 = '\0';
63 ArcNode* P = NULL;
64 ArcNode* Pre = NULL;
65
66 printf("请输入顶点数和边数(逗号分隔)：");
67 scanf("%d%*c%d", &G->vexnum, &G->arcnum);
68 for (i = 1; i <= G->vexnum; i++)
69 {
70 printf("请输入第%d个顶点：", i);
71 scanf(" %c", &G->vertex[i].vexdata);
72 G->vertex[i].head = NULL;
73 }
74 for (k = 1; k <= G->arcnum; k++)
75 {
76 printf("请输入第%d条边的两顶点(逗号分隔)：", k);
77 scanf(" %c%*c%c", &vex1, &vex2);
78 i = LocateVex(G, vex1);
79 j = LocateVex(G, vex2);
80 P = (ArcNode*)calloc(1, sizeof(ArcNode));
81 P->ivex = i;
82 P->jvex = j;
83 /*链接以vex1为顶点的下一条边*/
84 if (G->vertex[i].head == NULL)
85 {
86 G->vertex[i].head = P;
87 }
88 else
89 {
90 Pre = G->vertex[i].head;
91 while (Pre->inext)
92 {
93 Pre = Pre->inext;
94 }
95 Pre->inext = P;
96 }
97 /*链接以vex2为顶点的下一条边*/
98 if (G->vertex[j].head == NULL)
99 {
100 G->vertex[j].head = P;
101 }
102 else
103 {
104 Pre = G->vertex[j].head;
105 while (Pre->jnext)
106 {
107 Pre = Pre->jnext;
108 }
109 Pre->jnext = P;
110 }
111 }/*for循环*/
112 }
113 /**************************************************
114 * Name: LocateVex
115 * Called By: Create
116 * Parameter: G 邻接多重表
117 * vex 顶点
118 * return: 若顶点表中存在vex则返回其在表中下标，
119 * 否则返回0
120 * Description: 把顶点转换成对应顶点表中下标
121 ***************************************************/
122 int LocateVex(AMLGraph* G, char vex)
123 {
124 int i = 1;
125 for (i = 1; i <= G->vexnum; i++)
126 {
127 if (G->vertex[i].vexdata == vex)
128 {
129 return i;
130 }
131 }
132 return 0;
133 }
134 /*********************************************
135 * Name: Print
136 * Called By: main
137 * Parameter: G 邻接多重表
138 * Description: 打印邻接多重表
139 **********************************************/
140 void Print(AMLGraph G)
141 {
142 int i = 1;
143 int j = 0;
144 int k = 1;/*边数*/
145 char vex1 = '\0';
146 char vex2 = '\0';
147 ArcNode* P = NULL;
148 for (k = 1; k <= G.arcnum; k += j, i++)
149 {
150 j = 0;
151 P = G.vertex[i].head;
152 while (P && P->mark == 0)
153 {
154 j++;
155 vex1 = G.vertex[P->ivex].vexdata;
156 vex2 = G.vertex[P->jvex].vexdata;
157 printf("%c--%c\n", vex1, vex2);
158 P->mark = 1;
159 P = P->inext;
160 }
161 }/*for循环*/
162 }
View Code