用c语言编写一段代码,完成具有以下要求的数据结构代码(编程序建立有向图的邻接表,求指定第几个顶点的入度)
时间: 2024-12-30 22:37:25 浏览: 17
在C语言中,我们可以使用数组和链表来实现邻接表数据结构来表示有向图。这里我们创建一个结构体`Vertex`表示每个顶点及其连接的边,另一个结构体`AdjacencyList`用于存储所有顶点以及它们的邻接信息。下面是一个简单的例子:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义顶点结构体
typedef struct Vertex {
int vertex_id;
int degree; // 初始值设为0,代表入度
struct AdjListNode* first_edge; // 链表头指针
} Vertex;
// 邻接链表节点结构体
typedef struct AdjListNode {
int destination; // 目标顶点
struct AdjListNode* next; // 指向下一个邻接节点
} AdjListNode;
// 创建新顶点并初始化入度
Vertex* create_vertex(int id) {
Vertex* new_vertex = (Vertex*)malloc(sizeof(Vertex));
new_vertex->vertex_id = id;
new_vertex->degree = 0;
new_vertex->first_edge = NULL;
return new_vertex;
}
// 初始化邻接表
void init_adj_list(AdjListNode** adj_lists, int num_vertices) {
for (int i = 0; i < num_vertices; i++) {
adj_lists[i] = NULL;
}
}
// 添加边到邻接表中
void add_edge_to_vertex(Vertex* source, int destination) {
AdjListNode* new_edge = (AdjListNode*)malloc(sizeof(AdjListNode));
new_edge->destination = destination;
new_edge->next = source->first_edge;
source->first_edge = new_edge;
source->degree++; // 更新源顶点的入度
}
// 计算给定顶点的入度
int get_in_degree(Vertex* vertex) {
return vertex->degree;
}
int main() {
int num_vertices, src_vertex, dest_vertex;
printf("Enter number of vertices: ");
scanf("%d", &num_vertices);
AdjListNode** adj_lists = (AdjListNode**)malloc(num_vertices * sizeof(AdjListNode*));
init_adj_list(adj_lists, num_vertices);
printf("Enter source and destination vertices for each edge:\n");
for (int i = 0; i < num_vertices - 1; i++) {
scanf("Source %d Destination %d", &src_vertex, &dest_vertex);
Vertex* vertex = find_vertex(adj_lists, src_vertex); // 根据需要添加查找函数
if (!vertex) {
vertex = create_vertex(src_vertex);
adj_lists[src_vertex] = vertex;
}
add_edge_to_vertex(vertex, dest_vertex);
}
int query_vertex;
printf("Enter a vertex to check its in-degree: ");
scanf("%d", &query_vertex);
Vertex* query = find_vertex(adj_lists, query_vertex);
if (query) {
printf("The in-degree of vertex %d is: %d\n", query_vertex, get_in_degree(query));
} else {
printf("Vertex not found.\n");
}
// 清理内存
for (int i = 0; i < num_vertices; i++) {
free(adj_lists[i]);
}
free(adj_lists);
return 0;
}
```
在这个示例中,我们首先创建了`Vertex`和`AdjListNode`结构,然后实现了创建、初始化邻接表、添加边和获取入度的功能。注意,在实际应用中,可能还需要实现`find_vertex`函数来搜索顶点,以便在添加边时避免重复。
阅读全文