数据结构与算法学习笔记之稀疏数组数据结构与算法weixin45765809的博客-

数据结构与算法学习笔记之稀疏数组

我是阿尘。一个不想被生活放弃的野鬼。

最近在小破站找了韩顺平老师的视频，准备跟着复习一下数据结构和算法，常说好记性不如烂笔头，学过之后还是写点笔记的好。

关于稀疏数组

稀疏数组(sparse array) 是一种只为数组中的 非零元素分配内存的特殊类型数组，内存中存储了稀疏数组中非零元素的下标和值。

稀疏数组实际上就是对普通二维数组的压缩形式，当一个数组中大部分元素为0或者为同一个值时，可以使用稀疏数组来保存该数组。

稀疏数组是一个N行3列的二维数组：

1. 第一行记录普通二维数组的行数、列数和有效数据的个数
2. 剩下的N-1行记录每个有效数据所在二维数组的行数、列数和具体的值
3. 所以稀疏数组的行数N等于有效数据的个数+1

举个栗子！

1. 先创建一个8行8列的普通二维数组并给其赋值

// 创建一个二维数组 int generalArr1[][] = new int[8][8]; generalArr1[1][2] = 1; generalArr1[2][3] = 2; generalArr1[2][2] = 1; 

​ 这个数组的打印出来的样式

// 遍历二维数组并输出 for (int[] rows : generalArr1) { for (int data : rows) {         System.out.printf("%dt", data); }     System.out.println(); } 

2. 将此二维数组转换成稀疏数组

// 二维数组转稀疏数组 // 1.遍历二维数组，得到有效数据的个数 int sum = 0;// 初始化有效数据的个数 for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (generalArr1[i][j] != 0) {             sum++; } } } // 2.创建稀疏数组 int sparseArr[][] = new int[sum + 1][3]; sparseArr[0][0] = 8; sparseArr[0][1] = 8; sparseArr[0][2] = sum; // 3.遍历二维数组，将非零数据存入sparseArr中 int count = 0; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (generalArr1[i][j] != 0) {             count++;             sparseArr[count][0] = i;             sparseArr[count][1] = j;             sparseArr[count][2] = generalArr1[i][j]; } } } 

转换后的稀疏数组

// 3.输出稀疏数组 for (int i = 0; i < sparseArr.length; i++) {     System.out.printf("%dt%dt%dtn", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]); } 

3. 稀疏数组转回二维数组

// 稀疏数组转二维数组 // 1.创建一个二维数组 int generalArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]]; // 2.读取稀疏数组的数据并赋给二维数组 for (int i = 1; i < sparseArr.length; i++) {     generalArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; } 

总结一下

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

1. 遍历二维数组得到有效数据的个数sum
2. 得到sum之后就可以创建稀疏数组sparseArr[sum+1][3]
3. 将二维数组的行数、列数和有效数据个数存入稀疏数组的第一行
4. 将二维数组的有效数据所在行数、列数和值存入之后的行

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

1. 读取稀疏数组第一行，根据第一行的数据创建二维数组generalArr2[sparseArr[0][0]] [sparseArr[0][1]]

2. 读取稀疏数组后几行的数据赋给二维数组

3. 读取稀疏数组第一行，根据第一行的数据创建二维数组generalArr2[sparseArr[0][0]] [sparseArr[0][1]]

4. 读取稀疏数组后几行的数据赋给二维数组