已知一个带权有向图,其存储结构为邻接表结构 ,设计一算法,由键盘输入数据,建立邻接表,并将其输出。 用例说明: 第一行输入图的顶点数; 第二行输入顶点信息; 第三行以后,按照顺序,每个顶点对应一行,按行输入该顶点对应边的信息(位置 1 权值 1 位置 2 权值 2 ……. ,以 -1 结束)。
时间: 2024-02-02 17:03:28 浏览: 112
好的,我可以为您提供一个简单的C语言实现,实现建立带权有向图的邻接表并输出。下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表的结构体
typedef struct EdgeNode {
int adjvex; // 邻接点域,存储该节点的邻接点在顶点数组中的下标
int weight; // 权值域,存储该边的权值
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
typedef struct VertexNode {
char data; // 存储顶点信息
EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode, AdjList[100];
typedef struct {
AdjList adjList; // 邻接表
int n, e; // 顶点数和边数
} ALGraph;
// 创建邻接表
void createGraph(ALGraph *G) {
printf("请输入图的顶点数: ");
scanf("%d", &G->n);
getchar(); // 吸收回车符
printf("请输入顶点信息: ");
for (int i = 0; i < G->n; i++) {
scanf("%c", &G->adjList[i].data);
G->adjList[i].firstedge = NULL; // 初始化邻接表
}
getchar(); // 吸收回车符
printf("请输入每个顶点对应的邻接点信息: \n");
for (int i = 0; i < G->n; i++) {
printf("请输入第%d个顶点对应的邻接点信息(以-1结束): ", i + 1);
int adjvex, weight;
scanf("%d", &adjvex);
while (adjvex != -1) {
scanf("%d", &weight);
// 创建新边节点并插入邻接表中
EdgeNode *edge = (EdgeNode *)malloc(sizeof(EdgeNode));
edge->adjvex = adjvex;
edge->weight = weight;
edge->next = G->adjList[i].firstedge;
G->adjList[i].firstedge = edge;
scanf("%d", &adjvex); // 继续输入下一个邻接点
}
}
G->e = 0; // 初始化边数
for (int i = 0; i < G->n; i++) {
EdgeNode *p = G->adjList[i].firstedge;
while (p != NULL) {
G->e++;
p = p->next;
}
}
}
// 输出邻接表
void printGraph(ALGraph G) {
printf("图的邻接表如下: \n");
for (int i = 0; i < G.n; i++) {
printf("%d(%c):", i, G.adjList[i].data);
EdgeNode *p = G.adjList[i].firstedge;
while (p != NULL) {
printf("->%d(%d)", p->adjvex, p->weight);
p = p->next;
}
printf("\n");
}
}
int main() {
ALGraph G;
createGraph(&G);
printGraph(G);
return 0;
}
```
以上代码实现了建立带权有向图的邻接表并输出。您可以根据自己的需要进行调整和完善。
阅读全文