用c需要编写代码,已知一个带权有向图,其存储结构为邻接表结构 ,设计一算法,由键盘输入数据,建立邻接表,并将其输出。 用例说明: 第一行输入图的顶点数; 第二行输入顶点信息; 第三行以后,按照顺序,每个顶点对应一行,按行输入该顶点对应边的信息(位置 1 权值 1 位置 2 权值 2 ……. ,以 -1 结束)。
时间: 2024-01-13 09:03:39 浏览: 33
好的,我可以帮你设计一个建立带权有向图邻接表的算法,以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 边表结点
typedef struct EdgeNode {
int adjvex; // 邻接点位置
int weight; // 权值
struct EdgeNode *next; // 指向下一个邻接点
} EdgeNode;
// 顶点表结点
typedef struct VertexNode {
char data; // 顶点信息
EdgeNode *firstedge; // 指向第一个邻接点
} VertexNode, AdjList[MAX_VERTEX_NUM];
// 图结构
typedef struct {
AdjList adjList; // 邻接表
int vexNum, edgeNum; // 顶点数和边数
} Graph;
// 建立邻接表
void CreateGraph(Graph *G) {
int i, j, k, weight;
EdgeNode *e; // 边表结点
printf("请输入顶点数:");
scanf("%d", &G->vexNum);
printf("请输入顶点信息:");
for (i = 0; i < G->vexNum; i++) {
scanf(" %c", &G->adjList[i].data);
G->adjList[i].firstedge = NULL; // 初始化边表头指针
}
printf("请输入边数:");
scanf("%d", &G->edgeNum);
for (k = 0; k < G->edgeNum; k++) {
printf("请输入第%d条边(起点 权值 终点):", k + 1);
scanf("%d %d %d", &i, &weight, &j);
e = (EdgeNode *) malloc(sizeof(EdgeNode));
e->adjvex = j;
e->weight = weight;
e->next = G->adjList[i].firstedge;
G->adjList[i].firstedge = e;
}
}
// 输出邻接表
void PrintGraph(Graph G) {
int i;
EdgeNode *p;
printf("邻接表如下:\n");
for (i = 0; i < G.vexNum; i++) {
printf("%c", G.adjList[i].data);
p = G.adjList[i].firstedge;
while (p) {
printf(" --> %c(%d)", G.adjList[p->adjvex].data, p->weight);
p = p->next;
}
printf("\n");
}
}
int main() {
Graph G;
CreateGraph(&G);
PrintGraph(G);
return 0;
}
```
以上代码实现了建立带权有向图邻接表的算法,并将邻接表输出。其中,CreateGraph函数用于建立邻接表,PrintGraph函数用于输出邻接表。