稀疏矩阵和队列

一、稀疏数组sparsearray

1、应用场景

需求：五子棋”存盘退出“ --> 二维数组保存

问题：这个二维数组大部分都是默认值0，记录了很多没有意义的数据 --> 稀疏数组

2、稀疏数组

稀疏数组：数组大部分为同一个值

处理方法：记录数组几行几列，有多少个的值。把不同值的行和列记录在小规模数组中。

	行号row	列号col	值value
[0]	2	2	2
[1]	0	1	1
[2]	1	0	1

[0]：共几行几列，存在几个值
[1] - [n]：记录x行x列的值是多少

3、思路分析

1）二维转稀疏

遍历原始二维数组，得到有效数据个数 -> sum
创建稀疏数组sparseArr int[sum][3]
将有效数据存到sparseArr中

2）稀疏转二维

读取sparseArr的第一行的数据创建原始二维数组
读取sparseArr后面的数值，赋值给二维数组

4、代码实现

1）基础代码

java

package work.rexhao.sparsearray;

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;
		// 输出
		System.out.println("原始二维数组");
		for(int[] row : chessArr1) {
			for(int i : row) {
				System.out.printf("%d ",i);
			}
			System.out.println();
		}
		
		// 将二维数组转换成稀疏数组
		// 1.遍历二维数组，得到非0个数、行和列
		int r = 0, l = 0, v = 0;
		for(int[] row : chessArr1) {
			r++;
			for(int i : row) {
				l++;
				if(i != 0) {
					v++;
				}
			}
		}
		l /= r;
		
		// 2.创建稀疏数组
		int sparseArr[][] = new int[v+1][3];
		
		// 3.给稀疏数组赋值
		sparseArr[0][0] = r;
		sparseArr[0][1] = l;
		sparseArr[0][2] = v;
		int ii = 0;
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < l; j++) {
				if(chessArr1[i][j] != 0) {
					sparseArr[++ii][0] = i;
					sparseArr[ii][1] = j;
					sparseArr[ii][2] = chessArr1[i][j];
				}
			}
		}
		
		// 稀疏数组的输出
		System.out.println("得到的稀疏数组是：");
		for(int[] row : sparseArr) {
			for(int i : row) {
				System.out.print(i + " ");
			}
			System.out.println();
		}
		
		// 将稀疏数组恢复二维数组
		// 1.读取第一行，创建二维数组
		int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
		
		// 2.读取并赋值
		for(int i = 1; i <= sparseArr[0][2]; i++) {
			chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
		}
		
		// 输出
		System.out.println("转换的二维数组是：");
		for(int[] row : chessArr2) {
			for(int i : row) {
				System.out.printf("%d ",i);
			}
			System.out.println();
		}
	}

}

2）IO代码

java

package work.rexhao.sparsearray;

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;

public class sparsearray_out {
	public static void main(String[] args) throws FileNotFoundException, IOException {
		ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("./chess.data"));
		// 创建一个原始的二维数组11*11
		// 0：没有旗子，1：黑子，2：蓝子
		int chessArr1[][] = new int[11][11];
		chessArr1[1][2] = 1;
		chessArr1[1][3] = 2;
		// 将二维数组转换成稀疏数组
		// 1.遍历二维数组，得到非0个数、行和列
		int r = 0, l = 0, v = 0;
		for (int[] row : chessArr1) {
			r++;
			for (int i : row) {
				l++;
				if (i != 0) {
					v++;
				}
			}
		}
		l /= r;

		// 2.创建稀疏数组
		int sparseArr[][] = new int[v + 1][3];

		// 3.给稀疏数组赋值
		sparseArr[0][0] = r;
		sparseArr[0][1] = l;
		sparseArr[0][2] = v;
		int ii = 0;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < l; j++) {
				if (chessArr1[i][j] != 0) {
					sparseArr[++ii][0] = i;
					sparseArr[ii][1] = j;
					sparseArr[ii][2] = chessArr1[i][j];
				}
			}
		}
		
		
		// 4.序列化
		oos.writeObject(sparseArr);
		oos.close();
		System.out.println("存档成功！");
	}
}

java

package work.rexhao.sparsearray;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;

public class sparsearray_in {

	public static void main(String[] args) throws FileNotFoundException, IOException, ClassNotFoundException {
		ObjectInputStream ois = new ObjectInputStream(new FileInputStream("./chess.data"));
		int sparseArr[][] = (int[][])ois.readObject();
		System.out.println("读档成功!");
		// 将稀疏数组恢复二维数组
		// 1.读取第一行，创建二维数组
		int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
		
		// 2.读取并赋值
		for (int i = 1; i <= sparseArr[0][2]; i++) {
			chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
		}

		// 输出
 		for (int[] row : chessArr2) {
			for (int i : row) {
				System.out.printf("%d ", i);
			}
			System.out.println();
		}

	}

}

二、队列

1、队列概述

队列是一个有序列表，可以用数组或链表实现

遵循先入先出原则

2、数组模拟队列

1）数组结构介绍

数组的结构存储队列元素，maxSize是队列最大容量

两个变量front和rear记录队列前后端

2）思路分析

尾指针后移：rear+1
rear < maxSize - 1：可以存

