用c语言实现图的邻接表存储,要有输入的步骤
时间: 2023-12-14 15:40:04 浏览: 35
好的,以下是一个简单的示例代码,实现图的邻接表存储,包括输入过程:
```c
#include <stdio.h>
#include <stdlib.h>
// 边节点结构体
typedef struct EdgeNode {
int adjvex; // 邻接点下标
struct EdgeNode* next; // 指向下一个邻接点的指针
} EdgeNode;
// 顶点节点结构体
typedef struct VertexNode {
int data; // 顶点数据
EdgeNode* firstedge; // 指向第一个邻接点的指针
} VertexNode;
// 图结构体
typedef struct Graph {
VertexNode* vertexes; // 存储顶点的数组
int vexnum; // 顶点数
int edgenum; // 边数
} Graph;
// 创建图
void createGraph(Graph* G) {
printf("请输入图的顶点数和边数,格式为:顶点数 边数\n");
scanf("%d %d", &G->vexnum, &G->edgenum);
// 分配存储顶点的数组空间
G->vertexes = (VertexNode*)malloc(G->vexnum * sizeof(VertexNode));
if (G->vertexes == NULL) {
printf("内存分配失败!\n");
exit(1);
}
// 初始化每个顶点的邻接表为空
for (int i = 0; i < G->vexnum; i++) {
G->vertexes[i].data = i; // 顶点的数据为下标
G->vertexes[i].firstedge = NULL;
}
printf("请输入每条边的两个顶点的下标(从0开始),格式为:起点终点\n");
for (int i = 0; i < G->edgenum; i++) {
int start, end;
scanf("%d %d", &start, &end);
// 创建边节点
EdgeNode* edge = (EdgeNode*)malloc(sizeof(EdgeNode));
if (edge == NULL) {
printf("内存分配失败!\n");
exit(1);
}
edge->adjvex = end;
edge->next = NULL;
// 将边节点插入起点的邻接表中
EdgeNode* p = G->vertexes[start].firstedge;
if (p == NULL) {
G->vertexes[start].firstedge = edge;
} else {
while (p->next != NULL) {
p = p->next;
}
p->next = edge;
}
}
}
// 打印图
void printGraph(Graph G) {
printf("图的邻接表如下:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("%d -> ", G.vertexes[i].data);
EdgeNode* p = G.vertexes[i].firstedge;
while (p != NULL) {
printf("%d ", p->adjvex);
p = p->next;
}
printf("\n");
}
}
// 主函数
int main() {
Graph G;
createGraph(&G);
printGraph(G);
return 0;
}
```
以上代码中,createGraph() 函数用于创建图,其中包括输入顶点数和边数,以及每条边的两个顶点的下标。printGraph() 函数用于打印图的邻接表。在主函数中,首先创建一个空图,然后调用 createGraph() 函数输入图的信息,最后调用 printGraph() 函数打印图的邻接表。