用C语言编写在有向图的邻接表的基础上计算各顶点的度,并输出的代码
时间: 2024-02-13 19:02:26 浏览: 24
好的,下面是C语言代码,可以在有向图的邻接表的基础上计算各顶点的度,并输出:
```c
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 100 // 定义最大顶点数
typedef struct ArcNode // 定义邻接表的弧结构体
{
int adjvex; // 邻接顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
}ArcNode;
typedef struct VNode // 定义邻接表的顶点结构体
{
int data; // 顶点的数据
ArcNode *firstarc; // 指向第一条弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct // 定义邻接表结构体
{
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 顶点数和弧数
}ALGraph;
void CreateALGraph(ALGraph *G) // 创建邻接表
{
int i, j, k;
ArcNode *p;
printf("请输入顶点数和弧数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入%d个顶点的数据:", G->vexnum);
for(i = 0; i < G->vexnum; i++) // 输入各顶点的数据
{
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL; // 将指向第一条弧的指针初始化为空
}
printf("请输入%d条弧的起点和终点:\n", G->arcnum);
for(k = 0; k < G->arcnum; k++) // 建立邻接表
{
scanf("%d%d", &i, &j);
p = (ArcNode*)malloc(sizeof(ArcNode)); // 生成一个新的弧结点
p->adjvex = j; // 存储邻接顶点的位置
p->nextarc = G->vertices[i].firstarc; // 将p结点插入到顶点i的邻接表头部
G->vertices[i].firstarc = p;
}
}
void PrintDegree(ALGraph *G) // 计算各顶点的度并输出
{
int i, count;
ArcNode *p;
printf("各顶点的度为:\n");
for(i = 0; i < G->vexnum; i++)
{
count = 0;
p = G->vertices[i].firstarc; // 从顶点i的第一条弧开始遍历
while(p != NULL) // 遍历顶点i的所有邻接顶点
{
count++; // 统计顶点i的度
p = p->nextarc;
}
printf("%d: %d\n", G->vertices[i].data, count); // 输出顶点i的度
}
}
int main()
{
ALGraph G;
CreateALGraph(&G);
PrintDegree(&G);
return 0;
}
```
以上代码可以读入有向图的邻接表,计算各顶点的度并输出。