Java数据结构与算法_01 稀疏数组和队列

太过爱你忘了你带给我的痛 2023-07-07 11:25 121阅读 0赞

### Java数据结构与算法\_01 ###

*  稀疏数组
 *   *  应用实例
     *   *  代码实现
 *  队列
 *   *  数组模拟队列
     *  数组模拟环形队列

--------------------

***本人是个新手，写下博客用于自我复习、自我总结。  
如有错误之处，请各位大佬指出。  
学习资料来源于：尚硅谷***

--------------------

数据结构包括：线性结构和非线性结构。

**线性结构**：

1）线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。

2）线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构，顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。

3）链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。

4）线性结构常见的有：数组、队列、链表和栈。

**非线性结构**：

非线性结构包括：二维数组，多维数组，广义表，树结构，图结构。

--------------------

# 稀疏数组 #

引例：假如，编写了一个五子棋程序，要怎么记录落子位置呢？ => 可以使用二维数组的方式记录棋盘  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70]

0 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0
    0 0 2 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0
    0 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<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();
    		}
    	}
    
    }

输出结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70 1]

--------------------

# 队列 #

（1）队列是一个有序列表，可以用数组或是链表来实现。用数组来实现就是顺序存储，用链表来实现就是链式存储。

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

## 数组模拟队列 ##

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70 2]  
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front和rear，分别用来记录队列的前端和后端的下标，front会随着数据输出而改变，rear会随着数据输入而改变。

这就会出现两种判断的情况：

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200223101956751.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200223113049980.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200223223432802.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NjEzOTMx,size_16,color_FFFFFF,t_70