邻接表如何存储数据c语言
时间: 2023-12-25 18:28:23 浏览: 27
邻接表是一种常用的图的存储结构,它通过链表的方式存储每个顶点的邻接点信息。下面是使用C语言实现邻接表的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 邻接表中的边结构体
typedef struct EdgeNode {
int adjvex; // 邻接点在顶点数组中的下标
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
// 邻接表中的顶点结构体
typedef struct VertexNode {
int data; // 顶点的数据
EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode;
// 邻接表结构体
typedef struct {
VertexNode adjList[MaxSize]; // 顶点数组
int numVertexes, numEdges; // 顶点数和边数
} GraphAdjList;
// 创建邻接表
void CreateALGraph(GraphAdjList *G) {
int i, j, k;
EdgeNode *e;
printf("请输入顶点数和边数:");
scanf("%d %d", &G->numVertexes, &G->numEdges);
// 读入顶点信息,存入顶点数组中
for (i = 0; i < G->numVertexes; i++) {
printf("请输入第%d个顶点的值:", i + 1);
scanf("%d", &G->adjList[i].data);
G->adjList[i].firstedge = NULL; // 初始化邻接表为空表
}
// 读入边信息,建立邻接表
for (k = 0; k < G->numEdges; k++) {
printf("请输入边(vi, vj)上的顶点序号:");
scanf("%d %d", &i, &j);
// 在邻接表中插入边<vj, vi>
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = j - 1;
e->next = G->adjList[i - 1].firstedge;
G->adjList[i - 1].firstedge = e;
// 在邻接表中插入边<vi, vj>
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = i - 1;
e->next = G->adjList[j - 1].firstedge;
G->adjList[j - 1].firstedge = e;
}
}
// 输出邻接表
void PrintALGraph(GraphAdjList G) {
int i;
EdgeNode *p;
printf("邻接表:\n");
for (i = 0; i < G.numVertexes; i++) {
printf("%d: ", G.adjList[i].data);
p = G.adjList[i].firstedge;
while (p != NULL) {
printf("%d ", G.adjList[p->adjvex].data);
p = p->next;
}
printf("\n");
}
}
int main() {
GraphAdjList G;
CreateALGraph(&G);
PrintALGraph(G);
return 0;
}
```