C语言,编写算法,由依次输入的顶点数目,弧的数目,各顶点的信息和各条弧的信息建立有向图的邻接表
时间: 2024-02-23 08:00:56 浏览: 65
编写算法,由依次输入的顶点数目、弧的数目、各顶点信息和各条弧信息建立有向图的邻接表。
4星 · 用户满意度95%
好的,这是一个关于C语言的算法问题。我会根据你的要求进行回答。
首先,我们需要定义一个顶点的结构体,包括顶点的信息和指向第一个邻接点的指针。
```c
typedef struct ArcNode {
int adjvex; // 指向的顶点
struct ArcNode *nextarc; // 指向下一条弧的指针
int weight; // 弧的权值
} ArcNode;
typedef struct VertexNode {
char vertex; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点的指针
} VertexNode;
```
然后,我们定义一个图的结构体,包括顶点数目、弧的数目和一个指向顶点数组的指针。
```c
typedef struct {
VertexNode *vertices; // 顶点数组
int vexnum; // 顶点数目
int arcnum; // 弧的数目
} Graph;
```
接下来,我们定义一个函数来创建图的邻接表。该函数首先需要读取输入的顶点数目和弧的数目,然后创建顶点数组并初始化每个顶点。接着,读取每个顶点的信息和每条弧的信息,并将它们添加到邻接表中。
```c
Graph* createGraph() {
int vexnum, arcnum;
scanf("%d %d", &vexnum, &arcnum);
Graph *g = (Graph*)malloc(sizeof(Graph));
g->vexnum = vexnum;
g->arcnum = arcnum;
g->vertices = (VertexNode*)malloc(sizeof(VertexNode) * vexnum);
// 初始化每个顶点
for (int i = 0; i < vexnum; i++) {
scanf(" %c", &g->vertices[i].vertex);
g->vertices[i].firstarc = NULL;
}
// 添加每条弧到邻接表中
for (int i = 0; i < arcnum; i++) {
int start, end, weight;
scanf("%d %d %d", &start, &end, &weight);
ArcNode *arc = (ArcNode*)malloc(sizeof(ArcNode));
arc->adjvex = end;
arc->weight = weight;
arc->nextarc = g->vertices[start].firstarc;
g->vertices[start].firstarc = arc;
}
return g;
}
```
最后,我们可以调用 createGraph 函数来创建一个有向图的邻接表。
```c
int main() {
Graph *g = createGraph();
// 其他操作
return 0;
}
```
以上就是一个建立有向图邻接表的C语言算法。希望对你有所帮助!
阅读全文