数据结构

数据的概念

数据**是 一切可以输入到 计算机内 ,可以被计算机程序处理的一切事物 称为数据 , 如 图像 , MP3,files,txt,网页,数值数据等等各种类型

数据对象:有相同性质的数据元素的集合

数据元素:是数据的基本单位,

数据项:是单个数据内的属性，具体数值。

数据结构

数据结构研究的就是 数据元素与元素之间的逻辑，在物理存储中的集合关系的组织形式表现。

数据结构 通常是 逻辑结构 + 存储结构 的总和。

  1. 逻辑结构是数据元素之间的相互关系。1）集合结构 2）线性结构 3)树形结构 4)图形结构
  2. 每一个元素可以看作一个结点, 不同结点之间存在着不同关系:
  3. 1:1  1个结点只能连接1个结点
  4. 1:N  1个结点可以连接多个结点
  5. N:N  N 个结点 连接N个结点
  6. 集合  各结点没有关系 但同属于一个集合
物理存储结构是数据元素在计算机采取何种方式存储。1）顺序存储 2）链式存储 3）索引存储 4）散列存储
1）顺序存储，即数据元素之间在存储区域是 顺序的，连续的，紧靠的。
2）链式存储，即数据元素之间在存储区域是 分散的，可不连续的，松散的，只要借助指针才能找对上下线。如无间道的卧底，每个卧底都是链式存储的，一旦失去上线指引，则失去其存储的身份。

由于每种数据结构有它自己的逻辑结构和 存储结构。因此它们有多种组合，如：

1）线性结构+顺序存储 。如数组,线性表,栈,队列

2）线性结构+链式存储。如链表

3）树形结构+顺序存储。二叉树

4）树形结构+链式存储。

5）图形结构+顺序存储

6）图形结构+链式存储

…….

学习数据结构

知道了数据结构，那我们可以用数据结构来进行什么呢？

那当然是拿来运算呀，常见的运算就有 新增元素 ，删除元素，修改元素，查找元素四种基本操作。

因为数据结构混合了 不同的结构，因此在运算过程中有着不同的优缺点。

譬如数组，查找速度快和修改元素准确 ， 但新增和删除元素能力差。

数组是线性的，连续的，顺序存储最基本的数据结构，可分为一维数组 、多维数组.。下面介绍一个经典数组数据结构 -“稀疏数组”

） “稀疏数组”是二维数组，使用稀疏数组可以减小程序规模。

应用场景： 当一个数组的大部分元素都是0或者都是同一个值 ，可以使用稀疏数组进行保存该数组。譬如五子棋盘。

算法分析：

 【棋盘游戏 - 复盘功能:先存盘 】
1）游戏结束，获取并保存棋盘有效数值个数
2）新建稀疏数组[有效数值+1][3]，spareArr[0][0] = 原数组行数 , spareArr[0][1] = 原数组列数,spareArr[0][3]是所在位置值
3) 遍历原数组,把 != 0 的条件的结果 ,放入 稀疏数组中
4) 将结果值 赋值 到稀疏数组的行列中 （添加count值用于记录稀疏数组的行，如果！=0 为true ，则自增）
5）将符合的值放入 稀疏数组中 ： spareArr[count][0] = i , spareArr[count][1]=j ,spareArr[count][2]= a[i][j] ，得出稀疏数组。

【再复盘】
1）已知  稀疏数组，得出 spareArr[0][0] = 原数组行数,spareArr[0][1] = 原数组列数
2）根据行数，列数，新建还原 原数组。
3）遍历 稀疏数组， 因为spareArr第0行第0列数据已经被使用,因此循环初始化值从1 开始。循环体内 赋值给 原数组   row = spareArr[i][0] , column 值 = spareArr[i][2] , arr[i][j] = spareArr[row][column] 
4) 还原完成,返回值原数组

int[][] xishuArray = new int[11][11]

）假设 该数组的元素值如图下，请使用新的 稀疏数组保存该 数组。

二维数组 5x5=25 ，可以存放25个数据

处理方式：1.记录数组一个有n行m列（索引从0开始算起），有多少个不同的值 2.把具有不同值的元素的行列及值 记录在一个小规模新的数组中，新数组就是稀疏数组。

