1.稀疏数组与队列
1.1 稀疏数组
介绍：
- 记录数组一共有几行，有多少个不同的值
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
分析问题：二维数组的很多值默认为0，记录了很多没有意义的数据 --> 转为稀疏数组
稀疏数组
分析思路：
二维数组转稀疏数组
1.遍历原始二维数组，得到有效数据的个数sum
2.根据sum创建稀疏数组 sparseArr[sum+1][3]
3.将二维数组的有效数据存入到稀疏数组
4.将稀疏数组以文件形式存于磁盘
稀疏数组转二维数组
1.读取磁盘文件
2.根据稀疏数组的第一行数据创建二维数组，如上图 chessArr = int[11][11]
3.在读取稀疏数组后几行的数据，并赋值给二维数组即可
代码实现：
package sparsearray;
import java.io.*;
public class SparseArray {
//棋盘行数
private static final int ROWS = 11;
//棋盘列数
private static final int COLUMNS = 11;
//二维数组
static int[][] chessArr = new int[ROWS][COLUMNS];
//黑子和白字之和
private static int sum = 0;
/**
* 打印二维数组
*
* @param chessArr
*/
public static void printArr(int[][] chessArr) {
System.out.println("二维数组");
for (int[] row : chessArr) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
/**
* 二维数组转稀疏数组
*
* @param chessArr
* @return
*/
public static int[][] chessArr2SparesArr(int[][] chessArr) {
//求黑子和白子的总数
for (int[] row : chessArr) {
for (int data : row) {
if (data != 0) {
sum++;
}
}
}
//创建稀疏数组
int[][] sparseArr = new int[sum + 1][3];
sparseArr[0][0] = ROWS;
sparseArr[0][1] = COLUMNS;
sparseArr[0][2] = sum;
int count = 0;
//遍历二维数组，将不为0的值填入稀疏数组
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLUMNS; j++) {
if (chessArr[i][j] != 0) {
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chessArr[i][j];
}
}
}
return sparseArr;
}
/**
* 稀疏数组转二维数组
*
* @param sparseArr
* @return
*/
public static int[][] sparseArr2chessArr(int[][] sparseArr) {
int[][] chessArr = new int[sparseArr[0][0]][sparseArr[0][1]];
for (int i = 1; i < sparseArr.length; i++) {
chessArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
return chessArr;
}
/**
* 保存数组
*
* @param sparseArr 需要保存的数组
* @param fileName 文件名
*/
public static void saveArr2File(int[][] sparseArr, String fileName) {
File file = new File(fileName);
FileWriter out = null;
try {
out = new FileWriter(file);
//将稀疏数组中的数据存入文件
for (int i = 0; i < sparseArr.length; i++) {
out.write(sparseArr[i][0] + "\t" + sparseArr[i][1] + "\t" + sparseArr[i][2] + "\r\n");
}
System.out.println("文件保存成功！");
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* 从文件读取数组
*
* @param fileName
* @return
*/
public static int[][] readArrFromFile(String fileName) {
//从文件中读取稀疏数组
BufferedReader in = null;
int[][] sparseArr = new int[sum + 1][3];
try {
in = new BufferedReader(new FileReader(fileName));
String line;
int row = 0;
while ((line = in.readLine()) != null) {
String[] temp = line.split("\t");
sparseArr[row][0] = Integer.valueOf(temp[0]);
sparseArr[row][1] = Integer.valueOf(temp[1]);
sparseArr[row][2] = Integer.valueOf(temp[2]);
row++;
}
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
in.close();
} catch (IOException e) {
e.printStackTrace();
}
}
return sparseArr;
}
public static void main(String[] args) throws InterruptedException {
chessArr[1][2] = 1;
chessArr[2][3] = 2;
printArr(chessArr);
int[][] parseArr = chessArr2SparesArr(chessArr);
printArr(parseArr);
saveArr2File(parseArr, "test.data");
Thread.sleep(1);
int[][] parseArr2 = readArrFromFile("test.data");
printArr(parseArr2);
chessArr = sparseArr2chessArr(parseArr2);
printArr(chessArr);
}
}
1.2 队列
介绍：
- 队列是一个有序列表，可以用数组或链表来实现
- 遵循先入先出的原则。即：先存入队列的数据先取出，后存入的数据后取出
1.2.1 数组队列
分析问题：使用数组实现数据存储，先入先出
队列
分析思路：
1.队列本身是有序列表，若使用数组结构存储队列数据，则数组的声明如上图，MaxSize是该队列的最大容量
2.因为队列的输入、输出是从前后端来处理，需要两个变量front及rear来记录队列前后端的下标，front会随着数据输出而改变，rear随着数据输入而改变
3.front变量指向队列第一个元素的前一位，初始值=-1
4.rear变量指向队列最后一个元素，初始值=-1
5.当队列存入数据时，
(1)判断队列是否已满：rear == MaxSize - 1 ?
(2)将尾指针往后移一位：rear+1;
6.当队列取数据时，
(1)判断队列是否为空：rear == front ?
(2)将头指针往后移一位：front+1;
代码实现：
package queue;
import java.util.Scanner;
/**
* 数组使用一次就没用了，没有达到复用效果
*/
public class ArrayQueueDemo {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ArrayQueue queue = new ArrayQueue(3);
char option = ' ';
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): 查看队列头的数据");
option = scanner.next().charAt(0);
switch (option) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("请输入需要添加的数据：");
int vaule = scanner.nextInt();
queue.addQueue(vaule);
break;
case 'g':
try {
int value = queue.getQueue();
System.out.println("取出的数据为：" + value);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'h':
try {
int value = queue.headQueue();
System.out.println("队列头数据为：" + value);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'e':
loop = false;
scanner.close();
break;
default:
break;
}
}
System.out.println("程序退出！");
}
}
class ArrayQueue {
//最大容量
private int maxSize;
//队列头，指向第一个元素的前一个位置，初始值为-1
private int front;
//队列尾，指向最后一个元素的位置，初始值为-1
private int rear;
//用于存放数据
private int[] arr;
//构造方法
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.arr = new int[maxSize];
this.front = -1;
this.rear = -1;
}
/**
* 判断是否满了
*
* @return
*/
public boolean isFull() {
return rear == maxSize - 1;
}
/**
* 判断是否为空
*
* @return
*/
public boolean isEmpty() {
return front == rear;
}
/**
* 添加队列
*
* @param n
*/
public void addQueue(int n) {
if (isFull()) {
System.out.println("队列已满，无法添加！");
return;
}
rear++;
arr[rear] = n;
}
/**
* 获取队列
*
* @return
*/
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据！");
}
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]);
}
}
/**
* 获取头数据,不是取出数据
*
* @return
*/
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据！");
}
return arr[front + 1];
}
}
1.2.2 环形队列
分析问题：
- 数组队列只能使用一次，不能复用；
- 将数组队列使用算法，改进成一个环形队列，取模：%
队列
分析思路：
1.尾索引的下一个为头索引时，表示队列已满，即将队列容量空出一位作为约定
2.front变量指向队列的第一个元素，初始值=0
3.rear变量指向队列的最后一个元素的后一个位置，因为希望空出一位作为约定，初始值=0
4.当队列存入数据时，
(1)判断队列是否已满：(rear+1) % MaxSize == front?
(2)将尾指针往后移一位：rear = (rear + 1) % maxSize;
5.当队列取数据时，
(1)判断队列是否为空：rear == front?
(2)将头指针往后移一位：front = (front + 1) % maxSize;
6.队列中有效数据的个数：(rear + maxSize - front) % maxSize
代码实现：
package queue;
import java.util.Scanner;
public class CircleArrayQueueDemo {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
CircleArrayQueue queue = new CircleArrayQueue(4);
char option = ' ';
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): 查看队列头的数据");
option = scanner.next().charAt(0);
switch (option) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("请输入需要添加的数据：");
int vaule = scanner.nextInt();
queue.addQueue(vaule);
break;
case 'g':
try {
int value = queue.getQueue();
System.out.println("取出的数据为：" + value);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'h':
try {
int value = queue.headQueue();
System.out.println("队列头数据为：" + value);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'e':
loop = false;
scanner.close();
break;
default:
break;
}
}
System.out.println("程序退出！");
}
}
class CircleArrayQueue {
//最大容量
private int maxSize;
//队列头,指向第一个元素位置,初始值为0
private int front;
//队列尾，指向最后一个元素的后一个位置,初始值为0
private int rear;
//用于存放数据
private int[] arr;
public CircleArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.arr = new int[maxSize];
}
/**
* 判断是否满了
*
* @return
*/
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
/**
* 判断是否为空
*
* @return
*/
public boolean isEmpty() {
return rear == front;
}
/**
* 添加队列
*
* @param n
*/
public void addQueue(int n) {
if (isFull()) {
System.out.println("队列已满，无法添加！");
return;
}
arr[rear] = n;
rear = (rear + 1) % maxSize;
}
/**
* 获取队列
*
* @return
*/
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据！");
}
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
/**
* 显示队列
*/
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空，没有数据");
return;
}
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
/**
* 获取有效元素个数
*
* @return
*/
public int size() {
return (rear + maxSize - front) % maxSize;
}
/**
* 获取头数据,不是取出数据
*
* @return
*/
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，没有数据！");
}
return arr[front];
}
}
