用C语言实现(1) 键盘输入数据,建立一个有向图的邻接表。 (2) 输出该邻接表。 (3) 在有向图的邻接表的基础上计算各顶点的度,并输出。
时间: 2024-03-09 22:48:56 浏览: 91
好的,我可以为您解答这个问题。
首先,我们需要了解邻接表的定义和有向图的定义。
邻接表是一种表示图的数据结构,它将每个顶点的所有邻接点都保存在一个链表中,它是一种比邻接矩阵更节省空间的存储方式。
有向图是一种图,它的边有方向,即从一个顶点到另一个顶点有一个箭头指向。
接下来,我们来看看如何用C语言实现。
1. 键盘输入数据,建立一个有向图的邻接表。
我们可以先定义一个结构体表示每个顶点和它所连接的边:
```c
// 边节点结构体
typedef struct EdgeNode {
int adjvex; // 邻接点的下标
struct EdgeNode *next; // 下一个邻接点
} EdgeNode;
// 顶点结构体
typedef struct VertexNode {
char data; // 顶点的数据
EdgeNode *first_edge; // 指向第一个邻接点的指针
} VertexNode;
```
然后,我们可以通过循环输入每个顶点和它所连接的边来建立邻接表:
```c
VertexNode G[MAX_VEX]; // 定义邻接表
int vex_num, edge_num; // 顶点数和边数
// 输入顶点数和边数
scanf("%d %d", &vex_num, &edge_num);
// 输入顶点数据
for (int i = 0; i < vex_num; i++) {
scanf(" %c", &G[i].data);
G[i].first_edge = NULL; // 初始化每个顶点的邻接表为空
}
// 输入边信息,建立邻接表
for (int i = 0; i < edge_num; i++) {
int start, end;
scanf("%d %d", &start, &end);
// 新建一个边节点,并将它插入到对应的链表中
EdgeNode *edge = (EdgeNode*)malloc(sizeof(EdgeNode));
edge->adjvex = end;
edge->next = G[start].first_edge;
G[start].first_edge = edge;
}
```
2. 输出该邻接表。
我们可以依次遍历每个顶点的邻接表,并输出它所连接的边:
```c
// 输出邻接表
for (int i = 0; i < vex_num; i++) {
printf("%c -> ", G[i].data);
EdgeNode *p = G[i].first_edge;
while (p) {
printf("%c ", G[p->adjvex].data);
p = p->next;
}
printf("\n");
}
```
3. 在有向图的邻接表的基础上计算各顶点的度,并输出。
对于有向图,每个顶点的度分为入度和出度,分别表示指向该顶点的边数和从该顶点出发的边数。
我们可以通过遍历每个顶点的邻接表来计算它的出度,并遍历所有边来计算它的入度:
```c
// 计算顶点的出度
int out_degree(int v) {
int count = 0;
EdgeNode *p = G[v].first_edge;
while (p) {
count++;
p = p->next;
}
return count;
}
// 计算顶点的入度
int in_degree(int v) {
int count = 0;
for (int i = 0; i < vex_num; i++) {
EdgeNode *p = G[i].first_edge;
while (p) {
if (p->adjvex == v) {
count++;
}
p = p->next;
}
}
return count;
}
// 输出各顶点的度
for (int i = 0; i < vex_num; i++) {
printf("%c: in=%d, out=%d\n", G[i].data, in_degree(i), out_degree(i));
}
```
这样,我们就完成了用C语言实现键盘输入数据,建立一个有向图的邻接表,并输出该邻接表,最后计算各顶点的度,并输出的过程。
阅读全文