创建有向图G的十字链表,用C语言函数形式写出求图中各顶点度的算法:COUNT_D(G[n],D[n]),G[n]为顶点表, D[n]为存放各顶点度的数组,n为图中顶点的个数。
时间: 2024-04-16 14:26:28 浏览: 51
有向图的十字链表
好的,我明白了。下面是用C语言编写的求图中各顶点度的算法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义顶点表结构体
typedef struct VertexNode {
int indegree; // 入度
int outdegree; // 出度
struct ArcNode* firstInArc; // 指向以该顶点为终点的第一条弧
struct ArcNode* firstOutArc; // 指向以该顶点为起点的第一条弧
} VertexNode;
// 定义弧结构体
typedef struct ArcNode {
int tail; // 弧的起点
int head; // 弧的终点
struct ArcNode* nextInArc; // 指向下一条以终点为终点的弧
struct ArcNode* nextOutArc; // 指向下一条以起点为起点的弧
} ArcNode;
// 计算各顶点度的函数
void COUNT_D(VertexNode G[], int D[], int n) {
// 初始化度数组D为0
for (int i = 0; i < n; i++) {
D[i] = 0;
}
// 遍历顶点表,计算各顶点的度
for (int i = 0; i < n; i++) {
ArcNode* p = G[i].firstOutArc;
while (p != NULL) {
D[i]++; // 出度加1
D[p->head]++; // 入度加1
p = p->nextOutArc;
}
}
}
int main() {
int n; // 顶点个数
printf("请输入图中顶点的个数:");
scanf("%d", &n);
// 创建顶点表
VertexNode* G = (VertexNode*)malloc(n * sizeof(VertexNode));
for (int i = 0; i < n; i++) {
G[i].indegree = 0;
G[i].outdegree = 0;
G[i].firstInArc = NULL;
G[i].firstOutArc = NULL;
}
// 创建弧并构建有向图
int m; // 弧的个数
printf("请输入有向图的弧的个数:");
scanf("%d", &m);
printf("请输入每条弧的起点和终点(以空格分隔):\n");
for (int i = 0; i < m; i++) {
int tail, head;
scanf("%d %d", &tail, &head);
// 创建新的弧节点
ArcNode* arcNode = (ArcNode*)malloc(sizeof(ArcNode));
arcNode->tail = tail;
arcNode->head = head;
arcNode->nextInArc = NULL;
arcNode->nextOutArc = NULL;
// 更新顶点表的指针
if (G[tail].firstOutArc == NULL) {
// 如果该顶点的出弧为空,则直接指向新创建的弧节点
G[tail].firstOutArc = arcNode;
} else {
// 如果该顶点的出弧不为空,则将新创建的弧节点插入到链表头部
arcNode->nextOutArc = G[tail].firstOutArc;
G[tail].firstOutArc = arcNode;
}
if (G[head].firstInArc == NULL) {
// 如果该顶点的入弧为空,则直接指向新创建的弧节点
G[head].firstInArc = arcNode;
} else {
// 如果该顶点的入弧不为空,则将新创建的弧节点插入到链表头部
arcNode->nextInArc = G[head].firstInArc;
G[head].firstInArc = arcNode;
}
}
// 计算各顶点度
int* D = (int*)malloc(n * sizeof(int));
COUNT_D(G, D, n);
// 输出各顶点的度
printf("各顶点的度为:\n");
for (int i = 0; i < n; i++) {
printf("顶点 %d 的度为 %d\n", i, D[i]);
}
// 释放内存
for (int i = 0; i < n; i++) {
ArcNode* p = G[i].firstOutArc;
while (p != NULL) {
ArcNode* temp = p;
p = p->nextOutArc;
free(temp);
}
}
free(G);
free(D);
return 0;
}
```
这段代码可以创建有向图的十字链表,并计算各顶点的度。你可以根据需要进行测试和修改。
阅读全文