C语言 编写算法代码,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
时间: 2024-02-21 19:58:33 浏览: 25
以下是用 C 语言编写的算法代码,可以实现输入顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
#define MAX_ARC_NUM 1000 // 最大弧数
// 边表结点
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;
// 顶点表结点
typedef struct VNode {
char info; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode;
// 邻接表
typedef struct {
VNode vertices[MAX_VERTEX_NUM]; // 顶点表
int vexnum, arcnum; // 图的当前顶点数和弧数
} Graph;
// 初始化有向图
void InitGraph(Graph *G) {
int i;
G->vexnum = 0;
G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].info = '\0';
G->vertices[i].firstarc = NULL;
}
}
// 插入弧
void InsertArc(Graph *G, int tail, int head) {
ArcNode *arc = (ArcNode *)malloc(sizeof(ArcNode));
arc->adjvex = head;
arc->nextarc = G->vertices[tail].firstarc;
G->vertices[tail].firstarc = arc;
G->arcnum++;
}
// 建立有向图的邻接表
void CreateGraph(Graph *G) {
int i, tail, head;
char info;
ArcNode *arc;
printf("请输入顶点数目和弧的数目:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入各顶点的信息:\n");
for (i = 0; i < G->vexnum; i++) {
getchar();
printf("第%d个顶点的信息:", i + 1);
scanf("%c", &G->vertices[i].info);
}
printf("请输入各条弧的信息:\n");
for (i = 0; i < G->arcnum; i++) {
printf("第%d条弧的信息:", i + 1);
scanf("%d%d", &tail, &head);
InsertArc(G, tail - 1, head - 1);
}
}
// 输出邻接表
void PrintGraph(Graph *G) {
int i;
ArcNode *arc;
printf("顶点数目:%d\n", G->vexnum);
printf("弧的数目:%d\n", G->arcnum);
printf("各顶点的信息:\n");
for (i = 0; i < G->vexnum; i++) {
printf("%c ", G->vertices[i].info);
}
printf("\n各条弧的信息:\n");
for (i = 0; i < G->vexnum; i++) {
arc = G->vertices[i].firstarc;
while (arc) {
printf("(%c,%c) ", G->vertices[i].info,
G->vertices[arc->adjvex].info);
arc = arc->nextarc;
}
printf("\n");
}
}
int main() {
Graph G;
InitGraph(&G);
CreateGraph(&G);
PrintGraph(&G);
return 0;
}
```
以上代码实现了建立有向图的邻接表,并可以输出邻接表的内容。在代码中,先定义了边表结点 `ArcNode` 和顶点表结点 `VNode`,然后定义了有向图的邻接表 `Graph`。其中,`Graph` 中的 `vertices` 数组存储了所有顶点的信息,每个顶点的信息包括一个字符和一个指向第一条依附该顶点的弧的指针。`Graph` 中还包括了当前顶点数和弧数。
在 `CreateGraph` 函数中,先输入顶点数目和弧的数目,然后输入每个顶点的信息和每条弧的信息,并调用 `InsertArc` 函数插入弧。在 `PrintGraph` 函数中,先输出顶点数目和弧的数目,然后输出每个顶点的信息和每条弧的信息。
需要注意的是,在输入顶点和弧的信息时,可能需要用 `getchar` 函数读入一个多余的换行符。此外,在将顶点和弧的编号转换为数组下标时,要减去 1。