数据结构-图-领接表存储

一、了解图的领接表存储

1、定义与结构

  1. 定义：邻接表是图的一种链式存储结构，它通过链表将每个顶点与其相邻的顶点连接起来。

  2. 结构：

    • 顶点表：通常使用一个数组来存储图的顶点信息，数组的每个元素对应一个顶点，元素的内容可以是顶点的标识符或值，以及一个指向该顶点邻接链表的指针。
    • 邻接链表：对于图中的每个顶点，创建一个链表，链表中存储了与该顶点相邻的其他顶点。链表中的每个节点通常包含两个字段：邻接点域（指示与当前顶点相邻的顶点在图中的位置）和链域（指示下一条邻接边的节点）。

2、性质与特点

  1. 节省空间：对于稀疏图，邻接表能够节省大量的内存空间，因为它只存储实际存在的边，而不需要像邻接矩阵那样为所有可能的边分配空间。
  2. 灵活性强：邻接表易于增加和删除顶点及其邻接边，因为链表结构允许动态调整。
  3. 查找效率高：在查找与某个顶点相邻的所有顶点时，只需要遍历该顶点的邻接链表，而不需要遍历整个矩阵，从而提高了查找效率。

3、构建与存储

  1. 构建方法：

    • 确定图的顶点数量和边的关系。
    • 创建一个顶点表数组，数组的每个元素对应一个顶点，并初始化其邻接链表为空。
    • 根据图的边关系，将每条边对应的两个顶点添加到彼此的邻接链表中。

  2. 存储：

    • 顶点表数组通常存储在内存中，以便快速访问。
    • 邻接链表使用动态内存分配来存储，以适应不同顶点的邻接边数量。

4、应用与限制

  1. 应用：

    • 社交网络中的用户关系可以用无向图表示，每个用户是一个顶点，好友关系是一条边。使用邻接表存储后，可以方便地查找某个用户的好友列表或共同好友等信息。
    • 在图的遍历算法（如广度优先搜索BFS和深度优先搜索DFS）中，邻接表提供了一种高效的访问相邻顶点的方式。
    • 邻接表也适用于求解最短路径、网络流问题等图论算法。

  2. 限制：

    • 在查找特定的边时，可能需要遍历整个邻接表，相对较慢，特别是对于稠密图。
    • 对于有向图，如果需要同时获取顶点的入度和出度，则需要分别维护邻接表和逆邻接表，这会增加存储空间的开销。

5、示例

假设有一个有向图G，其顶点集合为V={V1, V2, V3, V4}，边集合为E={(V1, V2), (V1, V4), (V2, V1), (V2, V3), (V3, V0), (V4, V3)}（注意：这里V0可能是一个错误或假设的顶点，通常顶点编号应从1开始且连续，但为保持示例的一致性，我们在此保留V0）。

该图的邻接表表示如下：

  • V1的邻接链表包含：V2, V4
  • V2的邻接链表包含：V1, V3
  • V3的邻接链表包含：V0（注意：V0可能表示一个不存在的顶点或错误，根据实际情况调整）
  • V4的邻接链表包含：V3

二、领接表结构（C语言）

1. 弧的结构体

#define MaxVertexNum 100
// 定义顶点对应的数据类型，这里使用字符类型来表示顶点
typedef char VertexType;// 定义边对应的数据类型，这里使用整数类型来表示边的权重（如果有的话）
typedef int EdgeType;// 定义邻接表中的弧（边）节点结构
typedef struct ArcNode {int adjvex;            // adjvex 表示该弧所指向的顶点的位置（索引）struct ArcNode* nextarc; // nextarc 指向下一条与该顶点相连的弧的指针，形成链表// EdgeType data;       // 边的数据（如权重），如果需要使用边的权重，取消注释
} ArcNode;                 // 弧节点结构定义结束

2. 顶点结构体


// 定义邻接表中的顶点节点结构
typedef struct VNode {VertexType name[20];   // name 存储顶点的名称或标识符，这里假设最长为19个字符加上一个结束符ArcNode* firstarc;     // firstarc 指向该顶点的第一条相连的弧的指针，即该顶点的邻接链表的头指针
} VNode, AdjList[MaxVertexNum]; // VNode 和 AdjList 是同义类型，AdjList 是一个顶点数组类型，其大小由 MaxVertexNum 决定

3. 定义图，用领接表表示


// 定义图的结构，使用邻接表表示
typedef struct {int vexnum, arcnum;    // vexnum 表示图的顶点数，arcnum 表示图的边数AdjList vertices;      // vertices 是邻接表，存储了图的所有顶点及其邻接链表
} ALGraph;

4. 初始化图


// 初始化图的邻接表表示的函数
void InitALGraph(ALGraph* G) {// 初始化图的边数为0G->arcnum = 0;// 初始化图的顶点数为0G->vexnum = 0;// 遍历顶点数组，初始化每个顶点的邻接链表为空（即每个顶点的 firstarc 指针指向 NULL）for (int i = 0; i < MaxVertexNum; i++) {G->vertices[i].firstarc = NULL;}
}

