用C语言编写无向图的邻接矩阵存储向邻接表存储转换并打印
时间: 2024-03-01 18:51:00 浏览: 81
有向图的邻接矩阵
5星 · 资源好评率100%
好的,下面是用 C 语言实现将无向图的邻接矩阵存储方式转换为邻接表存储方式,并打印出转换后的邻接表的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表中的边结构体
typedef struct Edge {
int dest; // 目标顶点
struct Edge* next; // 指向下一个边的指针
} Edge;
// 定义邻接表中的顶点结构体
typedef struct Vertex {
Edge* head; // 指向第一条边的指针
} Vertex;
// 将邻接矩阵转换为邻接表
void adjMatrixToAdjList(int** adjMatrix, int n, Vertex* adjList) {
int i, j;
for (i = 0; i < n; i++) {
// 初始化每个顶点的边链表
adjList[i].head = NULL;
for (j = 0; j < n; j++) {
if (adjMatrix[i][j] != 0) {
// 如果邻接矩阵中 (i, j) 位置的值不为 0,则说明顶点 i 和 j 之间有一条边
// 创建一个新的边结构体,连接到目标顶点 j
Edge* newEdge = (Edge*)malloc(sizeof(Edge));
newEdge->dest = j;
newEdge->next = NULL;
// 将新建的边插入到当前顶点 i 对应的边链表的头部
newEdge->next = adjList[i].head;
adjList[i].head = newEdge;
}
}
}
}
// 打印邻接表
void printAdjList(Vertex* adjList, int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d: ", i);
Edge* cur = adjList[i].head;
while (cur != NULL) {
printf("%d ", cur->dest);
cur = cur->next;
}
printf("\n");
}
}
int main() {
// 定义一个 5 个顶点的无向图的邻接矩阵
int adjMatrix[5][5] = {
{0, 1, 1, 0, 1},
{1, 0, 1, 1, 0},
{1, 1, 0, 1, 0},
{0, 1, 1, 0, 1},
{1, 0, 0, 1, 0}
};
// 定义一个数组来存储邻接表
Vertex adjList[5];
// 将邻接矩阵转换为邻接表
adjMatrixToAdjList((int**)adjMatrix, 5, adjList);
// 打印邻接表
printAdjList(adjList, 5);
return 0;
}
```
这段代码中,我们首先定义了邻接表中的边和顶点结构体。在 `adjMatrixToAdjList` 函数中,我们遍历邻接矩阵中的每个元素,如果发现当前位置的值不为 0,则说明该位置对应的两个顶点之间有一条边。我们创建一个新的边结构体,将目标顶点的编号赋值给 `dest` 字段,并将新建的边插入到当前顶点对应的边链表的头部。最后,通过调用 `printAdjList` 函数,我们可以打印出转换后的邻接表。
希望这个回答能够帮到你!
阅读全文