用c语言生成一个邻接表的结构体
时间: 2023-04-03 08:04:57 浏览: 71
好的,我可以回答这个问题。邻接表是一种表示图的数据结构,可以用来存储图中的节点和边。在 C 语言中,可以通过结构体来定义邻接表。一个基本的邻接表结构体包含两个成员:一个指向节点的指针数组和一个指向边的指针数组。节点指针数组中的每个元素指向一个节点,边指针数组中的每个元素指向一个边。节点和边的定义可以根据具体的需求来设计。
相关问题
用C语言编程实现邻接表生成逆邻接表。
好的,以下是实现邻接表生成逆邻接表的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 CreateGraph(ALGraph *G) {
int i, j, k;
ArcNode *p;
printf("请输入顶点数和边数:\n");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入顶点信息:\n");
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
printf("请输入边的信息(起点 终点):\n");
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;
G->vertices[i].firstarc = p;
}
}
// 生成逆邻接表
void Inverse(ALGraph *G, ALGraph *GR) {
int i;
ArcNode *p;
GR->vexnum = G->vexnum;
GR->arcnum = G->arcnum;
for (i = 0; i < G->vexnum; i++) {
GR->vertices[i].data = G->vertices[i].data;
GR->vertices[i].firstarc = NULL;
}
for (i = 0; i < G->vexnum; i++) {
p = G->vertices[i].firstarc;
while (p != NULL) {
ArcNode *q = (ArcNode *)malloc(sizeof(ArcNode));
q->adjvex = i;
q->nextarc = GR->vertices[p->adjvex].firstarc;
GR->vertices[p->adjvex].firstarc = q;
p = p->nextarc;
}
}
}
// 主函数测试逆邻接表生成
int main() {
ALGraph G, GR;
CreateGraph(&G);
Inverse(&G, &GR);
printf("邻接表:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("%d -> ", G.vertices[i].data);
ArcNode *p = G.vertices[i].firstarc;
while (p != NULL) {
printf("%d -> ", G.vertices[p->adjvex].data);
p = p->nextarc;
}
printf("NULL\n");
}
printf("逆邻接表:\n");
for (int i = 0; i < GR.vexnum; i++) {
printf("%d -> ", GR.vertices[i].data);
ArcNode *p = GR.vertices[i].firstarc;
while (p != NULL) {
printf("%d -> ", GR.vertices[p->adjvex].data);
p = p->nextarc;
}
printf("NULL\n");
}
return 0;
}
```
在这个程序中,我们首先定义了邻接表的结构体,其中`VNode`表示一个顶点,`ArcNode`表示一个邻接点,`AdjList`是邻接表的类型,用于存储所有顶点的信息和它们的邻接点信息。然后,我们实现了两个函数来生成邻接表和逆邻接表。最后,在主函数中,我们使用`CreateGraph`函数生成邻接表,并使用`Inverse`函数生成逆邻接表,然后分别输出它们的信息。
注意,这里的逆邻接表是由原来的邻接表生成的,因此逆邻接表的顶点信息和边数与原来的邻接表相同。不同之处在于,对于每个顶点,逆邻接表中存储的是指向该顶点的所有边,而不是该顶点指向的所有边。
邻接表生成逆邻接表用C语言实现
下面是一个使用C语言实现邻接表生成逆邻接表的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE_NUM 100 // 最大节点数
// 邻接表节点结构体
typedef struct AdjListNode {
int dest; // 邻接节点编号
struct AdjListNode* next; // 指向下一个邻接节点的指针
} AdjListNode;
// 邻接表结构体
typedef struct AdjList {
AdjListNode* head; // 邻接表头指针
} AdjList;
// 图结构体
typedef struct Graph {
int num_vertices; // 节点数
AdjList* adj_lists; // 邻接表数组
} Graph;
// 创建邻接节点
AdjListNode* createAdjListNode(int dest) {
AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 创建图
Graph* createGraph(int num_vertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->num_vertices = num_vertices;
graph->adj_lists = (AdjList*)malloc(num_vertices * sizeof(AdjList));
for (int i = 0; i < num_vertices; i++) {
graph->adj_lists[i].head = NULL;
}
return graph;
}
// 添加边
void addEdge(Graph* graph, int src, int dest) {
AdjListNode* newNode = createAdjListNode(dest);
newNode->next = graph->adj_lists[src].head;
graph->adj_lists[src].head = newNode;
}
// 生成逆邻接表
Graph* getReverseGraph(Graph* graph) {
Graph* reverseGraph = createGraph(graph->num_vertices);
for (int i = 0; i < graph->num_vertices; i++) {
AdjListNode* curr = graph->adj_lists[i].head;
while (curr != NULL) {
addEdge(reverseGraph, curr->dest, i);
curr = curr->next;
}
}
return reverseGraph;
}
// 打印邻接表
void printGraph(Graph* graph) {
for (int i = 0; i < graph->num_vertices; i++) {
AdjListNode* curr = graph->adj_lists[i].head;
printf("节点 %d 的邻接节点:", i);
while (curr != NULL) {
printf("%d ", curr->dest);
curr = curr->next;
}
printf("\n");
}
}
int main() {
Graph* graph = createGraph(5);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
Graph* reverseGraph = getReverseGraph(graph);
printf("逆邻接表:\n");
printGraph(reverseGraph);
return 0;
}
```
在上面的示例代码中,我们首先定义了邻接表节点结构体和邻接表结构体,并使用它们创建了一个图结构体。接着,我们实现了创建邻接节点、创建图、添加边、打印邻接表等相关函数,其中 `addEdge` 函数用于向图中添加边,`getReverseGraph` 函数用于生成逆邻接表。
最后,在 `main` 函数中,我们创建了一个包含 5 个节点的图,并向其中添加边。然后,我们打印出图的邻接表,并生成其对应的逆邻接表并打印出来。