数据结构 c语言 有向图和无向图邻接表的建立、插入、和删除操作_c语言创建有向图

提示：部分内容我设置了隐藏，点赞之后会自动显示
这次的内容是我们数据结构本周的作业，大概是我做的最辛苦的一次作业
整体难度感觉还可，只是在删除操作里面我因为指针使用混乱导致改了好久
不过这次作业的难点也就是在删除操作那里，做完之后感觉收获还挺大的。

好吧，最让我崩溃的是写这篇文章的时候突然发现我作业的第二个算法题做错了555555555555555555555555555555555555
所以我会在文章的末尾附上无向图邻接表的同样操作供大家参考

题目如下：

下面是我的代码：

头文件和宏定义以及结构等内容

#include<stdio.h>
#include<stdlib.h>
#define MAX_VER_TEX 20//定点的最大个数 
#define VertexType int 
#define ERROR -1
#define OK 0
//typedef enum
//{	Digraph,//有向图 
//	Undigraph//无向图 
//}GraphKind;
typedef struct ArcNode{//弧结点结构 
	int adjvex;//本弧指向的结点的位置
	struct ArcNode *nextarc;//指向下一个弧的指针
	int weight;//权值 
}ArcNode;

typedef struct VNode{//定点结构
	VertexType data; //储存结点的信息 
	ArcNode* firstarc;//指向第一条弧的指针 
}VNode,AdjList[MAX_VER_TEX];
typedef struct{	//图的结构
	AdjList vertexs;//储存顶点的数组
	int vexnum;//顶点个数 
	int arcnum;//边的个数
	//GraphKind kind;//图的种类  
}ALGraph;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

函数部分

int Locate(ALGraph g,VertexType elem)//定位这个结点在数组中的位置
{	int i;
	for(i=0;i<g.vexnum;i++)
	{	if(elem==g.vertexs[i].data)
		return i; 
	}
	return ERROR;//找不到对应元素，返回-1表示不存在 
}
int CreateAlgraph(ALGraph *g)//输入图结构，图的顶点个数，边个数
{	
	int i;
	int a,b,c,pa,pb;
	ArcNode* p;
	printf("输入图的有关信息，\n输入格式：图顶点个数+空格+边个数\n");
	scanf("%d %d",&(g->vexnum),&(g->arcnum));
	printf("下面请输入第一个顶点信息：");
	for(i=0;i<g->vexnum;i++)
	{	scanf("%d",&g->vertexs[i].data);
		g->vertexs[i].firstarc=NULL;
		if(i!=g->vexnum-1)
		{	printf("请输入下一个结点的信息：");
		}
	}
	printf("下面输入第一条边的信息，\n输入格式：起点的信息+空格+终点的信息+权值\n");
	for(i=0;i<g->arcnum;i++)
	{	scanf("%d %d %d",&a,&b,&c);
		pa=Locate(*g,a);//起点在数组里的位置 
		pb=Locate(*g,b);//终点在数组里的位置
		if(pa<0||pb<0)
		{	printf("这个边并不存在，请重新输入\n");
			i--;
			continue; 
		}
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=pb;
		p->weight=c;
		//下面把这个边信息插到起点的弧信息的第一个 
		p->nextarc=g->vertexs[pa].firstarc;
		g->vertexs[pa].firstarc=p;
		if(i!=g->arcnum-1)
		printf("请输入下一条边的信息："); 
		
	}
} 
void PrintOutAlgraph(ALGraph g)
{	int i,j=1;
	ArcNode *p;
	printf("\n*---------分割线---------*\n");
	printf("这个图共有%d个顶点%d条边:\n",g.vexnum,g.arcnum); 
	printf("这个图的顶点信息：\n");
	for(i=0;i<g.vexnum;i++)
	{	printf("该图结构的第%d个顶点的信息是%d\n",i+1,g.vertexs[i].data);
	}
	printf("这个图的边信息：\n");
	for(i=0;i<g.vexnum;i++)
	{	p=g.vertexs[i].firstarc;
		while(p)
		{	printf("第%d条边:（%d ,%d) 权值为：%d\n",j,g.vertexs[i].data,g.vertexs[p->adjvex].data,p->weight);
			j++;
			p=p->nextarc;
		}
	 }
	printf("*---------分割线---------*\n");  
}
//插入一个顶点，返回顶点在图数组里的位置，如果该顶点已经存在，或者数组已满返回-1; 
int InsertArc(ALGraph *g,int a,int b,int aweight)
{	int pa,pb;
	ArcNode*p;
		pa=Locate(*g,a);//起点在数组里的位置 
		pb=Locate(*g,b);//终点在数组里的位置
		if(pa<0||pb<0)
		{	printf("这个边并不存在，请重新输入\n");
			return ERROR;
		}
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=pb;
		p->weight=aweight;
		//下面把这个边信息插到起点的弧信息的第一个 
		p->nextarc=g->vertexs[pa].firstarc;
		g->vertexs[pa].firstarc=p;
		g->arcnum++;//边个数增加 
		return OK;
}
int DeleteArc(ALGraph *g,int a,int b)
{	int pa,pb;
	ArcNode *p,*temp;
	pa=Locate(*g,a);//起点在数组里的位置 
	pb=Locate(*g,b);//终点在数组里的位置
	if(pa<0||pb<0)
		return ERROR;
	p=g->vertexs[pa].firstarc;
	if(p->adjvex==pb)//p为头结点的情况 
		 {	temp=p;
		 	free(temp);
		 	g->vertexs[pa].firstarc=p->nextarc;
		 }

	while(p->nextarc!=NULL)
		{	if(p->nextarc->adjvex==pb)
			{	temp=p->nextarc;
				p->nextarc=temp->nextarc;	
				free(temp);
				break;
			}			
			p=p->nextarc;
		}
	g->arcnum--;//边个数减一 
	return OK;
		 
 } 
