从、(1) 键盘输入数据,建立一个有向图的邻接表。 (2) 输出该邻接表。 (3) 在有向图的邻接表的基础上计算各顶点的度,并输出。
时间: 2024-03-03 17:51:40 浏览: 26
以下是一个简单的实现,通过邻接表表示有向图,并计算各顶点的出度和入度。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 邻接表中的边节点
typedef struct EdgeNode {
int dest; // 目标顶点
struct EdgeNode* next; // 下一个边节点
} EdgeNode;
// 邻接表中的顶点节点
typedef struct VertexNode {
int inDegree; // 入度
int outDegree; // 出度
EdgeNode* firstEdge; // 第一个边节点
} VertexNode;
// 邻接表
typedef struct AdjList {
VertexNode vertices[MAX_VERTICES]; // 顶点数组
int numVertices; // 顶点个数
} AdjList;
// 初始化邻接表
void initAdjList(AdjList* adjList) {
adjList->numVertices = 0;
for (int i = 0; i < MAX_VERTICES; i++) {
adjList->vertices[i].firstEdge = NULL;
adjList->vertices[i].inDegree = 0;
adjList->vertices[i].outDegree = 0;
}
}
// 添加一条边
void addEdge(AdjList* adjList, int src, int dest) {
EdgeNode* edgeNode = (EdgeNode*) malloc(sizeof(EdgeNode));
edgeNode->dest = dest;
edgeNode->next = adjList->vertices[src].firstEdge;
adjList->vertices[src].firstEdge = edgeNode;
adjList->vertices[src].outDegree++;
adjList->vertices[dest].inDegree++;
}
// 输出邻接表
void printAdjList(AdjList* adjList) {
printf("邻接表:\n");
for (int i = 0; i < adjList->numVertices; i++) {
printf("%d:", i);
EdgeNode* edgeNode = adjList->vertices[i].firstEdge;
while (edgeNode != NULL) {
printf(" -> %d", edgeNode->dest);
edgeNode = edgeNode->next;
}
printf("\n");
}
}
// 计算各顶点的度并输出
void printDegrees(AdjList* adjList) {
printf("各顶点的出度和入度:\n");
for (int i = 0; i < adjList->numVertices; i++) {
printf("%d:入度 %d,出度 %d\n", i, adjList->vertices[i].inDegree, adjList->vertices[i].outDegree);
}
}
int main() {
AdjList adjList;
initAdjList(&adjList);
// 从键盘输入并建立有向图的邻接表
printf("请输入顶点个数和边数:");
int numVertices, numEdges;
scanf("%d%d", &numVertices, &numEdges);
adjList.numVertices = numVertices;
printf("请输入每条边的起点和终点:\n");
for (int i = 0; i < numEdges; i++) {
int src, dest;
scanf("%d%d", &src, &dest);
addEdge(&adjList, src, dest);
}
// 输出邻接表
printAdjList(&adjList);
// 计算各顶点的度并输出
printDegrees(&adjList);
return 0;
}
```
你可以根据需要修改顶点数和边数,然后输入每条边的起点和终点。最后程序会输出邻接表和各顶点的度。