1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<time.h>
4 #define OK 1
5 #define NO 0
6 #define TRUE 1
7 #define FALSE 0
8 #define ERROR -1
9 #define MAX_VERTEX_NUM 20
10 #define INFINITY 20000000
11
12 typedef
int Status;
13 typedef
enum{DG,DN,UDG,UDN}GraphKind;
//0-有向图，1-有向网（带权值），2-无向图，3-无向网（带权值）
14 typedef
int VRType;
//图表顶点关系类型
15 typedef
struct ArcCell
16 {
17 VRType adj;
//带权图中表示权值，无权图中用0、1表示是否相邻
18 }ArcCell;
19 typedef ArcCell AdjMatrix[MAX_VERTEX_NUM+
1][MAX_VERTEX_NUM+
1];
//领接矩阵
20 /*图、表（数组表示方法）的存储表示*/
21 typedef
char VertexType_M;
//图、表顶点类型
22 typedef
struct
23 {
24 VertexType_M vexs[MAX_VERTEX_NUM+
1];
//顶点向量
25 AdjMatrix arcs;
//领接矩阵
26 int vexnum,arcnum;
//图和表当前的顶点数和弧数
27 int IncInfo;
//为0则各弧不包含其他的信息
28
29 GraphKind kind;
30 }MGraph;
31
32 /*全局变量*/
33 Status visited[MAX_VERTEX_NUM+
1];
//标志数组
34
35 Status CreateGraph_M(MGraph *G,
int r);
36
37 Status CreateDG_M(MGraph *
G);
38
39 Status CreateDN_M(MGraph *
G);
40
41 Status CreateUDG_M(MGraph *
G);
42
43 Status CreateUDN_M(MGraph *
G);
44
45 int LocateVex_M(MGraph G,VertexType_M u);
//寻找顶点u的位置
46
47 void OutputMGraph(MGraph G);
48
49
50 int main(
int argc,
char**
argv)
51 {
52 MGraph G;
53
54 printf(
"1、2、3、4、5\n函数CreateGraph_M等测试..\n");
55 {
56 int r;
57 srand((unsigned)time(NULL));
//用系统的时间做随机数的种子
58 r=rand()%
4;
//对4取余只能产生0，1，2，3，这几个数
59 switch(r)
60 {
61 case DG:
62 printf(
"初始化有向图 G..\n");
63 break;
64 case DN:
65 printf(
"初始化有向网 G..\n");
66 break;
67 case UDG:
68 printf(
"初始化无向图 G..\n");
69 break;
70 case UDN:
71 printf(
"初始化无向网 G..\n");
72 break;
73 }
74 CreateGraph_M(&
G,r);
75 printf(
"\n");
76 }
77 printf(
"19\n函数OutputMGraph 测试..\n");
78 {
79 printf(
"输出图（网）的邻接矩阵 G = \n");
80 OutputMGraph(G);
81 printf(
"\n");
82
83
84 }
85
86 }
87 Status CreateGraph_M(MGraph *G,
int r){
88 switch(r)
89 {
90 case DG:
91 G->kind=
DG;
92 return CreateDG_M(G);
93 case DN:
94 G->kind=
DN;
95 return CreateDN_M(G);
96 case UDG:
97 G->kind=
UDG;
98 return CreateUDG_M(G);
99 case UDN:
100 G->kind=
UDN;
101 return CreateUDN_M(G);
102 default:
103 return ERROR;
104
105 }
106
107 return OK;
108 }
109
110 Status CreateDG_M(MGraph *
G){
111 int i,j,k;
112 VertexType_M v1,v2;
113
114 printf(
"输入顶点数 ");
115 scanf(
"%d",&(G->
vexnum));
116 printf(
"输入弧数 ");
117 scanf(
"%d",&(G->
arcnum));
118 printf(
"输入各个顶点值 ");
119 getchar();
120 for(i=
1;i<=G->vexnum;i++
)
121 {
122 scanf(
"%c",&(G->
vexs[i]));
123 //printf("%d",G->vexs[i]);
124 }
125
126 printf(
"初始化邻接矩阵\n");
127 for(i=
1;i<=G->vexnum;i++
)
128 {
129 for(j=
1;j<=G->vexnum;j++
)
130 G->arcs[i][j].adj=
0;
131 }
132 for(k=
1;k<=G->arcnum;k++
)
133 {
134 getchar();
135 printf(
"输入相邻结点（添加弧的信息）");
136 scanf(
"%c%c",&v1,&
v2);
137 i=LocateVex_M(*
G,v1);
138 j=LocateVex_M(*
G,v2);
139 G->arcs[i][j].adj=
1;
140
141
142 }
143
144 return OK;
145 }
146 Status CreateDN_M(MGraph *
G){
147 int i,j,k;
148 VertexType_M v1,v2;
149 VRType w;
150 printf(
"输入顶点数 ");
151 scanf(
"%d",&(G->
vexnum));
152 printf(
"输入弧数 ");
153 scanf(
"%d",&(G->
arcnum));
154 printf(
"输入各个顶点值 ");
155 getchar();
156 for(i=
1;i<=G->vexnum;i++
)
157 {
158 scanf(
"%c",&(G->
vexs[i]));
159 }
160
161 printf(
"初始化邻接矩阵\n");
162 for(i=
1;i<=G->vexnum;i++
)
163 {
164 for(j=
1;j<=G->vexnum;j++
)
165 G->arcs[i][j].adj=
INFINITY;
166 }
167 for(k=
1;k<=G->arcnum;k++
)
168 {
169 getchar();
170 printf(
"输入相邻结点（添加弧的信息）");
171 scanf(
"%c%c%d",&v1,&v2,&
w);
172 i=LocateVex_M(*
G,v1);
173 j=LocateVex_M(*
G,v2);
174
175 G->arcs[i][j].adj=
w;
176 }
177 return OK;
178 }
179 Status CreateUDG_M(MGraph *
G){
180 int i,j,k;
181 VertexType_M v1,v2;
182
183 printf(
"输入顶点数 ");
184 scanf(
"%d",&(G->
vexnum));
185 printf(
"输入弧数 ");
186 scanf(
"%d",&(G->
arcnum));
187 printf(
"输入各个顶点值 ");
188 getchar();
//后面读取字符串 要加getchar低调前面的回车
189 for(i=
1;i<=G->vexnum;i++
)
190 {
191 scanf(
"%c",&(G->
vexs[i]));
192 }
193
194 printf(
"初始化邻接矩阵\n");
195 for(i=
1;i<=G->vexnum;i++
)
196 {
197 for(j=
1;j<=G->vexnum;j++
)
198 G->arcs[i][j].adj=
0;
199 }
200 for(k=
1;k<=G->arcnum;k++
)
201 {
202 getchar();
203 printf(
"输入相邻结点（添加弧的信息）");
204 scanf(
"%c%c",&v1,&
v2);
205 i=LocateVex_M(*
G,v1);
206 j=LocateVex_M(*
G,v2);
207 G->arcs[i][j].adj=
1;
208 G->arcs[j][i]=G->
arcs[i][j];
209
210
211 }
212
213 return OK;
214 }
215 Status CreateUDN_M(MGraph *
G){
216 int i,j,k;
217 VertexType_M v1,v2;
218 VRType w;
219 printf(
"输入顶点数 ");
220 scanf(
"%d",&(G->
vexnum));
221 printf(
"输入弧数 ");
222 scanf(
"%d",&(G->
arcnum));
223 printf(
"输入各个顶点值 ");
224 getchar();
225 for(i=
1;i<=G->vexnum;i++
)
226 {
227 scanf(
"%c",&(G->
vexs[i]));
228 }
229
230 printf(
"初始化邻接矩阵\n");
231 for(i=
1;i<=G->vexnum;i++
)
232 {
233 for(j=
1;j<=G->vexnum;j++
)
234 G->arcs[i][j].adj=
INFINITY;
235 }
236 for(k=
1;k<=G->arcnum;k++
)
237 {
238 getchar();
239 printf(
"输入相邻结点（添加弧的信息）");
240 scanf(
"%c%c%d",&v1,&v2,&
w);
241 i=LocateVex_M(*
G,v1);
242 j=LocateVex_M(*
G,v2);
243
244 G->arcs[i][j].adj=
w;
245 G->arcs[j][i]=G->
arcs[i][j];
246 }
247
248
249 return OK;
250 }
251
252 int LocateVex_M(MGraph G,VertexType_M u)
253 {
254 int i;
255 for(i=
1;i<=G.vexnum;i++
)
256 {
257 if(G.vexs[i]==
u)
258 return i;
259 }
260 return 0;
261
262 }
263
264 void OutputMGraph(MGraph G){
265 int i,j;
266 if(!G.vexnum&&!
G.arcnum)
267 printf(
"空图（表）！\n");
268 else
269 {
270 printf(
" ");
271 for(i=
1;i<=G.vexnum;i++
)
272 {
273 printf(
"<",G.vexs[i]);
274 }
275 printf(
"\n");
276 for(i=
1;i<=G.vexnum;i++
)
277 {
278 printf(
"%c",G.vexs[i]);
279 for(j=
1;j<=G.vexnum;j++
)
280 {
281 if(G.arcs[i][j].adj==
INFINITY)
282 printf(
" ∞");
283 else
284 printf(
"=",G.arcs[i][j]);
285 }
286 printf(
"\n");
287
288 }
289 }
290 }
转载于:https://www.cnblogs.com/lovecodepql/p/7723468.html
相关资源：数据结构—成绩单生成器
