稀疏数组

基本原理

当一个数组中大部分元素是一个相同元素时，可以使用稀疏数组来保存该数组，从而减少空间占用。

处理方法

1、记录数组一共有几行几列，有多少个不同的值 2、把具有不同值的元素的行数、列数以及值记录在一个小规模的数组中，从而缩小程序规模

样例

在稀疏数组中，第0行的三个数分别代表原始数组的总行数、总列数以及有效值的个数，其余行的数据分别代表有效值所在的行、列以及值。

代码

转换至稀疏数组

static int[,] CompressArray(int[,] originalArr) { //将二维数组转换为稀疏数组 //1.记录有效值个数 int num = 0; //有效值个数 foreach (var item in originalArr) { if (item != 0) { num++; } } int[,] sparseArray = new int[num + 1, 3]; sparseArray[0, 0] = originalArr.GetLength(0); sparseArray[0, 1] = originalArr.GetLength(1); sparseArray[0, 2] = num; //遍历二维数组，将非零值存入稀疏数组 int cnt = 1; //用于记录第几个非零值 for (int i = 0; i < originalArr.GetLength(0); i++) { for (int j = 0; j < originalArr.GetLength(1); j++) { if (originalArr[i, j] != 0) { sparseArray[cnt, 0] = i; sparseArray[cnt, 1] = j; sparseArray[cnt++, 2] = originalArr[i, j]; } } } return sparseArray; }

稀疏数组转换为原始数组

static int[,] RestoreArray(int[,] sparseArray) { /*将稀疏数组恢复为原始数组 * 1.读取稀疏数组第一行，根据第一行的数据创建原始二维数组 * 2.读取稀疏数组后几行数据，并赋给原始数组即可 */ int[,] restoredArr = new int[sparseArray[0, 0], sparseArray[0, 1]]; for (int i = 1; i <= sparseArray.GetLength(1); i++) { restoredArr[sparseArray[i, 0], sparseArray[i, 1]] = sparseArray[i, 2]; } return restoredArr; }

补充程序

实现目标：

1 使用稀疏数组实现对二维数组的压缩 2.将稀疏数组存入文件中 3.读取文件中的稀疏数组 4.将稀疏数组转换回二维数组

代码

using System; using System.IO; namespace SparseArrayExample2 { class Program { static void Main(string[] args) { int[,] originalArr = { {0,0,0,0,0,0,0,0,0,0,0}, {0,0,4,0,0,0,0,0,0,0,0}, {0,0,0,2,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0}, {0,0,6,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0}, {0,0,6,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0}, {0,0,2,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0} }; Console.WriteLine("原始二维数组"); Traverse(originalArr); int[,] sparseArray = CompressArray(originalArr); #region 将稀疏数组写入txt文件 string[] strs = GetStrings(sparseArray); var path = @"..\..\chestInfo"; if (!Directory.Exists(path)) Directory.CreateDirectory(path); path = Path.Combine(path, "info.txt"); var stream = File.Create(path); var writer = new StreamWriter(stream); for (int i = 0; i < strs.Length; i++) { writer.WriteLine(strs[i]); } writer.Flush(); writer.Close(); #endregion #region 读取txt文件中的稀疏数组 var reader = new StreamReader(path); int sum = 0; string nextLine; while ((nextLine = reader.ReadLine()) != null) { sum++; } reader.BaseStream.Seek(0, SeekOrigin.Begin); //返回文件开始处 int[,] sparseArray2 = new int[sum, 3]; for (int i = 0; i < sum; i++) { string[] temStr = (reader.ReadLine()).Split(' '); for (int j = 0; j < temStr.Length; j++) { sparseArray2[i, j] = Convert.ToInt32(temStr[j]); } } reader.Close(); #endregion Wrap(); int[,] restoredArray = RestoreArray(sparseArray2); Traverse(restoredArray); } //打印分割线 static void Wrap() { for (int i = 0; i < 3; i++) Console.WriteLine(); Console.WriteLine("==================================="); } //将数组压缩为稀疏数组 static int[,] CompressArray(int[,] originalArr) { //将二维数组转换为稀疏数组 //1.记录有效值个数 int num = 0; //有效值个数 foreach (var item in originalArr) { if (item != 0) { num++; } } int[,] sparseArray = new int[num + 1, 3]; sparseArray[0, 0] = 11; sparseArray[0, 1] = 11; sparseArray[0, 2] = num; //遍历二维数组，将非零值存入稀疏数组 int cnt = 1; //用于记录第几个非零值 for (int i = 0; i < originalArr.GetLength(0); i++) { for (int j = 0; j < originalArr.GetLength(1); j++) { if (originalArr[i, j] != 0) { sparseArray[cnt, 0] = i; sparseArray[cnt, 1] = j; sparseArray[cnt++, 2] = originalArr[i, j]; } } } return sparseArray; } //解压稀疏数组 static int[,] RestoreArray(int[,] sparseArray) { /*将稀疏数组恢复为原始数组 * 1.读取稀疏数组第一行，根据第一行的数据创建原始二维数组 * 2.读取稀疏数组后几行数据，并赋给原始数组即可 */ int[,] restoredArr = new int[sparseArray[0, 0], sparseArray[0, 1]]; for (int i = 1; i <= sparseArray.GetLength(1); i++) { restoredArr[sparseArray[i, 0], sparseArray[i, 1]] = sparseArray[i, 2]; } return restoredArr; } //遍历二维数组 static void Traverse(int[,] arr) { for (int i = 0; i < arr.GetLength(0); i++) { for (int j = 0; j < arr.GetLength(1); j++) { Console.Write($"{arr[i, j]} "); } Console.WriteLine(); } } //将二维数组转换成字符串数组 static string[] GetStrings(int[,] arr) { string[] str = new string[arr.GetLength(0)]; for (int i = 0; i < arr.GetLength(0); i++) { for (int j = 0; j < arr.GetLength(1); j++) { if (j != arr.GetLength(1) - 1) str[i] += arr[i, j].ToString() + " "; else str[i] += arr[i, j].ToString(); } } return str; } } }