用c语言实现图的邻接表的存储编写程序,输入顶点的个数、边的个数、每个顶点的值、每一条边及其权值,建立带权无向图G的邻接表,并输出之。
时间: 2024-02-06 08:12:56 浏览: 31
好的,根据你的要求,我编写了如下程序:
```c
#include <stdio.h>
#include <stdlib.h>
// 边结构体
struct Edge {
int to;
int weight;
};
int main() {
int n, m;
printf("请输入顶点的个数和边的个数:");
scanf("%d%d", &n, &m);
int* vertex = (int*)malloc(n * sizeof(int)); // 存储每个顶点的值
struct Edge** adj_list = (struct Edge**)malloc(n * sizeof(struct Edge*)); // 存储邻接表
printf("请依次输入每个顶点的值:");
for (int i = 0; i < n; i++) {
scanf("%d", &vertex[i]);
adj_list[i] = NULL; // 初始化邻接表为空链表
}
printf("请依次输入每一条边的起点、终点和权值:\n");
for (int i = 0; i < m; i++) {
int from, to, weight;
scanf("%d%d%d", &from, &to, &weight);
// 添加无向边
struct Edge* e1 = (struct Edge*)malloc(sizeof(struct Edge));
e1->to = to;
e1->weight = weight;
e1->next = adj_list[from];
adj_list[from] = e1;
struct Edge* e2 = (struct Edge*)malloc(sizeof(struct Edge));
e2->to = from;
e2->weight = weight;
e2->next = adj_list[to];
adj_list[to] = e2;
}
// 输出邻接表
for (int i = 0; i < n; i++) {
printf("%d: ", vertex[i]);
struct Edge* p = adj_list[i];
while (p != NULL) {
printf("%d(%d) ", vertex[p->to], p->weight);
p = p->next;
}
printf("\n");
}
// 释放内存
for (int i = 0; i < n; i++) {
struct Edge* p = adj_list[i];
while (p != NULL) {
struct Edge* tmp = p;
p = p->next;
free(tmp);
}
}
free(adj_list);
free(vertex);
return 0;
}
```
程序中,我们首先读入顶点个数和边的个数,并动态分配相应的内存空间。然后,我们依次读入每个顶点的值和每条边的起点、终点和权值,并在邻接表中添加相应的边。最后,我们遍历邻接表,并输出每个顶点的邻居节点和对应的权值,即可得到带权无向图的邻接表。最后,别忘了释放动态分配的内存。