数据结构和算法之稀疏数组

一.明白数据结构（DataStructure）和算法的关系
1.程序=数据结构+算法

2.数据结构包括：

• 线性结构：队列，数组，链表和栈等（一对一）
• 非线性结构：二维数组，广义表，多维数组，图结构和树结构等（非一对一）

3.数据结构的存储结构：

• 顺序存储
• 链式存储

二.稀疏数组
1.稀疏数组：当一个数组大部分元素为0，或为同一个值的数组时，可以用稀疏数组保存该数组

处理方法：
–》记录数组一共有几行几列，一共有多少不同的值
–》把具有不同值得行列及值记录在一个小规模数组中，从而缩小程序规模

2.二维数组转稀疏数组思路：
–》遍历原始二维数组，得到有效数据个数sum
–》根据有效数据个数创建稀疏数组int[sum+1][3]

3.稀疏数组转二维数组思路：
–》先读取稀疏数组第一行，根据第一行的数据，创建原始二维数组
–》在读取稀疏数组后几行元素，并赋值给原始二维数组即可

public class SparseArray {
    public static void main(String[] args) {
        //创建原始数组，11*11
        //0:没有棋子 1：黑子  2：蓝子
        int[][] chessAry1=new int[11][11];
        chessAry1[1][2]=1;
        chessAry1[5][3]=2;
        chessAry1[6][6]=1;
        //输出原始二维数组
        System.out.println("输出原始的二维数组：");
        for (int[] row:chessAry1){
            for (int data:row){
                System.out.print(" "+data+" ");
            }
            System.out.println();
        }

        //二维数组转稀疏数组步骤：

        //1.先遍历数组得到非零数据个数
        int sum=0;
        for (int i = 0; i <chessAry1.length ; i++) {
            for (int j = 0; j <chessAry1.length ; j++) {
                if (chessAry1[i][j]!=0){
                    sum++;
                }
            }
        }
        System.out.println("非零数据个数"+sum);
        //创建稀疏数组:稀疏数组第一行表示原始数组有多少行多少列，非零数据个数
        int[][] sparseAry=new int[sum+1][3];
        //给稀疏数组赋值
        sparseAry[0][0]=chessAry1.length;
        sparseAry[0][1]=chessAry1.length;
        sparseAry[0][2]=sum;

        //遍历二维数组,将非零的值存放在稀疏数组中

        int count=0;//用来记录第几个非零数据
        for (int i = 0; i <chessAry1.length ; i++) {
            for (int j = 0; j <chessAry1.length ; j++) {
                if (chessAry1[i][j]!=0){
                    count++;
                    sparseAry[count][0]=i;
                    sparseAry[count][1]=j;
                    sparseAry[count][2]=chessAry1[i][j];
                }
            }
        }
        //输出稀疏数组
        System.out.println();
        System.out.println("得到的稀疏数组");
        for (int i = 0; i <sparseAry.length ; i++) {
            System.out.println(sparseAry[i][0]+" "+sparseAry[i][1]+" "+sparseAry[i][2]);
        }
        System.out.println();
        //将稀疏数组恢复成二维数组
        //1.先读取稀疏数组第一行,根据第一行创建原始数组
        int[][] chessAry2=new int[sparseAry[0][0]][sparseAry[0][1]];

        //2.在读取后后几行数据并赋值给原始二维数组
        for (int i=1;i<sparseAry.length;i++){
            chessAry2[sparseAry[i][0]][sparseAry[i][1]]=sparseAry[i][2];
        }
        //输出恢复后的二维数组
        for (int[] row:chessAry2){
            for (int data:row){
                System.out.print(" "+data+" ");
            }
            System.out.println();
        }
    }
}