【数据结构】十字链表的画法

9月前作者：灯笼只能来教室体验生活分类：Toy博客阅读(48) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】十字链表的画法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

十字链表的基本概念

有向边又称为弧
假设顶点 v 指向 w，那么 w 称为弧头，v 称为弧尾
顶点节点采用顺序存储
顶点节点
- data：存放顶点的信息
- firstin：指向以该节点为终点（弧头）的弧节点
- firstout：指向以该节点为起点（弧尾）的弧节点
弧节点
- tailvex：起点（弧尾）在数组中的索引
- headvex：终点（弧头）在数组中的索引
- hlink：终点（弧头）相同的下一个弧节点
- tlink：起点（弧尾）相同的下一个弧节点
- info：存放边（弧）有关的信息

画法

示例

【数据结构】十字链表的画法,数据结构与算法,数据结构,图论,链表

第 1 步

先画顶点节点，并在右侧标出顶点对应的索引
右侧的这些索引就叫它第 i 列吧， $\in [0, 3]$

【数据结构】十字链表的画法,数据结构与算法,数据结构,图论,链表

第 2 步

遍历每个顶点，找到该顶点指向的其他顶点 i，从左到右画弧节点，弧节点的位置对应第 i 列，每一行最右侧弧节点的 tlink 置为空
如果索引为 i 的顶点节点没有出度，那么 firstout 置为空

第 3 步

索引为 i 的顶点节点的 firstin 指向第 i 列的第一个节点（从上到下的第一个弧节点）
如果第 i 列一个节点也没有，那么 firstin 置为空

【数据结构】十字链表的画法,数据结构与算法,数据结构,图论,链表

第 4 步

遍历每一列，将 hlink 按列从上到下进行连接
每一列最后一个弧节点的 hlink 置为空（从上到下，最上面的是第一个，最下面的是最后一个）

【数据结构】十字链表的画法,数据结构与算法,数据结构,图论,链表文章来源地址https://www.toymoban.com/news/detail-681543.html

到了这里，关于【数据结构】十字链表的画法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：

领支付宝红包赞助服务器费用

数据结构——十字链表

什么是十字链表：十字链表(Orthogonal List) 是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。同时，代码的可读性也会得到提升。了解十字链表：我们来看下面这

2024年02月05日
浏览(41)
【数据结构与算法——TypeScript】算法的复杂度分析、数组和链表的对比

什么是算法复杂度(现实案例)？ ❤️‍🔥 前面已经解释了什么是算法？其实就是解决问题的一系列步骤操作、逻辑。 ✅ 对于同一个问题，我们往往有很多种解决思路和方法，也就是可以采用不同的算法。举个例子（现实例子）：在一个庞大的图书馆中，我们需要找一本书

2024年02月14日
浏览(53)
【数据结构和算法初阶(C语言)】复杂链表（随机指针，随机链表的复制）题目详解+链表顺序表结尾

目录 1.随机链表的复制 1.2题目描述 1.3题目分析 1.4解题： 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。深拷贝

2024年03月10日
浏览(87)
数据结构--5.1图的存储结构（十字链表、邻接多重表、边集数组）

目录一、十字链表（Orthogonal List）二、邻接多重表三、边集数组四、深度优先遍历重新定义顶点表结点结构： data firstIn firstOut 重新定义边表结构结点： tailVex headVex headLink tailLink 十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到Vi为

2024年02月10日
浏览(43)
【数据结构】稀疏矩阵的压缩存储（三元组表、十字链表）（C语言）

稀疏矩阵是指矩阵中大多数元素为零的矩阵。从直观上讲，当非零元素个数低于总元素的30%时，这样的矩阵为稀疏矩阵。 1.1 三元组表的存储结构稀疏矩阵的三元组表表示法是指只存储非零元素，同时存储该非零元素在矩阵中所处的行号和列号的位置信息。为方便处理，将

2023年04月16日
浏览(43)
【数据结构】数组（稀疏矩阵、特殊矩阵压缩、矩阵存储、稀疏矩阵的快速转置、十字链表）

前几期期链接：【数据结构】栈与队列的概念和基本操作代码实现【数据结构】树与二叉树的概念与基本操作代码实现 k维数组的定义： k 维数组 D ＝ { a j 1 , j 2 , . . . , j k } k维数组D＝{ a_{j_1, j_2, ..., j_k} } k 维数组 D ＝ { a j 1 , j 2 , ... , j k } k 0 称为数组的维数，

2024年04月09日
浏览(140)
青岛大学_王卓老师【数据结构与算法】Week04_04_双向链表的插入_学习笔记

本文是个人学习笔记，素材来自青岛大学王卓老师的教学视频。一方面用于学习记录与分享，另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。如有侵权，请留言作删文处理。课程视频链接：数据结构与算法基础–第04周04–2.5.4双向链表2–双向链表

2024年02月12日
浏览(58)
西工大NOJ数据结构理论——013.以十字链表为存储结构实现矩阵相加（严5.27）

我第一下拿到这个题目，第一反应就是先定义好数据结构，然后构建好十字链表基础操作的函数，也就是“ 创插遍历 ”这些操作。下面是我的定义和函数操作。 typedef int ElemType; typedef struct OLNode{ int i,j;//行号和列号 ElemType elem; struct OLNode *right;//右边元素

2023年04月26日
浏览(86)
数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现，含注释

头文件和源文件分开有很多好处：可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性，同时也可以使代码结构更清晰，方便代码的管理和维护。 LinkList.h test.cpp （下面所有函数都默认在类中实现）我们以

2024年02月07日
浏览(58)
＜数据结构＞链表 - 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 1、链表由一系列结点（链表中每一个元素称为结点）组成。 2、结点可以在运行时动态(malloc)生成。 3、每个结点包括两个部分：一个是存储数据元素的

2023年04月09日
浏览(46)