稀疏数组：
应用场景，实际的需求：
编写五子棋程序中，有存档退出和保存上一句的功能。
实现：
用0代表还没有下的位置，用1代表黑子，用2代表白子。使用二维数组记录棋盘。
分析问题：
因为该二维数组的很多值默认值是0，因此记录了很多没有意义的数据->稀疏数组。
介绍：当一个数组中大部分元素为0，或者同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是：
1、记录数组一共有几行几列，有多少个不同的值。
2、把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
二维数组转稀疏数组的思路：
1、遍历原始的二维数组，得到有效数据个数sum
2、根据sum就可以创建稀疏数组spareseArr intsum+1
3、将二维数组的有效数据存入到稀疏数组中
棋盘的稀疏数组：
| row | col | val | |
|---|---|---|---|
| 0 | 11 | 11 | 2 |
| 1 | 1 | 2 | 1 |
| 2 | 2 | 3 | 2 |
第一行代表：棋盘的大小，11*11的二维数组，有2个有效位置。
第二行代表：row代表有效位置的行，col代表有效位置的列，val代表该位置的数：
第三行代表：第二个有效数字的位置和它的值。
//稀疏数组和五子棋盘
public class test01 {
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;
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);
//创建稀疏数组，遍历原始二维数组的数据，存入稀疏数组中
int xishuArr[][] = new int[sum+1][3];
//存入稀疏数组的第一行
xishuArr[0][0] = 11;
xishuArr[0][1] = 11;
xishuArr[0][2] = sum;
int count = 0;
for(int i =0 ; i < 11 ; i++) {
for(int j = 0 ; j < 11 ; j++) {
if(chessArr[i][j] != 0) {
count++;
//有效数据从稀疏数组的第二行开始存放
xishuArr[count][0] = i;
xishuArr[count][1] = j;
xishuArr[count][2] = chessArr[i][j];
}
}
}
//输出稀疏数组
for(int chess[]:xishuArr) {
for(int a:chess) {
System.out.printf("%d\t",a);
}
System.out.println();
}
/* 稀疏数组转二维数组的思路：
1、先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组。
2、再读取稀疏数组后几行数据，并赋予原始二维数组即可。
*/
int chessArr2[][] = new int[xishuArr[0][0]][xishuArr[0][1]];
//注意这里的xishuArr.length计算的就是稀疏数组的行数
for(int i=1;i<xishuArr.length;i++) {
//稀疏数组的第二行的第一列和第二列的数据分别作为棋子在新棋盘的位置，并赋予该棋子的值
chessArr2[xishuArr[i][0]][xishuArr[i][1]] = xishuArr[i][2];
}
System.out.println("根据稀疏数组恢复后的数组~~");
for(int row[]:chessArr2) {
for(int data: row) {
System.out.printf("%d\t",data);
}
System.out.println();
}
}
}
循环队列
介绍
队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。先存入的队列的数据，要先取出，后存入的要后取出。
数组模拟队列：
因为队列的输出，输入分别是从前后端来处理，因此需要两个变量front以及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则使随着数据输入而改变。注意先存先取原则。
循环队列思路分析：
注意循环队列是为了区分队列是否为空，是否为满，做了一个解决办法，将循环队列的空间空出一个位置。
队列为空的判断条件是：rear=front。
队列为满的判断条件是：（rear+1）%maxSize = front
以下是百度百科给出的解释：
- 在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=rear，而队列判满的条件是front=（rear+1)%MaxSize。
代码实现：
package queue;
import java.util.Scanner;
public class CircleArrayQueue {
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(git):获取数据");
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) {
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop =false;
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
class CircleArray{
private int maxSize; //表示数组的最大容量
private int front; //队列头
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("队列为空，不能取数据~~");
//这里不能写return,throw已经终止了程序。
}
/*
* 这里需要分析出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() {
//这里再加上一个maxSize的原因就是怕rear比front小的情况
return (rear+maxSize-front) % maxSize;
}
//显示队列的头部
public int headQueue() {
//判断是否为空
if(isEmpty()) {
throw new RuntimeException("队列时空的，无法输出~~");
}
return arr[front];
}
}
网友评论