/**
算法代码实现案例
）二维数组 转  稀疏数组的思路 ：
1.遍历原数组的数据 ， 获取有效数据 count个数
2.新建稀疏数组 ， 新数组长度 为 int[][] = new int[6][3] ，阵列数稳定就是3
3.将原有数组的有效数据存入 稀疏数组.

) 稀疏数组 转 二维数组的思路:
1.先读取 稀疏数组的第一行,根据第一行的数据,还原原始二维数组, 即 chessArr2 = int[5][5];
2.在读取稀疏数组 后几行的数据,赋值回原二维数组即可.
**/
TwoDemensionArray.java
package 线性结构_顺序存储.数组;

import java.util.Random;

/**
 * @author Tommy
 * @version 1.0
 * @desc 二维数组数据结构类
 * @ClassName TwoDemensionArray
 * @date 2022/6/22/10:41
 **/

public class TwoDemensionArray {

    private int row;
    private int column;
    private int[][] arr; //二维数组

    public TwoDemensionArray(int row, int column) {
        this.row = row;
        this.column = column;
        arr = new int[row][column];
    }

    public int playGame() {

        int count = 0;
        int[] r = new int[10];
        int[] x = new int[10];
        int[] y = new int[10];
        Random random = new Random();
        //随机给 走位 . 并随机给到 二维数组随机的(x,y)轴去
        for (int i = 0; i < r.length; i++) {
            r[i] = random.nextInt(1,3);
            x[i] = random.nextInt(10);
            y[i] = random.nextInt(10);
            arr[x[i]][y[i]] = r[i];
        }
        //遍历原数组
        for (int i = 0;i < arr.length;i++) {
            for (int j = 0; j < arr.length ; j++) {
                System.out.print(arr[i][j] + " ");
                if (arr[i][j] != 0) {
                    count++;
                }
            }
            System.out.println();
        }
        System.out.println("有效数值:" + count);
        System.out.println("=========开始保存本局下棋的盘局==========");
        return count;
    }

    /**
     * 将二维数组 转换成 稀疏数组
     * @param value
     * @return
     */
    public int[][] setSparseArray(int value){
        int[][] spareseArr = new int[value + 1][3];
        spareseArr[0][0] = 10;
        spareseArr[0][1] = 10;
        spareseArr[0][2] = value;
        int index = 0 ;//
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[i][j] != 0) {
                    index++;
                    spareseArr[index][0] = i;
                    spareseArr[index][1] = j;
                    spareseArr[index][2] = arr[i][j];
                }
            }
        }
        return spareseArr;
    }

}

package 线性结构_顺序存储.数组;

/**
 * @author Tommy
 * @version 1.0
 * @desc 稀疏数组的数据结构类
 * @ClassName SparseArray
 * @date 2022/6/22/15:17
 **/

public class SparseArray {

    private int row; //稀疏数组的行数
    private int column; //稀疏数组的列数
    public int[][] sparseArr; //二维数组


    public SparseArray(int[][] arr) {
        this.sparseArr = arr;
    }


    public int[][] getSparseArr() {
        return sparseArr;
    }

    /**
     * 稀疏数组还原成原数组
     * @return 还原成 二维数组
     */
    public int[][] resetTwoDemensionArray() {
        row = sparseArr[0][0];
        column = sparseArr[0][1];
        int[][] result = new int[row][column];
        //读取稀疏数组的后几行的数据
        for (int i = 1; i < sparseArr.length; i++) {
            //读取 稀疏数组arr 的数据
            row = sparseArr[i][0]; //原数组的行
            column = sparseArr[i][1];//原数组的列
            result[row][column] = sparseArr[i][2];
        }
        System.out.println("======复盘成功,恢复后的数组=========");
        for (int[] row : result){
            for (int data : row){
                System.out.printf(" " + data);
            }
            System.out.println();
        }
        return result;
    }
}

package 线性结构_顺序存储.数组;


/**
 * 二维数组经典数据结构 稀疏数组的 学习和使用
 * 应用场景:五子棋 的 存盘 和复盘 功能.
 */
public class TwoDemensionArrayTest {


    public static void main(String[] args) {
       TwoDemensionArray twoDemensionArray = new TwoDemensionArray(11,11);
        int count = twoDemensionArray.playGame();
        int[][] result = twoDemensionArray.setSparseArray(count);
        //遍历 稀疏数组的 内容
        for (int i = 0; i < result.length; i++) {
                System.out.printf("%d\t%d\t%d\t" ,result[i][0],result[i][1],result[i][2]);
                System.out.println();
        }
        //将稀疏 数组还原成 原数组
        SparseArray sparseArray = new SparseArray(result);
        sparseArray.resetTwoDemensionArray();

    }
}