第二十题 三元组

我们知道矩阵是一个非常强大的数据结构，在动态规划以及各种图论算法上都有广泛的应用，当然矩阵有着不足的地方就是空间和时间 复杂度都维持在N2上，比如1w个数字建立一个矩阵，在内存中会占用1w*1w=1亿的类型空间，这时就会遇到outofmemory。。。那么面

临的一个问题就是如何来压缩矩阵，当然压缩的方式有很多种，这里就介绍一个顺序表的压缩方式：三元组。

一：三元组

  1.  有时候我们的矩阵中只有零星的一些非零元素，其余的都是零元素，那么我们称之为稀疏矩阵，当然没有绝对的说有多少个零元素才算稀疏。

第二十题 三元组 - 图1

针对上面的这个无规律的存放非零元素，三元组提出了一种方法，就是仅仅记录矩阵中的非零元素以及它的行，列以及值N(x,y,v)构成的一个三元

组，标识一个稀疏矩阵的话，还要记录该矩阵的阶数，这样我们就将一个二维的变成了一个一维，极大的压缩的存储空间，这里要注意的就是，三

元组的构建采用“行“是从上到下，“列”也是从左到右的方式构建的顺序表。

其实说到这里也就差不多了，我们只要知道三元组是用来做矩阵压缩的一个顺序存储方式即可，然后知道怎么用三元组表来做一些常规的矩阵

运算，好了，既然说已经做成线性存储了，那就做个“行列置换”玩玩。

二：行列置换

  1.  做行列置换很容易，也就是交换"非零元素"的(x,y)坐标，要注意的就是，原先我们的三元组采用的是”行优先“，所以在做转置的时候需要

遵循"列优先“。

第二十题 三元组 - 图2 

  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.element
  32.                         });
  33.                     }
  34.                 }
  35.             }
  36.  
  37.             return spNodeLast;
  38.         }

最后是总的代码: 

  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.element
  122.                         });
  123.                     }
  124.                 }
  125.             }
  126.  
  127.             return spNodeLast;
  128.         }
  129.     }
  130. }

第二十题 三元组 - 图3