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
11 typedef
int Status;
12
13 typedef
enum{DG,UDG}GraphKind;
14
15 typedef
struct ArcNode
16 {
17 int adjvex;
//该弧指向的顶点的位置
18 struct ArcNode *nextarc;
//指向下一个弧结点的指针
19 }ArcNode;
20
21 typedef
char VertexType_AL;
22 typedef
struct VNode
//头结点
23 {
24 VertexType_AL data;
25 ArcNode *
firstarc;
26 }VNode;
27 typedef VNode AdjList[MAX_VERTEX_NUM+
1];
28
29 /*图的存储方式*/
30 typedef
struct
31 {
32 AdjList vertices;
//邻接表
33 int vexnum,arcnum;
//图当前顶点数和弧数
34 GraphKind kind;
35 }ALGraph;
36
37
38
39 Status CreateGraph_AL(ALGraph *G,
int r);
40
41 Status CreateDG_AL(ALGraph *
G);
42
43 Status CreateUDG_AL(ALGraph *
G);
44
45 int LocateVex_AL(ALGraph G,VertexType_AL u);
46
47 void OutputALGraph(ALGraph G);
48
49 int main(
int argc,
char**
argv)
50 {
51 ALGraph G;
52 printf(
"1、2、3\n函数CreateGraph_AL等测试..\n");
53 {
54 int r;
55 srand((unsigned)time(NULL));
//用系统的时间做随机数的种子
56 r=rand()%
2;
//对4取余只能产生0，1这几个数
57 switch(r)
58 {
59 case DG:
60 printf(
"初始化有向图 G..\n");
61 break;
62 case UDG:
63 printf(
"初始化无向图 G..\n");
64 break;
65 }
66 CreateGraph_AL(&
G,r);
67 printf(
"\n");
68 }
69
70
71 printf(
"17\n函数OutputALGraph 测试..\n");
72 {
73 printf(
"输出图的邻接表 G = \n");
74 OutputALGraph(G);
75 printf(
"\n");
76
77
78 }
79 return 0;
80 }
81
82 Status CreateGraph_AL(ALGraph *G,
int r){
83
84 switch(r)
85 {
86 case DG:
87 G->kind=
DG;
88 return CreateDG_AL(G);
89 case UDG:
90 G->kind=
UDG;
91 return CreateUDG_AL(G);
92 default:
93 return ERROR;
94
95 }
96
97 return OK;
98
99
100
101 }
102
103 int LocateVex_AL(ALGraph G,VertexType_AL u)
104 {
105 int i;
106 for(i=
1;i<=G.vexnum;i++
)
107 {
108 if(G.vertices[i].data==
u)
109 return i;
110 }
111 return 0;
112
113 }
114 Status CreateDG_AL(ALGraph *
G){
115 int i,j,k;
116 VertexType_AL v1,v2;
117 ArcNode *
p;
118 ArcNode *r[MAX_VERTEX_NUM+
1];
119 printf(
"输入顶点数 ");
120 scanf(
"%d",&(G->
vexnum));
121 printf(
"输入弧数 ");
122 scanf(
"%d",&(G->
arcnum));
123 printf(
"输入各个顶点值 ");
124 getchar();
125 for(i=
1;i<=G->vexnum;i++
)
126 {
127 scanf(
"%c",&(G->
vertices[i].data));
128 G->vertices[i].firstarc=
NULL;
129 r[i]=
NULL;
130 }
131
132 printf(
"读取各边，制作邻接表\n");
133 for(k=
1;k<=G->arcnum;k++
)
134 {
135 getchar();
136 printf(
"输入相邻结点（添加弧的信息）");
137 scanf(
"%c%c",&v1,&
v2);
138 i=LocateVex_AL(*G,v1);
//第i个结点的链表相连
139 j=LocateVex_AL(*
G,v2);
140 p=(ArcNode*)
malloc(
sizeof(ArcNode));
141 if(!
p)
142 exit(ERROR);
143 p->adjvex=
j;
144 p->nextarc=
NULL;
145 if(r[i]==
NULL)
146 G->vertices[i].firstarc=
p;
147 else
148 r[i]->nextarc=
p;
149 r[i]=p;
//r[i]用来标记链表的最后一个结点指针，起到延长链表添加新的结点的作用
150
151 }
152
153 return OK;
154 }
155 Status CreateUDG_AL(ALGraph *
G){
156 int i,j,k;
157 VertexType_AL v1,v2;
158 ArcNode *p,*
q;
159 ArcNode *r[MAX_VERTEX_NUM+
1];
160 printf(
"输入顶点数 ");
161 scanf(
"%d",&(G->
vexnum));
162 printf(
"输入弧数 ");
163 scanf(
"%d",&(G->
arcnum));
164 printf(
"输入各个顶点值 ");
165 getchar();
166 for(i=
1;i<=G->vexnum;i++
)
167 {
168 scanf(
"%c",&(G->
vertices[i].data));
169 G->vertices[i].firstarc=
NULL;
170 r[i]=
NULL;
171 }
172
173 printf(
"读取各边，制作邻接表\n");
174 for(k=
1;k<=G->arcnum;k++
)
175 {
176 getchar();
177 printf(
"输入相邻结点（添加弧的信息）");
178 scanf(
"%c%c",&v1,&
v2);
179 i=LocateVex_AL(*G,v1);
//第i个结点的链表相连
180 j=LocateVex_AL(*
G,v2);
181 p=(ArcNode*)
malloc(
sizeof(ArcNode));
182 if(!
p)
183 exit(ERROR);
184 p->adjvex=
j;
185 p->nextarc=
NULL;
186 if(r[i]==
NULL)
187 G->vertices[i].firstarc=
p;
188 else
189 r[i]->nextarc=
p;
190 r[i]=p;
//r[i]用来标记链表的最后一个结点指针，起到延长链表添加新的结点的作用
191 q=(ArcNode*)
malloc(
sizeof(ArcNode));
192 if(!
q)
193 exit(ERROR);
194 q->adjvex=
i;
195 q->nextarc=
NULL;
196 if(r[j]==
NULL)
197 G->vertices[j].firstarc=
q;
198 else
199 r[j]->nextarc=
q;
200 r[j]=q;
//i和j轮换对称，上面的方法可以给i添加邻接表，下面的也可以给j按同样的方法添加，只是也就是输入两个结点的时候会同时进行两次操作
201
202
203 }
204
205
206 return OK;
207 }
208
209 void OutputALGraph(ALGraph G){
210 int i,j;
211 ArcNode *
p;
212 if(!G.vexnum&&!
G.arcnum)
213 printf(
"空图！\n");
214 else
215 {
216 for(i=
1;i<=G.vexnum;i++
)
217 {
218 printf(
"%c->",G.vertices[i].data);
219 p=
G.vertices[i].firstarc;
220 while(p)
221 {
222 printf(
" %c",G.vertices[p->
adjvex].data);
223 p=p->
nextarc;
224
225 }
226 printf(
"\n");
227 }
228 }
229 }
转载于:https://www.cnblogs.com/lovecodepql/p/7724391.html
