用C语言先依次输入有向图的顶点信息,再依次输入有向图的弧信息,建立图的邻接表存储结构并将其打印输出并举例
时间: 2024-02-06 07:10:12 浏览: 23
好的,以下是用 C 语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef struct ArcNode { // 弧结点
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *next; // 指向下一条弧的指针
} ArcNode;
typedef struct VNode { // 顶点结点
int data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { // 邻接表
AdjList vertices; // 存储图中所有顶点的数组
int vexnum, arcnum; // 顶点数和弧数
} ALGraph;
// 初始化邻接表
void InitGraph(ALGraph *G) {
int i;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].data = 0;
G->vertices[i].firstarc = NULL;
}
}
// 添加顶点
int AddVertex(ALGraph *G, int v) {
if (G->vexnum >= MAX_VERTEX_NUM) {
printf("Error: the graph is full!\n");
return 0;
}
G->vertices[G->vexnum].data = v;
G->vexnum++;
return 1;
}
// 添加弧
int AddArc(ALGraph *G, int v, int w) {
if (v < 0 || v >= G->vexnum || w < 0 || w >= G->vexnum) {
printf("Error: invalid vertex!\n");
return 0;
}
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = w;
p->next = G->vertices[v].firstarc;
G->vertices[v].firstarc = p;
G->arcnum++;
return 1;
}
// 打印邻接表
void PrintGraph(ALGraph *G) {
int i;
printf("Vertices: ");
for (i = 0; i < G->vexnum; i++) {
printf("%d ", G->vertices[i].data);
}
printf("\nArcs:\n");
for (i = 0; i < G->vexnum; i++) {
ArcNode *p = G->vertices[i].firstarc;
while (p != NULL) {
printf("%d -> %d\n", G->vertices[i].data, G->vertices[p->adjvex].data);
p = p->next;
}
}
}
int main() {
ALGraph G;
int v, w, i, j;
InitGraph(&G);
// 输入顶点信息
printf("Enter the vertices (maximum %d): ", MAX_VERTEX_NUM);
for (i = 0; i < MAX_VERTEX_NUM; i++) {
scanf("%d", &v);
if (v < 0) break;
if (!AddVertex(&G, v)) break;
}
// 输入弧信息
printf("Enter the arcs (enter -1 to end):\n");
while (1) {
scanf("%d %d", &v, &w);
if (v == -1 || w == -1) break;
if (!AddArc(&G, v, w)) break;
}
// 打印邻接表
PrintGraph(&G);
return 0;
}
```
下面是一个示例输入输出:
```
Enter the vertices (maximum 20): 0 1 2 3 4 -1
Enter the arcs (enter -1 to end):
0 1
0 3
1 2
1 4
2 3
2 4
3 1
-1 -1
Vertices: 0 1 2 3 4
Arcs:
0 -> 1
0 -> 3
1 -> 2
1 -> 4
2 -> 3
2 -> 4
3 -> 1
4 ->
```
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)