/*第二关 完成图初始化-邻接表,并完成输出图的邻接表函数 */ GraphList *initGraphList( ) { /*第一行输入图的类型、图的顶点数和边数,第二行输入各条边的两顶点的编号,按顶点编号从小到大的顺序输入。 输出邻接表。不需考虑输入的数字非法情况,输入顶点的信息*/ }
时间: 2024-03-09 19:50:35 浏览: 67
有向图的邻接表表示(c/c ++语言)
4星 · 用户满意度95%
以下是初始化邻接表并输出图的邻接表的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
// 邻接表节点
typedef struct ArcNode {
int adjvex; // 邻接点的位置
struct ArcNode *next; // 指向下一个邻接点
} ArcNode;
// 顶点信息
typedef struct VertexNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点
} VertexNode;
// 邻接表
typedef struct GraphList {
VertexNode vertex[MAX_VERTEX_NUM]; // 存放顶点信息
int vexnum; // 顶点数目
int arcnum; // 边数目
} GraphList;
// 初始化邻接表并输出图的邻接表
GraphList *initGraphList() {
GraphList *G = (GraphList *)malloc(sizeof(GraphList));
if (!G) {
printf("Memory allocation failed.\n");
exit(1);
}
printf("Please enter graph type, number of vertices, and number of edges: ");
scanf("%*s%d%d", &G->vexnum, &G->arcnum);
// 初始化邻接表
for (int i = 0; i < G->vexnum; i++) {
printf("Please enter the information of vertex %d: ", i + 1);
scanf("%d", &G->vertex[i].data);
G->vertex[i].firstarc = NULL;
}
// 读入边信息,建立邻接表
for (int i = 0; i < G->arcnum; i++) {
int v1, v2;
printf("Please enter the two vertices of edge %d: ", i + 1);
scanf("%d%d", &v1, &v2);
// 添加边 v1 -> v2
ArcNode *arc1 = (ArcNode *)malloc(sizeof(ArcNode));
arc1->adjvex = v2 - 1;
arc1->next = G->vertex[v1 - 1].firstarc;
G->vertex[v1 - 1].firstarc = arc1;
// 添加边 v2 -> v1
ArcNode *arc2 = (ArcNode *)malloc(sizeof(ArcNode));
arc2->adjvex = v1 - 1;
arc2->next = G->vertex[v2 - 1].firstarc;
G->vertex[v2 - 1].firstarc = arc2;
}
// 输出邻接表
printf("Adjacency list of the graph:\n");
for (int i = 0; i < G->vexnum; i++) {
printf("%d: ", G->vertex[i].data);
ArcNode *arc = G->vertex[i].firstarc;
while (arc) {
printf("%d ", G->vertex[arc->adjvex].data);
arc = arc->next;
}
printf("\n");
}
return G;
}
```
注意事项:
1. 该函数会返回一个 `GraphList` 类型的指针,指向初始化好的邻接表。
2. 在输入图的类型、顶点数和边数时,使用 `%*s` 跳过输入的图的类型。
3. 顶点编号从 1 开始,但是在程序中需要将其转换为从 0 开始的下标。
阅读全文