用c语言完成,试在邻接组阵存储结构上实现图的基本操作: Insert Vex ( G , v) , Insert Arc (G,v,w), DeleteVex(G,v )和 DeleteArc(G ,v ,w )。
时间: 2023-10-11 08:10:38 浏览: 38
好的,我可以为您解答这个问题。
在邻接矩阵存储结构中,我们可以用二维数组来表示图,其中数组的行和列分别代表图中的顶点。如果顶点之间存在边,则数组元素的值为1,否则为0。
以下是用C语言实现图的基本操作的代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100 // 最大顶点数
typedef int Vertex; // 顶点类型
typedef int WeightType; // 边的权重类型
typedef struct {
Vertex V[MaxVertexNum]; // 顶点数组
WeightType G[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
int N, E; // 顶点数和边数
} MGraph;
// 插入顶点
void InsertVex(MGraph *G, Vertex v) {
if (G->N == MaxVertexNum) {
printf("图的顶点数已达到最大值,无法插入新顶点!\n");
return;
}
G->V[G->N++] = v;
}
// 插入边
void InsertArc(MGraph *G, Vertex v, Vertex w, WeightType weight) {
int i, j;
for (i = 0; i < G->N; i++) {
if (G->V[i] == v) {
break;
}
}
for (j = 0; j < G->N; j++) {
if (G->V[j] == w) {
break;
}
}
if (i == G->N || j == G->N) {
printf("输入的顶点不存在!\n");
return;
}
G->G[i][j] = weight;
G->E++;
}
// 删除顶点
void DeleteVex(MGraph *G, Vertex v) {
int i, j, k;
for (i = 0; i < G->N; i++) {
if (G->V[i] == v) {
break;
}
}
if (i == G->N) {
printf("输入的顶点不存在!\n");
return;
}
for (j = 0; j < G->N; j++) {
if (G->G[i][j] != 0) {
G->E--;
}
}
for (j = 0; j < G->N; j++) {
G->G[i][j] = 0;
G->G[j][i] = 0;
}
G->N--;
for (k = i; k < G->N; k++) {
G->V[k] = G->V[k + 1];
}
}
// 删除边
void DeleteArc(MGraph *G, Vertex v, Vertex w) {
int i, j;
for (i = 0; i < G->N; i++) {
if (G->V[i] == v) {
break;
}
}
for (j = 0; j < G->N; j++) {
if (G->V[j] == w) {
break;
}
}
if (i == G->N || j == G->N) {
printf("输入的顶点不存在!\n");
return;
}
if (G->G[i][j] == 0) {
printf("输入的边不存在!\n");
return;
}
G->G[i][j] = 0;
G->E--;
}
int main() {
MGraph G;
G.N = 0;
G.E = 0;
// 插入顶点
InsertVex(&G, 1);
InsertVex(&G, 2);
InsertVex(&G, 3);
// 插入边
InsertArc(&G, 1, 2, 1);
InsertArc(&G, 2, 3, 2);
// 删除顶点
DeleteVex(&G, 2);
// 删除边
DeleteArc(&G, 1, 2);
return 0;
}
```
以上代码中,`InsertVex`、`InsertArc`、`DeleteVex`、`DeleteArc`四个函数分别实现了插入顶点、插入边、删除顶点、删除边的操作。在主函数中,我们先插入了三个顶点,然后插入了两条边,接着删除了一个顶点和一条边。