当front == rear，队列空
当rear == maxSize - 1，队列满

3）代码实现

java

package work.rexhao.queue;

import java.util.Scanner;

public class arrayQueueDemo {

	public static void main(String[] args) {
		ArrayQueue aq = new ArrayQueue(3);
		boolean loop = true;
		while (loop) {
			Scanner sc = new Scanner(System.in);
			System.out.println("1. 添加数据");
			System.out.println("2. 弹出数据");
			System.out.println("3. 显示首数据");
			System.out.println("4. 遍历");
			System.out.println("0. 退出");
			int key = sc.nextInt();
			if (key == 1) {
				System.out.println("请输入需要添加的数据");
				int value = sc.nextInt();
				aq.addQueue(value);
			} else if (key == 2) {
				try {
					int value = aq.getQueue();
					System.out.printf("弹出元素：%d\n",value);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}

			} else if (key == 3) {
				try {
					int value = aq.headQueue();
					System.out.printf("首元素：%d\n", value);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
			} else if (key == 4) {
				aq.showQueue();
			} else if (key == 0) {
				loop = false;
			} else {
				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[arrMaxSize];
		front = -1;// 指向队列头的前一个位置
		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;
		}
		arr[++rear] = n;
	}

	/**
	 * 出队列
	 */
	public int getQueue() {
		if (isEmpty()) {
			// 抛出异常 -- 不需要写return
			throw new RuntimeException("队列空");
		}
		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];
	}
}

4）问题与优化

对于普通队列，数组使用一次就不能用，没有达到复用的效果
将这个数组使用算法，改进成一个环形的队列 （取模：%）

3、数组模拟环形队列

1）思路分析

front变量的含叉做一个调整：front就指向队列的第一个元素，也就是说ari[front] 就是队列的第一个元素。front 的初始值=0
rear 变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，空出一个空间做为约定。rear 的初始值=0
当队列满时，条件是 (rear +1) % maxsize == front
对队列为空的条件，rear == front
队列中有效的数据的个数 (rear+ maxsize - front) % maxsize

2）代码实现

java

package work.rexhao.queue;

import java.util.Scanner;

public class circleQueueDemo {

	public static void main(String[] args) {
		CircleQueue cq = new CircleQueue(3);
		boolean loop = true;
		while (loop) {
			Scanner sc = new Scanner(System.in);
			System.out.println("1. 添加数据");
			System.out.println("2. 弹出数据");
			System.out.println("3. 显示首数据");
			System.out.println("4. 遍历");
			System.out.println("0. 退出");
			int key = sc.nextInt();
			if (key == 1) {
				System.out.println("请输入需要添加的数据");
				int value = sc.nextInt();
				cq.addQueue(value);
			} else if (key == 2) {
				try {
					int value = cq.getQueue();
					System.out.printf("弹出元素：%d\n", value);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}

			} else if (key == 3) {
				try {
					int value = cq.headQueue();
					System.out.printf("首元素：%d\n", value);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
			} else if (key == 4) {
				cq.showQueue();
			} else if (key == 0) {
				loop = false;
			} else {
				System.out.println("请检查输入");
			}
		}

	}

}

/**
 * 使用数组模拟环形队列----编写一个CircleQueue类
 */
class CircleQueue {
	private int maxSize; // 数组最大容量
	private int front; // 队列头
	private int rear; // 队列尾
	private int[] arr; // 队列的数据

	/**
	 * 创建队列的构造器
	 */
	public CircleQueue(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[arrMaxSize];
		front = 0;// 指向队列头
		rear = 0;// 指向队列尾的后一个位置（空出一个空间做为约定）

	}

	/**
	 * 判断队列是否满
	 */
	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 + 1) % maxSize;
	}

	/**
	 * 出队列
	 */
	public int getQueue() {
		if (isEmpty()) {
			// 抛出异常 -- 不需要写return
			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]);
		}
	}

	/**
	 * 显示头数据（不取出）
	 */
	public int headQueue() {
		if (isEmpty()) {
			throw new RuntimeException("队列空");
		}
		return arr[front];
	}

	/**
	 * 有效数据
	 */
	public int size() {
		return (rear - front + maxSize) % maxSize;
	}
}

稀疏矩阵和队列 ​

一、稀疏数组sparsearray ​

1、应用场景 ​

2、稀疏数组 ​

3、思路分析 ​

1）二维转稀疏 ​

2）稀疏转二维 ​

4、代码实现 ​

1）基础代码 ​

2）IO代码 ​

二、队列 ​

1、队列概述 ​

2、数组模拟队列 ​

1）数组结构介绍 ​

2）思路分析 ​

3）代码实现 ​

4）问题与优化 ​

3、数组模拟环形队列 ​

1）思路分析 ​

2）代码实现 ​

稀疏矩阵和队列

一、稀疏数组sparsearray

1、应用场景

2、稀疏数组

3、思路分析

1）二维转稀疏

2）稀疏转二维

4、代码实现

1）基础代码

2）IO代码

二、队列

1、队列概述

2、数组模拟队列

1）数组结构介绍

2）思路分析

3）代码实现

4）问题与优化

3、数组模拟环形队列

1）思路分析

2）代码实现