[数据结构与算法]数据结构-稀疏数组

数据结构

数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

1. 集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
2. 线性结构：数据结构中的元素存在一对一的相互关系；
3. 树形结构：数据结构中的元素存在一对多的相互关系；
4. 图形结构：数据结构中的元素存在多对多的相互关系。

数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。

数据的顺序存储结构的特点是：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序存储的特点是：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。
线性结构：
简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点：

• 线性结构是非空集。
• 线性结构有且仅有一个开始结点和一个终端结点。
• 线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。
  线性表就是典型的线性结构，还有栈、队列和串等都属于线性结构。

非线性结构：
简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点：
1、非线性结构是非空集。
2、非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。
在实际应用中，数组、广义表、树结构和图结构等数据结构都属于非线性结构。

稀疏数组

当一个数组中大部分元素都为0或者是同一值时，为了节省空间，可以使用稀疏数组来保存该数组。

稀疏数组将会记录原数组一共有几行几列，一共有多少不同的值，并且将具有不同值的元素和行列及值记录在一个小规模的数组之中，从而缩小程序的规模。

假设我们现在需要编写一个五子棋程序，且这个程序具有存盘和续上盘的功能，如下图：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rDtLRrUq-1631977484851)(数据结构.assets/image-20210910141702112.png)]

分析问题：因为该数组中绝大部分数据是默认值0，记录了很多没有意义的数据，所以可以采用稀疏数组。

稀疏数组的处理方式是：

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

稀疏数组举例说明：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2Sunb5Vk-1631977484853)(C:/Users/12709/AppData/Roaming/Typora/typora-user-images/image-20210910142011319.png)]

整体思路分析：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uamronca-1631977484854)(C:/Users/12709/AppData/Roaming/Typora/typora-user-images/image-20210910141803822.png)]

public class SparseArray {
    public static void main(String[] args) throws IOException {
        int[][] array = new int[11][11];
        array[0][1] = 1;
        array[0][2] = 2;
        PrintArray(array);
        // 值的总数
        int number = 0;
        for (int[] ints : array) {
            for (int anInt : ints) {
                if (anInt != 0) {
                    number++;
                }
            }
        }
        System.out.println("=================================================");
        // 将二维数组转为稀疏数组
        int[][] SparseArray = new int[number + 1][3];
        int count = 1;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                // 原二维数组的行数
                SparseArray[0][0] = array.length;
                // 原二维数组的列数
                SparseArray[0][1] = array[array.length -1].length;
                SparseArray[0][2] = number;
                if (array[i][j] != 0) {
                    SparseArray[count][0] = i;
                    SparseArray[count][1] = j;
                    SparseArray[count][2] = array[i][j];
                    count++;
                }
            }
        }
        PrintArray(SparseArray);
        System.out.println("=================================================");
        // 将稀疏数组转为二维数组
        int[][] ReArray = new int[SparseArray[0][0]][SparseArray[0][1]];
        for (int i = 1; i < SparseArray.length; i++) {
            ReArray[SparseArray[i][0]][SparseArray[i][1]] = SparseArray[i][2];
        }
        PrintArray(ReArray);
    }
    // 打印二维数组
    public static void PrintArray(int[][] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + "\t\t");
            }
            System.out.println();
        }
    }
}