Java数据结构

线性结构

数组

稀疏数组(sparseArr)

稀疏数组可以看做是普通数组的压缩，但是这里说的普通数组是值无效数据量远大于有效数据量的数组

应用场景: 当一个数组多数数据都为无效值时可以通过压缩数组的方式进行优化

二维数据转稀疏数组的思路

遍历原始数组得到有效数据个数 Sum

//创建一个原始二维数组
int[][] chessArr = new int[11][11];
chessArr[1][2] = 1;
chessArr[2][3] = 2;

System.out.println("原始数组");
for (int[] row : chessArr) {
  for (int col : row) {
    System.out.printf("%d\t", col);
  }
  System.out.println();
}
//稀疏数组有效数据个数
int sum = 0;

//将二维数组转为稀疏数组

//获取二维数组的有效数据个数
for (int i = 0; i < 11; i++) {
  for (int j = 0; j < 11; j++) {
    if (chessArr[i][j] != 0) {
      sum++;
    }
  }
}

根据sum创建稀疏数组 sparseArr int[sum+1][3]

//创建对应的数组
int[][] sparseArr = new int[sum + 1][3];
/**
     * 稀疏数组的格式为 第一列为 row 第二列为 col 第三列为 data
     * row col data
     * 11 11  2
     * 1  2 1
     * 2  3 2
     *
     */
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;

将二维数组的有效数据存入到稀疏数组

//遍历二维数组 ,将非0的数据放入稀疏数组中
int count = 0;

for (int i = 0; i < 11; i++) {
    for (int j = 0; j < 11; j++) {
        if (chessArr[i][j] != 0) {
            count++;
            //第一列 第一行是 行
            sparseArr[i][0] = i;
            //列 
            sparseArr[i][1] = j;
            //数据
            sparseArr[i][2] = chessArr[i][j];
        }
    }
}

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

先读稀疏数组的第一行读取到行和列和数据个数再根据获取的行和列创建二维数组 chessArr2 int [i][j]
```
//读取稀疏数组数据并生成对应的二维数组
int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
```

读取到后几行的数据后进行赋值原始数组即可

 //从第一行数据开始复原数据
for (int i = 1; i < sparseArr.length; i++) {
    /**
       * 稀疏数组数组
       * 行 列 数据
       * 11 11  2
       * 1  2 1
       * 2  3 2
       */
    chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}

集合

链表

栈

队列

队列是一个有序的列表遵守**FIFO(Frist In Frist Out)**原则即先入先出

非线性结构

树

二叉树

01_二叉树结构图

二叉查找树

二叉查找树的特点
- 二叉查找树,又称二叉排序树或者二叉搜索树
- 每一个节点上最多有两个子节点
- 左子树上所有节点的值都小于根节点的值
- 右子树上所有节点的值都大于根节点的值
- 遵循小中大的数据结构

02_二叉查找树结构图

二叉查找树又称二叉排序树或者二叉搜索树

平衡二叉树

平衡二叉树的特点
- 二叉树左右两个子树的高度差不超过1
- 任意节点的左右两个子树都是一颗平衡二叉树
平衡二叉树旋转
- 旋转触发时机
  - 当添加一个节点之后,该树不再是一颗平衡二叉树
- 左旋
  - 就是将根节点的右侧往左拉,原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点
  - 复杂左旋示意图
- 右旋
  - 就是将根节点的左侧往左拉,原先的左子节点变成新的父节点,并把多余的右子节点出让,给已经降级的根节点当左子节点
  - 复杂右旋示意图
  - 平衡二叉树旋转的四种情况
    - 左左
      - 左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡
      - 如何旋转: 直接对整体进行右旋即可
    - 左右
      - 左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡
      - 如何旋转: 先在左子树对应的节点位置进行左旋,在对整体进行右旋
    - 右右
      - 右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡
      - 如何旋转: 直接对整体进行左旋即可
    - 右左
      - 右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡
      - 如何旋转: 先在右子树对应的节点位置进行右旋,在对整体进行左旋

红黑树

红黑树的特点
- 平衡二叉B树
- 每一个节点可以是红或者黑
- 红黑树不是高度平衡的,它的平衡是通过"自己的红黑规则"进行实现的
红黑树的红黑规则有哪些
1. 每一个节点或是红色的,或者是黑色的
2. 根节点必须是黑色
3. 如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的
  1. 如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
4. 对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点
红黑树添加节点的默认颜色
- 添加节点时,默认为红色,效率高
红黑树添加节点后如何保持红黑规则
- 根节点位置
  - 直接变为黑色
- 非根节点位置
  - 父节点为黑色
    - 不需要任何操作,默认红色即可
  - 父节点为红色
    - 叔叔节点为红色
      1. 将"父节点"设为黑色,将"叔叔节点"设为黑色
      2. 将"祖父节点"设为红色
      3. 如果"祖父节点"为根节点,则将根节点再次变成黑色
    - 叔叔节点为黑色
      1. 将"父节点"设为黑色
      2. 将"祖父节点"设为红色
      3. 以"祖父节点"为支点进行旋转

文章作者: Alex

文章连结: /archives/datastruct

微信扫一扫