Java数据结构与算法之稀疏数组与队列深入理解

网友投稿 656 2022-12-09

Java数据结构与算法之稀疏数组与队列深入理解

Java数据结构与算法之稀疏数组与队列深入理解

目录一、数据结构和算法简介二、稀疏数组稀疏数组的应用实例二维数组与稀疏数组的转换二维数组 转 稀疏数组的思路稀疏数组 转 原始的二维数组的思路三、队列数组模拟队列代码优化:数组模拟环形队列

之前学完了java SE的知识,掌握了面向对象的编程思想,但对集合、多线程、反射、流的使用等内容理解的还不是很深入,打算再学习数据结构与算法的同时,在空闲的时间里去图书馆看《Java核心技术 卷 I》这本书,很多大佬对这本书很推崇,之前在图书馆也看过其他Java的书籍,经过对比,这本书确实写的很有内涵;之后也会把看书过程中的收获写出来分享给大家,同时,连续的更新博客也是对自己学习的督促。终极目标:超越大我两级的学长,拿到大厂sp,年薪40w+!!!

一、数据结构和算法简介

二、稀疏数组

稀疏数组的应用实例

1) 稀疏数组,来保留类似前面的二维数组(棋盘、地图等等)

2) 把稀疏数组存盘,并且可以从新恢复原来的二维数组数据

二维数组与稀疏数组的转换

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

1.遍历原始的二维数组,得到有效数据的个数 sum

2.根据sum就可以创建稀疏数组 sparseArr int[sum + 1][3]

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

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

1.先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组,比如上面的 chessArr2 = int[11][11]

2.在读取稀疏数组后几行的数据,并赋给原始的二维数组即可。

public class SparseArray {

public static void main(String[] args) {

// 创建一个原始的二维数组11 * 11

// 0:表示没有棋子,1表示黑子 2表示蓝子

int chessArr1[][] = new int[11][11];

chessArr1[1][2] = 1;

chessArr1[2][3] = 2;

// 新加的棋子;只需在这加就可以

chessArr1[4][5] = 6;

// 输出原始的二维数组

System.out.println("原始的二维数组~~");

for (int[] row : chessArr1) {

for (int data : row) {

System.out.printf("%d\t", data);

}

System.out.println();

}

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

// 1.先遍历二维数组 得到非0数据的个数

int sum = 0;

for (int i = 0; i < 11; i++) {

for (int j = 0; j < 11; j++) {

if (chessArr1[i][j] != 0) {

sum++;

}

}

}

// 2.创建对应的稀疏数组

int sparseArr[][] = new int[sum + 1][3];

// 给稀疏数组赋值

sparseArr[0][0] = 11;

sparseArr[0][1] = 11;

sparseArr[0][2] = sum;

// 遍历二维数组,将非0的值存放到sparseArr中

int count = 0;// count 用于记录是第几个非0数据

for (int i = 0; i < 11; i++) {

for (int j = 0; j < 11; 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]);

}

// 将稀疏数组-->>恢复成原始的二维数组

// 1.先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组

int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

// 2.在读取稀疏数组后几行的数据(从第二行开始),并赋给原始的二维数组即可

for (int i = 1; i < sparseArr.length; i++) {

chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];

}

// 输出恢复后的二维数组

System.out.println();

System.out.println("恢复后的二维数组");

for (int[] row : chessArr2) {

for (int data : row) {

System.out.printf("%d\t", data);

}

System.out.println();

}

}

}

三、队列

数组模拟队列

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) {

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;

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];

}

}

上述代码问题分析:

1)目前数组使用一次就不能用,没有达到复用的效果

2)将这个数组使用算法,改进成一个环形的队列(使用到了取模:%相关的算法)

代码优化:数组模拟环形队列

思路如下:

1.front变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素front的初始值 = 0

2.rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间做为约定。rear的初始值 = 0

3.当队列满时,条件是[rear + 1] % maxSize == front【满】

4.对队列为空的条件,rear == front空

5.当我们这样分析,队列中有效的数据的个数:(rear + maxSize - front) % maxSize

6.我们就可以在原来的队列上修改得到,一个环形队列

public class CircleArrayQueueDemo {

public static void main(String[] args) {

// 测试

System.out.println("测试数组模拟环形队列的案例~~");

// 创建一个环形队列

CircleArray queue = new CircleArray(4);// 说明设置4,其队列的有效数据最大是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) {

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;

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];

}

}

以上就是Java数据结构与算法之稀疏数组与队列深入理解的详细内容,更多关于Java稀疏数组与队列的资料请关注我们其它相关文章!

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:Java Durid进行JDBC连接详解
下一篇:Java的Hello World详解
相关文章

 发表评论

暂时没有评论,来抢沙发吧~