int InsertVex(ALGraph *g,int adata)
{	int i;
	if(g->vexnum==MAX_VER_TEX)
	return ERROR;
	for(i=0;i<g->vexnum;i++)
	{	if(adata==g->vertexs[i].data)
		return ERROR;
	}
	g->vertexs[g->vexnum].data=adata;
	g->vertexs[g->vexnum].firstarc=NULL;
	g->vexnum++;//顶点个数增加 
	return g->vexnum-1;
}
int Delete(ArcNode *p)//删除顶点的辅助函数：递归调用删除弧结点内容 
{	if(p)
	{
		Delete(p->nextarc);
		free(p);
		return OK;
	}
	else 
		return NULL;
}
int DeleteVex(ALGraph *g,VertexType adata)
{	int qq=0;
	ArcNode *p,*del,*pre;
	int pdata=Locate(*g,adata);//定位结点位置 
	if(pdata<0)//结点不存在，返回错误信息 
	return ERROR;
	//Delete(g->vertexs[pdata].firstarc);//删除这个结点储存的弧信息
	p=g->vertexs[pdata].firstarc;
	while(p)
	{	g->arcnum--;
		p=p->nextarc;
	 } 
	int i;
	for(i=pdata;i<g->vexnum-1;i++)//数组内容移位 
	{	g->vertexs[i].data=g->vertexs[i+1].data;
		g->vertexs[i].firstarc=g->vertexs[i+1].firstarc;//顶点信息和第一条弧的指针都移位 
	}
	g->vertexs[g->vexnum-1].data=-1;
	g->vertexs[g->vexnum-1].firstarc=NULL;
	g->vexnum--;//顶点个数减1 
	for(i=0;i<g->vexnum;i++)
	{	p=g->vertexs[i].firstarc;
		while(p)
		{	if(p->adjvex==pdata)
			{	
				if(p==g->vertexs[i].firstarc)
				{	del=p;
					p=p->nextarc;
					g->vertexs[i].firstarc=p;
					pre=NULL;
					free(del);
					g->arcnum--;
					break;
				}
				else
				{	del=p;
					p=p->nextarc;
					pre->nextarc=p;
					free(del);
					g->arcnum--;
					break;
				}
			}
			else if(p->adjvex>pdata)
			{	p->adjvex--;
			}
			pre=p;
			p=p->nextarc;
		}
		
	}
	return OK; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

测试函数：

int main()
{	ALGraph test;
	CreateAlgraph(&test);
	PrintOutAlgraph(test);
	InsertArc(&test,11,33,9);
	InsertVex(&test,44);
	printf("插入后：\n");
	PrintOutAlgraph(test);
	DeleteVex(&test,33);
	//DeleteArc(&test,11,22);
	printf("删除后：\n");
	PrintOutAlgraph(test);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

输入及输出结果：

输入图的有关信息，
输入格式：图顶点个数+空格+边个数
3 3
下面请输入第一个顶点信息：11
请输入下一个结点的信息：22
请输入下一个结点的信息：33
下面输入第一条边的信息，
输入格式：起点的信息+空格+终点的信息+权值
11 22 5
请输入下一条边的信息：22 33 6
请输入下一条边的信息：33 11 7

---------分割线---------
这个图共有3个顶点3条边:
这个图的顶点信息：
该图结构的第1个顶点的信息是11
该图结构的第2个顶点的信息是22
该图结构的第3个顶点的信息是33
这个图的边信息：
第1条边:（11 ,22) 权值为：5
第2条边:（22 ,33) 权值为：6
第3条边:（33 ,11) 权值为：7
---------分割线---------
插入后：

