C语言完成图的邻接表创建和输出实验要求:要建立的是有向图(1)还是无向图(0)参考代码
时间: 2024-03-09 07:51:27 浏览: 55
建立和输出有向图的邻接表的问题
4星 · 用户满意度95%
好的,以下是C语言实现有向图和无向图邻接表创建和输出的参考代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
// 邻接点结构体
typedef struct ArcNode {
int adjvex; // 邻接点编号
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
// 顶点结构体
typedef struct VNode {
int vertex; // 顶点编号
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 图结构体
typedef struct {
int vexnum; // 顶点个数
int arcnum; // 边个数
AdjList vertices; // 邻接表数组
} ALGraph;
// 初始化邻接表
void init(ALGraph *G) {
int i;
for (i = 0; i < G->vexnum; i++) {
G->vertices[i].vertex = i;
G->vertices[i].firstarc = NULL;
}
}
// 添加边到邻接表
void addArc(ALGraph *G, int v, int w) {
ArcNode *node = (ArcNode *) malloc(sizeof(ArcNode));
node->adjvex = w;
node->nextarc = G->vertices[v].firstarc;
G->vertices[v].firstarc = node;
}
// 创建有向图
void createDirectedGraph(ALGraph *G) {
int v, w, i;
printf("请输入顶点个数和边个数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
init(G);
printf("请输入每条边的起点和终点:\n");
for (i = 0; i < G->arcnum; i++) {
scanf("%d%d", &v, &w);
addArc(G, v, w);
}
}
// 创建无向图
void createUndirectedGraph(ALGraph *G) {
int v, w, i;
printf("请输入顶点个数和边个数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
init(G);
printf("请输入每条边的起点和终点:\n");
for (i = 0; i < G->arcnum; i++) {
scanf("%d%d", &v, &w);
addArc(G, v, w);
addArc(G, w, v);
}
}
// 输出邻接表
void print(ALGraph *G) {
int i;
ArcNode *p;
for (i = 0; i < G->vexnum; i++) {
printf("%d: ", G->vertices[i].vertex);
p = G->vertices[i].firstarc;
while (p != NULL) {
printf("%d ", p->adjvex);
p = p->nextarc;
}
printf("\n");
}
}
int main() {
ALGraph G;
int kind;
printf("请输入图的类型(0表示无向图,1表示有向图):");
scanf("%d", &kind);
if (kind == 0) {
createUndirectedGraph(&G);
} else {
createDirectedGraph(&G);
}
print(&G);
return 0;
}
```
以上代码中,`init`函数用于初始化邻接表,`addArc`函数用于将边信息添加到邻接表中,`createDirectedGraph`函数和`createUndirectedGraph`函数分别用于创建有向图和无向图,`print`函数用于输出邻接表。在创建有向图时,只需要将边信息添加到起点的邻接表中即可;而在创建无向图时,需要同时将边信息添加到起点和终点的邻接表中。
阅读全文