三、领接表存储使用案例

        实现的功能包括多个部分，涉及文件操作、从终端读取图的信息（由用户输入）、将图信息写入文件、从文件读取图信息、有向图转换为无向图以及查看图的信息。

1. 判断图中是否有a指向b

// 判断在有向图 G 中，顶点 a 是否有一条直接指向顶点 b 的边
bool VertexConnect(ALGraph G, int a, int b) {// 从顶点 a 的邻接链表的头指针开始遍历ArcNode* p = G.vertices[a].firstarc;// 遍历顶点 a 的所有邻接顶点for (; p != NULL; p = p->nextarc) {// 如果当前邻接顶点的位置（索引）等于 b，则返回 true，表示 a 指向 bif (p->adjvex == b) {return true;}}// 如果遍历完所有邻接顶点都没有找到指向 b 的边，则返回 falsereturn false;
}

2. 将图中a连向b


// 将图中顶点 a 与顶点 b 相连
void ConnectAB(ALGraph* G, int a, int b) {ArcNode* p, * t; // 声明两个指针，p 用于遍历，t 用于存储新创建的邻接点// 初始化指针 p，指向顶点 a 的首条邻接边p = G->vertices[a].firstarc;// 为新邻接点分配内存// 创建新的邻接点t = (ArcNode*)malloc(sizeof(ArcNode)); // 分配内存给新节点// 检查内存分配是否成功if (t == NULL) {printf("空间不足\n"); // 打印错误信息exit(1); // 内存分配失败，退出程序}// 设置新邻接点的信息t->adjvex = b; // 设置新节点的目标顶点索引为 bt->nextarc = NULL; // 新节点为链表末尾，nextarc 指向 NULL// 若顶点 a 无邻接边，则新边为首条边if (p == NULL) {G->vertices[a].firstarc = t; // 将新节点设置为顶点 a 的首条邻接边return; // 添加完成，直接返回}// 若顶点 a 有邻接边，则将新边添加到邻接链表末尾// 将 p 调整到最后一条边while (p->nextarc != NULL) { // 遍历至链表末尾p = p->nextarc; // 移动指针至下一条边}// 将新边添加到顶点 a 的邻接链表末尾p->nextarc = t; // 将链表的最后一个节点的 nextarc 指向新节点}

3 通过用户输入创建图


// 通过用户输入创建图
void StructGraph(ALGraph* G) {// 初始化数据G->arcnum = 0;G->vexnum = 0;// 假设 MaxVertexNum 已经在其他地方定义printf("请输入图的总顶点数(<=%d) : ", MaxVertexNum);scanf("%d", &G->vexnum);if (G->vexnum > MaxVertexNum || G->vexnum <= 0) {printf("图的顶点数输入错误!\n");exit(1);}// 初始化顶点数组for (int i = 0; i < G->vexnum; i++) {G->vertices[i].firstarc = NULL;printf("\n请输入第 %d 顶点的名字: ", i);scanf("%s", G->vertices[i].name); // 确保 name 数组足够大以存储输入int key; // 将 key 的声明移到循环内部ArcNode* p = G->vertices[i].firstarc;while (1) { clearScreen();printf("请输入顶点： %s(%d) 将连接的点 \n(退出：-1； 输入限制： 0 <= num < %d) : ",G->vertices[i].name, i, G->vexnum - 1); scanf("%d", &key);if (key == -1) break;if (key < 0 || key >= G->vexnum) { // 修改条件，确保 key 在有效范围内printf("输入顶点信息错误\n\n");continue;}// 检查两点是否已经相连或者是否是与自身相连if (VertexConnect(*G, i, key) || key == i) {printf("此边已连接!!\n\n");continue; // continue 会跳过后面的代码直接回到 while 循环的开始}// 创建新的邻接点ArcNode* t = (ArcNode*)malloc(sizeof(ArcNode));if (t == NULL) {printf("空间不足\n");exit(1);}t->adjvex = key;t->nextarc = NULL;// 将新的邻接点添加到链表中if (p == NULL) {G->vertices[i].firstarc = t;p = t;}else {p->nextarc = t;p = t;}G->arcnum++;printf("该边添加成功\n\n");}}
}

4. 将图像信息写入文件


// 将邻接表表示的图写入文本文件
void WriteALGraph(ALGraph* G) {// 打开文件用于写入，如果文件打开失败则打印错误信息并退出程序FILE* fp = fopen("Graph.txt", "w");if (fp == NULL) {printf("Graph.txt 文件打开失败！\n");exit(1); // 退出程序，返回错误码1}// 将图的顶点数和边数写入文件fprintf(fp, "%d %d\n", G->vexnum, G->arcnum);// 遍历每个顶点for (int i = 0; i < G->vexnum; i++) {// 写入 "begin" 标记，表示一个顶点的邻接表开始fprintf(fp, "begin ");// 写入顶点的名称，假设名称不会超过20个字符，并使用空格填充至20个字符宽度fprintf(fp, "%20s ", G->vertices[i].name);// 获取当前顶点的第一个邻接点ArcNode* p = G->vertices[i].firstarc;// 遍历当前顶点的所有邻接点while (p != NULL) {// 写入 "to" 标记和邻接点的索引fprintf(fp, "to %d ", p->adjvex);// 如果弧有数据，可以取消以下行的注释，并写入弧的数据// fprintf(fp, "arcdata %d", p->data);// 移动到下一个邻接点p = p->nextarc;}// 写入 "end" 标记，表示一个顶点的邻接表结束fprintf(fp, "end\n");}// 关闭文件fclose(fp);// 打印成功信息printf("写入成功\n");
}

5. 从文件读取图的信息


void ReadGrcph(ALGraph* G) {// 打开文件用于读取，如果文件打开失败则打印错误信息并退出程序FILE* fp = fopen("Graph.txt", "r");if (fp == NULL) {printf("Graph.txt 文件打开失败！\n");exit(1); // 退出程序，返回错误码1}// 初始化图GInitALGraph(G);int cntarcnum = 0; // 用于记录实际读取的边数// 读入顶点数和边数（注意：这里读取的边数可能会被后续的实际边数覆盖）fscanf(fp, "%d %d", &G->vexnum, &G->arcnum);// 遍历每个顶点，读取其邻接信息for (int i = 0; i < G->vexnum && !feof(fp); i++) {char temps[20];fscanf(fp, "%s", temps);// 检查是否为"begin"标记，如果不是则报错并退出if (strcmp(temps, "begin") != 0) {printf("文件信息错误！！！\n");fclose(fp);exit(1);}// 读取顶点名称fscanf(fp, "%s", G->vertices[i].name);ArcNode* p = G->vertices[i].firstarc; // 指向当前顶点的首条邻接边// 读取当前顶点的所有邻接信息，直到遇到"end"标记while (1) {fscanf(fp, "%s", temps);if (strcmp(temps, "end") == 0) {break; // 遇到"end"标记，结束当前顶点的邻接信息读取}else if (strcmp(temps, "to") != 0) {// 如果不是"to"标记，则报错并退出printf("文件信息错误！！！\n");fclose(fp);exit(1);}int key = 0; // 用于存储邻接顶点的索引fscanf(fp, "%d", &key); // 读取邻接顶点的索引// 检查索引的有效性，避免越界和自环if (key < 0 || key >= G->vexnum) {printf("文件信息错误！！！\n");fclose(fp);exit(1);}// 检查两点是否已经相连或者是否是与自身相连，如果是则跳过if (VertexConnect(*G, i, key) || key == i) {continue; // 跳过当前循环迭代，继续检查下一个邻接信息}// 创建新的邻接点并添加到链表中ArcNode* t = (ArcNode*)malloc(sizeof(ArcNode));if (t == NULL) {fclose(fp);printf("空间不足\n");exit(1);}t->adjvex = key; // 设置邻接点的目标顶点索引t->nextarc = NULL; // 新节点为链表末尾，nextarc 指向 NULL// 将新节点添加到当前顶点的邻接链表末尾if (p == NULL) {G->vertices[i].firstarc = t; // 如果当前顶点无邻接边，则新边为首条边p = t; // 更新指针p，使其指向新添加的节点}else {p->nextarc = t; // 将新节点添加到链表末尾p = t; // 更新指针p，使其指向新添加的节点}cntarcnum++; // 更新实际读取的边数// 注释掉的代码是之前添加邻接点的另一种方式，与当前方式重复（调试中好像不能正常运行），因此被注释掉/*if (G->vertices[i].firstarc == NULL) {G->vertices[i].firstarc = t;}else {while (p->nextarc != NULL) {p = p->nextarc;}p->nextarc = t;}*/}}// 更新图的边数为实际读取的边数G->arcnum = cntarcnum;// 关闭文件fclose(fp);
}

6. 查看图的信息


// 定义一个函数，用于监视（遍历并显示）图的邻接表表示
void WatchGraph(ALGraph G) {ArcNode* p = NULL; // 定义一个指向边的指针，初始化为NULLint key = 0; // 定义一个变量，用于存储当前正在查看的顶点编号，初始化为0// 使用无限循环来不断显示顶点信息，直到用户选择退出while (1) {clearScreen(); // 清除屏幕，以便显示新的信息// 获取当前顶点的第一条相邻边p = G.vertices[key].firstarc;// 显示图的基本信息和当前顶点的信息printf("顶点数：%d    边数：%d  \n", G.vexnum, G.arcnum);printf("当前顶点：%d\n", key);printf("与之相连的边(编号)：\n");// 遍历当前顶点的所有相邻边，并打印相邻顶点的编号for (; p != NULL; p = p->nextarc) {printf("%d ", p->adjvex);}// 提示用户输入要跳转的顶点编号，或输入-1退出printf("\n\n跳转顶点 退出：-1（0 <= k <= %d）：", G.vexnum - 1);int k;scanf("%d", &k); // 读取用户输入的顶点编号// 再次清除屏幕，以防之前的输入或错误信息干扰接下来的显示clearScreen();// 根据用户输入进行处理if (k == -1) {// 如果用户输入-1，则退出循环break;}else if (k < 0 || k >= G.vexnum) {// 如果用户输入的编号无效，则显示错误信息，并继续显示当前顶点printf("\n\n输入错误，当前顶点将不变\n\n");continue; // 跳过循环的剩余部分，继续下一次迭代}else {// 如果用户输入了有效的顶点编号，则更新当前顶点编号key = k;}}
}

7. 有向图转换为无向图


// 将图转换为无向图
void ConvertUndirectedGraph(ALGraph G, ALGraph* UG) {*UG = G;// int arccnt = 0;for (int i = 0; i < UG->vexnum; i++) {ArcNode* p = UG->vertices[i].firstarc;for (p; p != NULL; p = p->nextarc) {// 查看两点是否相连if (!VertexConnect(*UG, p->adjvex, i)) {// 若没有相连，则连接上ConnectAB(UG, p->adjvex, i);UG->arcnum++;// printf("%d to %d\n", p->adjvex, i);}}}// 从新计算边的数量/*for (int i = 0; i < UG->vexnum; i++) {ArcNode* p = UG->vertices[i].firstarc;for (p; p != NULL; p = p->nextarc) {arccnt++;}}*/// 调整无向图中边的计数。UG->arcnum = UG->arcnum / 2;
}

8.文件内容（参考）// 无向图

4 4
begin              adfsgvb to 1 to 3 end
begin                 dca2 to 2 to 0 end
begin               fdgfch to 3 to 1 end
begin                 afcf to 0 to 2 end

四、总代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#pragma warning(disable:4996);// 清屏
void clearScreen() {system("cls");
}#define MaxVertexNum 100
// 定义顶点对应的数据类型，这里使用字符类型来表示顶点
typedef char VertexType;// 定义边对应的数据类型，这里使用整数类型来表示边的权重（如果有的话）
typedef int EdgeType;// 定义邻接表中的弧（边）节点结构
typedef struct ArcNode {int adjvex;            // adjvex 表示该弧所指向的顶点的位置（索引）struct ArcNode* nextarc; // nextarc 指向下一条与该顶点相连的弧的指针，形成链表// EdgeType data;       // 边的数据（如权重）如果需要使用边的权重，取消注释
} ArcNode;                 // 弧节点结构定义结束// 定义邻接表中的顶点节点结构
typedef struct VNode {VertexType name[20];   // name 存储顶点的名称或标识符，这里假设最长为19个字符加上一个结束符ArcNode* firstarc;     // firstarc 指向该顶点的第一条相连的弧的指针，即该顶点的邻接链表的头指针
} VNode, AdjList[MaxVertexNum]; // VNode 和 AdjList 是同义类型，AdjList 是一个顶点数组类型，其大小由 MaxVertexNum 决定// 定义图的结构，使用邻接表表示
typedef struct {int vexnum, arcnum;    // vexnum 表示图的顶点数，arcnum 表示图的边数AdjList vertices;      // vertices 是邻接表，存储了图的所有顶点及其邻接链表
} ALGraph;// 初始化图的邻接表表示的函数
void InitALGraph(ALGraph* G) {// 初始化图的边数为0G->arcnum = 0;// 初始化图的顶点数为0G->vexnum = 0;// 遍历顶点数组，初始化每个顶点的邻接链表为空（即每个顶点的 firstarc 指针指向 NULL）for (int i = 0; i < MaxVertexNum; i++) {G->vertices[i].firstarc = NULL;}
}// 判断在有向图 G 中，顶点 a 是否有一条直接指向顶点 b 的边
bool VertexConnect(ALGraph G, int a, int b) {// 从顶点 a 的邻接链表的头指针开始遍历ArcNode* p = G.vertices[a].firstarc;// 遍历顶点 a 的所有邻接顶点for (; p != NULL; p = p->nextarc) {// 如果当前邻接顶点的位置（索引）等于 b，则返回 true，表示 a 指向 bif (p->adjvex == b) {return true;}}// 如果遍历完所有邻接顶点都没有找到指向 b 的边，则返回 falsereturn false;
}// 将图中顶点 a 与顶点 b 相连
void ConnectAB(ALGraph* G, int a, int b) {ArcNode* p, * t; // 声明两个指针，p 用于遍历，t 用于存储新创建的邻接点// 初始化指针 p，指向顶点 a 的首条邻接边p = G->vertices[a].firstarc;// 为新邻接点分配内存// 创建新的邻接点t = (ArcNode*)malloc(sizeof(ArcNode)); // 分配内存给新节点// 检查内存分配是否成功if (t == NULL) {printf("空间不足\n"); // 打印错误信息exit(1); // 内存分配失败，退出程序}// 设置新邻接点的信息t->adjvex = b; // 设置新节点的目标顶点索引为 bt->nextarc = NULL; // 新节点为链表末尾，nextarc 指向 NULL// 若顶点 a 无邻接边，则新边为首条边if (p == NULL) {G->vertices[a].firstarc = t; // 将新节点设置为顶点 a 的首条邻接边return; // 添加完成，直接返回}// 若顶点 a 有邻接边，则将新边添加到邻接链表末尾// 将 p 调整到最后一条边while (p->nextarc != NULL) { // 遍历至链表末尾p = p->nextarc; // 移动指针至下一条边}// 将新边添加到顶点 a 的邻接链表末尾p->nextarc = t; // 将链表的最后一个节点的 nextarc 指向新节点}// 通过用户输入创建图
void StructGraph(ALGraph* G) {// 初始化数据G->arcnum = 0;G->vexnum = 0;// 假设 MaxVertexNum 已经在其他地方定义printf("请输入图的总顶点数(<=%d) : ", MaxVertexNum);scanf("%d", &G->vexnum);if (G->vexnum > MaxVertexNum || G->vexnum <= 0) {printf("图的顶点数输入错误!\n");exit(1);}// 初始化顶点数组for (int i = 0; i < G->vexnum; i++) {G->vertices[i].firstarc = NULL;printf("\n请输入第 %d 顶点的名字: ", i);scanf("%s", G->vertices[i].name); // 确保 name 数组足够大以存储输入int key; // 将 key 的声明移到循环内部ArcNode* p = G->vertices[i].firstarc;while (1) { clearScreen();printf("请输入顶点： %s(%d) 将连接的点 \n(退出：-1； 输入限制： 0 <= num < %d) : ",G->vertices[i].name, i, G->vexnum - 1); scanf("%d", &key);if (key == -1) break;if (key < 0 || key >= G->vexnum) { // 修改条件，确保 key 在有效范围内printf("输入顶点信息错误\n\n");continue;}// 检查两点是否已经相连或者是否是与自身相连if (VertexConnect(*G, i, key) || key == i) {printf("此边已连接!!\n\n");continue; // continue 会跳过后面的代码直接回到 while 循环的开始}// 创建新的邻接点ArcNode* t = (ArcNode*)malloc(sizeof(ArcNode));if (t == NULL) {printf("空间不足\n");exit(1);}t->adjvex = key;t->nextarc = NULL;// 将新的邻接点添加到链表中if (p == NULL) {G->vertices[i].firstarc = t;p = t;}else {p->nextarc = t;p = t;}G->arcnum++;printf("该边添加成功\n\n");}}
}// 将邻接表表示的图写入文本文件
void WriteALGraph(ALGraph* G) {// 打开文件用于写入，如果文件打开失败则打印错误信息并退出程序FILE* fp = fopen("Graph.txt", "w");if (fp == NULL) {printf("Graph.txt 文件打开失败！\n");exit(1); // 退出程序，返回错误码1}// 将图的顶点数和边数写入文件fprintf(fp, "%d %d\n", G->vexnum, G->arcnum);// 遍历每个顶点for (int i = 0; i < G->vexnum; i++) {// 写入 "begin" 标记，表示一个顶点的邻接表开始fprintf(fp, "begin ");// 写入顶点的名称，假设名称不会超过20个字符，并使用空格填充至20个字符宽度fprintf(fp, "%20s ", G->vertices[i].name);// 获取当前顶点的第一个邻接点ArcNode* p = G->vertices[i].firstarc;// 遍历当前顶点的所有邻接点while (p != NULL) {// 写入 "to" 标记和邻接点的索引fprintf(fp, "to %d ", p->adjvex);// 如果弧有数据，可以取消以下行的注释，并写入弧的数据// fprintf(fp, "arcdata %d", p->data);// 移动到下一个邻接点p = p->nextarc;}// 写入 "end" 标记，表示一个顶点的邻接表结束fprintf(fp, "end\n");}// 关闭文件fclose(fp);// 打印成功信息printf("写入成功\n");
}void ReadGrcph(ALGraph* G) {// 打开文件用于读取，如果文件打开失败则打印错误信息并退出程序FILE* fp = fopen("Graph.txt", "r");if (fp == NULL) {printf("Graph.txt 文件打开失败！\n");exit(1); // 退出程序，返回错误码1}// 初始化图GInitALGraph(G);int cntarcnum = 0; // 用于记录实际读取的边数// 读入顶点数和边数（注意：这里读取的边数可能会被后续的实际边数覆盖）fscanf(fp, "%d %d", &G->vexnum, &G->arcnum);// 遍历每个顶点，读取其邻接信息for (int i = 0; i < G->vexnum && !feof(fp); i++) {char temps[20];fscanf(fp, "%s", temps);// 检查是否为"begin"标记，如果不是则报错并退出if (strcmp(temps, "begin") != 0) {printf("文件信息错误！！！\n");fclose(fp);exit(1);}// 读取顶点名称fscanf(fp, "%s", G->vertices[i].name);ArcNode* p = G->vertices[i].firstarc; // 指向当前顶点的首条邻接边// 读取当前顶点的所有邻接信息，直到遇到"end"标记while (1) {fscanf(fp, "%s", temps);if (strcmp(temps, "end") == 0) {break; // 遇到"end"标记，结束当前顶点的邻接信息读取}else if (strcmp(temps, "to") != 0) {// 如果不是"to"标记，则报错并退出printf("文件信息错误！！！\n");fclose(fp);exit(1);}int key = 0; // 用于存储邻接顶点的索引fscanf(fp, "%d", &key); // 读取邻接顶点的索引// 检查索引的有效性，避免越界和自环if (key < 0 || key >= G->vexnum) {printf("文件信息错误！！！\n");fclose(fp);exit(1);}// 检查两点是否已经相连或者是否是与自身相连，如果是则跳过if (VertexConnect(*G, i, key) || key == i) {continue; // 跳过当前循环迭代，继续检查下一个邻接信息}// 创建新的邻接点并添加到链表中ArcNode* t = (ArcNode*)malloc(sizeof(ArcNode));if (t == NULL) {fclose(fp);printf("空间不足\n");exit(1);}t->adjvex = key; // 设置邻接点的目标顶点索引t->nextarc = NULL; // 新节点为链表末尾，nextarc 指向 NULL// 将新节点添加到当前顶点的邻接链表末尾if (p == NULL) {G->vertices[i].firstarc = t; // 如果当前顶点无邻接边，则新边为首条边p = t; // 更新指针p，使其指向新添加的节点}else {p->nextarc = t; // 将新节点添加到链表末尾p = t; // 更新指针p，使其指向新添加的节点}cntarcnum++; // 更新实际读取的边数// 注释掉的代码是之前添加邻接点的另一种方式，与当前方式重复（调试中好像不能正常运行），因此被注释掉/*if (G->vertices[i].firstarc == NULL) {G->vertices[i].firstarc = t;}else {while (p->nextarc != NULL) {p = p->nextarc;}p->nextarc = t;}*/}}// 更新图的边数为实际读取的边数G->arcnum = cntarcnum;// 关闭文件fclose(fp);
}// 定义一个函数，用于监视（遍历并显示）图的邻接表表示
void WatchGraph(ALGraph G) {ArcNode* p = NULL; // 定义一个指向边的指针，初始化为NULLint key = 0; // 定义一个变量，用于存储当前正在查看的顶点编号，初始化为0// 使用无限循环来不断显示顶点信息，直到用户选择退出while (1) {clearScreen(); // 清除屏幕，以便显示新的信息// 获取当前顶点的第一条相邻边p = G.vertices[key].firstarc;// 显示图的基本信息和当前顶点的信息printf("顶点数：%d    边数：%d  \n", G.vexnum, G.arcnum);printf("当前顶点：%d\n", key);printf("与之相连的边(编号)：\n");// 遍历当前顶点的所有相邻边，并打印相邻顶点的编号for (; p != NULL; p = p->nextarc) {printf("%d ", p->adjvex);}// 提示用户输入要跳转的顶点编号，或输入-1退出printf("\n\n跳转顶点 退出：-1（0 <= k <= %d）：", G.vexnum - 1);int k;scanf("%d", &k); // 读取用户输入的顶点编号// 再次清除屏幕，以防之前的输入或错误信息干扰接下来的显示clearScreen();// 根据用户输入进行处理if (k == -1) {// 如果用户输入-1，则退出循环break;}else if (k < 0 || k >= G.vexnum) {// 如果用户输入的编号无效，则显示错误信息，并继续显示当前顶点printf("\n\n输入错误，当前顶点将不变\n\n");continue; // 跳过循环的剩余部分，继续下一次迭代}else {// 如果用户输入了有效的顶点编号，则更新当前顶点编号key = k;}}
}// 将图转换为无向图
void ConvertUndirectedGraph(ALGraph G, ALGraph* UG) {*UG = G;// int arccnt = 0;for (int i = 0; i < UG->vexnum; i++) {ArcNode* p = UG->vertices[i].firstarc;for (p; p != NULL; p = p->nextarc) {// 查看两点是否相连if (!VertexConnect(*UG, p->adjvex, i)) {// 若没有相连，则连接上ConnectAB(UG, p->adjvex, i);UG->arcnum++;// printf("%d to %d\n", p->adjvex, i);}}}// 从新计算边的数量/*for (int i = 0; i < UG->vexnum; i++) {ArcNode* p = UG->vertices[i].firstarc;for (p; p != NULL; p = p->nextarc) {arccnt++;}}*/// 调整无向图中边的计数。UG->arcnum = UG->arcnum / 2;
}int main() {ALGraph G;InitALGraph(&G);//StructGraph(&G);//WriteALGraph(&G);ReadGrcph(&G);ConvertUndirectedGraph(G, &G);//WatchGraph(G);WriteALGraph(&G);//WatchGraph(G);return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/479753.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Python编程语言中的优雅艺术：数值分隔符的巧妙运用

Python编程语言中的优雅艺术：数值分隔符的巧妙运用

在Python编程的世界里&#xff0c;有许多精巧的设计让代码更优雅、更易读。今天要分享的是一个看似简单却能大幅提升代码可读性的特性 —— 数值分隔符。这个特性从Python 3.6版本开始引入&#xff0c;它用一种极其优雅的方式解决了大数值表示的难题。 数值分隔符的本质与应用…
阅读更多...
心情追忆：构建支付模块的五个基本接口设计

心情追忆：构建支付模块的五个基本接口设计

之前&#xff0c;我独自一人开发了一个名为“心情追忆”的小程序&#xff0c;旨在帮助用户记录日常的心情变化及重要时刻。我从项目的构思、设计、前端&#xff08;小程序&#xff09;开发、后端搭建到最终部署。经过一个月的努力&#xff0c;通过群聊分享等方式&#xff0c;用…
阅读更多...
实验三 z变换及离散时间LTI系统的z域分析

实验三 z变换及离散时间LTI系统的z域分析

实验原理 有理函数z 变换的部分分式展开 【实例2-1】试用Matlab 命令对函数 X ( z ) 18 18 3 − 1 − 4 z − 2 − z − 3 X\left(z\right)\frac{18}{183^{-1} -4z^{-2} -z^{-3} } X(z)183−1−4z−2−z−318​ 进行部分分式展开&#xff0c;并求出其z 反变换。 B[18]; A…
阅读更多...
Web登录页面设计

Web登录页面设计

记录第一个前端界面&#xff0c;暑假期间写的&#xff0c;用了Lottie动画和canvas标签做动画&#xff0c;登录和注册也连接了数据库。 图片是从网上找的&#xff0c;如有侵权私信我删除&#xff0c;谢谢啦~
阅读更多...
【es6】原生js在页面上画矩形及删除的实现方法

【es6】原生js在页面上画矩形及删除的实现方法

画一个矩形&#xff0c;可以选中高亮&#xff0c;删除自己效果的实现&#xff0c;后期会丰富下细节&#xff0c;拖动及拖动调整矩形大小 实现效果 代码实现 class Draw {constructor() {this.x 0this.y 0this.disX 0this.disY 0this.startX 0this.startY 0this.mouseDo…
阅读更多...
高级 K8s 面试题（Advanced K8S Interview Questions）

高级 K8s 面试题（Advanced K8S Interview Questions）

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…
阅读更多...
HiISP（一)

HiISP（一)

系列文章目录 文章目录 系列文章目录前言一、Hi3518EV200 芯片架构1.1. ARM子系统1.2. 图像子系统&#xff08;Image Subsystem&#xff09;1.3. 视频子系统&#xff08;Video Subsystem&#xff09;1.4. 存储与接口模块1.5. 通用功能模块1.6. DDR与总线1.7. 数据流1.7.1. 数据…
阅读更多...
京东物流与亿纬锂能达成战略合作，双方跨界意义何在？

京东物流与亿纬锂能达成战略合作，双方跨界意义何在？

首先&#xff0c;这一合作有助于双方实现资源共享和优势互补。京东物流作为国内领先的物流服务商&#xff0c;拥有先进的物流技术和丰富的运营经验&#xff0c;能够为亿纬锂能提供高效、安全、可靠的物流服务。而亿纬锂能作为新能源领域的佼佼者&#xff0c;拥有先进的电池技术…
阅读更多...
103.【C语言】数据结构之二叉树的三种递归遍历方式

103.【C语言】数据结构之二叉树的三种递归遍历方式

目录 1.知识回顾 2.分析二叉树的三种遍历方式 1.总览 2.前序遍历 3.中序遍历 4.后序遍历 5.层序遍历 3.代码实现 1.准备工作 2.前序遍历函数PreOrder 测试结果 3.中序遍历函数InOrder 测试结果 4.后序遍历函数PostOrder 测试结果 4.底层分析 1.知识回顾 在99.…
阅读更多...
【kafka03】消息队列与微服务之Kafka 读写数据

【kafka03】消息队列与微服务之Kafka 读写数据

Kafka 读写数据 参考文档 Apache Kafka 常见命令 kafka-topics.sh #消息的管理命令 kafka-console-producer.sh #生产者的模拟命令 kafka-console-consumer.sh #消费者的模拟命令 创建 Topic 创建topic名为 chen&#xff0c;partitions(分区)为3&#xff0…
阅读更多...
SAP开发语言ABAP开发入门

SAP开发语言ABAP开发入门

1. 了解ABAP开发环境和基础知识 - ABAP简介 - ABAP&#xff08;Advanced Business Application Programming&#xff09;是SAP系统中的编程语言&#xff0c;主要用于开发企业级的业务应用程序&#xff0c;如财务、物流、人力资源等模块的定制开发。 - 开发环境搭建 - 首先需…
阅读更多...
[护网杯 2018]easy_tornado

[护网杯 2018]easy_tornado

这里有一个hint点进去看看&#xff0c;他说md5(cookie_secretmd5(filename))&#xff0c;所以我们需要获得cookie_secret的value 根据题目tornado,它可能是tornado的SSTI 这里吧filehash改为NULL. 是tornado的SSTI 输入{{handler.settings}} (settings 属性是一个字典&am…
阅读更多...
【k8s深入学习之 Scheme】全面理解 Scheme 的注册机制、内外部版本、自动转换函数、默认填充函数、Options等机制

【k8s深入学习之 Scheme】全面理解 Scheme 的注册机制、内外部版本、自动转换函数、默认填充函数、Options等机制

参考 【k8s基础篇】k8s scheme3 之序列化_基于schema进行序列化-CSDN博客【k8s基础篇】k8s scheme4 之资源数据结构与资源注册_kubernetes 的scheam-CSDN博客 Scheme的字段总览 type Scheme struct {// gvkToType 允许通过给定的版本和名称来推断对象的 Go 类型。// map 键是…
阅读更多...
PySide6 QSS(Qt Style Sheets) Reference: PySide6 QSS参考指南

PySide6 QSS(Qt Style Sheets) Reference: PySide6 QSS参考指南

Qt官网参考资料&#xff1a; QSS介绍&#xff1a; Styling the Widgets Application - Qt for Pythonhttps://doc.qt.io/qtforpython-6/tutorials/basictutorial/widgetstyling.html#tutorial-widgetstyling QSS 参考手册&#xff1a; Qt Style Sheets Reference | Qt Widge…
阅读更多...
python控制鼠标，键盘，adb

python控制鼠标，键盘，adb

python控制鼠标&#xff0c;键盘&#xff0c;adb 听说某系因为奖学金互相举报&#xff0c;好像拿不到要命一样。不禁想到几天前老墨偷走丁胖子的狗&#xff0c;被丁胖子逮到。他面对警察的问询面不改色坚持自我&#xff0c;反而是怒气冲冲的丁胖子被警察认为是偷狗贼。我觉得这…
阅读更多...
前端Vue项目整合nginx部署到docker容器

前端Vue项目整合nginx部署到docker容器

一、通过Dockerfile整合nginx方法&#xff1a; 1&#xff0c;使用Vue CLI或npm脚本构建生产环境下的Vue项目。 npm run build or yarn build2&#xff0c;构建完成后&#xff0c;项目目录中会生成一个dist文件夹&#xff0c;里面包含了所有静态资源文件&#xff08;HTML、CSS…
阅读更多...
ChatGPT的应用场景：开启无限可能的大门

ChatGPT的应用场景：开启无限可能的大门

ChatGPT的应用场景：开启无限可能的大门 随着人工智能技术的快速发展，自然语言处理领域迎来了前所未有的突破。其中，ChatGPT作为一款基于Transformer架构的语言模型，凭借其强大的语言理解和生成能力，在多个行业和场景中展现出了广泛的应用潜力。以下是ChatGPT八个最具代表…
阅读更多...
Wireshark抓取HTTPS流量技巧

Wireshark抓取HTTPS流量技巧

一、工具准备 首先安装wireshark工具&#xff0c;官方链接&#xff1a;Wireshark Go Deep 二、环境变量配置 TLS 加密的核心是会话密钥。这些密钥由客户端和服务器协商生成&#xff0c;用于对通信流量进行对称加密。如果能通过 SSL/TLS 日志文件&#xff08;例如包含密钥的…
阅读更多...
【dvwa靶场：File Upload系列】File Upload低-中-高级别，通关啦

【dvwa靶场：File Upload系列】File Upload低-中-高级别，通关啦

目录 一、low级别,直接上传木马文件 1.1、准备一个木马文件 1.2、直接上传木马文件 1.3、访问木马链接 1.4、连接蚁剑 二、medium级别&#xff1a;抓包文件缀名 2.1、准备一个木马文件&#xff0c;修改后缀名为图片的后缀名 2.2、上传文件&#xff0c;打开burpSuite&…
阅读更多...
【深度学习|目标跟踪】StrongSort 详解(以及StrongSort++)

【深度学习|目标跟踪】StrongSort 详解(以及StrongSort++)

StrongSort详解 1、论文及源码2、DeepSort回顾3、StrongSort的EMA4、StrongSort的NSA Kalman5、StrongSort的MC6、StrongSort的BOT特征提取器7、StrongSort的AFLink8、未完待续 1、论文及源码 论文地址&#xff1a;https://arxiv.org/pdf/2202.13514 源码地址&#xff1a;https…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023