【数据结构第 6 章 ③】- 用 C 语言实现邻接表并简单介绍十字链表和邻接多重表

2023-12-10 07:44
文章标签 语言 简单 实现 链表 介绍 数据结构 多重 十字 邻接 表并

本文主要是介绍【数据结构第 6 章 ③】- 用 C 语言实现邻接表并简单介绍十字链表和邻接多重表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一、邻接表

1.1 - ALGraph.h

1.2 - ALGraph.c

1.3 - Test.c

二、十字链表

三、邻接多重表

 

一、邻接表

邻接表（Adjacency List）是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 vi 的边（对有向图是以顶点 vi 为尾的弧）。每个结点由 3 个域组成，其中邻接顶点域（adjVexPos）指示与顶点 vi 邻接的顶点在图中的位置，链域（nextEdge）指示下一条边（或弧）的结点；数据域（info）存储和边（或弧）相关的信息，如权值等。

在表头结点中，除了设有链域（firstEdge）指向链表中的第一个结点之外，还设有存储顶点 vi 的名称或其他有关信息的数据域（vertex）。这些表头结点通常以顺序结构的形式存储，以便随机访问任一顶点的边链表。

下图 (a) 和 (b) 所示为图一中 G1 和 G2 的邻接表。

在无向图的邻接表中，顶点 vi 的度恰为第 i 个链表中的结点数；而在有向图中，第 i 个链表中的结点个数只是顶点 vi 的出度，为求入度，必须遍历整个邻接表。在所有链表中，其邻接顶点域的值为 i 的结点个数是顶点 vi 的入度。有时，为了便于确定顶点的入度，可以建立一个有向图的逆邻接表，即对每个顶点 vi 建立一个链接所有进入 vi 的边的表。

下图 (c) 所示为图一中有向图 G1 的逆邻接表。

1.1 - ALGraph.h

注意：下面是以无向图为例的。

#pragma once#define DEFAULT_CAPACITY 10typedef char VertexType;typedef struct EdgeNode
{int adjVexPos;struct EdgeNode* nextEdge;
}EdgeNode;typedef struct VertexNode
{VertexType vertex;EdgeNode* firstEdge;
}VertexNode;typedef struct ALGraph
{VertexNode* vertices;int vSize;int eSize;int capacity;
}ALGraph;// 基本操作
void ALGraphInit(ALGraph* pg);  // 初始化void ShowAdjList(ALGraph* pg);  // 显示邻接表int GetVertexPos(ALGraph* pg, VertexType v);  // 获取顶点的位置void InsertVertex(ALGraph* pg, VertexType v);  // 插入顶点
void InsertEdge(ALGraph* pg, VertexType v1, VertexType v2);  // 插入边void EraseVertex(ALGraph* pg, VertexType v);  // 删除顶点
void EraseEdge(ALGraph* pg, VertexType v1, VertexType v2);  // 删除边int GetFirstAdjVexPos(ALGraph* pg, VertexType v);  // 获取 v 的第一个邻接顶点的位置
int GetNextAdjVexPos(ALGraph* pg, VertexType v, VertexType w);
// 获取 v 的（相对于 w）的下一个邻接顶点的位置void ALGraphDestroy(ALGraph* pg);  // 销毁

1.2 - ALGraph.c

  1. 初始化：

    void ALGraphInit(ALGraph* pg)
{assert(pg);pg->vSize = pg->eSize = 0;pg->capacity = DEFAULT_CAPACITY;pg->vertices = (VertexNode*)malloc(sizeof(VertexNode) * pg->capacity);assert(pg->vertices);for (int i = 0; i < pg->capacity; ++i){pg->vertices[i].firstEdge = NULL;}
}

  2. 显示邻接表：

    void ShowAdjList(ALGraph* pg)
{assert(pg);for (int i = 0; i < pg->vSize; ++i){printf("%d %c:>", i, pg->vertices[i].vertex);EdgeNode* cur = pg->vertices[i].firstEdge;while (cur){printf("%d-->", cur->adjVexPos);cur = cur->nextEdge;}printf("NULL\n");}
}

  3. 获取顶点的位置：

    int GetVertexPos(ALGraph* pg, VertexType v)
{assert(pg);for (int i = 0; i < pg->vSize; ++i){if (pg->vertices[i].vertex == v)return i;}return -1;
}

  4. 插入顶点：

    void InsertVertex(ALGraph* pg, VertexType v)
{assert(pg);// 考虑是否需要扩容if (pg->vSize == pg->capacity){VertexNode* tmp = (VertexNode*)realloc(pg->vertices, sizeof(VertexNode) * 2 * pg->capacity);assert(tmp);pg->vertices = tmp;for (int i = pg->capacity; i < 2 * pg->capacity; ++i){pg->vertices[i].firstEdge = NULL;}pg->capacity *= 2;}// 插入顶点pg->vertices[pg->vSize++].vertex = v;
}

  5. 插入边：

    void InsertEdge(ALGraph* pg, VertexType v1, VertexType v2)
{assert(pg);int pos1 = GetVertexPos(pg, v1);int pos2 = GetVertexPos(pg, v2);if (pos1 == -1 || pos2 == -1)return;// 插入 (v1, v2)EdgeNode* p = (EdgeNode*)malloc(sizeof(EdgeNode));assert(p);p->adjVexPos = pos2;// 头插p->nextEdge = pg->vertices[pos1].firstEdge;pg->vertices[pos1].firstEdge = p;// 插入 (v2, v1)p = (EdgeNode*)malloc(sizeof(EdgeNode));assert(p);p->adjVexPos = pos1;// 头插p->nextEdge = pg->vertices[pos2].firstEdge;pg->vertices[pos2].firstEdge = p;++pg->eSize;  // 注意：边数只需要加 1
}

  6. 删除顶点：

    // 删除顶点
