稀疏数组

基本介绍

image.png

  1. 稀疏数组的列数固定为3列
  2. 稀疏数组的行数=有效数据个数+1

稀疏数组的意义：

  1. 原数组中存在大量的无效数据，占据了大量的存储空间，有效数据很少。
  2. 压缩存储可以节省存储空间，避免资源不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率。

处理步骤：

  1. 记录原数组的行数，列数，有效数据（不为0的数）。

  2. 把有效数据的的行数，列数和值记录在一个小规模的数组中，从而缩小程序的规模。

    实际应用

  3. 使用稀疏数组来保留图中的棋盘（二维数组）

  4. 将稀疏数组重新恢复为二维数组

image.png
代码：

  1. package ch03_sparseArray;
  3. /**
  4.  * 稀疏数组
  5.  */
  6. public class SparseArray {
  7.     public static void main(String[] args) {
  8.         /**
  9.          *使用二维数组，模拟棋盘数据
  10.          */
  11.         int[][] array = new int[11][11];
  12.         array[1][2] = 1;
  13.         array[2][3] = 2;
  14.         //打印棋盘，查看效果
  15.         for (int i = 0; i < array.length; i++) {
  16.             for (int j = 0; j < array[i].length; j++) {
  17.                 System.out.print(array[i][j] + " ");
  18.             }
  19.             System.out.println();
  20.         }
  22.         /**
  23.          * 使用稀疏数组来保存以上二维数组
  24.          */
  25.         //计算二维数组中有效数据（不为0）的个数。
  26.         int sum = 0;
  27.         for (int i = 0; i < array.length; i++) {
  28.             for (int j = 0; j < array[i].length; j++) {
  29.                 if (array[i][j] != 0) {
  30.                     sum++;
  31.                 }
  32.             }
  33.         }
  34.         /*
  35.         定义稀疏数组
  36.         1.稀疏数组的列数固定为3列
  37.         2.稀疏数组的行数=有效数据个数+1
  38.          */
  39.         int[][] sparseArray = new int[sum + 1][3];
  40.         //原数组行数
  41.         sparseArray[0][0] = 11;
  42.         //原数组列数
  43.         sparseArray[0][1] = 11;
  44.         //有效数据个数
  45.         sparseArray[0][2] = sum;
  47.         //将有效数据存放至稀疏数组中
  48.         int count = 0;
  49.         for (int i = 0; i < array.length; i++) {
  50.             for (int j = 0; j < array[i].length; j++) {
  51.                 if (array[i][j] != 0) {
  52.                     count++;
  53.                     sparseArray[count][0] = i;
  54.                     sparseArray[count][1] = j;
  55.                     sparseArray[count][2] = array[i][j];
  56.                 }
  57.             }
  58.         }
  60.         //打印稀疏数组
  61.         System.out.println("-----------------------------------");
  62.         for (int[] row : sparseArray) {
  63.             for (int val : row) {
  64.                 System.out.print(val + "\t");
  65.             }
  66.             System.out.println();
  67.         }
  69.         /**
  70.          * 将稀疏数组重新恢复为二维数组
  71.          */
  72.         //创建二维数组
  73.         int[][] oldArray = new int[sparseArray[0][0]][sparseArray[0][1]];
  74.         //赋值
  75.         for (int i = 1; i <= count; i++) {
  76.             oldArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
  77.         }
  78.         //打印二维数组
  79.         System.out.println("-------------------------------");
  80.         for (int[] row : oldArray) {
  81.             for (int i : row) {
  82.                 System.out.print(i+"\t");
  83.             }
  84.             System.out.println();
  85.         }
  86.     }
  87. }

队列

基本介绍

