用c语言创建一个无向图,选用任一数据存储结构,并求出任意一个项的度,要求是可以运行的代码
时间: 2024-02-18 07:59:22 浏览: 79
好的,这里给您提供一个使用邻接表来存储无向图,并求出任意一个顶点的度数的示例代码。请参考下面的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50
// 定义邻接表中的节点结构体
typedef struct node {
int vertex;
struct node *next;
} Node;
// 定义邻接表结构体
typedef struct {
Node *head;
} AdjList[MAX_VERTICES];
// 定义图结构体
typedef struct {
AdjList adj_list;
int num_vertices;
} Graph;
// 初始化图
void init_graph(Graph *g, int num_vertices) {
g->num_vertices = num_vertices;
for (int i = 0; i < num_vertices; i++) {
g->adj_list[i].head = NULL;
}
}
// 添加边
void add_edge(Graph *g, int v1, int v2) {
// 添加顶点v2到顶点v1的邻接表
Node *node = (Node*) malloc(sizeof(Node));
node->vertex = v2;
node->next = g->adj_list[v1].head;
g->adj_list[v1].head = node;
// 添加顶点v1到顶点v2的邻接表
node = (Node*) malloc(sizeof(Node));
node->vertex = v1;
node->next = g->adj_list[v2].head;
g->adj_list[v2].head = node;
}
// 求顶点的度数
int get_degree(Graph *g, int v) {
int degree = 0;
Node *node = g->adj_list[v].head;
while (node != NULL) {
degree++;
node = node->next;
}
return degree;
}
int main() {
Graph g;
init_graph(&g, 5);
add_edge(&g, 0, 1);
add_edge(&g, 0, 2);
add_edge(&g, 1, 2);
add_edge(&g, 1, 3);
add_edge(&g, 2, 4);
add_edge(&g, 3, 4);
int degree = get_degree(&g, 2);
printf("顶点2的度数为:%d\n", degree);
return 0;
}
```
上面的代码中,我们定义了一个邻接表结构体 `AdjList`,它是一个包含了所有顶点的链表数组,每个链表表示一个顶点的邻居节点。使用 `init_graph` 函数来初始化图,`add_edge` 函数用来添加边,`get_degree` 函数用来返回某个顶点的度数。在 `main` 函数中,我们创建了一个例子图,然后求出了顶点2的度数,输出结果为2。
注意,为了避免内存泄漏,我们需要在 `add_edge` 函数中使用动态内存分配来创建新的节点,然后在程序结束前释放掉这些节点的内存空间。
阅读全文