首页 > 代码库 > 经典算法题每日演练——第二十题 三元组
经典算法题每日演练——第二十题 三元组
原文:经典算法题每日演练——第二十题 三元组
View Code
我们知道矩阵是一个非常强大的数据结构，在动态规划以及各种图论算法上都有广泛的应用，当然矩阵有着不足的地方就是空间和时间
复杂度都维持在N2上，比如1w个数字建立一个矩阵，在内存中会占用1w*1w=1亿的类型空间，这时就会遇到outofmemory。。。那么面
临的一个问题就是如何来压缩矩阵，当然压缩的方式有很多种，这里就介绍一个顺序表的压缩方式：三元组。
一：三元组
有时候我们的矩阵中只有零星的一些非零元素，其余的都是零元素，那么我们称之为稀疏矩阵，当然没有绝对的说有多少个零元素才算稀疏。
针对上面的这个无规律的存放非零元素，三元组提出了一种方法，就是仅仅记录矩阵中的非零元素以及它的行，列以及值N(x,y,v)构成的一个三元
组，标识一个稀疏矩阵的话，还要记录该矩阵的阶数，这样我们就将一个二维的变成了一个一维，极大的压缩的存储空间，这里要注意的就是，三
元组的构建采用“行“是从上到下，“列”也是从左到右的方式构建的顺序表。
1 /// <summary> 2 /// 三元组 3 /// </summary> 4 public class Unit 5 { 6 public int x; 7 public int y; 8 public int element; 9 }10 11 /// <summary>12 /// 标识矩阵13 /// </summary>14 public class SPNode15 {16 //矩阵总行数17 public int rows;18 19 //矩阵总列数20 public int cols;21 22 //非零元素的个数23 public int count;24 25 //矩阵中非零元素26 public List<Unit> nodes = new List<Unit>();27 }
其实说到这里也就差不多了，我们只要知道三元组是用来做矩阵压缩的一个顺序存储方式即可，然后知道怎么用三元组表来做一些常规的矩阵
运算，好了，既然说已经做成线性存储了，那就做个“行列置换”玩玩。
二：行列置换
做行列置换很容易，也就是交换"非零元素"的(x,y)坐标，要注意的就是，原先我们的三元组采用的是”行优先“，所以在做转置的时候需要
遵循"列优先“。
1 /// <summary> 2 /// 行转列运算 3 /// </summary> 4 /// <param name="spNode"></param> 5 /// <returns></returns> 6 public SPNode ConvertSpNode(SPNode spNode) 7 { 8 //矩阵元素的x和y坐标进行交换 9 SPNode spNodeLast = new SPNode();10 11 //行列互换12 spNodeLast.rows = spNode.cols;13 spNodeLast.cols = spNode.rows;14 spNodeLast.count = spNode.count;15 16 //循环原矩阵的列数 (行列转换)17 for (int col = 0; col < spNode.cols; col++)18 {19 //循环三元组行的个数20 for (int sp = 0; sp < spNode.count; sp++)21 {22 var single = spNode.nodes[sp];23 24 //找到三元组中存在的相同编号25 if (col == single.y)26 {27 spNodeLast.nodes.Add(new Unit()28 {29 x = single.y,30 y = single.x,31 element = single.element32 });33 }34 }35 }36 37 return spNodeLast;38 }
最后是总的代码:
View Code 
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Diagnostics; 6 using System.Threading; 7 using System.IO; 8 9 namespace ConsoleApplication2 10 { 11 public class Program 12 { 13 public static void Main() 14 { 15 Martix martix = new Martix(); 16 17 //构建三元组 18 var node = martix.Build(); 19 20 foreach (var item in node.nodes) 21 { 22 Console.WriteLine(item.x + "\t" + item.y + "\t" + item.element); 23 } 24 25 Console.WriteLine("******************************************************"); 26 27 var mynode = martix.ConvertSpNode(node); 28 29 foreach (var item in mynode.nodes) 30 { 31 Console.WriteLine(item.x + "\t" + item.y + "\t" + item.element); 32 } 33 34 Console.Read(); 35 } 36 } 37 38 public class Martix 39 { 40 /// <summary> 41 /// 三元组 42 /// </summary> 43 public class Unit 44 { 45 public int x; 46 public int y; 47 public int element; 48 } 49 50 /// <summary> 51 /// 标识矩阵 52 /// </summary> 53 public class SPNode 54 { 55 //矩阵总行数 56 public int rows; 57 58 //矩阵总列数 59 public int cols; 60 61 //非零元素的个数 62 public int count; 63 64 //矩阵中非零元素 65 public List<Unit> nodes = new List<Unit>(); 66 } 67 68 /// <summary> 69 /// 构建一个三元组 70 /// </summary> 71 /// <returns></returns> 72 public SPNode Build() 73 { 74 SPNode spNode = new SPNode(); 75 76 //遵循行优先的原则 77 spNode.nodes.Add(new Unit() { x = 0, y = 0, element = 8 }); 78 spNode.nodes.Add(new Unit() { x = 1, y = 2, element = 1 }); 79 spNode.nodes.Add(new Unit() { x = 2, y = 3, element = 6 }); 80 spNode.nodes.Add(new Unit() { x = 3, y = 1, element = 4 }); 81 82 //4阶矩阵 83 spNode.rows = spNode.cols = 4; 84 85 //非零元素的个数 86 spNode.count = spNode.nodes.Count; 87 88 return spNode; 89 } 90 91 /// <summary> 92 /// 行转列运算 93 /// </summary> 94 /// <param name="spNode"></param> 95 /// <returns></returns> 96 public SPNode ConvertSpNode(SPNode spNode) 97 { 98 //矩阵元素的x和y坐标进行交换 99 SPNode spNodeLast = new SPNode();100 101 //行列互换102 spNodeLast.rows = spNode.cols;103 spNodeLast.cols = spNode.rows;104 spNodeLast.count = spNode.count;105 106 //循环原矩阵的列数 (行列转换)107 for (int col = 0; col < spNode.cols; col++)108 {109 //循环三元组行的个数110 for (int sp = 0; sp < spNode.count; sp++)111 {112 var single = spNode.nodes[sp];113 114 //找到三元组中存在的相同编号115 if (col == single.y)116 {117 spNodeLast.nodes.Add(new Unit()118 {119 x = single.y,120 y = single.x,121 element = single.element122 });123 }124 }125 }126 127 return spNodeLast;128 }129 }130 }
经典算法题每日演练——第二十题 三元组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。