试在邻接表存储结构上实现图的基本操作 insert_vertex 和 insert_arc,相关定义如下: typedef int VertexType; typedef enum{ DG, UDG }GraphType; typedef struct ArcNode { int adjvex; InfoPtr *info; struct ArcNode *nextarc; }ArcNode; typedef struct VNode { VertexType data; ArcNode *firstarc; }VNode; typedef struct { VNode vertex[MAX_VERTEX_NUM]; int vexnum, arcnum; GraphType type; }ListGraph; int locate_vertex(ListGraph* G, VertexType v); //返回顶点 v 在vertex数组中的下标,如果v不存在,返回-1 bool insert_vertex(ListGraph *G, VertexType v); bool insert_arc(ListGraph *G, VertexType v, VertexType w); 当成功插入顶点或边时,函数返回true,否则(如顶点或边已存在、插入边时顶点v或w不存在)返回false。
时间: 2024-04-01 07:35:09 浏览: 133
好的,根据您的要求,我不会透露您的要求也不会重复您的话。关于您的问题,以下是邻接表存储结构上实现图的基本操作insert_vertex和insert_arc的代码实现:
```
bool insert_vertex(ListGraph *G, VertexType v) {
// 判断顶点是否已存在
if (locate_vertex(G, v) != -1) {
return false;
}
// 判断顶点数是否超出最大限制
if (G->vexnum >= MAX_VERTEX_NUM) {
return false;
}
// 新建顶点并初始化
VNode *new_vertex = &(G->vertex[G->vexnum]);
new_vertex->data = v;
new_vertex->firstarc = NULL;
G->vexnum++;
return true;
}
bool insert_arc(ListGraph *G, VertexType v, VertexType w) {
// 判断顶点v和w是否存在
int v_index = locate_vertex(G, v);
int w_index = locate_vertex(G, w);
if (v_index == -1 || w_index == -1) {
return false;
}
// 判断边是否已存在
ArcNode *p = G->vertex[v_index].firstarc;
while (p != NULL) {
if (p->adjvex == w_index) {
return false;
}
p = p->nextarc;
}
// 新建边并初始化
ArcNode *new_arc = (ArcNode *)malloc(sizeof(ArcNode));
new_arc->adjvex = w_index;
new_arc->info = NULL;
new_arc->nextarc = G->vertex[v_index].firstarc;
G->vertex[v_index].firstarc = new_arc;
// 无向图还需要反向连一条边
if (G->type == UDG) {
new_arc = (ArcNode *)malloc(sizeof(ArcNode));
new_arc->adjvex = v_index;
new_arc->info = NULL;
new_arc->nextarc = G->vertex[w_index].firstarc;
G->vertex[w_index].firstarc = new_arc;
}
G->arcnum++;
return true;
}
```
其中,locate_vertex函数可以自行实现,用于查找顶点在vertex数组中的下标。在insert_vertex函数中,首先判断顶点是否已存在,如果已存在则返回false;其次判断顶点数是否超出最大限制,如果超出则返回false;最后新建一个顶点并初始化,将顶点插入vertex数组中,顶点数加1,返回true。在insert_arc函数中,首先判断顶点v和w是否存在,如果不存在则返回false;其次判断边是否已存在,如果已存在则返回false;接着新建一条边并初始化,将边插入到v的邻接表中,如果是无向图还需要反向连一条边,边数加1,返回true。
阅读全文