帮我用C语言邻接表写一个有向无权图的增删改查的代码
时间: 2023-12-10 22:37:57 浏览: 34
好的,下面是一个简单的邻接表实现的有向无权图的增删改查的代码,仅供参考:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表中的节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 定义邻接表结构体
typedef struct Graph {
int V; // 图中节点数
Node** adjList; // 存储邻接表的指针数组
} Graph;
// 创建节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 创建图
Graph* createGraph(int V) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->V = V;
graph->adjList = (Node**)malloc(V * sizeof(Node*));
for (int i = 0; i < V; i++) {
graph->adjList[i] = NULL;
}
return graph;
}
// 添加边
void addEdge(Graph* graph, int src, int dest) {
Node* newNode = createNode(dest);
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;
}
// 删除边
void removeEdge(Graph* graph, int src, int dest) {
Node* curr = graph->adjList[src];
Node* prev = NULL;
while (curr != NULL && curr->data != dest) {
prev = curr;
curr = curr->next;
}
if (curr == NULL) {
printf("Edge not found\n");
return;
}
if (prev == NULL) {
graph->adjList[src] = curr->next;
} else {
prev->next = curr->next;
}
free(curr);
}
// 修改边
void modifyEdge(Graph* graph, int src, int oldDest, int newDest) {
removeEdge(graph, src, oldDest);
addEdge(graph, src, newDest);
}
// 查询边
int hasEdge(Graph* graph, int src, int dest) {
Node* curr = graph->adjList[src];
while (curr != NULL) {
if (curr->data == dest) {
return 1;
}
curr = curr->next;
}
return 0;
}
// 打印图
void printGraph(Graph* graph) {
for (int i = 0; i < graph->V; i++) {
Node* curr = graph->adjList[i];
printf("Vertex %d: ", i);
while (curr != NULL) {
printf("%d -> ", curr->data);
curr = curr->next;
}
printf("NULL\n");
}
}
// 测试
int main() {
int V = 5;
Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printf("Original Graph:\n");
printGraph(graph);
removeEdge(graph, 1, 3);
printf("Graph after removing edge (1, 3):\n");
printGraph(graph);
modifyEdge(graph, 1, 2, 0);
printf("Graph after modifying edge (1, 2) to (1, 0):\n");
printGraph(graph);
printf("Query result for edge (3, 4): %d\n", hasEdge(graph, 3, 4));
printf("Query result for edge (4, 3): %d\n", hasEdge(graph, 4, 3));
return 0;
}
```
这里使用了邻接表来存储图,并实现了添加边、删除边、修改边和查询边的功能。在测试中,我们首先创建了一个有向无权图,然后进行了一些操作并打印了结果。