用C语言编写:已知一个带权有向图,其存储结构为邻接表结构 ,设计一算法,由键盘输入数据,建立邻接表,并将其输出。 用例说明: 第一行输入图的顶点数; 第二行输入顶点信息; 第三行以后,按照顺序,每个顶点对应一行,按行输入该顶点对应边的信息(位置 1 权值 1 位置 2 权值 2 ……. ,以 -1 结束)。 输出格式中,代表链表节点的信息是:(边)权值,参见下面用例。
时间: 2023-12-06 09:02:45 浏览: 225
好的,我可以帮你解决这个问题。这里给出一个用C语言实现的建立邻接表并输出的算法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 图的最大顶点数
// 定义边的结构体
typedef struct ArcNode {
int adjvex; // 该边所指向的顶点的位置
int weight; // 该边的权值
struct ArcNode *next; // 指向下一条边的指针
} ArcNode;
// 定义顶点的结构体
typedef struct VertexNode {
char data; // 顶点的数据
ArcNode *firstarc; // 指向第一条边的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];
// 定义图的结构体
typedef struct {
AdjList vertices; // 顶点数组
int vexnum; // 顶点数
int arcnum; // 边数
} ALGraph;
// 创建邻接表
void CreateALGraph(ALGraph *G)
{
printf("请输入图的顶点数:");
scanf("%d", &G->vexnum);
printf("请依次输入各个顶点的信息:\n");
for (int i = 0; i < G->vexnum; i++) {
printf("第 %d 个顶点的信息:", i+1);
scanf(" %c", &G->vertices[i].data); // 输入顶点的数据
G->vertices[i].firstarc = NULL; // 初始化第一条边
}
printf("请输入图的边数:");
scanf("%d", &G->arcnum);
printf("请依次输入各个边的信息:\n");
for (int i = 0; i < G->arcnum; i++) {
printf("第 %d 条边的信息:", i+1);
int v1, v2, w;
scanf("%d %d %d", &v1, &w, &v2); // 输入边的信息
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode)); // 创建新边的节点
p->adjvex = v2-1; // 设置该边所指向的顶点
p->weight = w; // 设置该边的权值
p->next = G->vertices[v1-1].firstarc; // 将该边加入顶点 v1 的链表中
G->vertices[v1-1].firstarc = p;
}
}
// 输出邻接表
void PrintALGraph(ALGraph *G)
{
printf("图的邻接表如下:\n");
for (int i = 0; i < G->vexnum; i++) {
printf("%c -> ", G->vertices[i].data); // 输出顶点的数据
ArcNode *p = G->vertices[i].firstarc;
while (p != NULL) { // 遍历该顶点的所有边
printf("(%d)%c -> ", p->weight, G->vertices[p->adjvex].data); // 输出该边的信息
p = p->next;
}
printf("NULL\n");
}
}
int main()
{
ALGraph G;
CreateALGraph(&G);
PrintALGraph(&G);
return 0;
}
```
以上算法通过键盘输入数据,建立带权有向图的邻接表,并输出该邻接表。其中,`ArcNode` 结构体表示边,`VertexNode` 结构体表示顶点,`ALGraph` 结构体表示图。在 `CreateALGraph()` 函数中,我们首先输入图的顶点数和边数,然后依次输入每个顶点的信息和每条边的信息,并将它们加入到邻接表中。在 `PrintALGraph()` 函数中,我们遍历整个邻接表,并输出每个顶点的链表中的所有边的信息。
希望能够帮助到你!
阅读全文