---------分割线---------
这个图共有4个顶点4条边:
这个图的顶点信息：
该图结构的第1个顶点的信息是11
该图结构的第2个顶点的信息是22
该图结构的第3个顶点的信息是33
该图结构的第4个顶点的信息是44
这个图的边信息：
第1条边:（11 ,33) 权值为：9
第2条边:（11 ,22) 权值为：5
第3条边:（22 ,33) 权值为：6
第4条边:（33 ,11) 权值为：7
---------分割线---------
删除后：

---------分割线---------
这个图共有3个顶点1条边:
这个图的顶点信息：
该图结构的第1个顶点的信息是11
该图结构的第2个顶点的信息是22
该图结构的第3个顶点的信息是44
这个图的边信息：
第1条边:（11 ,22) 权值为：5
---------分割线---------

---

Process exited after 11.89 seconds with return value 0
请按任意键继续. . .

关键问题就是在数组移位后，弧域里的位置并没有改变，需要在删除之后将其改变才能正常输出

无向图邻接表操作

#include<stdio.h>
#include<stdlib.h>
#define MAX_VER_TEX 20//定点的最大个数 
#define VertexType int 
#define ERROR -1
#define OK 0
//typedef enum
//{	Digraph,//有向图 
//	Undigraph//无向图 
//}GraphKind;
typedef struct ArcNode{//弧结点结构 
	int adjvex;//本弧指向的结点的位置
	struct ArcNode *nextarc;//指向下一个弧的指针
	int weight;//权值 
}ArcNode;
typedef struct VNode{//定点结构
	VertexType data; //储存结点的信息 
	ArcNode* firstarc;//指向第一条弧的指针 
}VNode,AdjList[MAX_VER_TEX];
typedef struct{	//图的结构
	AdjList vertexs;//储存顶点的数组
	int vexnum;//顶点个数 
	int arcnum;//边的个数
	//GraphKind kind;//图的种类  
}UnGraph;
int Locate(UnGraph g,VertexType elem)//定位这个结点在数组中的位置
{	int i;
	for(i=0;i<g.vexnum;i++)
	{	if(elem==g.vertexs[i].data)
		return i; 
	}
	return ERROR;//找不到对应元素，返回-1表示不存在 
}
int CreateUnGraph(UnGraph *g)//输入图结构，图的顶点个数，边个数
{	
	int i;
	int a,b,c,pa,pb;
	ArcNode* p,*p2;
	printf("输入图的有关信息，\n输入格式：图顶点个数+空格+边个数\n");
	scanf("%d %d",&(g->vexnum),&(g->arcnum));
	printf("下面请输入第一个顶点信息：");
	for(i=0;i<g->vexnum;i++)
	{	scanf("%d",&g->vertexs[i].data);
		g->vertexs[i].firstarc=NULL;
		if(i!=g->vexnum-1)
		{	printf("请输入下一个结点的信息：");
		}
	}
	printf("下面输入第一条边的信息，\n输入格式：起点的信息+空格+终点的信息+权值\n");
	for(i=0;i<g->arcnum;i++)
	{	scanf("%d %d %d",&a,&b,&c);
		pa=Locate(*g,a);//起点在数组里的位置 
		pb=Locate(*g,b);//终点在数组里的位置
		if(pa<0||pb<0)
		{	printf("这个边并不存在，请重新输入\n");
			i--;
			continue; 
		}
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=pb;
		p->weight=c;
		//下面把这个边信息插到起点的弧信息的第一个 
		p->nextarc=g->vertexs[pa].firstarc;
		g->vertexs[pa].firstarc=p;
		//在另一个结点的弧域中插入 
		p2=(ArcNode*)malloc(sizeof(ArcNode));
		p2->adjvex=pa;
		p2->weight=c;
		//下面把这个边信息插到起点的弧信息的第一个 
		p2->nextarc=g->vertexs[pb].firstarc;
		g->vertexs[pb].firstarc=p2;
		if(i!=g->arcnum-1)
		printf("请输入下一条边的信息："); 
		
	}
} 
void PrintOutUnGraph(UnGraph g)
{	int i,j=1;
	ArcNode *p;
	printf("\n*---------分割线---------*\n");
	printf("这个图共有%d个顶点%d条边:\n",g.vexnum,g.arcnum); 
	printf("这个图的顶点信息：\n");
	for(i=0;i<g.vexnum;i++)
	{	printf("该图结构的第%d个顶点的信息是%d\n",i+1,g.vertexs[i].data);
	}
	printf("这个图的边信息：\n");
	for(i=0;i<g.vexnum;i++)
	{	p=g.vertexs[i].firstarc;
		while(p)
		{	if(i<p->adjvex)
			{
				printf("第%d条边:（%d ,%d) 权值为：%d\n",j,g.vertexs[i].data,g.vertexs[p->adjvex].data,p->weight);
				j++;
			}
			p=p->nextarc;
		}
	 }
	printf("*---------分割线---------*\n");  
}
int InsertArc(UnGraph *g,int a,int b,int aweight)
{	int pa,pb;
	ArcNode*p,*p2;
		pa=Locate(*g,a);//起点在数组里的位置 
		pb=Locate(*g,b);//终点在数组里的位置
		if(pa<0||pb<0)
		{	printf("这个边并不存在，请重新输入\n");
			return ERROR;
		}
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=pb;
		p->weight=aweight;
		//下面把这个边信息插到起点的弧信息的第一个 
		p->nextarc=g->vertexs[pa].firstarc;
		g->vertexs[pa].firstarc=p;
		//在另一个结点的弧域中插入 
		p2=(ArcNode*)malloc(sizeof(ArcNode));
		p2->adjvex=pa;
		p2->weight=aweight;
		//下面把这个边信息插到起点的弧信息的第一个 
		p2->nextarc=g->vertexs[pb].firstarc;
		g->vertexs[pb].firstarc=p2;
		
		g->arcnum++;//边个数增加 
		return OK;
}
int DeleteArc(UnGraph *g,int a,int b)
{	int pa,pb;
	ArcNode *p,*temp,*p2;
	pa=Locate(*g,a);//起点在数组里的位置 
	pb=Locate(*g,b);//终点在数组里的位置
	if(pa<0||pb<0)
		return ERROR;
	
	p=g->vertexs[pa].firstarc;
	if(p->adjvex==pb)//p为头结点的情况 
		 {	temp=p;
		 	free(temp);
		 	g->vertexs[pa].firstarc=p->nextarc;
		 	
		 	
		 }
	if(p->nextarc->adjvex==pb)
	{	temp=p->nextarc;
		p->nextarc=temp->nextarc;	
		free(temp);
	}
	//从另一个结点删除 
		p2=g->vertexs[pb].firstarc;
	if(p2->adjvex==pa)//p为头结点的情况 
		 {	temp=p2;
		 	free(temp);
		 	g->vertexs[pb].firstarc=p2->nextarc;
		 }
	if(p2->nextarc->adjvex==pa)
	{	temp=p2->nextarc;
		p2->nextarc=temp->nextarc;	
		free(temp);
	}
	g->arcnum--;//边个数减一 
	return OK;
		 
 } 
