尚硅谷图解Java数据结构和算法.pdf尚硅谷Java数据结构和算法【最新版】.pptx
图解.xlsx

1、稀疏数组

基本功能

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

处理方法

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

一、稀疏数组和队列 - 图1
如图，把一个6X7的二维数组变为了一个9X3的稀疏数组。其中

  • 第一行保存的是原二维数组的行、列以及非0值的个数

  • 第二到九行保存的是每个非0值所在的位置及其数值

    转换思路

    二维数组转稀疏数组

  • 遍历二维数组，得到二维数组中有效值的个数sum

  • 创建稀疏数组，有sum+1行，3列（固定）
  • 将二维数组中的有效值存入稀疏数组中

稀疏数组转二维数组

  • 先读取稀疏数组的第一行（保存二维数组的行列信息），还原二维数组
  • 读取稀疏数组的其他行，将值赋给二维数组的对应位置上的数

代码

  1. public class Demo2 {
  2.    public static void main(String[] args) {
  3.       //创建一个二维数组
  4.       int[][] arr1 = new int[11][11];
  5.       //向二维数组里放值
  6.       arr1[1][2] = 1;
  7.       arr1[2][3] = 2;
  8.       arr1[3][4] = 3;
  10.       //打印二维数组
  11.       System.out.println("遍历二维数组");
  12.       for (int i = 0; i < arr1.length; i++) {
  13.          for (int j = 0; j < arr1[0].length; j++) {
  14.             System.out.print(arr1[i][j] + "   ");
  15.          }
  16.          System.out.println();
  17.       }
  19.       //二位数组----->稀疏数组
  20.       //遍历二维数组中有效值的个数,用sum来记录
  21.       int sum = 0;
  22.       for (int i = 0; i < arr1.length; i++) {
  23.          for (int j = 0; j < arr1[0].length; j++) {
  24.             if (arr1[i][j] != 0) {
  25.                //二维数组中元素不为0即为有效值
  26.                sum++;
  27.             }
  28.          }
  29.       }
  31.       //创建稀疏数组
  32.       //行数为sum+1，第一行用于保存二维数组的行列及有效值个数，列数固定为3
  33.       int[][] sparseArr = new int[sum + 1][3];
  34.       //存入二维数组的行列及有效值个数
  35.       sparseArr[0][0] = arr1.length;
  36.       sparseArr[0][1] = arr1[0].length;
  37.       sparseArr[0][2] = sum;
  39.       //再次遍历二维数组，将有效值存入稀疏数组
  40.       //用于保存稀疏数组的行数
  41.       int count = 1;
  42.       for (int i = 0; i < arr1.length; i++) {
  43.          for (int j = 0; j < arr1[i].length; j++) {
  44.             if (arr1[i][j] != 0) {
  45.                //将值存入稀疏数组
  46.                sparseArr[count][0] = i;
  47.                sparseArr[count][1] = j;
  48.                sparseArr[count][2] = arr1[i][j];
  49.                count++;
  50.             }
  51.          }
  52.       }
  54.       //打印稀疏数组
  55.       System.out.println("遍历稀疏数组");
  56.       for (int i = 0; i < sparseArr.length; i++) {
  57.          for (int j = 0; j < sparseArr[0].length; j++) {
  58.             System.out.print(sparseArr[i][j] + "   ");
  59.          }
  60.          System.out.println();
  61.       }
  64.       //稀疏数组------>二维数组
  65.       //先得到二位数组的行列数
  66.       int row = sparseArr[0][0];
  67.       int col = sparseArr[0][1];
  68.       int[][] arr2 = new int[row][col];
  70.       //遍历稀疏数组，同时给二维数组赋值
  71.       for (int i = 1; i < sparseArr.length; i++) {
  72.          row = sparseArr[i][0];
  73.          col = sparseArr[i][1];
  74.          //该位置上对应的值
  75.          int val = sparseArr[i][2];
  76.          arr2[row][col] = val;
  77.       }
  79.       //打印二维数组
  80.       System.out.println("遍历还原后的二维数组");
  81.       for (int i = 0; i < arr2.length; i++) {
  82.          for (int j = 0; j < arr2[0].length; j++) {
  83.             System.out.print(arr2[i][j] + "   ");
  84.          }
  85.          System.out.println();
  86.       }
  87.    }
  88. }
  90. 运行结果
  91. 遍历二维数组
  92. 0   0   0   0   0   0   0   0   0   0   0   
  93. 0   0   1   0   0   0   0   0   0   0   0   
  94. 0   0   0   2   0   0   0   0   0   0   0   
  95. 0   0   0   0   3   0   0   0   0   0   0   
  96. 0   0   0   0   0   0   0   0   0   0   0   
  97. 0   0   0   0   0   0   0   0   0   0   0   
  98. 0   0   0   0   0   0   0   0   0   0   0   
  99. 0   0   0   0   0   0   0   0   0   0   0   
  100. 0   0   0   0   0   0   0   0   0   0   0   
  101. 0   0   0   0   0   0   0   0   0   0   0   
  102. 0   0   0   0   0   0   0   0   0   0   0   
  103. 遍历稀疏数组
  104. 11   11   3   
  105. 1   2   1   
  106. 2   3   2   
  107. 3   4   3   
  108. 遍历还原后的二维数组
  109. 0   0   0   0   0   0   0   0   0   0   0   
  110. 0   0   1   0   0   0   0   0   0   0   0   
  111. 0   0   0   2   0   0   0   0   0   0   0   
  112. 0   0   0   0   3   0   0   0   0   0   0   
  113. 0   0   0   0   0   0   0   0   0   0   0   
  114. 0   0   0   0   0   0   0   0   0   0   0   
  115. 0   0   0   0   0   0   0   0   0   0   0   
  116. 0   0   0   0   0   0   0   0   0   0   0   
  117. 0   0   0   0   0   0   0   0   0   0   0   
  118. 0   0   0   0   0   0   0   0   0   0   0   
  119. 0   0   0   0   0   0   0   0   0   0   0

