int CreateUDG(ALGragh &G,int vexnum,int arcnum,char ch[]) {//采用邻接表表示法,创建无向图G /**************begin************/ /**************end************/ }帮我补全
时间: 2023-07-01 14:26:31 浏览: 121
无向图的邻接表表示
4星 · 用户满意度95%
下面是采用邻接表表示法,创建无向图G的完整代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXVEX 100 // 最大顶点数
// 边表结点
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
// 顶点表结点
typedef struct VNode {
char data; // 顶点数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAXVEX];
// 图的邻接表结构
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 根据顶点数据在邻接表中查找顶点的下标
int locateVex(ALGraph G, char v) {
int i;
for (i = 0; i < G.vexnum; i++) {
if (G.vertices[i].data == v) {
return i;
}
}
return -1;
}
// 创建无向图G
int CreateUDG(ALGraph &G, int vexnum, int arcnum, char ch[]) {
int i, j, k;
ArcNode *p;
char v1, v2;
G.vexnum = vexnum;
G.arcnum = arcnum;
// 初始化顶点表
for (i = 0; i < G.vexnum; i++) {
G.vertices[i].data = ch[i];
G.vertices[i].firstarc = NULL;
}
// 构造邻接表
for (k = 0; k < G.arcnum; k++) {
printf("输入边(vi,vj)上的顶点序号:\n");
scanf("%c%c", &v1, &v2);
getchar();
i = locateVex(G, v1);
j = locateVex(G, v2);
// 头插法插入边表结点
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p;
// 由于是无向图,对称地插入边表结点
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = p;
}
return 1;
}
int main() {
ALGraph G;
char ch[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
CreateUDG(G, 7, 9, ch);
return 0;
}
```
阅读全文