image.png

  • 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
  • 进行插入操作的一端叫做队尾（rear），进行删除操作的一端称为队头（front）。
  • 队列中的元素只能 先进先出（FIFIO）。
  • 队列是一个有序列表，可以用数组和链表来实现。

    循环队列

    数据结构与算法（中） - 图4
    循环队列的出现就是为了解决队列的假溢出问题。
    真溢出：我们运用数组实现队列时，数组长度为 5，我们放入了[1,2,3,4,5],此时如果继续加入 6 时，是真的满了，放不了。
    假溢出：我们运用数组实现队列时，数组长度为 5，我们放入了[1,2,3,4,5],我们将 1，2 出队，此时如果继续加入 6 时，因为数组末尾元素已经被占用，再向后加则会溢出，但是我们的下标 0，和下标 1 还是空闲的。所以我们把这种现象叫做“假溢出”。
    我们用来解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环，我们把队列的这种头尾相接的顺序存储结构成为循环队列。
    队尾指针指向的位置永远空出1位， 所以队列最大容量比数组长度小1。

    基本操作

    我们发现队列为空时 front == rear，队列满时也是 front == rear，如何区分队列是空还是满？
  1. 设置标记变量 flag。
  2. 当队列为空时，front==rear；

当队列满时，我们保留一个元素空间，也就是说，队列满时，数组内还有一个空间
数据结构与算法（中） - 图5
数据结构与算法（中） - 图6

  • 公式（判断队列是否满了）：(rear+1)%queuesize==front
    • rear：尾部指针指向的数组下标
    • front：头部指针指向的数组下标
    • queuesize：队列的长度

代码：

  1. package ch04_queue;
  3. public class ArrayQueue {
  4.     public static void main(String[] args) throws Exception {
  5.         ArrayQueue arrayQueue = new ArrayQueue(5);
  6.         arrayQueue.addQueue(1);
  7.         arrayQueue.addQueue(2);
  8.         arrayQueue.addQueue(3);
  9.         arrayQueue.addQueue(4);
  10.         arrayQueue.getQueue();
  11.         arrayQueue.getQueue();
  12.         arrayQueue.headQueue();
  13.         //arrayQueue.output();
  15.     }
  18.     private int[] array;
  19.     private int front;
  20.     private int rear;
  22.     public ArrayQueue(int capacity) {
  23.         this.array = new int[capacity];
  24.     }
  26.     /**
  27.      * 判断队列是否已满
  28.      *
  29.      * @return：true-满了，false-没满
  30.      */
  31.     public boolean isFull() {
  32.         return (rear + 1) % array.length == front;
  33.     }
  35.     /**
  36.      * 判断队列是否为空
  37.      *
  38.      * @return：true-空，false-非空
  39.      */
  40.     public boolean isEmpty() {
  41.         return front == rear;
  42.     }
  44.     /**
  45.      * 入队操作
  46.      *
  47.      * @param element：入队元素
  48.      */
  49.     public void addQueue(int element) throws Exception {
  50.         if (isFull()) {
  51.             throw new Exception("队列已满！");
  52.         }
  53.         array[rear] = element;
  54.         rear = (rear + 1) % array.length;
  55.     }
  57.     /**
  58.      * 出队操作
  59.      *
  60.      * @return
  61.      */
  62.     public int getQueue() throws Exception {
  63.         if (isEmpty()) {
  64.             throw new Exception("队列已空！");
  65.         }
  66.         int getElement = array[front];
  67.         front = (front + 1) % array.length;
  68.         return getElement;
  69.     }
  71.     /**
  72.      * 输出队列
  73.      */
  74.     public void output() {
  75.         for (int i = front; i != rear; i = (i + 1) % array.length) {
  76.             System.out.println(array[i]);
  77.         }
  78.     }
  80.     /**
  81.      * 输出队列的第一个数据
  82.      */
  83.     public void headQueue(){
  84.         System.out.println(array[front]);
  85.     }
  86. }

递归

基本介绍

概念：
递归就是方法自己调用自己，每次调用时传入的参数是不同的，递归有助于解决程序中复杂的问题，同时可以让代码更为简洁。
规则：

  • 执行一个方法时，就创建一个新的受保护的独立栈空间
  • 方法的局部变量是独立的，不会相互影响
  • 如果方法中使用的是引用型类型变量，比如数组，则会共享引用型的数据
  • 递归必须向退出递归的条件接近，否则就是无限递归，会出现StackOverflowError
  • 一个方法执行完毕后，或者遇到return，会就返回数据，遵守谁调用就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

    递归（迷宫问题）

    image.png