原文:
经典算法题每日演练——第二十题 三元组
我们知道矩阵是一个非常强大的数据结构，在动态规划以及各种图论算法上都有广泛的应用，当然矩阵有着不足的地方就是空间和时间
复杂度都维持在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 SPNode
15 {
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.element
32 });
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.element
122 });
123 }
124 }
125 }
126
127 return spNodeLast;
128 }
129 }
130 }
