C#資料結構-稀疏矩陣

了解稀疏矩陣之前，我們先聊聊數組，數組都清楚string[10] str;這裡的str就是一個數組，它的存儲方式是str[0],str[1],str[2]...這樣，放在一個連續存儲空間裡面。。那麼同樣的，二維數組我們這裡stirng[2][2] str;，它的存儲結構也是一個順序存儲，是以我們這裡把這個str的2*2寫全，str[0][0],str[0][1],str[1][0],str[1][1]這樣。。。 二維數組通常稱為矩陣，so，矩陣跟稀疏矩陣文字上面是非常相近了

，稀疏：我們可以認為是少，什麼少，數組裡面隻有元素...so，元素非常少的矩陣就是稀疏矩陣。比如說100*100的矩陣，裡面不為0的元素隻有100個，那麼我們可以稱為他是稀疏矩陣，也就是有效元素遠小于總元素的時候，我們可以稱為稀疏矩陣。 稀疏矩陣的特點： 1.非0（有效）元素非常少

2.排列沒有規律

根據這些特點，我們存儲稀疏矩陣元素的時候會以:行号,列号,元素（i,j,a）這樣的三元組存儲，接下來我們對稀疏矩陣的一些操作。

首先建立資料：

/// <summary>
    /// 一個三元組類型
    /// </summary>
    public struct TupNode
    {
        //行号
        public int r;
        //列号
        public int c;
        //元素值
        public int d;
    }
    /// <summary>
    /// 稀疏矩陣順序表
    /// </summary>
    public struct TupSparseMatrix
    {
        //行數
        public int rows;
        //列數
        public int cols;
        //非0元素個數
        public int nums;
        public TupNode[] data;
    }
           

然後就是操作了

/// <summary>
    /// 稀疏矩陣的操作
    /// </summary>
    class SparseMatrixClass
    {
        readonly int MaxSize = 100;
        public TupSparseMatrix trip;
        public SparseMatrixClass()
        {
            trip = new TupSparseMatrix();
            trip.data = new TupNode[MaxSize];
        }
        #region 把二維數組（矩陣）轉換成三元組
        public void CreateTupSparseMatrix(int[,] matrix)
        {
            //GetLength是求次元的個數，從0開始
            trip.rows = matrix.GetLength(0);
            trip.cols = matrix.GetLength(1);
            trip.nums = 0;

            //周遊這個二維數組
            for (int i = 0; i < trip.rows; i++)
            {
                for (int j = 0; j < trip.cols; j++)
                {
                    //不等于0并且存儲數量不超過存儲數量的存儲
                    if (matrix[i, j] != 0 && MaxSize > trip.nums)
                    {
                        trip.data[trip.nums].r = i;
                        trip.data[trip.nums].c = j;
                        trip.data[trip.nums].d = matrix[i, j];
                        trip.nums++;
                    }
                }
            }
        }
        #endregion

        #region 輸出三元組（i，j，d）
        public string DispTupSparseMatrix()
        {
            string tupStr = "";
            for (int i = 0; i < trip.nums; i++)
            {
                tupStr += string.Format("({0},{1},{2})", trip.data[i].r, trip.data[i].c, trip.data[i].d);
            }
            return tupStr;
        }
        #endregion

        #region 矩陣轉置,這裡稍微優化了下
        public void Transpose(ref SparseMatrixClass tb)
        {
            SparseMatrixClass sm = new SparseMatrixClass();
            sm.trip.rows = tb.trip.cols;
            sm.trip.cols = tb.trip.rows;
            sm.trip.nums = tb.trip.nums;
            //置換
            for (int i = tb.trip.nums; i >0; i--)
            {
                sm.trip.data[i].r = tb.trip.data[i].c;
                sm.trip.data[i].c = tb.trip.data[i].r;
                sm.trip.data[i].d = tb.trip.data[i].d;
            }
            tb = sm;
        }
        #endregion
    }