C#實現(xiàn)三元組的使用示例
我們知道矩陣是一個非常強大的數(shù)據(jù)結(jié)構(gòu),在動態(tài)規(guī)劃以及各種圖論算法上都有廣泛的應(yīng)用,當(dāng)然矩陣有著不足的地方就是空間和時間復(fù)雜度都維持在 N2 上,比如 1w 個數(shù)字建立一個矩陣,在內(nèi)存中會占用 1w*1w=1 億的類型空間,這時就會遇到 outofmemory。。。那么面臨的一個問題就是如何來壓縮矩陣,當(dāng)然壓縮的方式有很多種,這里就介紹一個順序表的壓縮方式:三元組。
一、三元組
有時候我們的矩陣中只有零星的一些非零元素,其余的都是零元素,那么我們稱之為稀疏矩陣,當(dāng)然沒有絕對的說有多少個零元素才算稀疏。
針對上面的這個無規(guī)律的存放非零元素,三元組提出了一種方法,就是僅僅記錄矩陣中的非零元素以及它的行,列以及值 N(x,y,v)構(gòu)成的一個三元組,標(biāo)識一個稀疏矩陣的話,還要記錄該矩陣的階數(shù),這樣我們就將一個二維的變成了一個一維,極大的壓縮的存儲空間,這里要注意的就是,三元組的構(gòu)建采用“行“是從上到下,“列”也是從左到右的方式構(gòu)建的順序表。
/// <summary> /// 三元組 /// </summary> public class Unit { public int x; public int y; public int element; } /// <summary> /// 標(biāo)識矩陣 /// </summary> public class SPNode { //矩陣總行數(shù) public int rows; //矩陣總列數(shù) public int cols; //非零元素的個數(shù) public int count; //矩陣中非零元素 public List<Unit> nodes = new List<Unit>(); }
其實說到這里也就差不多了,我們只要知道三元組是用來做矩陣壓縮的一個順序存儲方式即可,然后知道怎么用三元組表來做一些常規(guī)的矩陣運算,好了,既然說已經(jīng)做成線性存儲了,那就做個“行列置換”玩玩。
二、行列置換
做行列置換很容易,也就是交換"非零元素"的(x,y)坐標(biāo),要注意的就是,原先我們的三元組采用的是”行優(yōu)先“,所以在做轉(zhuǎn)置的時候需要遵循"列優(yōu)先“。
/// <summary> /// 行轉(zhuǎn)列運算 /// </summary> /// <param name="spNode"></param> /// <returns></returns> public SPNode ConvertSpNode(SPNode spNode) { //矩陣元素的x和y坐標(biāo)進行交換 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)三元組行的個數(shù) for (int sp = 0; sp < spNode.count; sp++) { var single = spNode.nodes[sp]; //找到三元組中存在的相同編號 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)識矩陣 /// </summary> public class SPNode { //矩陣總行數(shù) public int rows; //矩陣總列數(shù) public int cols; //非零元素的個數(shù) public int count; //矩陣中非零元素 public List<Unit> nodes = new List<Unit>(); } /// <summary> /// 構(gòu)建一個三元組 /// </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; //非零元素的個數(shù) spNode.count = spNode.nodes.Count; return spNode; } /// <summary> /// 行轉(zhuǎn)列運算 /// </summary> /// <param name="spNode"></param> /// <returns></returns> public SPNode ConvertSpNode(SPNode spNode) { //矩陣元素的x和y坐標(biāo)進行交換 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)三元組行的個數(shù) for (int sp = 0; sp < spNode.count; sp++) { var single = spNode.nodes[sp]; //找到三元組中存在的相同編號 if (col == single.y) { spNodeLast.nodes.Add(new Unit() { x = single.y, y = single.x, element = single.element }); } } } return spNodeLast; } } }
到此這篇關(guān)于C#實現(xiàn)三元組的使用示例的文章就介紹到這了,更多相關(guān)C# 三元組內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
silverlight實現(xiàn)圖片局部放大效果的方法
這篇文章主要介紹了silverlight實現(xiàn)圖片局部放大效果的方法,結(jié)合實例形式分析了silverlight針對圖片屬性的相關(guān)操作技巧,需要的朋友可以參考下2017-03-03