【数据结构第 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 10

typedef 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;
			else
				prev2->nextEdge = cur2->nextEdge;
			free(cur2);
		}

		// 再删除 (v, v2)
		pg->vertices[pos].firstEdge = cur->nextEdge;
		free(cur);
		cur = pg->vertices[pos].firstEdge;

		--pg->eSize;  // 注意不要遗漏
	}

	// 第二步：删除顶点 v
	pg->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;
	else
		prev->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;
	else
		prev->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;
	else
		return -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;
	else
		return -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'));  // 3
	printf("%d\n", GetNextAdjVexPos(&g, 'A', 'D'));  // -1
	ALGraphDestroy(&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 的邻接多重表。

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

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

用modelbox server启动流程图，暴露Restful接口

用modelbox server启动流程图，暴露Restful接口

背景 假设你已经搭建了modelbox开发容器&#xff0c;能够使用webUI构建流程图。如果没有请参考昇腾npu上构建modelbox webUI开发容器教程。 现在&#xff0c;本文会说明&#xff0c;如何在终端用命令的方式将流程图暴露为服务&#xff0c;并能够在本地用postman访问。 本文参…
阅读更多...
二分查找|双指针:LeetCode:2398.预算内的最多机器人数目

二分查找|双指针:LeetCode:2398.预算内的最多机器人数目

作者推荐 本文涉及的基础知识点 二分查找算法合集 滑动窗口 单调队列&#xff1a;计算最大值时&#xff0c;如果前面的数小&#xff0c;则必定被淘汰&#xff0c;前面的数早出队。 题目 你有 n 个机器人&#xff0c;给你两个下标从 0 开始的整数数组 chargeTimes 和 runnin…
阅读更多...
java学习part41泛型

java学习part41泛型

164-泛型-泛型的理解及其在集合、比较器中的使用_哔哩哔哩_bilibili 1.泛型 泛型可以加&#xff0c;加了不用也可以 2.例子 2.1List泛型 2.2Map泛型 新特性var 类似c的auto&#xff0c;可以根据后面赋值推断类型&#xff0c;在这种类型很复杂的时候可以提高可读性 3.自定义泛型…
阅读更多...
什么是TDR（威胁检测与响应）

什么是TDR（威胁检测与响应）

网络安全是被动和主动方法的混合体。过去&#xff0c;企业往往局限于被动的方法&#xff0c;随着合规性和安全策略越来越受到重视&#xff0c;主动方法也越来越受到关注。与其他行业相比&#xff0c;网络安全是高度动态的&#xff0c;网络安全团队采用任何可以帮助他们优化的新…
阅读更多...
大数据技术5：OLAP引擎对比分析

大数据技术5：OLAP引擎对比分析

前言&#xff1a;数据仓库建设&#xff0c;初级的理解就是建表&#xff0c;将业务数据、日志数据、消息队列数据等&#xff0c;通过各种调度任务写入到表里供OLAP引擎使用。但要想建好数仓也是一个复杂、庞大的工程&#xff0c;比如要考虑&#xff1a;数据清洗、数据建模&#…
阅读更多...
联邦多任务蒸馏助力多接入边缘计算下的个性化服务 | TPDS 2023

联邦多任务蒸馏助力多接入边缘计算下的个性化服务 | TPDS 2023

联邦多任务蒸馏助力多接入边缘计算下的个性化服务 | TPDS 2023 随着移动智能设备的普及和人工智能技术的发展,越来越多的分布式数据在终端被产生与收集&#xff0c;并以多接入边缘计算(MEC)的形式进行处理和分析。但是由于用户的行为模式与服务需求的多样,不同设备上的数据分布…
阅读更多...
【2023传智杯-新增场次】第六届传智杯程序设计挑战赛AB组-DEF题复盘解题分析详解【JavaPythonC++解题笔记】

【2023传智杯-新增场次】第六届传智杯程序设计挑战赛AB组-DEF题复盘解题分析详解【JavaPythonC++解题笔记】

本文仅为【2023传智杯-第二场】第六届传智杯程序设计挑战赛-题目解题分析详解的解题个人笔记，个人解题分析记录。 本文包含：第六届传智杯程序设计挑战赛题目、解题思路分析、解题代码、解题代码详解 文章目录 一.前言二.赛题题目D题题目-E题题目-F题题目-二.赛题题解D题题解-…
阅读更多...
thinkphp6入门（12）-- 一对一关联模型

thinkphp6入门（12）-- 一对一关联模型

定义一对一关联&#xff0c;例如&#xff0c;一个用户都有一个个人资料。 一、两表 1.用户表:user 2.工作经验表&#xff1a;work_experience user表的id关联work_experience表的user_id。 注意看&#xff0c;user_id1的有2条工作经验 二、数据模型 主表模型&#xff1a;…
阅读更多...
求导公式，求导的四则运算，复合函数求导

求导公式，求导的四则运算，复合函数求导

求导公式 求导的四则运算 复合函数求导
阅读更多...
目标检测、目标跟踪、重识别

目标检测、目标跟踪、重识别

文章目录 环境前言项目复现特征提取工程下载参考资料 环境 ubuntu 18.04 64位yolov5deepsortfastreid 前言 基于YOLOv5和DeepSort的目标跟踪 介绍过针对行人的检测与跟踪。本文介绍另一个项目&#xff0c;结合 FastReid 来实现行人的检测、跟踪和重识别。作者给出的2个主…
阅读更多...
swing快速入门（一）

swing快速入门（一）

注释很详细&#xff0c;直接上代码 涉及内容 1. 默认布局方式BorderLayout 2. 设置窗口位置和大小 3. 设置窗口可见性 4. panel对象&#xff08;面板容器&#xff09; 5. 文本和按钮组件的创建 6. 组件和容器的嵌套 import java.awt.*;public class Main{public static …
阅读更多...
MN316 OpenCPU丨HTTP使用介绍

MN316 OpenCPU丨HTTP使用介绍

HTTP&#xff08;Hyper Text Transfer Protocol&#xff09;即超文本传输协议&#xff0c;是一个简单的请求-响应协议&#xff0c;通常运行在TCP之上&#xff0c;它指定了客户端可能发送给服务器消息类型以及得到什么类型响应。HTTPS&#xff08;Hyper Text Transfer Protoc…
阅读更多...
二维码智慧门牌管理系统升级：社区关怀

二维码智慧门牌管理系统升级：社区关怀

文章目录 前言一、系统的工作原理二、系统功能与关怀服务三、社区关怀的意义 前言 随着科技的发展&#xff0c;生活日益智能化&#xff0c;门牌系统也随之发展。近日&#xff0c;一种新型的二维码智慧门牌管理系统正在崛起&#xff0c;以创新的方式将社区关怀融入到每一个家庭…
阅读更多...
STM32F407-14.3.9-02输出比较模式

STM32F407-14.3.9-02输出比较模式

输出比较模式 输出比较模式生成波形时 当采用上升沿或下降沿计数时&#xff0c;更改ARR的值可改变周期&#xff1b; 更改CCRx的值会影响到生成波形的相位。波形的占空比永远50% 当采用中心对齐模式时&#xff0c; 更改ARR的值可以改变周期&#xff0c;更改CCRx的值可以改…
阅读更多...
动态规划（dp）初步学习案例讲解

动态规划（dp）初步学习案例讲解

问题&#xff08;来源&#xff1a;leetcode300&#xff09;&#xff1a; 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列&#xff0c;删除&#xff08;或不删除&#xff09;数组中的元素而不改变其余元素的顺序。例如&a…
阅读更多...
HarmonyOS--ArkTS(1)--基本语法(1)

HarmonyOS--ArkTS(1)--基本语法(1)

目录 基本语法概述 声明式UI描述 自定义组件 创建自定义组件 自定义组件的结构--struct &#xff0c;Component&#xff0c;build()函数 生命周期 基本语法概述 装饰器&#xff1a; 用于装饰类、结构、方法以及变量&#xff0c;并赋予其特殊的含义。如上述示例中Entry、C…
阅读更多...
TypeScript基本语法

TypeScript基本语法

想在自己电脑上快速演示下方代码&#xff1f;点击ts官方演练场&#xff1a;https://www.typescriptlang.org/play 变量声明&#xff1a;TypeScript 在 Javascript的基础上加入了静态类型检查功能&#xff0c;因此每一个变量都有固定的数据类型。 //string: 字符串&#xff0c;…
阅读更多...
GPT-4 变懒了？官方回复

GPT-4 变懒了？官方回复

你是否注意到&#xff0c;最近使用 ChatGPT 的时候&#xff0c;当你向它提出一些问题&#xff0c;却得到的回应似乎变得简短而敷衍了&#xff1f;对于这一现象&#xff0c;ChatGPT 官方给出了回应。 译文&#xff1a;我们听到了你们所有关于 GPT4 变得更懒的反馈&#xff01;我…
阅读更多...
智能优化算法应用：基于蜉蝣算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于蜉蝣算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于蜉蝣算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于蜉蝣算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.蜉蝣算法4.实验参数设定5.算法结果6.参考文献7.MA…
阅读更多...
区块链实验室(30) - 区块链期刊:Distributed Ledger Technologies: Research and Practice

区块链实验室(30) - 区块链期刊:Distributed Ledger Technologies: Research and Practice

区块链涉及多学科及技术&#xff0c;众多期刊接收区块链文章。Distributed Ledger Technologies: Research and Practice是ACM出版集团的一本期刊。 Distributed Ledger Technologies: Research and Practice创刊历史很短&#xff0c;始于2022年&#xff0c;出版期数也不多。 载…
阅读更多...
最新文章

Copyright @ 2022~2023