2、队列

定义

  • 队列是一个有序列表，可以用数组或是链表来实现。

  • 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

    模拟思路

  • 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量

  • 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示

    一、稀疏数组和队列 - 图2

    入队出队操作模拟

    当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：

  • 将尾指针往后移：rear+1 , 当 front == rear 时，队列为空

  • 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。rear == maxSize - 1时，队列满

注意：front指向的是队列首元素的前一个位置
实现代码

  1. package com.atguigu.queue;
  3. import java.util.Scanner;
  5. public class ArrayQueueDemo {
  7.     public static void main(String[] args) {
  8.         //测试一把
  9.         //创建一个队列
  10.         ArrayQueue queue = new ArrayQueue(3);
  11.         char key = ' '; //接收用户输入
  12.         Scanner scanner = new Scanner(System.in);//
  13.         boolean loop = true;
  14.         //输出一个菜单
  15.         while(loop) {
  16.             System.out.println("s(show): 显示队列");
  17.             System.out.println("e(exit): 退出程序");
  18.             System.out.println("a(add): 添加数据到队列");
  19.             System.out.println("g(get): 从队列取出数据");
  20.             System.out.println("h(head): 查看队列头的数据");
  21.             key = scanner.next().charAt(0);//接收一个字符
  22.             switch (key) {
  23.             case 's':
  24.                 queue.showQueue();
  25.                 break;
  26.             case 'a':
  27.                 System.out.println("输出一个数");
  28.                 int value = scanner.nextInt();
  29.                 queue.addQueue(value);
  30.                 break;
  31.             case 'g': //取出数据
  32.                 try {
  33.                     int res = queue.getQueue();
  34.                     System.out.printf("取出的数据是%d\n", res);
  35.                 } catch (Exception e) {
  36.                     // TODO: handle exception
  37.                     System.out.println(e.getMessage());
  38.                 }
  39.                 break;
  40.             case 'h': //查看队列头的数据
  41.                 try {
  42.                     int res = queue.headQueue();
  43.                     System.out.printf("队列头的数据是%d\n", res);
  44.                 } catch (Exception e) {
  45.                     // TODO: handle exception
  46.                     System.out.println(e.getMessage());
  47.                 }
  48.                 break;
  49.             case 'e': //退出
  50.                 scanner.close();
  51.                 loop = false;
  52.                 break;
  53.             default:
  54.                 break;
  55.             }
  56.         }
  58.         System.out.println("程序退出~~");
  59.     }
  61. }
  63. // 使用数组模拟队列-编写一个ArrayQueue类
  64. class ArrayQueue {
  65.     private int maxSize; // 表示数组的最大容量
  66.     private int front; // 队列头
  67.     private int rear; // 队列尾
  68.     private int[] arr; // 该数据用于存放数据, 模拟队列
  70.     // 创建队列的构造器
  71.     public ArrayQueue(int arrMaxSize) {
  72.         maxSize = arrMaxSize;
  73.         arr = new int[maxSize];
  74.         front = -1; // 指向队列头部，分析出front是指向队列头的前一个位置.
  75.         rear = -1; // 指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
  76.     }
  78.     // 判断队列是否满
  79.     public boolean isFull() {
  80.         return rear == maxSize - 1;
  81.     }
  83.     // 判断队列是否为空
  84.     public boolean isEmpty() {
  85.         return rear == front;
  86.     }
  88.     // 添加数据到队列
  89.     public void addQueue(int n) {
  90.         // 判断队列是否满
  91.         if (isFull()) {
  92.             System.out.println("队列满，不能加入数据~");
  93.             return;
  94.         }
  95.         rear++; // 让rear 后移
  96.         arr[rear] = n;
  97.     }
  99.     // 获取队列的数据, 出队列
  100.     public int getQueue() {
  101.         // 判断队列是否空
  102.         if (isEmpty()) {
  103.             // 通过抛出异常
  104.             throw new RuntimeException("队列空，不能取数据");
  105.         }
  106.         front++; // front后移
  107.         return arr[front];
  109.     }
  111.     // 显示队列的所有数据
  112.     public void showQueue() {
  113.         // 遍历
  114.         if (isEmpty()) {
  115.             System.out.println("队列空的，没有数据~~");
  116.             return;
  117.         }
  118.         for (int i = 0; i < arr.length; i++) {
  119.             System.out.printf("arr[%d]=%d\n", i, arr[i]);
  120.         }
  121.     }
  123.     // 显示队列的头数据， 注意不是取出数据
  124.     public int headQueue() {
  125.         // 判断
  126.         if (isEmpty()) {
  127.             throw new RuntimeException("队列空的，没有数据~~");
  128.         }
  129.         return arr[front + 1];
  130.     }
  131. }

