Java数据结构与算法_01 稀疏数组和队列
本文共 9486 字，大约阅读时间需要 31 分钟。
Java数据结构与算法_01
本人是个新手，写下博客用于自我复习、自我总结。 如有错误之处，请各位大佬指出。 学习资料来源于：尚硅谷
数据结构包括：线性结构和非线性结构。
线性结构：
1）线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
2）线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构，顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。
3）链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。
4）线性结构常见的有：数组、队列、链表和栈。
非线性结构：
非线性结构包括：二维数组，多维数组，广义表，树结构，图结构。
稀疏数组
引例：假如，编写了一个五子棋程序，要怎么记录落子位置呢？ => 可以使用二维数组的方式记录棋盘
0 0 0 0 0 0 0 00 1 0 0 0 0 0 00 0 2 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0
因为该二维数组的很多值是默认值0，因此记录了很多没有意义的数据。稀疏数组就该出现了。
稀疏数组：
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是：
1）记录数组一共有几行几列，有多少个不同的值。
2）把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。即：
行(row) 列(col) 值(value)[0] 8 8 2[1] 1 1 1[2] 2 2 2
本来之前是 8X8=64 的一个数组，现在变成了 3X3=9 的一个数组，大大的缩小了数组的规模。
解释：
（1）稀疏数组中的行和列，和普通数组一样，从0开始记录。 （2）稀疏数组的第0行，记录的是，整个普通数组的真实行值（不从0记录）、整个普通数组的真实列值（不从0记录）、整个普通数组中与默认值不同的值的个数（与其他数值不同的那些）。 （3）稀疏数组中，从上到下数值的排序，可以按照原二维数组的行，从上到下的排序。（比如先把原二维数组的第0行中所有数据记录，再记录原二维数组的第1行中所有数据…以此类推） （4）稀疏数组的第1行，记录的是，稀疏数组的第一个值。原二维数组的第1行，第1列处的数值1。以此类推。应用实例
1）使用稀疏数组，来保留类似前面的二维数组（棋盘、地图等等）
2）这个稀疏数组可以重新恢复原来的二维数组 3）整体思路分析：二维数组 转 稀疏数组的思路：
①遍历原始的二维数组，得到有效数据的个数sum。 ②根据sum就可以创建稀疏数组sparseArr int[sum+1][3] ③将二维数组的有效数据存入到稀疏数组中。稀疏数组 转 二维数组的思路：
①读取稀疏数组的第0行，根据这一行的数据，创建原始的二维数组chessArr2 = int[8][8] ②再读取稀疏数组后几行的数据，并赋给原始的二维数组即可。代码实现
public class SparseArray { public static void main(String[] args) { // 创建一个原始的二维数组 8*8 // 0：表示没有棋子 1：表示黑色棋子 2：表示蓝色棋子 int chessArr1[][] = new int[8][8]; chessArr1[1][1] = 1; chessArr1[2][2] = 2; // 输出原始的二维数组 System.out.println("原始的二维数组："); for (int[] row : chessArr1) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } // 遍历原始的二维数组，得到有效数据的个数sum int sum = 0; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (chessArr1[i][j] != 0) { sum++; } } } // 创建对应的稀疏数组 int sparseArr[][] = new int[sum + 1][3]; // 给稀疏数组赋值 sparseArr[0][0] = 8; sparseArr[0][1] = 8; sparseArr[0][2] = sum; // 遍历二维数组，将非0的值存放到稀疏数组中 int count = 0;// 用于记录是第一个非0数据 for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if (chessArr1[i][j] != 0) { count++; sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = chessArr1[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]); } // 将稀疏数组转成二维数组 // 先读取稀疏数组的第0行，根据这一行的数据，创建原始的二维数组 int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]]; // 读取稀疏数组后几行的数据，并赋给原始的二维数组 for(int i =1;i 输出结果：
队列
（1）队列是一个有序列表，可以用数组或是链表来实现。用数组来实现就是顺序存储，用链表来实现就是链式存储。
（2）队列遵循先入先出的原则，即：先存入队列的数据，要先取出，后存入的要后取出。
数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。
这就会出现两种判断的情况：
第1种情况：front==rear，意味着空队列；第2种情况：rear==maxSize-1，意味着队列满。
具体思路的分析：最开始rear和front都为-1，数组arr[]的容量为maxSize。程序无非也就以下几种操作：
（先判断，再改变数据） （1）添加数据：当队列不满时，rear++ 之后 arr[rear] = 要添加的数据 （2）获取数据：当队列不空时，front++ 之后 输出 arr[front] （3）显示数据：当队列不空时，遍历数组 （4）获取头数据：当队列不空时，直接输出arr[front+1]接下来，看代码：
import java.util.Scanner;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; System.out.println("输入相应字母，完成操作"); // 输出一个菜单 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) { System.out.println(e.getMessage()); } break; case 'h': try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\n", res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'e': scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~"); }}// 使用数组模拟队列-编写一个ArrayQueue类class ArrayQueue { private int maxSize; // 表示数组的最大容量 private int front; // 队列头 private int rear; // 队列尾 private int[] arr; // 该数据用于存放数据, 模拟队列 // 创建队列的构造器 public ArrayQueue(int arrMaxSize) { maxSize = arrMaxSize; arr = new int[maxSize]; front = -1; // 指向队列头部，分析出front是指向队列头的前一个位置 rear = -1; // 指向队列尾，指向队列尾的数据(即就是队列最后一个数据) } // 判断队列是否满 public boolean isFull() { return rear == maxSize - 1; } // 判断队列是否为空 public boolean isEmpty() { return rear == front; } // 添加数据到队列 public void addQueue(int n) { // 判断队列是否满 if (isFull()) { System.out.println("队列满，不能加入数据~"); return; } rear++; // 让rear 后移 arr[rear] = n; } // 获取队列的数据, 出队列 public int getQueue() { // 判断队列是否空 if (isEmpty()) { // 通过抛出异常 throw new RuntimeException("队列空，不能取数据"); } front++; // front后移 return arr[front]; } // 显示队列的所有数据 public void showQueue() { // 遍历 if (isEmpty()) { System.out.println("队列空的，没有数据~~"); return; } for (int i = 0; i < arr.length; i++) { System.out.printf("arr[%d]=%d\n", i, arr[i]); } } // 显示队列的头数据， 注意不是取出数据 public int headQueue() { // 判断 if (isEmpty()) { throw new RuntimeException("队列空的，没有数据~~"); } return arr[front + 1]; }} 进行到这，只要经过测试，就会发现数组模拟队列其实是有问题的。当数据填满，然后全部取出来或者取了一部分之后，理论上应该可以从最初的位置或者说从当前位置继续存储，因为数组的最大容量显然还没满，但是已经不能加入数据了，这和front和rear是有很大关系的，这个数组只能用这么一次。接下来可以使用环形队列来解决问题。
数组模拟环形队列
有了上述的基础之后，对它进行扩展，其实就方便很多。
接下来所有的讨论，队列留出了一个预留空间，就是以下所有分析是基于：队列长度为有效数据+1的基础上，就是CircleArray queue = new CircleArray(4);但实际上最多只能存放3个数据。留一个预留空间是为了更好的做出调整。
仍然会出现两种判断的情况，但是第2种情况有了改变：
第1种情况：front==rear，意味着空队列；第2种情况：(rear+1)%maxSize==front，意味着队列满。除此以外：队列中有效的数据的个数 (rear + maxSize - front) % maxSize
具体思路的分析：最开始rear和front都改为0，数组arr[]的容量为maxSize。程序依然是以下几种操作：
（先判断，再改变数据） （1）添加数据：当队列不满时，arr[rear]=要添加的数据，之后rear后移：rear=(rear+1)%maxSize。也就是说，既然队列不满，rear是肯定要后移的。但是需要考虑的情况就是，rear的后移有可能超出了原本数组的最大容量的那个数，但是数组本身之前占用的空间或者说之前的数据已经被取出，那么就可以重新占用这些空间。怎么让rear重新回到起点，那就需要取模。（2）获取数据：当队列不空时，将arr[front]输出。然后front后移：front=(front+1)%maxSize。
（3）显示数据：当队列不空时，遍历数组。但是需要从front开始遍历。因为很显然的，有可能front所在位置之前的位置，比如数组的0位置，可能数据不合理或者说不是它该出现的位置。所以现在要从front开始遍历。遍历多少个，取决于当前队列中有效数据的个数。
（4）获取头数据：当队列不空时，直接输出arr[front]
与之前最大的不同是需要取模。
代码如下：
import java.util.Scanner;public class CircleArrayQueueDemo { public static void main(String[] args) { // 创建一个环形队列 CircleArray queue = new CircleArray(4); char key = ' '; // 接收用户输入 Scanner scanner = new Scanner(System.in); boolean loop = true; System.out.println("输入相应字母，完成操作"); // 输出一个菜单 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) { System.out.println(e.getMessage()); } break; case 'h': try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\n", res); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 'e': scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出"); }}class CircleArray { private int maxSize; // 表示数组的最大容量 //front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 //front 的初始值 = 0 private int front; //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定. //rear 的初始值 = 0 private int rear; // 队列尾 private int[] arr; // 该数据用于存放数据, 模拟队列 public CircleArray(int arrMaxSize) { maxSize = arrMaxSize; arr = new int[maxSize]; } // 判断队列是否满 public boolean isFull() { return (rear + 1) % maxSize == front; } // 判断队列是否为空 public boolean isEmpty() { return rear == front; } // 添加数据到队列 public void addQueue(int n) { // 判断队列是否满 if (isFull()) { System.out.println("队列满，不能加入数据~"); return; } //直接将数据加入 arr[rear] = n; //将 rear 后移, 这里必须考虑取模 rear = (rear + 1) % maxSize; } // 获取队列的数据, 出队列 public int getQueue() { // 判断队列是否空 if (isEmpty()) { // 通过抛出异常 throw new RuntimeException("队列空，不能取数据"); } // 这里需要分析出 front是指向队列的第一个元素 // 1. 先把 front 对应的值保留到一个临时变量 // 2. 将 front 后移, 考虑取模 // 3. 将临时保存的变量返回 int value = arr[front]; front = (front + 1) % maxSize; return value; } // 显示队列的所有数据 public void showQueue() { // 遍历 if (isEmpty()) { System.out.println("队列空的，没有数据~~"); return; } // 思路：从front开始遍历，遍历多少个元素 for (int i = front; i < front + size() ; i++) { System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]); } } // 求出当前队列有效数据的个数 public int size() { return (rear + maxSize - front) % maxSize; } // 显示队列的头数据， 注意不是取出数据 public int headQueue() { // 判断 if (isEmpty()) { throw new RuntimeException("队列空的，没有数据~~"); } return arr[front]; }} 转载地址：http://sayki.baihongyu.com/
你可能感兴趣的文章
Pandas 精萃
查看>>
[第19课] 二项分布1
查看>>
什么是 Pandas?
查看>>
Pandas 如何创建 DataFrame
查看>>
Pandas 查看数据
查看>>
[第20课] 二项分布2
查看>>
感 冒
查看>>
职业瓶颈
查看>>
有些问题不一定要一次完成，有时候可以增加中间步骤
查看>>
Eclipse 常用快捷键
查看>>
DB2 系列文章目录
查看>>
DB2 认证路线图
查看>>
在FedaroCore4下安装DB2 Express-C
查看>>
DB2 目录结构
查看>>
DB2 配置
查看>>
DB2 CHNGPGS_THRES 参数
查看>>
DB2安全性概述
查看>>
DB2 用户管理
查看>>
DB2 脚本
查看>>
DB2 锁升级失败将引起死锁
查看>>