邻接表的存储结构C语言
时间: 2023-12-12 11:34:48 浏览: 47
邻接表是一种图的存储结构,它通过链表的方式存储每个顶点的邻接点,相比于邻接矩阵,邻接表更适合存储稀疏图。下面是邻接表的存储结构C语言实现:
```c
// 边表结点
typedef struct EdgeNode {
int adjvex; // 邻接点在顶点数组中的下标
int weight; // 权值
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
// 顶点表结点
typedef struct VertexNode {
int data; // 顶点数据
EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode, AdjList[MAXVEX];
// 邻接表
typedef struct {
AdjList adjList; // 顶点数组
int numVertexes, numEdges; // 顶点数和边数
} GraphAdjList;
```
其中,`EdgeNode`表示边表结点,`VertexNode`表示顶点表结点,`AdjList`是一个顶点数组,`GraphAdjList`表示邻接表。在邻接表中,每个顶点的邻接点通过链表的方式连接起来,`firstedge`指向第一个邻接点的指针,如果没有邻接点,则为`NULL`。`numVertexes`表示顶点数,`numEdges`表示边数。
下面是一个简单的邻接表创建和遍历的例子:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100 // 最大顶点数
// 边表结点
typedef struct EdgeNode {
int adjvex; // 邻接点在顶点数组中的下标
int weight; // 权值
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
// 顶点表结点
typedef struct VertexNode {
int data; // 顶点数据
EdgeNode *firstedge; // 指向第一个邻接点的指针
} VertexNode, AdjList[MAXVEX];
// 邻接表
typedef struct {
AdjList adjList; // 顶点数组
int numVertexes, numEdges; // 顶点数和边数
} GraphAdjList;
// 创建邻接表
int Create_ALGraph(GraphAdjList *G) {
int i, j, k, w;
EdgeNode *e;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->numVertexes, &G->numEdges);
printf("请输入顶点信息:\n");
for (i = 0; i < G->numVertexes; i++) {
scanf("%d", &G->adjList[i].data);
G->adjList[i].firstedge = NULL;
}
printf("请输入边信息:\n");
for (k = 0; k < G->numEdges; k++) {
printf("请输入边(vi, vj)的下标i、下标j和权值w:");
scanf("%d%d%d", &i, &j, &w);
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = j;
e->weight = w;
e->next = G->adjList[i].firstedge;
G->adjList[i].firstedge = e;
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = i;
e->weight = w;
e->next = G->adjList[j].firstedge;
G->adjList[j].firstedge = e;
}
return 0;
}
// 输出邻接表
void Output_ALGraph(GraphAdjList G) {
int i;
EdgeNode *e;
printf("邻接表:\n");
for (i = 0; i < G.numVertexes; i++) {
printf("%d: ", G.adjList[i].data);
e = G.adjList[i].firstedge;
while (e) {
printf("%d(%d) ", G.adjList[e->adjvex].data, e->weight);
e = e->next;
}
printf("\n");
}
}
int main() {
GraphAdjList G;
Create_ALGraph(&G);
Output_ALGraph(G);
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)