用c语言创建图的邻接矩阵和邻接表
时间: 2024-05-10 12:17:11 浏览: 15
邻接矩阵和邻接表是表示图的两种常用方式,下面分别介绍如何用C语言创建它们。
1. 邻接矩阵
邻接矩阵是一个二维数组,用于表示图中各节点之间的连通关系。其中数组的每个元素都表示两个节点之间的边的权值,如果两个节点之间没有边相连,则该元素的值为0。下面是用C语言创建邻接矩阵的示例代码:
```c
#define MAX_VERTEX_NUM 100 // 图中顶点的最大数量
// 邻接矩阵结构体
typedef struct {
int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 二维数组,存储图的邻接矩阵
int vertex_num; // 图中顶点的数量
} AdjacencyMatrix;
// 创建邻接矩阵
void create_adjacency_matrix(AdjacencyMatrix *graph) {
int i, j;
printf("请输入图中顶点的数量:");
scanf("%d", &(graph->vertex_num));
printf("请输入图的邻接矩阵:\n");
for (i = 0; i < graph->vertex_num; i++) {
for (j = 0; j < graph->vertex_num; j++) {
scanf("%d", &(graph->matrix[i][j]));
}
}
}
```
2. 邻接表
邻接表是一种链式存储结构,用于表示图中各节点之间的连通关系。其中每个节点都对应一个链表,链表中存储与该节点相邻的其他节点。下面是用C语言创建邻接表的示例代码:
```c
#define MAX_VERTEX_NUM 100 // 图中顶点的最大数量
// 邻接表结点结构体
typedef struct ArcNode {
int adjvex; // 该节点所对应的顶点在图中的下标
struct ArcNode *nextarc; // 指向下一个邻接表结点的指针
int weight; // 边的权值
} ArcNode;
// 邻接表头结点结构体
typedef struct VNode {
char data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接表结点的指针
} VNode;
// 邻接表结构体
typedef struct {
VNode adjlist[MAX_VERTEX_NUM]; // 邻接表头结点数组
int vertex_num; // 图中顶点的数量
} AdjacencyList;
// 创建邻接表
void create_adjacency_list(AdjacencyList *graph) {
int i, j, k;
ArcNode *arcnode;
printf("请输入图中顶点的数量:");
scanf("%d", &(graph->vertex_num));
printf("请输入图的邻接表:\n");
for (i = 0; i < graph->vertex_num; i++) {
printf("请输入第%d个顶点的数据:", i + 1);
scanf("%s", &(graph->adjlist[i].data));
graph->adjlist[i].firstarc = NULL; // 初始化链表为空
printf("请输入第%d个顶点的邻接点数量:", i + 1);
scanf("%d", &k);
for (j = 0; j < k; j++) {
arcnode = (ArcNode *)malloc(sizeof(ArcNode)); // 创建一个新的邻接表结点
printf("请输入第%d个顶点的第%d个邻接点的下标和边的权值:", i + 1, j + 1);
scanf("%d%d", &(arcnode->adjvex), &(arcnode->weight));
arcnode->nextarc = graph->adjlist[i].firstarc; // 将新的邻接表结点插入到链表头部
graph->adjlist[i].firstarc = arcnode;
}
}
}
```