环形队列

思路：

  • front变量指向队首元素，初值为0
  • rear变量指向队尾元素的下一个元素，初值为0。规定空出一个位置
  • 队列为空的判定条件：front == rear
  • 队列为满的判定条件：(rear + 1) % maxSize == front
  • 队列中有效元素的个数：(rear - front + maxSize) % maxSize
  • 入队和出队时，都需要让标记对maxSize取模

代码

  1. package com.atguigu.queue;
  3. import java.util.Scanner;
  5. public class CircleArrayQueueDemo {
  7.     public static void main(String[] args) {
  9.         //测试一把
  10.         System.out.println("测试数组模拟环形队列的案例~~~");
  12.         // 创建一个环形队列
  13.         CircleArray queue = new CircleArray(4); //说明设置4, 其队列的有效数据最大是3
  14.         char key = ' '; // 接收用户输入
  15.         Scanner scanner = new Scanner(System.in);//
  16.         boolean loop = true;
  17.         // 输出一个菜单
  18.         while (loop) {
  19.             System.out.println("s(show): 显示队列");
  20.             System.out.println("e(exit): 退出程序");
  21.             System.out.println("a(add): 添加数据到队列");
  22.             System.out.println("g(get): 从队列取出数据");
  23.             System.out.println("h(head): 查看队列头的数据");
  24.             key = scanner.next().charAt(0);// 接收一个字符
  25.             switch (key) {
  26.             case 's':
  27.                 queue.showQueue();
  28.                 break;
  29.             case 'a':
  30.                 System.out.println("输出一个数");
  31.                 int value = scanner.nextInt();
  32.                 queue.addQueue(value);
  33.                 break;
  34.             case 'g': // 取出数据
  35.                 try {
  36.                     int res = queue.getQueue();
  37.                     System.out.printf("取出的数据是%d\n", res);
  38.                 } catch (Exception e) {
  39.                     // TODO: handle exception
  40.                     System.out.println(e.getMessage());
  41.                 }
  42.                 break;
  43.             case 'h': // 查看队列头的数据
  44.                 try {
  45.                     int res = queue.headQueue();
  46.                     System.out.printf("队列头的数据是%d\n", res);
  47.                 } catch (Exception e) {
  48.                     // TODO: handle exception
  49.                     System.out.println(e.getMessage());
  50.                 }
  51.                 break;
  52.             case 'e': // 退出
  53.                 scanner.close();
  54.                 loop = false;
  55.                 break;
  56.             default:
  57.                 break;
  58.             }
  59.         }
  60.         System.out.println("程序退出~~");
  61.     }
  63. }
  66. class CircleArray {
  67.     private int maxSize; // 表示数组的最大容量
  68.     //front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 
  69.     //front 的初始值 = 0
  70.     private int front; 
  71.     //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
  72.     //rear 的初始值 = 0
  73.     private int rear; // 队列尾
  74.     private int[] arr; // 该数据用于存放数据, 模拟队列
  76.     public CircleArray(int arrMaxSize) {
  77.         maxSize = arrMaxSize;
  78.         arr = new int[maxSize];
  79.     }
  81.     // 判断队列是否满
  82.     public boolean isFull() {
  83.         return (rear  + 1) % maxSize == front;
  84.     }
  86.     // 判断队列是否为空
  87.     public boolean isEmpty() {
  88.         return rear == front;
  89.     }
  91.     // 添加数据到队列
  92.     public void addQueue(int n) {
  93.         // 判断队列是否满
  94.         if (isFull()) {
  95.             System.out.println("队列满，不能加入数据~");
  96.             return;
  97.         }
  98.         //直接将数据加入
  99.         arr[rear] = n;
  100.         //将 rear 后移, 这里必须考虑取模
  101.         rear = (rear + 1) % maxSize;
  102.     }
  104.     // 获取队列的数据, 出队列
  105.     public int getQueue() {
  106.         // 判断队列是否空
  107.         if (isEmpty()) {
  108.             // 通过抛出异常
  109.             throw new RuntimeException("队列空，不能取数据");
  110.         }
  111.         // 这里需要分析出 front是指向队列的第一个元素
  112.         // 1. 先把 front 对应的值保留到一个临时变量
  113.         // 2. 将 front 后移, 考虑取模
  114.         // 3. 将临时保存的变量返回
  115.         int value = arr[front];
  116.         front = (front + 1) % maxSize;
  117.         return value;
  119.     }
  121.     // 显示队列的所有数据
  122.     public void showQueue() {
  123.         // 遍历
  124.         if (isEmpty()) {
  125.             System.out.println("队列空的，没有数据~~");
  126.             return;
  127.         }
  128.         // 思路：从front开始遍历，遍历多少个元素
  129.         // 动脑筋
  130.         for (int i = front; i < front + size() ; i++) {
  131.             System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
  132.         }
  133.     }
  135.     // 求出当前队列有效数据的个数
  136.     public int size() {
  137.         // rear = 2
  138.         // front = 1
  139.         // maxSize = 3 
  140.         return (rear + maxSize - front) % maxSize;   
  141.     }
  143.     // 显示队列的头数据， 注意不是取出数据
  144.     public int headQueue() {
  145.         // 判断
  146.         if (isEmpty()) {
  147.             throw new RuntimeException("队列空的，没有数据~~");
  148.         }
  149.         return arr[front];
  150.     }
  151. }