2-1认识稀疏数组

因为该二维数组的很多值是默认值0，因此记录了很多没有意义的数据
我们称之为稀疏数组

图中描述的记录在一个小规模的数组中，这个数组就是我们说的稀疏数组

接下来，具体看看稀疏数组的价值以及实际模样
下面是一个二维数组，6行7列，占用42个格子

变换为稀疏数组，9行3列，占用27个格子，空间占用明显减少

解释说明：
[0]对应的值代表，整个原二维数组的具体情况，即行数、列数、非0值总个数

2-2原始二维数组和稀疏数组的互换思路及代码实现

原始的二维数组转稀疏数组的思路

遍历原始的二维数组，得到有效数据的个数 sum
1. 列数固定值为3，行数由有效数据的个数决定
根据sum 就可以创建稀疏数组 sparseArr int[sum + 1] [3]
1. 行数默认加1，是因为第一行要用来存储原二维数组的基本信息
将二维数组的有效数据数据存入到稀疏数组

稀疏数组转原始的二维数组的思路

先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int [11][11]
1. 行列信息存储在稀疏数组的第一行，可以帮我们很快确定原始数组的框架
在读取稀疏数组后几行的数据，并赋给原始的二维数组即可
1. 稀疏数组第一行的sum值明显是给原二维数组转稀疏数组才有用的

思路明晰，代码上场

package com.xy.sparsearray;
import java.util.Iterator;
public class SparseArray {
    public static void main(String[] args) {
        int count = 0;
        //先建造出棋盘
        int[][] OriginChess = new int[11][11];
        OriginChess[1][2] = 1;
        OriginChess[2][3] = 2;
        //打印原始二维数组
        System.out.println("原始二维数组~~\n");
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                System.out.print(OriginChess[i][j]);
                System.out.print("\t");
            }
            System.out.println("\n");
        }
        //遍历原始二维数组，得到有效数字总个数
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (OriginChess[i][j] != 0) {
                    count++;                                        
                }
            }
        }
        //确定有效总个数count，我们可以构造出稀疏数组，即[count][2]
        int[][] DilutionArray = new int[count+1][3];
        //对稀疏数组赋值
        DilutionArray[0][0] = 11;
        DilutionArray[0][1] = 11;
        DilutionArray[0][2] = count;
        DilutionArray[1][0] = 1;
        DilutionArray[1][1] = 2;
        DilutionArray[1][2] = OriginChess[1][2];
        DilutionArray[2][0] = 2;
        DilutionArray[2][1] = 3;
        DilutionArray[2][2] = OriginChess[2][3];
        //打印稀疏数组
        System.out.println("稀疏数组~~\n");
        for (int i = 0; i < count+1; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(DilutionArray[i][j]);
                System.out.print("\t");
            }
            System.out.println("\n");
        }
        //完成原始二维数组到稀疏数组的转化，接下来就是由稀疏数组转换为原始二维数组了
        //首先获取稀疏数组的第0行*列的数据，借此恢复原始数组的总框架，然后逐步获取其他行对应列的数据进行赋值
        int RecoverOriginArray[][] = new int[DilutionArray[0][0]][DilutionArray[0][1]];
        for (int i = 1; i < count+1; i++) {
            int number = 0;
            RecoverOriginArray[DilutionArray[i][number]][DilutionArray[i][number+1]] = DilutionArray[i][number+2];
        }
        //打印恢复的二维数组
        System.out.println("恢复后的原始二维数组~~\n");
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                System.out.print(RecoverOriginArray[i][j]);
                System.out.print("\t");
            }
            System.out.println("\n");
        }            
    }
}

输出结果展示

2-3认识队列

队列是一个有序列表，可以用数组或链表来实现。
遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

仔细观察这张图片

原始的时候real（尾指针）=front（头指针）=-1
入队的时候real移动，front保持不动
出队的时候real保持不动，front移动

通过上面的分析，想必明白何为队列了

2-4数组模拟队列思路及代码实现

依旧是选择这张图

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如图, 其中 maxSize 是该队列的最大容量
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变

其中更为重要的一步是，何时拒绝入队（队列无空间可给），何时允许入队（队列空间有剩余）
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤

将尾指针往后移：rear+1 , 当front == rear 【空】
若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]

思路明晰，代码上场

2-5数组模拟环形队列思路及代码

2-6Java补

2-6-1创建数组

创建一维数组

int[] arrayRefVar = new int[arraySize];

int[] arrayRefVar = {value0, value1, ..., valuek};

arrayRefVar = new int[arraySize];

创建二维数组

//第一种方式：
        int a[][]={{1,2,3},{4,5,6}};
//第二种方式；
        int[][] ints = new int[4][2];
        ints[i][j] =__; //分别赋值
//第三种方式：第二维的长度可以动态申请
        int[][] arr3 = new int[5][];//五行的长度
        for(int i=0; i<arr3.length; ++i){
            arr3[i]=new int[i+1];   //列的长度每次都变化。每次都要重新申请空间(长度)
            for(int j=0; j<arr3[i].length; ++j)
                arr3[i][j]= i+j;
        }

数据结构与算法

02-稀疏数组和队列