怎么调用该函数:void CreateALGraph(ALGraph *&G) { int i,u,v,w; ArcNode *p; G=(ALGraph *)malloc(sizeof(ALGraph)); printf("输入顶点数和边数,用逗号分隔:"); scanf("%d,%d",&G->n,&G->e); //G->n = 6; //G->e = 9; printf("依次输入各顶点的信息:"); for(i=0;i<G->n;i++) { getchar(); scanf("%c",&(G->adjlist[i].data.info));//给有头节点的数据域置初值 G->adjlist[i].firstarc=NULL;//给所有头节点的指针域置初值 } printf("依次输入各条边的起点编号、终点编号、权值,中间逗号分隔:\n"); for (i=0;i<G->e;i++) { getchar(); scanf("%d,%d,%d",&u,&v,&w); p=(ArcNode *)malloc(sizeof(ArcNode)); //创建节点*p p->adjvex=v; p->info=w; p->nextarc=G->adjlist[u].firstarc; //将*p链到链表头 G->adjlist[u].firstarc=p; } } void DispAdj(ALGraph *G) //输出邻接表G { int i; ArcNode *p; for (i=0;i<G->n;i++) { p=G->adjlist[i].firstarc; printf("%c(%d): ",G->adjlist[i].data.info,i); while (p!=NULL) { printf("%3d(%2d)",p->adjvex,p->info); p=p->nextarc; } printf("\n"); } }
时间: 2024-01-07 14:04:42 浏览: 31
可以这样调用该函数:
```
int main() {
ALGraph *G;
CreateALGraph(G);
DispAdj(G);
return 0;
}
```
其中,`CreateALGraph` 函数用来创建一个无向图的邻接表,`DispAdj` 函数用来输出该邻接表。在 `main` 函数中,我们先定义了一个指向 `ALGraph` 类型的指针 `G`,然后调用 `CreateALGraph` 函数来创建邻接表,并将其赋值给 `G`。最后调用 `DispAdj` 函数输出邻接表。
相关问题
1)编写一个能够创建4种不同类型图的邻接表存储的通用函数,函数格式如下: CreateALGraph(GraphKind GKind, ALGraph &G, int vexnum, int arcnum, char *vexs, int *arcs)
好的,我可以帮你解答这个问题。根据你的要求,我可以为你编写一个能够创建4种不同类型图的邻接表存储的通用函数,函数格式如下:
```C++
typedef enum {DG, DN, UDG, UDN} GraphKind; //图的种类,分别为有向图、有向网、无向图、无向网
typedef struct ArcNode { //边结点定义
int adjvex; //邻接点在顶点数组中的下标
struct ArcNode *nextarc; //指向下一条边的指针
int weight; //边的权重
} ArcNode;
typedef struct VNode { //顶点结点定义
char data; //顶点存储的数据
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { //邻接表图的定义
AdjList vertices; //邻接表
int vexnum, arcnum; //顶点数和边数
GraphKind kind; //图的种类
} ALGraph;
void CreateALGraph(GraphKind GKind, ALGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
G.kind = GKind; //设置图的种类
G.vexnum = vexnum; //设置顶点数
G.arcnum = arcnum; //设置边数
for (int i = 0; i < G.vexnum; i++) { //初始化邻接表
G.vertices[i].data = vexs[i]; //设置顶点的数据
G.vertices[i].firstarc = NULL; //初始化指向第一条边的指针为空
}
int k = 0;
for (int i = 0; i < G.arcnum; i++) { //依次读取每条边的信息并添加到邻接表中
int v1, v2, w;
v1 = arcs[k++]; //读取边的起点下标
v2 = arcs[k++]; //读取边的终点下标
w = arcs[k++]; //读取边的权重
ArcNode *p = new ArcNode; //创建新的边结点
p->adjvex = v2; //设置邻接点在顶点数组中的下标
p->weight = w; //设置边的权重
p->nextarc = G.vertices[v1].firstarc; //将新边结点插入到起点的边链表的头部
G.vertices[v1].firstarc = p;
if (G.kind == UDG || G.kind == UDN) { //如果是无向图或无向网,则还需要在终点处添加一条反向边
p = new ArcNode; //创建新的边结点
p->adjvex = v1; //设置邻接点在顶点数组中的下标
p->weight = w; //设置边的权重
p->nextarc = G.vertices[v2].firstarc; //将新边结点插入到终点的边链表的头部
G.vertices[v2].firstarc = p;
}
}
}
```
该函数的实现思路如下:
1. 首先根据参数中给定的图的种类、顶点数和边数,初始化邻接表图的基本信息。
2. 然后依次读取每条边的信息,将其添加到邻接表中。
3. 对于每条边,我们需要创建新的边结点,并将其插入到起点的边链表的头部。如果是无向图或无向网,则还需要在终点处添加一条反向边。
4. 最后返回创建好的邻接表图。
希望这个函数能够帮助到你,如果你还有其他问题,可以继续问我。
编写一个能够创建4种不同类型图的邻接表存储的通用函数,函数格式如下: CreateALGraph(GraphKind GKind, ALGraph &G, int vexnum, int arcnum, char *vexs, int *arcs)这个函数的main函数实现效果举例
好的,我明白了。以下是CreateALGraph函数的实现及其main函数的使用示例:
```c++
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
// 定义图的类型
enum GraphKind {
DG, // 有向图
DN, // 有向网
UDG, // 无向图
UDN // 无向网
};
// 边结点的类型
struct ArcNode {
int adjvex; // 该边所指向的顶点的位置
int weight; // 权值
ArcNode *nextarc; // 指向下一条边的指针
};
// 顶点结点的类型
struct VNode {
char data; // 顶点的数据域
ArcNode *firstarc; // 指向第一条边的指针
};
// 图的类型(邻接表存储)
struct ALGraph {
VNode *vexs; // 存储顶点的数组
int vexnum; // 顶点数
int arcnum; // 边数
GraphKind kind; // 图的类型
};
// 创建有向图
void CreateDG(ALGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
G.vexs = new VNode[vexnum];
G.vexnum = vexnum;
G.arcnum = arcnum;
G.kind = DG;
int i, j;
// 初始化顶点
for (i = 0; i < vexnum; i++) {
G.vexs[i].data = vexs[i];
G.vexs[i].firstarc = NULL;
}
// 插入边
for (i = 0; i < arcnum; i++) {
int tail = arcs[i * 2];
int head = arcs[i * 2 + 1];
ArcNode *arc = new ArcNode;
arc->adjvex = head;
arc->nextarc = G.vexs[tail].firstarc;
G.vexs[tail].firstarc = arc;
}
}
// 创建有向网
void CreateDN(ALGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
G.vexs = new VNode[vexnum];
G.vexnum = vexnum;
G.arcnum = arcnum;
G.kind = DN;
int i, j;
// 初始化顶点
for (i = 0; i < vexnum; i++) {
G.vexs[i].data = vexs[i];
G.vexs[i].firstarc = NULL;
}
// 插入边
for (i = 0; i < arcnum; i++) {
int tail = arcs[i * 3];
int head = arcs[i * 3 + 1];
int weight = arcs[i * 3 + 2];
ArcNode *arc = new ArcNode;
arc->adjvex = head;
arc->weight = weight;
arc->nextarc = G.vexs[tail].firstarc;
G.vexs[tail].firstarc = arc;
}
}
// 创建无向图
void CreateUDG(ALGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
G.vexs = new VNode[vexnum];
G.vexnum = vexnum;
G.arcnum = arcnum;
G.kind = UDG;
int i, j;
// 初始化顶点
for (i = 0; i < vexnum; i++) {
G.vexs[i].data = vexs[i];
G.vexs[i].firstarc = NULL;
}
// 插入边
for (i = 0; i < arcnum; i++) {
int tail = arcs[i * 2];
int head = arcs[i * 2 + 1];
// 插入tail到head的边
ArcNode *arc1 = new ArcNode;
arc1->adjvex = head;
arc1->nextarc = G.vexs[tail].firstarc;
G.vexs[tail].firstarc = arc1;
// 插入head到tail的边
ArcNode *arc2 = new ArcNode;
arc2->adjvex = tail;
arc2->nextarc = G.vexs[head].firstarc;
G.vexs[head].firstarc = arc2;
}
}
// 创建无向网
void CreateUDN(ALGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
G.vexs = new VNode[vexnum];
G.vexnum = vexnum;
G.arcnum = arcnum;
G.kind = UDN;
int i, j;
// 初始化顶点
for (i = 0; i < vexnum; i++) {
G.vexs[i].data = vexs[i];
G.vexs[i].firstarc = NULL;
}
// 插入边
for (i = 0; i < arcnum; i++) {
int tail = arcs[i * 3];
int head = arcs[i * 3 + 1];
int weight = arcs[i * 3 + 2];
// 插入tail到head的边
ArcNode *arc1 = new ArcNode;
arc1->adjvex = head;
arc1->weight = weight;
arc1->nextarc = G.vexs[tail].firstarc;
G.vexs[tail].firstarc = arc1;
// 插入head到tail的边
ArcNode *arc2 = new ArcNode;
arc2->adjvex = tail;
arc2->weight = weight;
arc2->nextarc = G.vexs[head].firstarc;
G.vexs[head].firstarc = arc2;
}
}
// 创建图的通用函数
void CreateALGraph(GraphKind GKind, ALGraph &G, int vexnum, int arcnum, char *vexs, int *arcs) {
switch (GKind) {
case DG: CreateDG(G, vexnum, arcnum, vexs, arcs); break;
case DN: CreateDN(G, vexnum, arcnum, vexs, arcs); break;
case UDG: CreateUDG(G, vexnum, arcnum, vexs, arcs); break;
case UDN: CreateUDN(G, vexnum, arcnum, vexs, arcs); break;
default: break;
}
}
// 测试函数
void PrintALGraph(ALGraph G) {
int i, j;
cout << "顶点数:" << G.vexnum << endl;
cout << "边数:" << G.arcnum << endl;
cout << "图的类型:";
switch (G.kind) {
case DG: cout << "有向图" << endl; break;
case DN: cout << "有向网" << endl; break;
case UDG: cout << "无向图" << endl; break;
case UDN: cout << "无向网" << endl; break;
default: break;
}
for (i = 0; i < G.vexnum; i++) {
cout << "顶点" << i << ":" << G.vexs[i].data << endl;
ArcNode *arc = G.vexs[i].firstarc;
while (arc != NULL) {
cout << " -> 边<" << i << ", " << arc->adjvex << ">";
if (G.kind == DN || G.kind == UDN) {
cout << ",权值:" << arc->weight;
}
cout << endl;
arc = arc->nextarc;
}
}
}
// 测试
int main() {
int vexnum = 5;
int arcnum = 7;
char vexs[5] = {'A', 'B', 'C', 'D', 'E'};
int arcs1[14] = {0, 1, 0, 2, 1, 2, 1, 3, 2, 4, 3, 4, 4, 0};
int arcs2[21] = {0, 1, 1, 2, 2, 3, 3, 4, 4, 0, 0, 2, 1, 3, 2, 4, 3, 0, 4, 1, 2};
int arcs3[21] = {0, 1, 1, 2, 2, 3, 3, 4, 4, 0, 2, 0, 3, 1, 4, 1, 2, 3, 2, 4, 3};
int arcs4[30] = {0, 1, 2, 1, 2, 1, 3, 3, 2, 3, 4, 4, 0, 4, 1, 5, 2, 5, 3, 5, 4, 6, 0, 6, 2, 6, 4, 6, 5};
ALGraph G1, G2, G3, G4;
CreateALGraph(DG, G1, vexnum, arcnum, vexs, arcs1);
CreateALGraph(UDG, G2, vexnum, arcnum, vexs, arcs2);
CreateALGraph(DN, G3, vexnum, arcnum, vexs, arcs3);
CreateALGraph(UDN, G4, vexnum, arcnum, vexs, arcs4);
PrintALGraph(G1);
PrintALGraph(G2);
PrintALGraph(G3);
PrintALGraph(G4);
return 0;
}
```
这个程序实现了一个通用的函数CreateALGraph,可以根据不同的图的类型创建邻接表存储的图。它的输入参数包括图的类型、图的结构信息(顶点数、边数、顶点数组和边数组),以及一个空的图对象,输出结果是一个存储了图结构的图对象。main函数中,我们使用了四个不同的图类型,测试了CreateALGraph函数的正确性。