小说投稿赚钱的网站,黑客基础菜鸟入门教程,做网站公司需要准备资料,宁波知名seo关键词优化上一篇我们看了矩阵的顺序存储#xff0c;这篇我们再看看一种链式存储方法“十字链表”#xff0c;当然目的都是一样#xff0c;压缩空间。
一、概念
既然要用链表节点来模拟矩阵中的非零元素#xff0c;肯定需要如下 5 个元素(row,col,val,down,right)#xff0c;其中这篇我们再看看一种链式存储方法“十字链表”当然目的都是一样压缩空间。
一、概念
既然要用链表节点来模拟矩阵中的非零元素肯定需要如下 5 个元素(row,col,val,down,right)其中
row:矩阵中的行。
col:矩阵中的列。
val:矩阵中的值。
right:指向右侧的一个非零元素。
down指向下侧的一个非零元素。现在我们知道单个节点该如何表示了那么矩阵中同行的非零元素的表示不就是一个单链表吗比如如下 那么进一步来说一个多行的非零元素的表示不就是多个单链表吗是的这里我把单链表做成循环链表我们来看看如何用十字链表来表示稀疏矩阵。 从上面的十字链表中要注意两个问题 第一这里有一个填充色的节点是十字链表中的总结点它是记录该矩阵中的row,col,value和一个指向下一个头节点的 next 指针。 第二每个链表都有一个头指针总结点用 next 指针将它们贯穿起来。
二、操作
2.1、数据结构
刚才也说了十字链表的总结点有一个 next 指针而其他非零节点没有所以为了方便我们用一个 Unit 类包装起来。 #region 单一节点/// summary/// 单一节点/// /summarypublic class Node{//行号public int rows;//列号public int cols;//向下的指针域public Node down;//向右的指针域public Node right;//单元值头指针的next和valpublic Unit unit;}#endregion#region 统一“表头节点”和“非零节点”/// summary/// 统一“表头节点”和“非零节点”/// /summarypublic class Unit{//表头节点的next域public Node next;//非零元素的值public int value;}#endregion2.2、初始化
这一步我们初始化总结点并且用 next 指针将每个单链表的头节点链接成单链表也就是上图中十字链表的第一行
#region 十字链表中的“行数列数非零元素个数”/// summary/// 十字链表中的“行数列数非零元素个数”/// /summary/// param namerows/param/// param namecols/param/// param namecount/parampublic 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];}}#endregion2.3、插入节点
根据插入节点的 row 和 col 将节点插入到十字链表中指定的位置即可。
#region 插入十字链表中/// summary/// 插入十字链表中/// /summary/// param namenums矩阵/param/// param namerows矩阵的行数/param/// param namecols矩阵的列数/param/// param namecount非0元素个数/param/// returns/returnspublic 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;}#endregion2.4、打印链表
我们只要遍历每行链表的 right 指针即可。
#region 打印十字链表/// summary/// 打印十字链表/// /summary/// param namenodes/parampublic 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;}}}#endregion2.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/// 十字链表/// /summarypublic class Crosslist{#region 单一节点/// summary/// 单一节点/// /summarypublic class Node{//行号public int rows;//列号public int cols;//向下的指针域public Node down;//向右的指针域public Node right;//单元值头指针的next和valpublic Unit unit;}#endregion#region 统一“表头节点”和“非零节点”/// summary/// 统一“表头节点”和“非零节点”/// /summarypublic class Unit{//表头节点的next域public Node next;//非零元素的值public int value;}#endregionNode[] nodes;#region 十字链表中的“行数列数非零元素个数”/// summary/// 十字链表中的“行数列数非零元素个数”/// /summary/// param namerows/param/// param namecols/param/// param namecount/parampublic 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 namenode/param/// returns/returnspublic 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 namenums矩阵/param/// param namerows矩阵的行数/param/// param namecols矩阵的列数/param/// param namecount非0元素个数/param/// returns/returnspublic 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 namenodes/parampublic 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}}
