C#實(shí)現(xiàn)三元組的使用示例

更新時(shí)間：2023年11月28日 10:15:36 作者：神仙別鬧

本文介紹了C#中的三元組數(shù)據(jù)結(jié)構(gòu),以及如何使用三元組在C#中進(jìn)行一些特定的計(jì)算,具有一定的參考價(jià)值,感興趣的可以了解一下

我們知道矩陣是一個(gè)非常強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，在動(dòng)態(tài)規(guī)劃以及各種圖論算法上都有廣泛的應(yīng)用，當(dāng)然矩陣有著不足的地方就是空間和時(shí)間復(fù)雜度都維持在 N2 上，比如 1w 個(gè)數(shù)字建立一個(gè)矩陣，在內(nèi)存中會(huì)占用 1w*1w=1 億的類型空間，這時(shí)就會(huì)遇到 outofmemory。。。那么面臨的一個(gè)問(wèn)題就是如何來(lái)壓縮矩陣，當(dāng)然壓縮的方式有很多種，這里就介紹一個(gè)順序表的壓縮方式：三元組。

一、三元組

有時(shí)候我們的矩陣中只有零星的一些非零元素，其余的都是零元素，那么我們稱之為稀疏矩陣，當(dāng)然沒有絕對(duì)的說(shuō)有多少個(gè)零元素才算稀疏。

針對(duì)上面的這個(gè)無(wú)規(guī)律的存放非零元素，三元組提出了一種方法，就是僅僅記錄矩陣中的非零元素以及它的行，列以及值 N(x,y,v)構(gòu)成的一個(gè)三元組，標(biāo)識(shí)一個(gè)稀疏矩陣的話，還要記錄該矩陣的階數(shù)，這樣我們就將一個(gè)二維的變成了一個(gè)一維，極大的壓縮的存儲(chǔ)空間，這里要注意的就是，三元組的構(gòu)建采用“行“是從上到下，“列”也是從左到右的方式構(gòu)建的順序表。

 /// <summary>
 /// 三元組
 /// </summary>
 public class Unit
 {
     public int x;
     public int y;
     public int element;
 }

 /// <summary>
 /// 標(biāo)識(shí)矩陣
 /// </summary>
 public class SPNode
 {
     //矩陣總行數(shù)
     public int rows;

     //矩陣總列數(shù)
     public int cols;

     //非零元素的個(gè)數(shù)
     public int count;

     //矩陣中非零元素
     public List<Unit> nodes = new List<Unit>();
 }

其實(shí)說(shuō)到這里也就差不多了，我們只要知道三元組是用來(lái)做矩陣壓縮的一個(gè)順序存儲(chǔ)方式即可，然后知道怎么用三元組表來(lái)做一些常規(guī)的矩陣運(yùn)算，好了，既然說(shuō)已經(jīng)做成線性存儲(chǔ)了，那就做個(gè)“行列置換”玩玩。

二、行列置換

做行列置換很容易，也就是交換"非零元素"的(x,y)坐標(biāo)，要注意的就是，原先我們的三元組采用的是”行優(yōu)先“，所以在做轉(zhuǎn)置的時(shí)候需要遵循"列優(yōu)先“。

 /// <summary>
 /// 行轉(zhuǎn)列運(yùn)算
 /// </summary>
 /// <param name="spNode"></param>
 /// <returns></returns>
 public SPNode ConvertSpNode(SPNode spNode)
 {
     //矩陣元素的x和y坐標(biāo)進(jìn)行交換
     SPNode spNodeLast = new SPNode();

     //行列互換
     spNodeLast.rows = spNode.cols;
     spNodeLast.cols = spNode.rows;
     spNodeLast.count = spNode.count;

     //循環(huán)原矩陣的列數(shù) (行列轉(zhuǎn)換)
     for (int col = 0; col < spNode.cols; col++)
     {
         //循環(huán)三元組行的個(gè)數(shù)
         for (int sp = 0; sp < spNode.count; sp++)
         {
             var single = spNode.nodes[sp];

             //找到三元組中存在的相同編號(hào)
             if (col == single.y)
             {
                 spNodeLast.nodes.Add(new Unit()
                 {
                     x = single.y,
                     y = single.x,
                     element = single.element
                 });
             }
         }
     }

     return spNodeLast;
 }

最后是總的代碼:

 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()
         {
            Martix martix = new Martix();
 
             //構(gòu)建三元組
             var node = martix.Build();
 
             foreach (var item in node.nodes)
             {
                 Console.WriteLine(item.x + "\t" + item.y + "\t" + item.element);
             }
 
             Console.WriteLine("******************************************************");
 
             var mynode = martix.ConvertSpNode(node);
 
             foreach (var item in mynode.nodes)
             {
                 Console.WriteLine(item.x + "\t" + item.y + "\t" + item.element);
             }
 
             Console.Read();
         }
     }
 
     public class Martix
     {
         /// <summary>
         /// 三元組
         /// </summary>
         public class Unit
         {
             public int x;
             public int y;
             public int element;
         }
 
         /// <summary>
         /// 標(biāo)識(shí)矩陣
         /// </summary>
         public class SPNode
         {
             //矩陣總行數(shù)
             public int rows;
 
             //矩陣總列數(shù)
             public int cols;
 
             //非零元素的個(gè)數(shù)
             public int count;
 
             //矩陣中非零元素
             public List<Unit> nodes = new List<Unit>();
         }
 
         /// <summary>
         /// 構(gòu)建一個(gè)三元組
         /// </summary>
         /// <returns></returns>
         public SPNode Build()
         {
             SPNode spNode = new SPNode();
 
             //遵循行優(yōu)先的原則
             spNode.nodes.Add(new Unit() { x = 0, y = 0, element = 8 });
             spNode.nodes.Add(new Unit() { x = 1, y = 2, element = 1 });
             spNode.nodes.Add(new Unit() { x = 2, y = 3, element = 6 });
             spNode.nodes.Add(new Unit() { x = 3, y = 1, element = 4 });
 
             //4階矩陣
             spNode.rows = spNode.cols = 4;
 
             //非零元素的個(gè)數(shù)
             spNode.count = spNode.nodes.Count;
 
             return spNode;
         }
 
         /// <summary>
         /// 行轉(zhuǎn)列運(yùn)算
         /// </summary>
         /// <param name="spNode"></param>
         /// <returns></returns>
         public SPNode ConvertSpNode(SPNode spNode)
         {
             //矩陣元素的x和y坐標(biāo)進(jìn)行交換
             SPNode spNodeLast = new SPNode();
 
             //行列互換
             spNodeLast.rows = spNode.cols;
             spNodeLast.cols = spNode.rows;
             spNodeLast.count = spNode.count;
 
             //循環(huán)原矩陣的列數(shù) (行列轉(zhuǎn)換)
             for (int col = 0; col < spNode.cols; col++)
             {
                 //循環(huán)三元組行的個(gè)數(shù)
                 for (int sp = 0; sp < spNode.count; sp++)
                 {
                     var single = spNode.nodes[sp];
 
                     //找到三元組中存在的相同編號(hào)
                     if (col == single.y)
                     {
                         spNodeLast.nodes.Add(new Unit()
                         {
                             x = single.y,
                             y = single.x,
                             element = single.element
                         });
                     }
                 }
             }
 
             return spNodeLast;
         }
     }
 }