//插入一个顶点，返回顶点在图数组里的位置，如果该顶点已经存在，或者数组已满返回-1; 
int InsertVex(UnGraph *g,int adata)
{	int i;
	if(g->vexnum==MAX_VER_TEX)
	return ERROR;
	for(i=0;i<g->vexnum;i++)
	{	if(adata==g->vertexs[i].data)
		return ERROR;
	}
	g->vertexs[g->vexnum].data=adata;
	g->vertexs[g->vexnum].firstarc=NULL;
	g->vexnum++;//顶点个数增加 
	return g->vexnum-1;
}
int Delete(ArcNode *p)//删除顶点的辅助函数：递归调用删除弧结点内容 
{	if(p)
	{
		Delete(p->nextarc);
		free(p);
		return OK;
	}
	else 
		return NULL;
}
int DeleteVex(UnGraph *g,VertexType adata)
{	int qq=0;
	ArcNode *p,*del,*pre;
	int pdata=Locate(*g,adata);//定位结点位置 
	if(pdata<0)//结点不存在，返回错误信息 
	return ERROR;
	//Delete(g->vertexs[pdata].firstarc);//删除这个结点储存的弧信息
	p=g->vertexs[pdata].firstarc;
	while(p)
	{	g->arcnum--;
		p=p->nextarc;
	 } 
	int i;
	for(i=pdata;i<g->vexnum-1;i++)//数组内容移位 
	{	g->vertexs[i].data=g->vertexs[i+1].data;
		g->vertexs[i].firstarc=g->vertexs[i+1].firstarc;//顶点信息和第一条弧的指针都移位 
	}
	g->vertexs[g->vexnum-1].data=-1;
	g->vertexs[g->vexnum-1].firstarc=NULL;
	g->vexnum--;//顶点个数减1 
	for(i=0;i<g->vexnum;i++)
	{	p=g->vertexs[i].firstarc;
		while(p)
		{	if(p->adjvex==pdata)
			{	
				if(p==g->vertexs[i].firstarc)
				{	del=p;
					p=p->nextarc;
					g->vertexs[i].firstarc=p;
					pre=NULL;
					free(del);
					g->arcnum--;
					break;
				}
				else
				{	del=p;
					p=p->nextarc;
					pre->nextarc=p;
					free(del);
					g->arcnum--;
					break;
				}
			}
			else if(p->adjvex>pdata)
			{	p->adjvex--;
			}
			pre=p;
			p=p->nextarc;
		}
		
	}
	return OK; 
}



int main()
{	UnGraph test;
	CreateUnGraph(&test);
	PrintOutUnGraph(test);
	InsertVex(&test,44);
	InsertArc(&test,11,44,9);
	printf("插入后：\n");
	PrintOutUnGraph(test);
	DeleteVex(&test,33);
	//DeleteArc(&test,11,33);
	printf("删除后：\n");
	PrintOutUnGraph(test);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255