void EraseVertex(ALGraph* pg, VertexType v)
{assert(pg);int pos = GetVertexPos(pg, v);if (pos == -1)return;// 第一步：删除和顶点 v 相关联的边EdgeNode* cur = pg->vertices[pos].firstEdge;while (cur){// 找到邻接顶点 v2, 先删除 (v2, v)int pos2 = cur->adjVexPos;EdgeNode* prev2 = NULL;EdgeNode* cur2 = pg->vertices[pos2].firstEdge;while (cur2 && cur2->adjVexPos != pos){prev2 = cur2;cur2 = cur2->nextEdge;}if (cur2){if (prev2 == NULL)pg->vertices[pos2].firstEdge = cur2->nextEdge;elseprev2->nextEdge = cur2->nextEdge;free(cur2);}// 再删除 (v, v2)pg->vertices[pos].firstEdge = cur->nextEdge;free(cur);cur = pg->vertices[pos].firstEdge;--pg->eSize;  // 注意不要遗漏}// 第二步：删除顶点 vpg->vertices[pos].vertex = pg->vertices[pg->vSize - 1].vertex;pg->vertices[pos].firstEdge = pg->vertices[pg->vSize - 1].firstEdge;cur = pg->vertices[pos].firstEdge;while (cur){int pos2 = cur->adjVexPos;EdgeNode* cur2 = pg->vertices[pos2].firstEdge;while (cur2){if (cur2->adjVexPos == pg->vSize - 1){cur2->adjVexPos = pos;break;}cur2 = cur2->nextEdge;}cur = cur->nextEdge;}--pg->vSize;  // 注意不要遗漏
}

  7. 删除边：

    void EraseEdge(ALGraph* pg, VertexType v1, VertexType v2)
{assert(pg);int pos1 = GetVertexPos(pg, v1);int pos2 = GetVertexPos(pg, v2);if (pos1 == -1 || pos2 == -1)return;// 删除 (v1, v2)EdgeNode* prev = NULL;EdgeNode* cur = pg->vertices[pos1].firstEdge;while (cur && cur->adjVexPos != pos2){prev = cur;cur = cur->nextEdge;}if (cur == NULL)  // 说明 (v1, v2) 不存在 return;if (prev == NULL)pg->vertices[pos1].firstEdge = cur->nextEdge;elseprev->nextEdge = cur->nextEdge;free(cur);// 删除 (v2, v1)// 注意：此时 (v2, v1) 一定存在prev = NULL;cur = pg->vertices[pos2].firstEdge;while (cur->adjVexPos != pos1){prev = cur;cur = cur->nextEdge;}if (prev == NULL)pg->vertices[pos2].firstEdge = cur->nextEdge;elseprev->nextEdge = cur->nextEdge;free(cur);--pg->eSize;  // 注意不要遗漏
}

  8. 获取 v 的第一个邻接顶点的位置：

    int GetFirstAdjVexPos(ALGraph* pg, VertexType v)
{assert(pg);int pos = GetVertexPos(pg, v);if (pos == -1)return -1;EdgeNode* cur = pg->vertices[pos].firstEdge;if (cur)return cur->adjVexPos;elsereturn -1;
}

  9. 获取 v 的（相对于 w）的下一个邻接顶点的位置：

    int GetNextAdjVexPos(ALGraph* pg, VertexType v, VertexType w)
{assert(pg);int pos1 = GetVertexPos(pg, v);int pos2 = GetVertexPos(pg, w);if (pos1 == -1 || pos2 == -1)return -1;EdgeNode* cur = pg->vertices[pos1].firstEdge;while (cur && cur->adjVexPos != pos2){cur = cur->nextEdge;}if (cur && cur->nextEdge)return cur->nextEdge->adjVexPos;elsereturn -1;
}

  10. 销毁：

    void ALGraphDestroy(ALGraph* pg)
{assert(pg);for (int i = 0; i < pg->vSize; ++i){EdgeNode* cur = pg->vertices[i].firstEdge;while (cur){// 头删pg->vertices[i].firstEdge = cur->nextEdge;free(cur);cur = pg->vertices[i].firstEdge;}}free(pg->vertices);pg->vertices = NULL;pg->vSize = pg->eSize = pg->capacity = 0;
}

1.3 - Test.c

#include "ALGraph.h"
#include <stdio.h>int main()
{ALGraph g;ALGraphInit(&g);InsertVertex(&g, 'A');InsertVertex(&g, 'B');InsertVertex(&g, 'C');InsertVertex(&g, 'D');InsertVertex(&g, 'E');InsertEdge(&g, 'A', 'B');InsertEdge(&g, 'A', 'D');InsertEdge(&g, 'B', 'C');InsertEdge(&g, 'B', 'E');InsertEdge(&g, 'C', 'D');InsertEdge(&g, 'C', 'E');ShowAdjList(&g);printf("\n");EraseVertex(&g, 'C');ShowAdjList(&g);printf("\n");EraseEdge(&g, 'A', 'B');ShowAdjList(&g);printf("\n");printf("%d\n", GetFirstAdjVexPos(&g, 'A'));  // 3printf("%d\n", GetNextAdjVexPos(&g, 'A', 'D'));  // -1ALGraphDestroy(&g);return 0;
}

二、十字链表

十字链表（Orthogonal List）是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中的每一条弧有一个结点，对应于每个顶点也有一个结点。这些结点的结构如下图所示。

在弧结点中有 5 个域：其中尾域（tailvex）和头域（headvex）分别指示弧尾和弧头这两个顶点在图中的位置，链域 hlink 指向弧头相同的下一条弧，而链域 tlink 指向弧尾相同的下一条弧，info 域指向该弧的相关信息。弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。

它们的头结点即为顶点结点，它由 3 个域组成：其中 data 域存储和顶点相关的信息，如顶点的名称等；firstin 和 firstout 为两个链域，分别指向以该顶点为弧头或弧尾的第一个弧结点。

例如下图 (a) 中所示的图的十字链表如下图 (b) 所示。

三、邻接多重表

邻接多重表（Adjacency Multilist）是无向图的另一种链式存储结构。虽然邻接表是无向图的一种有效的存储结构，在邻接表中容易求得顶点和边的各种信息，但是在邻接表中每一条边 有两个结点，分别在第 i 个和第 j 个链表中，这给某些图的操作带来不便，例如在某些图的应用问题中需要对边进行某种操作，如对已被搜索过的边做记号或删除一条边等，此时需要找到表示同一条边的两个结点。因此，在进行这一类操作的无向图的问题中采用邻接多重表更为适宜。

邻接多重表的结构和十字链表类似，在邻接多重表中，每一条边用一个结点表示，它由下图 (a) 所示的 6 个域组成。其中 mark 为标志域，可用以标记该条边是否被搜索过；ivex 和 jvex 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点 ivex 的边；jlink 指向下一条依附于顶点 jvex 的边，info 为指向和边相关的各种信息的指针域。

每个顶点也用一个结点表示，它由下图 (b) 所示的 2 个域组成。其中，data 域存储和该顶点相关的信息；firstedge 域指示第一条依附于该顶点的边。

例如下图所示为图一中无向图 G2 的邻接多重表。

在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。可见，对于无向图而言，其邻接多重表和邻接表的差别，仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。因此，除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同。

这篇关于【数据结构第 6 章 ③】- 用 C 语言实现邻接表并简单介绍十字链表和邻接多重表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/476455。

相关文章

性能测试介绍

性能测试介绍

性能测试是一种测试方法，旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试，可以确定系统是否能够满足预期的性能要求，找出性能瓶颈和潜在的问题，并进行优化和调整。 发现性能瓶颈：性能测试可以帮助发现系统的性能瓶颈，即系统在高负载或高并发情况下可能出现的问题
阅读更多...
水位雨量在线监测系统概述及应用介绍

水位雨量在线监测系统概述及应用介绍

在当今社会，随着科技的飞速发展，各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中，水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术，其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成，形成了一个完整的闭环系统。 数据采集单元：这是系统的“眼睛”，
阅读更多...
Hadoop数据压缩使用介绍

Hadoop数据压缩使用介绍

一、压缩原则 （1）运算密集型的Job，少用压缩 （2）IO密集型的Job，多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1）为了支持多种压缩/解压缩算法，Hadoop引入了编码/解码器 2）要在Hadoop中启用压缩，可以配置如下参数
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
hdu2289（简单二分）

hdu2289（简单二分）

虽说是简单二分，但是我还是wa死了  题意：已知圆台的体积，求高度 首先要知道圆台体积怎么求：设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ
阅读更多...
hdu1171（母函数或多重背包）

hdu1171（母函数或多重背包）

题意：把物品分成两份，使得价值最接近 可以用背包，或者是母函数来解，母函数（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v）（1 + x^v+x^2v+.....+x^num*v） 其中指数为价值，每一项的数目为（该物品数+1）个 代码如下： #include<iostream>#include<algorithm>
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2