使用c语言解决以下问题需要是一个有完整主函数的代码(1) 键盘输入数据,建立一个有向图的邻接表。 (2) 输出该邻接表。 (3) 在有向图的邻接表的基础上计算各顶点的度,并输出。
时间: 2024-03-18 18:42:02 浏览: 68
以下是一个实现题目要求的完整C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表结构体
typedef struct AdjListNode {
int dest; // 目标顶点
struct AdjListNode* next; // 指向下一个邻接点的指针
} AdjListNode;
typedef struct AdjList {
AdjListNode* head; // 指向邻接点链表的头指针
} AdjList;
typedef struct Graph {
int V; // 顶点数
AdjList* array; // 邻接表数组
} Graph;
// 初始化邻接表
AdjListNode* newAdjListNode(int dest) {
AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 创建有向图的邻接表
Graph* createGraph(int V) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = V;
graph->array = (AdjList*)malloc(V * sizeof(AdjList));
for (int i = 0; i < V; ++i) {
graph->array[i].head = NULL;
}
return graph;
}
// 添加边到邻接表中
void addEdge(Graph* graph, int src, int dest) {
AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}
// 打印邻接表
void printGraph(Graph* graph) {
for (int i = 0; i < graph->V; ++i) {
AdjListNode* pCrawl = graph->array[i].head;
printf("\n 顶点 %d 的邻接点有: ", i);
while (pCrawl) {
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
// 计算各顶点的出度和入度
void calculateDegree(Graph* graph) {
int inDegree[graph->V], outDegree[graph->V];
for (int i = 0; i < graph->V; ++i) {
inDegree[i] = 0;
outDegree[i] = 0;
}
for (int i = 0; i < graph->V; ++i) {
AdjListNode* pCrawl = graph->array[i].head;
while (pCrawl) {
++outDegree[i];
++inDegree[pCrawl->dest];
pCrawl = pCrawl->next;
}
}
printf("\n顶点 入度 出度\n");
for (int i = 0; i < graph->V; ++i) {
printf(" %d %d %d\n", i, inDegree[i], outDegree[i]);
}
}
int main() {
int V, E, src, dest;
printf("请输入顶点数和边数:");
scanf("%d%d", &V, &E);
// 创建邻接表
Graph* graph = createGraph(V);
// 添加边
printf("请输入边的起点和终点:\n");
for (int i = 0; i < E; ++i) {
scanf("%d%d", &src, &dest);
addEdge(graph, src, dest);
}
// 打印邻接表
printf("\n该有向图的邻接表如下:\n");
printGraph(graph);
// 计算顶点度
calculateDegree(graph);
return 0;
}
```
这个程序首先根据用户输入的顶点数和边数创建了邻接表,然后遍历所有边,将边添加到邻接表中。接着打印邻接表和计算各顶点的度。
阅读全文