数据结构与算法
稀疏数组
二维数组创建方法
int arr[][] = new int[1][1];
第一个【】内存放有多少个一维数组
第二个【】存放一维数组的长度
arr[0][0] = 1 arr[0][1] =2 arr[0][2] =3 [输出] [1,2,3]
二维数组的遍历
int arr[][] = new int[2][2]; for (int[] row : arr) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); }
棋盘案例
稀疏 sparsearray 数组，编写的五子棋程序中，有存盘退出和续上盘的功能。
分析问题:
因为该二维数组的很多值是默认值 0, 因此记录了很多没有意义的数据.->稀疏数组。
稀疏数组介绍
使用场景
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。 
我们创造的稀疏数组，
- 也是一个二维数组 他的【0】【n】会用来存放原来的二维数组的大小和长度
- 接下来的【n】【n】都会用放每一个值和他的二维数组坐标
应用实例
- 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
- 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
- 整体思路分析
编写实例思路操作图
代码实现
/** * @projectName: DataStructure * @package: com.hyc.DataStructure.SarseArray * @className: sarseArray * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2021/12/15 16:14 * @version: 1.0 */ public class sarseArray { public static void main(String[] args) { /*创建原始的二维数组 11*11*/ //0：表示没有棋子，1表示黑子，2表示白字 int chessArr[][] = new int[11][11]; chessArr[1][2] = 1; chessArr[2][3] = 2; chessArr[4][6] = 3; System.out.println("输出原始的二维数组"); for (int[] row : chessArr) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } //遍历二维数组所有非0 的数 int sum = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArr[i][j] != 0) { sum++; } } } System.out.println("sum = " + sum); //将二维数组转化成 稀疏数组，创建对应的稀疏数组 int sparseArr[][] = new int[sum + 1][3]; sparseArr[0][0] = 11; sparseArr[0][1] = 11; sparseArr[0][2] = sum; // 完成了上述的步骤我们就拿到了 稀疏数组的第一行 就是我们存放数组大小和值的 //接下来我们需要将二维数组的值放到 稀疏数组中 /* * sparseArr[?][0] = i * sparseArr[?][1] = j * sparseArr[?][2] = chessArr[i][j]; * 我们通过这种方式将 二维数组的坐标和值存到稀疏数组中 * */ // 我们用一个int 变量来记录是第几个 int count = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArr[i][j] != 0) { count++; sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = chessArr[i][j]; } } } // 输出稀疏数组 System.out.println(); System.out.println("得到的稀疏数组为"); for (int i = 0; i < sparseArr.length; i++) { System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]); } // 将稀疏数组回复成原始的二维数组 /* * 1.先从稀疏数组的第一列 读取出 有关原始数组长度和有多少非0的值 * 2.之后读取稀疏数组的后几行数据，并且赋值给原始的二维数组即可 * */ int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]]; for (int i = 1; i < sparseArr.length; i++) { chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; } System.out.println("输出恢复之后的二维数组"); for (int[] row : chessArr2) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } } }
输出结果
队列
队列的一个使用场景
银行排队的案例:
队列介绍
- 队列是一个有序列表，可以用数组或是链表来实现。
- 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
- 示意图：(使用数组模拟队列示意图)
数组模拟队列
数组模拟队列思路：思路图
- 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队 列的最大容量。
- 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标， front 会随着数据输出而改变，而 rear 则是随着数据输入而改变，如图所示
新增思路
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析
- 将尾指针往后移：rear+1 , 当 front == rear 【空】
- 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]
根据队列思路实现数组模拟队列
/** * @projectName: DataStructure * @package: com.hyc.DataStructure.Queue * @className: ArrayQueueDemo * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2021/12/16 14:24 * @version: 1.0 */ public class ArrayQueueDemo { public static void main(String[] args) { //创建一个队列 ArrayQueue queue = new ArrayQueue(3); char key = ' '; //接收用户输入 Scanner scanner = new Scanner(System.in);// boolean loop = true; //输出一个菜单 while (loop) { System.out.println("s(show): 显示队列"); System.out.println("e(exit): 退出程序"); System.out.println("a(add): 添加数据到队列"); System.out.println("g(get): 从队列取出数据"); System.out.println("h(head): 查看队列头的数据"); key = scanner.next().charAt(0);//接收一个字符 switch (key) { case 's': queue.showQueue(); break; case 'a': System.out.println("输出一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': //取出数据 try { int res = queue.getQueue(); System.out.printf("取出的数据是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'h': //查看队列头的数据 try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'e': //退出 scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~"); } } /* 根据 数组来实现的队列*/ class ArrayQueue { //队列最大上限 private int MaxSize; //队列尾部 private int rear; //队列头部 private int front; //存放队列数据的数组 private int[] ArrayQueue; /** * @author 冷环渊 Doomwatcher * @context: 初始化构造队列，初始化队列和头尾值向 * @date: 2021/12/16 14:30 * @param maxSize * @return: */ public ArrayQueue(int maxSize) { // 获取最大值 this.MaxSize = maxSize; //初始化 队列 ArrayQueue = new int[MaxSize]; //设置最大最小值 rear = -1; front = -1; } /** * @author 冷环渊 Doomwatcher * @context: 判断是否队列是否达到存储上限 * @date: 2021/12/16 14:30 * @param * @return: boolean */ public boolean isfull() { return rear == MaxSize - 1; } /** * @author 冷环渊 Doomwatcher * @context: 判断队列是否是空的 * @date: 2021/12/16 14:32 * @param * @return: boolean */ public boolean isemity() { return rear == front; } /** * @author 冷环渊 Doomwatcher * @context: 向队列插入一条数据 * @date: 2021/12/16 14:34 * @param value * @return: void */ public void addQueue(int value) { if (isfull()) { System.out.println("队列已满 不能加入更多的数据"); return; } //++ 是后赋值，意思是执行完当前赋值，rear向后移动一位 rear++; ArrayQueue[rear] = value; } /** * @author 冷环渊 Doomwatcher * @context:获取队列的值 * @date: 2021/12/16 14:37 * @param * @return: void */ public int getQueue() { if (isemity()) { throw new RuntimeException("该队列是空的 无法获取到内容"); } front++; return ArrayQueue[front]; } /** * @author 冷环渊 Doomwatcher * @context:遍历队列输出 注意是遍历 不会更改队列的指向 * @date: 2021/12/16 14:42 * @param * @return: void */ public void showQueue() { if (isemity()) { System.out.println("队列没有可以遍历的数值"); } for (int i = 0; i < ArrayQueue.length; i++) { System.out.printf("arrQueue[%d]: %d\n", i, ArrayQueue[i]); } } /** * @author 冷环渊 Doomwatcher * @context:这里我们和上一个遍历方法一样 只是展示数据并不是去出数据 * @date: 2021/12/16 14:45 * @param * @return: void */ public int headQueue() { if (isemity()) { throw new RuntimeException("没有头数据"); } return ArrayQueue[front + 1]; } }
问题分析并优化
- 目前数组使用一次就不能用， 没有达到复用的效果
- 将这个数组使用算法，改进成一个环形的队列 取模：%
数组模拟环形队列
对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)
分析说明：
- 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize == front 满]
- rear == front [空]
根据思路实现数组模拟环形队列
/** * @projectName: DataStructure * @package: com.hyc.DataStructure.Queue * @className: CircleArrayQueueDemo * @author: 冷环渊 doomwatcher * @description: TODO * @date: 2021/12/16 16:28 * @version: 1.0 */ public class CircleArrayQueueDemo { public static void main(String[] args) { System.out.println("测试环形队列"); //创建一个队列 这里空间为4 最大有效空间为3 留出一个空间作为约定 CircleArrayQueue queue = new CircleArrayQueue(4); char key = ' '; //接收用户输入 Scanner scanner = new Scanner(System.in);// boolean loop = true; //输出一个菜单 while (loop) { System.out.println("s(show): 显示队列"); System.out.println("e(exit): 退出程序"); System.out.println("a(add): 添加数据到队列"); System.out.println("g(get): 从队列取出数据"); System.out.println("h(head): 查看队列头的数据"); key = scanner.next().charAt(0);//接收一个字符 switch (key) { case 's': queue.showQueue(); break; case 'a': System.out.println("输出一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': //取出数据 try { int res = queue.getQueue(); System.out.printf("取出的数据是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'h': //查看队列头的数据 try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'e': //退出 scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~"); } } /** 环形队列 * 思路变化： * 之前的队列有问什么问题所在 * 问题分析并优化 *1) 目前数组使用一次就不能用， 没有达到复用的效果 *2) 将这个数组使用算法，改进成一个环形的队列 取模：% * 思路如下 ： * 1.front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr(front]就是队列的第一个元素 * front的初始值 * 2.rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定. * rear的初始值=0 * 3.当队列满时，条件是（rear+1)%maxSize=front【满】 * 4.对队列为空的条件，rear==front空 * 5.当我们这样分析，队列中有效的数据的个数（rear+maxSize-front)%maxSize//rear=1front=0 * 6.我们就可以在原来的队列上修改得到，一个环形队列 * * */ class CircleArrayQueue { //队列最大上限 private int MaxSize; //队列尾部 思路发生变化这次我们的队尾值变化为0指向队列最后一位的前一位 private int rear; //队列头部 思路变化 指向队头的第一位 也就是下标 为 0 private int front; //存放队列数据的数组 private int[] ArrayQueue; /** * @author 冷环渊 Doomwatcher * @context: 初始化构造队列，初始化队列和头尾值向 * 这里为什么没有初始化队头队尾，因为默认 = 0 * @date: 2021/12/16 14:30 * @param maxSize * @return: */ public CircleArrayQueue(int maxSize) { // 获取最大值 this.MaxSize = maxSize; //初始化 队列 ArrayQueue = new int[MaxSize]; } /** * @author 冷环渊 Doomwatcher * @context: * 这里思路变化，因为我们要做环形队列这里我们有一个位置是动态变化的所以我们需要更新计算是否队列已满的方法 * @date: 2021/12/16 14:30 * @param * @return: boolean */ public boolean isfull() { return (rear + 1) % MaxSize == front; } /** * @author 冷环渊 Doomwatcher * @context: 判断队列是否是空的 * @date: 2021/12/16 14:32 * @param * @return: boolean */ public boolean isemity() { return rear == front; } /** * @author 冷环渊 Doomwatcher * @context: * 加入数据我们也要发生变化 这里我们用的是环形了 * rear 的后移不再是最后一位，可能会出现越界的问题 * （rear+1）%maxSize * @date: 2021/12/16 14:34 * @param value * @return: void */ public void addQueue(int value) { if (isfull()) { System.out.println("队列已满 不能加入更多的数据"); return; } //赋值 ArrayQueue[rear] = value; //考虑用取模来后移 rear rear = (rear + 1) % MaxSize; } /** * @author 冷环渊 Doomwatcher * @context: * 为什么不用 ++了呢 因为我们是环形 一定会出现越界，这里考虑取模动态的算出后移的位置 * @date: 2021/12/16 14:37 * @param * @return: void */ public int getQueue() { if (isemity()) { throw new RuntimeException("该队列是空的 无法获取到内容"); } /* * 1，我们这次的思路是front代表的是队列的第一个下标 * 2. 用临时变量来拿出 当前的值 * 3.后移front 返回值 * */ int value = ArrayQueue[front]; front = (front + 1) % MaxSize; return value; } /** * @author 冷环渊 Doomwatcher * @context: * 遍历环形队列 输出 这里我们不再是遍历数组长度了 * 我们需要求出有效的数量 * @date: 2021/12/16 14:42 * @param * @return: void */ public void showQueue() { if (isemity()) { System.out.println("队列没有可以遍历的数值"); } //这里我们因该是从 front 开始遍历 for (int i = front; i < front + Size(); i++) { //这里下标我们选择取模 应为是环形的会出现越界的情况，所以我们使用取模运算 System.out.printf("arrQueue[%d]: %d\n", i % MaxSize, ArrayQueue[i % MaxSize]); } } /*编写一个求出队列有效数据数量的放啊*/ public int Size() { /* 取模思路套用 * 1. rear = 1 * 2. front = 0 * 3. maxSize = 3 * （1+3-0）%3 = 1 应为算出来是下标 所以我们这里有两个有效数据 0，1 * */ return (rear + MaxSize - front) % MaxSize; } /** * @author 冷环渊 Doomwatcher * @context:这里我们和上一个遍历方法一样 只是展示数据并不是去出数据 * 这里不再是 front-1 应为 front此时默认就是0 * @date: 2021/12/16 14:45 * @param * @return: void */ public int headQueue() { if (isemity()) { throw new RuntimeException("没有头数据"); } return ArrayQueue[front]; } }
代码执行效果
Java数据结构与算法-java数据结构与算法（二）https://developer.aliyun.com/article/1469490
