C#数据结构-稀疏数组

目录

一.稀疏数组的引入（一个实际需求）

二.稀疏数组的处理方法

 三.用代码演示稀疏数组

1.思路

2.代码演示

---

一.稀疏数组的引入（一个实际需求）

这个棋盘首先考虑用二维数组存放，当你需要存放一个数组时，这数据有点多，这么多0，就想能不能简化一下存储，不占用那么多空间，那么我们可以用稀疏数组来解决，稀疏数组可以理解成是一个压缩和解压的过程。

二.稀疏数组的处理方法

1.记录数组一共有几行几列，有多少个不同的值

2.把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

下面来具体说明一下怎么处理：

比如下面这个数组怎么转换为稀疏数组

稀疏数组只有三列，行数为非0元素个数+1，稀疏数组的第一行第一列表示原数组的总行数，第一行第二列表示原数组的总列数，第一行第三列表示一共有几个非0元素。

稀疏数组从第二行开始，每一行的第二列第三列用来表示某个值在原数组的位置，第三列用来表示原数组的位置对应的某个值。

例如下面图片的第二行 0 3 22，表示的意思是：在原数组中，22这个元素的位置为（0，3）。第二行往后都一样的意思。

上面那个数组转换成稀疏数组就是下面这样

 

 三.用代码演示稀疏数组 1.思路

二维数组转稀疏数组思路：

1.首先需要遍历二维数组，得到有效数据（非0元素）个数sum

2.根据sum创建稀疏数组，稀疏数组行数为sum+1，列数为3

3.把二维数组的有效数据存入到稀疏数组

稀疏数组转二维数组思路：

1.读取稀疏数组第一行，根据第一行的数据，创建二维数组

2.继续读取后几行，用来赋给二维数组原始值

2.代码演示

 using System;

namespace _1稀疏数组SparseArray
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] chessArr1 = new int[11, 11];
            int chessLength1 = chessArr1.GetLength(0);
            int chessLength2 = chessArr1.GetLength(1);
            chessArr1[1, 2] = 1;
            chessArr1[2, 3] = 2;
            //输出原始的二维数组
            for (int i = 0; i < chessLength1; i++)
            {
                for (int j = 0; j < chessLength2; j++)
                {
                    Console.Write(chessArr1[i, j] + " ");
                }
                Console.WriteLine();
            }
            //将二维数组转为稀疏数组
            //1.得到非0元个数
            int sum = 0;
            for (int i = 0; i < chessLength1; i++)
            {
                for (int j = 0; j < chessLength2; j++)
                {
                    if (chessArr1[i, j] != 0)
                        sum++;
                }
            }
            //2.创建对应的稀疏数组
            int[,] sparseArr = new int[sum + 1, 3];
            int sparseLength = sparseArr.GetLength(0);
            sparseArr[0, 0] = chessLength1;
            sparseArr[0, 1] = chessLength2;
            sparseArr[0, 2] = sum;
            int count = 0;
            for (int i = 0; i < chessLength1; i++)
            {
                for (int j = 0; j < chessLength2; j++)
                {
                    if (chessArr1[i, j] != 0)
                    {
                        count++;
                        sparseArr[count, 0] = i;
                        sparseArr[count, 1] = j;
                        sparseArr[count, 2] = chessArr1[i, j];
                    }
                }
            }
            //输出稀疏数组
            for (int i = 0; i < sparseLength; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    
                    Console.Write("{0,2}",sparseArr[i, j]);
                    Console.Write("   ");
                }
                Console.WriteLine();
            }
            //稀疏数组恢复成原来的二维数组
            //1.根据稀疏数组第一行创建二维数组
            int[,] chessArr2 = new int[sparseArr[0, 0], sparseArr[0, 1]];
            //2.根据稀疏数组后面的行恢复二维数组
            for (int i = 1; i < sparseArr.GetLength(0); i++)
            {
                chessArr2[sparseArr[i, 0], sparseArr[i, 1]] = sparseArr[i, 2];
            }
            //恢复后的二维数组
            for (int i = 0; i < chessArr2.GetLength(0); i++)
            {
                for (int j = 0; j < chessArr2.GetLength(1); j++)
                {
                    Console.Write(chessArr2[i, j] + " ");
                }
                Console.WriteLine();
            }
        }
    }
}