数据结构邻接表C语言实现
时间: 2023-07-21 22:06:51 浏览: 116
所有基础数据结构和算法的纯C语言实现,如各自排序、链表、栈、队列、各种树....
邻接表是一种常用的表示图的数据结构。在C语言中,可以使用结构体和链表来实现邻接表。
首先,我们定义一个结构体来表示图的顶点:
```c
typedef struct Vertex {
int data; // 顶点的数据
struct Edge* next; // 指向第一条与该顶点相连的边
} Vertex;
```
然后,我们定义一个结构体来表示图的边:
```c
typedef struct Edge {
int dest; // 边的目标顶点
struct Edge* next; // 指向下一条与同一个起始顶点相连的边
} Edge;
```
接下来,我们可以使用一个数组来存储图的所有顶点,每个顶点都是一个链表的头节点:
```c
#define MAX_VERTICES 100
Vertex vertices[MAX_VERTICES];
int numVertices = 0;
```
接下来,我们可以实现一些操作来增加和访问图的顶点和边。以下是一些常见的操作:
1. 添加顶点:
```c
void addVertex(int data) {
Vertex newVertex;
newVertex.data = data;
newVertex.next = NULL;
vertices[numVertices++] = newVertex;
}
```
2. 添加边:
```c
void addEdge(int src, int dest) {
Edge* newEdge = (Edge*)malloc(sizeof(Edge));
newEdge->dest = dest;
newEdge->next = vertices[src].next;
vertices[src].next = newEdge;
}
```
3. 打印邻接表:
```c
void printGraph() {
for (int i = 0; i < numVertices; i++) {
printf("Vertex %d:", vertices[i].data);
Edge* currEdge = vertices[i].next;
while (currEdge != NULL) {
printf(" -> %d", currEdge->dest);
currEdge = currEdge->next;
}
printf("\n");
}
}
```
这样,我们就可以使用上述代码来实现邻接表的数据结构和一些操作。希望对你有帮助!
阅读全文