基于C#实现十字链表

上一篇我们看了矩阵的顺序存储，这篇我们再看看一种链式存储方法“十字链表”，当然目的都是一样，压缩空间。

一、概念

既然要用链表节点来模拟矩阵中的非零元素，肯定需要如下 5 个元素(row,col,val,down,right)，其中：

row:矩阵中的行。
col:矩阵中的列。
val:矩阵中的值。
right:指向右侧的一个非零元素。
down：指向下侧的一个非零元素。

image.png
现在我们知道单个节点该如何表示了，那么矩阵中同行的非零元素的表示不就是一个单链表吗？比如如下：
image.png
那么进一步来说一个多行的非零元素的表示不就是多个单链表吗，是的，这里我把单链表做成循环链表，我们来看看如何用十字链表来表示稀疏矩阵。
image.png
从上面的十字链表中要注意两个问题：
第一：这里有一个填充色的节点，是十字链表中的总结点，它是记录该矩阵中的（row,col,value）和一个指向下一个头节点的 next 指针。
第二：每个链表都有一个头指针，总结点用 next 指针将它们贯穿起来。

二、操作

2.1、数据结构

刚才也说了，十字链表的总结点有一个 next 指针，而其他非零节点没有，所以为了方便，我们用一个 Unit 类包装起来。

 #region 单一节点/// <summary>/// 单一节点/// </summary>public class Node{//行号public int rows;//列号public int cols;//向下的指针域public Node down;//向右的指针域public Node right;//单元值（头指针的next和val）public Unit unit;}#endregion#region 统一“表头节点”和“非零节点”/// <summary>/// 统一“表头节点”和“非零节点”/// </summary>public class Unit{//表头节点的next域public Node next;//非零元素的值public int value;}#endregion

2.2、初始化

这一步，我们初始化总结点，并且用 next 指针将每个单链表的头节点链接成单链表（也就是上图中十字链表的第一行）

#region 十字链表中的“行数，列数，非零元素个数”/// <summary>/// 十字链表中的“行数，列数，非零元素个数”/// </summary>/// <param name="rows"></param>/// <param name="cols"></param>/// <param name="count"></param>public void Init(int rows, int cols, int count){var len = Math.Max(rows, cols) + 1;//从下标1开始算起nodes = new Node[len];//十字链表的总头节点nodes[0] = new Node();nodes[0].rows = rows;nodes[0].cols = cols;nodes[0].unit = new Unit(){value = count,next = null,};//down和right都指向自身nodes[0].right = nodes[0];nodes[0].down = nodes[0];var temp = nodes[0];//初始化多条链表的头结点for (int i = 1; i < len; i++){nodes[i] = new Node();nodes[i].rows = 0;nodes[i].cols = 0;nodes[i].unit = new Unit(){value = 0,next = temp.unit.next};//给上一个节点的next域赋值temp.unit.next = nodes[i];//将当前节点作为下一次循环的上一个节点temp = nodes[i];nodes[i].right = nodes[i];nodes[i].down = nodes[i];}}#endregion

2.3、插入节点

根据插入节点的 row 和 col 将节点插入到十字链表中指定的位置即可。

#region 插入十字链表中/// <summary>/// 插入十字链表中/// </summary>/// <param name="nums">矩阵</param>/// <param name="rows">矩阵的行数</param>/// <param name="cols">矩阵的列数</param>/// <param name="count">非0元素个数</param>/// <returns></returns>public Node[] Insert(int[,] nums, int rows, int cols, int count){//初始化操作Init(rows, cols, count);//插入操作for (int i = 0; i < rows; i++){for (int j = 0; j < cols; j++){//直插入"非0元素"if (nums[i, j] != 0){var node = new Node();node.rows = i + 1;node.cols = j + 1;node.unit = new Unit(){value = nums[i, j]};node.right = node;node.down = node;InsertNode(node);}}}return nodes;}#endregion

2.4、打印链表

我们只要遍历每行链表的 right 指针即可。

#region 打印十字链表/// <summary>/// 打印十字链表/// </summary>/// <param name="nodes"></param>public void Print(Node[] nodes){var head = nodes[0];//遍历每一行的rightfor (int i = 1; i < head.rows + 1; i++){var p = nodes[i];while (p.right != nodes[i]){Console.WriteLine("({0},{1})\tval => {2}",p.right.rows,p.right.cols,p.right.unit.value);//指向下一个节点p = p.right;}}}#endregion

