稀疏数组(1种数据结构)
把棋盘转变为二维数组存储 黑棋用1代表,白棋用2代表
11行11列 有效数字2个
[0] 11行 11列 2(有效数字)
[1] 1行 2列 1值
[2] 2行 3列 2值 对稀疏数组的数组来说就是3行(有效数字2个+1,[0],[1],[2]即3行)
列数就是固定3列(行、列、值)
int[][] array1 = new int[11][11];//11*11的五子棋盘 把[0]新建
array1[1][2] = 1;//定义第一个值 黑棋
array1[2][3] = 2;//定义第二个值 白棋
稀疏数组介绍:
-
当一个数组中大部分元素为0,或者为同一值的数组时,可以使用稀疏数组来保存该数组。
-
稀疏数组的处理方式是:
-
记录数组一共有几行几列,有多少个不同值
-
把具有不同值的元素和行列及值记录在一个小规模的数组中,从而缩小程序的规模
-
-
如下图:左边是原始数组,右边是稀疏数组
上图原始数组 6行 7列 里面有8个有效的数字 转化成二维数组
[0] 6行 7列 8(有效数字共8个)
[1] 0行 3列 22(值)
[2] 0 6 15
[3] 1 1 11
[4] 1 5 17
.....
[8] 5 2 28
注:所有行跟列都是从0开始的
看上边右图 若把稀疏数组创建成一个数组 对这个稀疏数组的数组来说 就是9行(有效数字8+1),3列(固定:行、列、值)
代码实操:
package com.baixiaofan.array;
public class ArrayDemo11 {
public static void main(String[] args) {
//一.创建一个二维数组 11*11 0:没有棋子, 1:黑棋 2:白棋
int[][] array1 = new int[11][11];//11*11的五子棋盘
array1[1][2] = 1; //第1行2列的位置 值为1
array1[2][3] = 2;
//输出原始的数组 打印棋盘
System.out.println("输出原始的数组");
for (int[] ints : array1) { //输入array1.for回车即可得到
for (int anInt : ints) { //输入ints.for回车即可得到
System.out.print(anInt+"\t");// 1.加上"\t"让他每个中间有个空格 2.把 println改成print不换行
}
System.out.println(); //外面再来个换行 如果没有这个 会在1行全部数组的元素
}
System.out.println("================================");
//二.转换为稀疏数组保存(由于里面有太多同样的数字0了,这些数字毫无意义)
//1.获取有效值的个数
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (array1[i][j]!=0){ //!=0 不等于0 即棋盘上不是0的地方
sum++;//即可以计算出里面到底有多少个有效数字
}
}
}
System.out.println("有效值的个数:"+sum);//sum就代表有几个有效值
//2.创建一个稀疏数组的数组
int[][] array2 = new int[sum+1][3]; //有效值有sum个,行数就是sum+1行,列数固定3列(行、列、值)
array2[0][0] = 11; //11行 11列 有效数字个数sum 11,11,sum
array2[0][1] = 11;
array2[0][2] = sum;
//遍历二维数组,将非零的值,存放稀疏数组中
int count = 0;
for (int i = 0; i < array1.length; i++) { //array1原来的棋盘
for (int j = 0; j < array1[i].length; j++) {
if (array1[i][j]!=0){ //如果原先棋盘的数字不等于0 就把它记录到稀疏数组中
count++; //count即代表里面存了几个数字 count就是一个计数的作用
array2[count][0] = i; //i即代表行(横坐标) 定义稀疏数组中第几个数字的横坐标 纵坐标 跟值
array2[count][1] = j; //j即代表列(纵坐标)
array2[count][2] = array1[i][j]; //array1[i][j]即值
}
}
}
//输出稀疏数组
System.out.println("稀疏数组:");
for (int i = 0; i < array2.length; i++) { //只有[0][1][2]三列
System.out.println(array2[i][0]+"\t"
+array2[i][1]+"\t"
+array2[i][2]+"\t");
}
System.out.println("=======================");
System.out.println("还原");
//1.读取稀疏数组的值
int[][] array3 = new int[array2[0][0]][array2[0][1]]; //头部信息array2[0][0]][array2[0][1]即行,列
//2.给其中的元素还原它的值
for (int i = 1; i < array2.length; i++) { //注意这里的i从1开始 因为头部信息不用读取
array3[array2[i][0]][array2[i][1]] = array2[i][2];
}
//打印
System.out.println("输出还原的数组");
for (int[] ints : array3) {
for (int anInt : ints) {
System.out.print(anInt + "\t");
}
System.out.println();
}
}
}
运行结果为:
输出原始的数组
0 0 0 0 0 0 0 0 0 0 0
0 0 1 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 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 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
0 0 0 0 0 0 0 0 0 0 0
================================
有效值的个数:2
稀疏数组:
11 11 2
1 2 1
2 3 2
=======================
还原
输出还原的数组
0 0 0 0 0 0 0 0 0 0 0
0 0 1 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 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 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
0 0 0 0 0 0 0 0 0 0 0