数据结构の线性结构の稀疏数组 | Monster

数据结构の线性结构の稀疏数组

线性结构与非线性结构
  1. 线性结构

    • 线性结构作为最常用的数据结构,其特点是数据元素之间存在一对一的线性关系
    • 线性结构有两种不同的存储方式,即顺序存储结构链式存储结构
    • 顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的
    • 链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素中节点存放数据元素以及相邻元素的地址信息

    • 数组、队列、链表、栈等。。

  2. 非线性结构

    • 二维数组、多维数组、广义表、树结构、图结构
稀疏数组(sparesearry
  • 当一个数组中大部分元素为0或者为同一个值的数组时,可以使用稀疏数组来保存该数组

  • 应用场景

  • 处理方式:

    • 记录数组一共有几行几列,有多少个不同的值

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

    • 原数组

    • 转为稀疏数组,将行列位置坐标和值进行存储,从而压缩空间

  • 二维数组转稀疏数组

    • 遍历原始二维数组,得到有效数据个数 sum
    • 根据sum 可以创建细数数组 spareseArr int [sum+1][3]
    • 将二维数组的有效数据存入到稀疏数组
  • 稀疏数组转二维数组的思路

    • 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组
    • 读取稀疏数组后一行的数组,并赋值给二维数组
  • 实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    // 创建一个原始的二维数组
    // 以某一棋盘为例 0:未落子位置 1:黑子落子 2:白子落子
    int chessArr[][] = new int[11][11];
    chessArr[2][3] = 1;
    chessArr[4][5] = 2;
    chessArr[2][7] = 1;
    chessArr[7][9] = 2;

    for (int[] ints : chessArr) {
    for (int anInt : ints) {
    System.out.print(anInt+"\t");
    }
    System.out.println();
    }

    // 转为细数数组
    // 1. 遍历二维数组 得到有效数字的个数
    int sum = 0;
    for (int[] i : chessArr) {
    for (int j : i) {
    if(j!=0){
    sum ++;
    }
    }
    }
    // 2. 创建 稀疏数组 行数为sum 列为 3
    int spareArr[][] = new int[sum+1][3];
    spareArr[0][0] = 11;
    spareArr[0][1] = 11;
    spareArr[0][2] = sum;
    int index = 1;
    for (int i = 0; i <chessArr.length ; i++) {
    for (int j = 0; j <chessArr[i].length ; j++) {
    if(chessArr[i][j]!=0){
    // 记录有效数字的位 置
    spareArr[index][0] = i; //行位置
    spareArr[index][1] = j; //列位置
    spareArr[index][2] = chessArr[i][j]; // 值
    index++;
    }
    }
    }


    // 细数数组
    for (int[] ints : spareArr) {
    for (int anInt : ints) {
    System.out.print(anInt+"\t");
    }
    System.out.println();
    }


    // 将稀疏数组恢复成二维数组
    int[][] chessArr2 = new int[spareArr[0][0]][spareArr[0][1]];
    for (int i = 1; i < spareArr.length ; i++) {
    chessArr2[spareArr[i][0]][spareArr[i][1]] = spareArr[i][2];
    }


    // 恢复后的二维数组
    for (int[] ints : chessArr2) {
    for (int anInt : ints) {
    System.out.print(anInt+"\t");
    }
    System.out.println();
    }
-------------本文结束感谢您的阅读-------------
既然来了就打个赏吧= =
0%