2.5、总的代码：

 using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Diagnostics;using System.Threading;using System.IO;namespace ConsoleApplication2{public class Program{public static void Main(){Crosslist crosslist = new Crosslist();int[,] nums = {{2,0,4 },{0,3,0 },{0,0,9 }};var nodes = crosslist.Insert(nums, 3, 3, 4);crosslist.Print(nodes);Console.Read();}}/// <summary>/// 十字链表/// </summary>public class Crosslist{#region 单一节点/// <summary>/// 单一节点/// </summary>public class Node{//行号public int rows;//列号public int cols;//向下的指针域public Node down;//向右的指针域public Node right;//单元值（头指针的next和val）public Unit unit;}#endregion#region 统一“表头节点”和“非零节点”/// <summary>/// 统一“表头节点”和“非零节点”/// </summary>public class Unit{//表头节点的next域public Node next;//非零元素的值public int value;}#endregionNode[] nodes;#region 十字链表中的“行数，列数，非零元素个数”/// <summary>/// 十字链表中的“行数，列数，非零元素个数”/// </summary>/// <param name="rows"></param>/// <param name="cols"></param>/// <param name="count"></param>public void Init(int rows, int cols, int count){var len = Math.Max(rows, cols) + 1;//从下标1开始算起nodes = new Node[len];//十字链表的总头节点nodes[0] = new Node();nodes[0].rows = rows;nodes[0].cols = cols;nodes[0].unit = new Unit(){value = count,next = null,};//down和right都指向自身nodes[0].right = nodes[0];nodes[0].down = nodes[0];var temp = nodes[0];//初始化多条链表的头结点for (int i = 1; i < len; i++){nodes[i] = new Node();nodes[i].rows = 0;nodes[i].cols = 0;nodes[i].unit = new Unit(){value = 0,next = temp.unit.next};//给上一个节点的next域赋值temp.unit.next = nodes[i];//将当前节点作为下一次循环的上一个节点temp = nodes[i];nodes[i].right = nodes[i];nodes[i].down = nodes[i];}}#endregion#region 在指定的“行，列”上插入节点/// <summary>/// 在指定的“行，列”上插入节点/// </summary>/// <param name="node"></param>/// <returns></returns>public void InsertNode(Node node){//先定位行Node pnode = nodes[node.rows];//在指定的“行”中找，一直找到该行最后一个节点（right指针指向自己的为止）while (pnode.right != nodes[node.rows] && pnode.right.cols < node.cols)pnode = pnode.right;//将最后一个节点的right指向插入节点的right，以此达到是循环链表node.right = pnode.right;//将插入节点给最后一个节点的right指针上pnode.right = node;//再定位列pnode = nodes[node.cols];//同理while (pnode.down != nodes[node.cols] && pnode.down.rows < node.rows){pnode = pnode.down;}node.down = pnode.down;pnode.down = node;}#endregion#region 插入十字链表中/// <summary>/// 插入十字链表中/// </summary>/// <param name="nums">矩阵</param>/// <param name="rows">矩阵的行数</param>/// <param name="cols">矩阵的列数</param>/// <param name="count">非0元素个数</param>/// <returns></returns>public Node[] Insert(int[,] nums, int rows, int cols, int count){//初始化操作Init(rows, cols, count);//插入操作for (int i = 0; i < rows; i++){for (int j = 0; j < cols; j++){//直插入"非0元素"if (nums[i, j] != 0){var node = new Node();node.rows = i + 1;node.cols = j + 1;node.unit = new Unit(){value = nums[i, j]};node.right = node;node.down = node;InsertNode(node);}}}return nodes;}#endregion#region 打印十字链表/// <summary>/// 打印十字链表/// </summary>/// <param name="nodes"></param>public void Print(Node[] nodes){var head = nodes[0];//遍历每一行的rightfor (int i = 1; i < head.rows + 1; i++){var p = nodes[i];while (p.right != nodes[i]){Console.WriteLine("({0},{1})\tval => {2}",p.right.rows,p.right.cols,p.right.unit.value);//指向下一个节点p = p.right;}}}#endregion}}

image.png

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

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

相关文章

C语言第三十六弹--实现转移表的多种方法

C语言第三十六弹--实现转移表的多种方法

使用C语言通过多种方法实现转移表 方法一、普通法 思路&#xff1a;如图实现多种操作&#xff0c;首先创建菜单&#xff0c;需要运行一次再判断条件&#xff0c;所以通过do{}while(); 循环来实现多次。有多种选择&#xff0c;使用switch case选择语句&#xff0c;再在对应case…
阅读更多...
SpectralGPT: Spectral Foundation Model 论文翻译2

SpectralGPT: Spectral Foundation Model 论文翻译2

遥感领域的通用大模型 2023.11.13在CVPR发表 原文地址&#xff1a;[2311.07113] SpectralGPT: Spectral Foundation Model (arxiv.org) 实验 ​ 在本节中&#xff0c;我们将严格评估我们的SpectralGPT模型的性能&#xff0c;并对其进行基准测试SOTA基础模型&#xff1a;ResN…
阅读更多...
【沁恒蓝牙mesh】CH58x 将RTC时钟切换为LSE外部低速时钟

【沁恒蓝牙mesh】CH58x 将RTC时钟切换为LSE外部低速时钟

本文主要记录了【沁恒蓝牙mesh】CH58x 如何将RTC时钟切换为外部时钟 &#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是喜欢记录零碎知识点的小菜鸟。&#x1f60e;&#x1f4dd; 个人主页&#xff1a;欢迎访问我的 Ethernet_Comm 博客主页&#x1f525;&#x1f389;…
阅读更多...
【代码】基于卷积神经网络（CNN）-支持向量机（SVM）的分类预测算法

【代码】基于卷积神经网络（CNN）-支持向量机（SVM）的分类预测算法

程序名称&#xff1a;基于卷积神经网络&#xff08;CNN&#xff09;-支持向量机&#xff08;SVM&#xff09;的分类预测算法 实现平台&#xff1a;matlab 代码简介&#xff1a;CNN-SVM是一种常用的图像分类方法&#xff0c;结合了卷积神经网络&#xff08;CNN&#xff09;和支…
阅读更多...
Roll-A-Ball 游戏

Roll-A-Ball 游戏

Roll-A-Ball 游戏 1&#xff09;学习资料 b站视频教程&#xff1a;https://www.bilibili.com/video/BV18W411671S/文档&#xff1a; * Roll-A-Ball 教程&#xff08;一)&#xff0c; * Roll-A-Ball 教程&#xff08;二)线上体验roll-a-ball成品 * http://www-personal.umich.e…
阅读更多...
Databend 开源周报第 121 期

Databend 开源周报第 121 期

Databend 是一款现代云数仓。专为弹性和高效设计&#xff0c;为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务&#xff1a;https://app.databend.cn 。 Whats On In Databend 探索 Databend 本周新进展&#xff0c;遇到更贴近你心意的 Databend 。 支持追加流 Da…
阅读更多...
技巧-PyTorch中num_works的作用和实验测试

技巧-PyTorch中num_works的作用和实验测试

简介 在 PyTorch 中&#xff0c;num_workers 是 DataLoader 中的一个参数&#xff0c;用于控制数据加载的并发线程数。它允许您在数据加载过程中使用多个线程&#xff0c;以提高数据加载的效率。 具体来说&#xff0c;num_workers 参数指定了 DataLoader 在加载数据时将创建的…
阅读更多...
网络安全--基于Kali的网络扫描基础技术

网络安全--基于Kali的网络扫描基础技术

文章目录 1. 标准ICMP扫描1.1使用Ping命令1.1.1格式1.1.2实战 1.2使用Nmap工具1.2.1格式1.2.2实战1.2.2.1主机在线1.2.2.2主机不在线 1.3使用Fping命令1.3.1格式1.3.2实战 2. 时间戳查询扫描2.1格式2.2实战 3. 地址掩码查询扫描3.1格式3.2实战 2. TCP扫描2.1TCP工作机制2.2TCP …
阅读更多...
基于YOLO模型建筑工地个人防护设备目标检测

基于YOLO模型建筑工地个人防护设备目标检测

使用安全装备可以保护他们免受建筑工地的意外事故。据统计&#xff0c;每年有数以万计的工人在建筑工地受到严重伤害&#xff0c;造成终生困难。然而&#xff0c;通过自我监控来确保工人穿戴个人防护装备非常重要。在这方面&#xff0c;需要一个准确和快速的系统来检测工人是否…
阅读更多...
鸿蒙开发-ArkTS 语言-状态管理

鸿蒙开发-ArkTS 语言-状态管理

[写在前面: 文章多处用到gif动图&#xff0c;如未自动播放&#xff0c;请点击图片] 衔接上一篇:鸿蒙开发-ArkTS 语言-基础语法 3. 状态管理 变量必须被装饰器装饰才能成为状态变量&#xff0c;状态变量的改变才能导致 UI 界面重新渲染 概念描述状态变量被状态装饰器装饰的变…
阅读更多...
ArrayList源码全面解析

ArrayList源码全面解析

一、概述 ArrayList 是 java 集合框架中比较常用的数据结构,继承自 AbstractList&#xff0c;实现了 List 接口。底层采用数组来实现。ArrayList 实现了java.io.Serializable接口&#xff0c;这意味着ArrayList支持序列化&#xff0c;能通过序列化去传输。 1.1、底层数据结构…
阅读更多...
python基础练习题库实验6

python基础练习题库实验6

文章目录 题目1代码实验结果题目2代码实验结果题目3代码实验结果题目4代码实验结果题目总结题目1 根据以下规范编写一个函数： 函数名称：triple输入参数：1个输入参数数据类型字符串返回值：函数返回1个字符串值。该字符串由每个字符重复3次的句子构成。例如，如果句子是Uni，…
阅读更多...
Vue2问题：如何全局使用less和sass变量？

Vue2问题：如何全局使用less和sass变量？

前端功能问题系列文章&#xff0c;点击上方合集↑ 序言 大家好&#xff0c;我是大澈&#xff01; 本文约2400字&#xff0c;整篇阅读大约需要4分钟。 本文主要内容分三部分&#xff0c;如果您只需要解决问题&#xff0c;请阅读第一、二部分即可。如果您有更多时间&#xff…
阅读更多...
ESP32-Web-Server编程-建立第一个网页

ESP32-Web-Server编程-建立第一个网页

ESP32-Web-Server编程-建立第一个网页 HTTP 简述 可能你每天都要刷几个短视频&#xff0c;打开几个网页来娱乐一番。当你打开一个网络上的视频或者图片时&#xff0c;其实际发生了下面的流程&#xff1a; 其中客户端就是你的浏览器啦&#xff0c;服务器就是远程一个存放视频或…
阅读更多...
【网络奇幻之旅】那年我与大数据的邂逅

【网络奇幻之旅】那年我与大数据的邂逅

&#x1f33a;个人主页&#xff1a;Dawn黎明开始 &#x1f380;系列专栏&#xff1a;网络奇幻之旅 ⭐每日一句&#xff1a;循梦而行&#xff0c;向阳而生 &#x1f4e2;欢迎大家&#xff1a;关注&#x1f50d;点赞&#x1f44d;评论&#x1f4dd;收藏⭐️ 文章目录 &#x1f4…
阅读更多...
Mysql的二阶段提交

Mysql的二阶段提交

先看执行器与InnoDB引擎是如何更新一条指定的数据的 可以看到&#xff0c;InnoDB在写redo log时&#xff0c;并不是一次性写完的&#xff0c;而有两个阶段&#xff0c;Prepare与Commit阶段&#xff0c;这就是"两阶段提交"的含义。 为什么要写redo log&#xff0c;不…
阅读更多...
win_sever系列：windows sever 2012R和windows sever 2016如何开启远程连接服务以及问题解决

win_sever系列：windows sever 2012R和windows sever 2016如何开启远程连接服务以及问题解决

windows sever 2012R和windows sever 2016如何开启远程连接服务以及问题解决 一. windows sever 2012R和windows sever 2016如何开启远程连接服务前言一、确保需要进行远程的两个服务器处于同一网段二、关闭防火墙三、需要把被远程的电脑的允许远程打开3.1打开windows sever 20…
阅读更多...
N8975A/安捷伦Agilent N8975A噪声系数分析仪

N8975A/安捷伦Agilent N8975A噪声系数分析仪

181/2461/8938产品概述N8975A是一款高性能噪声系数分析仪 用于进行快速、准确且可重复的噪声系统测量。 N8975A易用的特性能将复杂的测量简单化并让您获得值得信任的可重复且可靠的测量结果。 N8975A可同时提供噪声系数和增益测量&#xff0c;并可以多种格式查看、打印和保存…
阅读更多...
CCFCSP试题编号：202109-2试题名称：非零段划分

CCFCSP试题编号：202109-2试题名称：非零段划分

用差分法 #include<iostream> #include<algorithm> #include<cstring> using namespace std;const int N 500000; const int M 10000; int a[N 2 ] { 0 }; int d[M 1] { 0 };int main() {int n;cin >> n;for (int i 1; i < n; i){cin >&g…
阅读更多...
Android修行手册-溢出父布局的按钮实现点击

Android修行手册-溢出父布局的按钮实现点击

Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列Scratch编程案例软考全系列Unity3D学习专栏蓝桥系列ChatGPT和AIGC &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发