数据结构稀疏矩阵的三元组转置,数据结构稀疏矩阵的应用

稀疏矩阵稀疏矩阵的定义与操作稀疏矩阵的定义：若矩阵A中非0元素的个数远远小于零元素的个数，则称A为稀疏矩阵
稀疏矩阵的操作获取矩阵的行数获取矩阵的列数获取或设置指定索引处的元素矩阵加法矩阵转置矩阵乘法
using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace DataStruct2020.demo{ public interface IMatrix<T> { int Cols { get; } int Rows { get; } T this[int i, int c] { get;set; } IMatrix<T> Add(IMatrix<T> b); IMatrix<T> Multiply(IMatrix<T> b); IMatrix<T> Transpoese(); }} 稀疏矩阵的存储与实现可以利用Row,Col,Value的方式存储和定位稀疏矩阵中的非零元素，这种存储稀疏矩阵结点的方式称为三元组Triple
顺序存储
链式存储

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace DataStruct2020.demo{ public class Triple { private int _col; private int _row; private double _value; public int Col { get { return _col; } } public int Row { get { return _row; } } public double Value { get { return _value; } set { _value = value; } } public Triple(int i, int j, double value) { if (i < 0 || j < 0) throw new ArgumentOutOfRangeException(); _row = i; _col = j; _value = value; } public int CompareTo(Triple other) { if (_value < other._value) return -1; if (_value > other._value) return 1; return 0; } public override string ToString() { return string.Format("{0},{1},{2}", _row, _col, _value); } }} using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;namespace DataStruct2020.demo{ public class SparseMatrix : IMatrix<double> { private SLinkList<Triple> _lst; private int _rows; private int _cols; public int Rows { get { return _rows; } } public int Cols { get { return _cols; } } public SparseMatrix(int rows, int cols) { if (rows <= 0 || cols <= 0) throw new ArgumentOutOfRangeException(); _rows = rows; _cols = cols; _lst = new SLinkList<Triple>(); } private int GetIndex(int i, int j) { if (i < 0 || i > _rows - 1 || j < 0 || j > Cols - 1) throw new ArgumentOutOfRangeException(); SNode<Triple> temp = _lst.PHead; int result = 0; while (temp != null) { if (temp.Data.Row == i && temp.Data.Col == j) break; temp = temp.Next; result++; } return result == _lst.Length ? -1 : result; } public double this[int i, int j] { get { if (i < 0 || i > _rows - 1 || j < 0 || j > Cols - 1) throw new ArgumentOutOfRangeException(); int index = GetIndex(i, j); if (index == -1) return 0.0; return _lst[index].Value; } set { if (i < 0 || i > _rows - 1 || j < 0 || j > Cols - 1) throw new ArgumentOutOfRangeException(); int index = GetIndex(i, j); if (index == -1) { if (value != 0.0) _lst.InsertAtRear(new Triple(i, j, value)); } else { if (value != 0.0) _lst[index].Value = value; else _lst.Remove(index); } } } public SparseMatrix Add(SparseMatrix b) { if (b == null) throw new ArgumentNullException(); if (_rows != b.Rows || _cols != b.Cols) throw new Exception("两个矩阵不能进行加法"); SparseMatrix result = new SparseMatrix(_rows, _cols); for (int i = 0; i < _rows; i++) for (int j = 0; j < _cols; j++) result[i, j] = this[i, j苹果美女 b[i, j]; return result; } public SparseMatrix Multiply(SparseMatrix b) { if (b == null) throw new ArgumentNullException(); if (_cols != b.Rows) throw new Exception("两个矩阵不能做乘法"); SparseMatrix result = new SparseMatrix(_rows, b._cols); for (int i = 0; i < _rows; i++) { for (int j = 0; j < b._cols; j++) { result[i, j] = 0; for (int k = 0; k < _cols; k++) { result[i, j苹果美女= this[i, k] * b[k, j]; } } } return result; } public SparseMatrix Transpose() { SparseMatrix result = new SparseMatrix(_cols, _rows); for (int i = 0; i < _cols; i++) { for (int j = 0; j < _rows; j++) result[i, j] = this[j, i]; } return result; } public static SparseMatrix operator wydcc, SparseMatrix b) { if (a == null || b == null) throw new ArgumentNullException(); return a.Add(b); } public static SparseMatrix operator *(SparseMatrix a, SparseMatrix b) { if (a == null || b == null) throw new ArgumentNullException(); return a.Multiply(b); } IMatrix<double> IMatrix<double>.Add(IMatrix<double> b) { if (b == null) throw new ArgumentNullException(); return Add((SparseMatrix)b); } IMatrix<double> IMatrix<double>.Multiple(IMatrix<double> b) { if (b == null) throw new ArgumentNullException(); return Multiply((SparseMatrix)b); } IMatrix<double> IMatrix<double>.Transpose() { return Transpose(); } public override string ToString() { string result = string.Empty; for (int i = 0; i < _lst.Length; i++) { result += _lst[i苹果美女 "n"; } return result; } }} //客户端 IMatrix<double> a = new SparseMatrix(2, 3); IMatrix<double> b = new SparseMatrix(3, 2); SparseMatrix c = new SparseMatrix(2, 2); a[0, 2] = 1; a[1, 0] = 1; b[1, 1] = 4; b[2, 0] = 1; c[0, 1] = 1; c[1, 0] = 1; SparseMatrix d = (SparseMatrix)a * (SparseMatrix)b + c; IMatrix<double> e = a.Multiple(b).Add(c); Console.WriteLine("D:n{0}", d); Console.WriteLine("E:n{0}", e);