手记

重学数据结构 --- 分类+稀疏数组

一、数据结构的分类

1. 数据结构两大类

线性结构非线性结构

1) 线性结构

  • 线性结构是最常见的数据结构,特点是元素间存在一对一的线性关系。
  • 线性结构又分两种,一种是顺序存储(称为顺序表),另外一种是链式存储(称为链表)。顺序表中的存储元素的连续的。链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息。
  • 常见的线性结构有:数组、队列、链表和栈(这里只是讲个大概,具体内容后面的文章会展开阐述)。

2) 非线性结构

非线性结构就是结点元素可能存在多个直接前趋和多个直接后续(联想一下二叉树就懂了,但是非线性结构不仅仅只有二叉树)。

  • 非线性结构包括:多维数组、广义表、树结构、图结构。

二、稀疏数组

1. 稀疏数组(sparse array)

1) 分析场景

有这么一个场景,需要实现一个 10*10 的围棋的步数记录。那么最简单的就可以使用一个二维数组int[10][10]便可,但是在棋盘伊始,这个二维数组几乎没有意义的数据。假如能找到将这个二维数组压缩,只记录有用的数据的方法就好了。这时候稀疏数组就可以派上用场了。

2) 稀疏数组

像上述棋盘,开始的时候,数据中记录的大部分元素为 0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。

3) 稀疏数组的处理方法是:

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

4) 举个例子:

假如有如下的 10*6的棋盘,用正整数表示落子顺序,使用稀疏数组压缩该棋盘则有右侧的表示。第 0 行,分别表示:行数,列数,总有多少个值。从第 1 行开始到最后,都表示行数,列数,数值。

如此一来,本来是 610 的数组就被压缩成 37,大大节省了内存空间。

5) 代码实现

思路分析

(1) 二维数组转稀疏数组
  1. 遍历原始二维数组,得到有效数据的个数 sum
  2. 创建稀疏数组 sparseArr[sum+1][3]
  3. 把有效数据逐个填入稀疏数组 sparseArr 中
  • 代码实现:
/**
* 二维数组转稀疏数组
* 
* @param arr 原数组
* @return 稀疏数组
*/
public int[][] reserveSparseArray(int[][] arr) {
    // 统计有效数据
    int sum = 0;
    // 遍历稀疏数组
    for (int[] is : arr) {
        for (int num : is) {
            if (num != 0) {
                sum++;
            }
        }
    }
    // 创建稀疏数组
    int[][] sparseArr = new int[sum + 1][3];
    sparseArr[0][0] = arr.length;
    sparseArr[0][1] = arr[0].length;
    sparseArr[0][2] = sum;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {
            if (arr[i][j] != 0) {
                sparseArr[sum][0] = i;
                sparseArr[sum][1] = j;
                sparseArr[sum][2] = arr[i][j];
                sum--;
            }
        }
    }
    return sparseArr;
}
(2) 稀疏数组转原始数组
  1. 读取稀疏数组的第 1 行,取出第一 row、第二个数 col,创建二维数组 shessArr[row][col]
  2. 遍历稀疏数组后面几行,把有效值填入原数组 chessArr
  • 代码实现:
/**
* 稀疏数组转二位数组
* 
* @param sparseArr 稀疏数组
* @return 原数组
*/
public static int[][] reserveOriginalArray(int[][] sparseArr) {
    // 根据稀疏数组第一行创建原数组
    int[][] originalArr = new int[sparseArr[0][0]][sparseArr[0][1]];
    // 把稀疏数组的值放回到原数组中
    for (int i = 1; i < sparseArr.length; i++) {
        int row = sparseArr[i][0];
        int col = sparseArr[i][1];
        int value = sparseArr[i][2];
        originalArr[row][col] = value;
    }
    return originalArr;
}

0人推荐
随时随地看视频
慕课网APP