1. 稀疏 sparsearray 數(shù)組
1.1. 看一個(gè)實(shí)際的需求
-
編寫編寫的五子棋程序中姑隅，有存盤退出和續(xù)上盤的功能岳悟。
- 分析問題
因?yàn)樵摱S數(shù)組的很多值是默認(rèn)值 0, 因此記錄了很多沒有意義的數(shù)據(jù)=>稀疏數(shù)組。
1.2. 基本介紹
當(dāng)一個(gè)數(shù)組中大部分元素為０酝豪，或者為同一個(gè)值的數(shù)組時(shí)，可以使用稀疏數(shù)組來保存該數(shù)組。
稀疏數(shù)組的處理方法是:
1. 記錄數(shù)組一共有幾行幾列耸棒，有多少個(gè)不同的值
2. 把具有不同值的元素的行列及值記錄在一個(gè)小規(guī)模的數(shù)組中，從而縮小程序的規(guī)模
-
稀疏數(shù)組舉例說明
1.3. 應(yīng)用實(shí)例
- 使用稀疏數(shù)組报辱，來保留類似前面的二維數(shù)組(棋盤与殃、地圖等等)
- 把稀疏數(shù)組存盤，并且可以從新恢復(fù)原來的二維數(shù)組數(shù)
-
整體思路分析
- 代碼實(shí)現(xiàn)
import java.io.*;
import java.util.ArrayList;
import java.util.List;
/**
* 五子棋
* 將二維數(shù)組轉(zhuǎn)換成稀疏數(shù)組并存入文件
* 從文件中讀取碍现，將其還原成稀疏數(shù)組幅疼，再還原成二維數(shù)組
*/
public class sparseArray {
public static void main(String[] args) throws Exception {
//創(chuàng)建棋盤：二維數(shù)組
//0.定義一個(gè)11*11的棋盤
int[][] chessArr1 = new int[11][11];
//1.填充數(shù)字
chessArr1[2][3] = 1;
chessArr1[3][4] = 2;
//2.輸出結(jié)果顯示
System.out.println("原始棋盤:");
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
System.out.print(chessArr1[i][j] + "\t");
}
System.out.println();
}
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~");
//將二維數(shù)組轉(zhuǎn)換成稀疏數(shù)組
//0.先遍歷一遍數(shù)組得到非零數(shù)據(jù)的個(gè)數(shù)
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr1[i][j] != 0) {
sum += 1;
}
}
}
//1.定義稀疏數(shù)組
int[][] sparseArr = new int[sum + 1][3];
//2.給第一行填充數(shù)據(jù)（二維數(shù)組的行、列昼接、不為零的個(gè)數(shù)）
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
//3.遍歷二維數(shù)組,將不為零的數(shù)據(jù)所對(duì)應(yīng)的行和列填入稀疏數(shù)組中
int count = 0;//用于記錄是第幾個(gè)非 0 數(shù)據(jù)
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];
}
}
}
//4.打印輸出稀疏數(shù)組
for (int[] ints : sparseArr) {
for (int anInt : ints) {
System.out.print(anInt + "\t");
}
System.out.println();
}
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~");
//將稀疏數(shù)組存入文件
//0.獲得字節(jié)輸出流
FileOutputStream fos = new FileOutputStream("稀疏數(shù)組/map.data");
//1.拼接字符串
System.out.println("寫入文件ingＫ瘛！Ｂ逐工！");
for (int[] ints : sparseArr) {
String s = "" + ints[0] + "\t" + ints[1] + "\t" + ints[2] + "\t\n";
//2.寫出文件
fos.write(s.getBytes());
}
//3.關(guān)閉資源
fos.close();
System.out.println("文件寫入成功");
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~");
//從文件中讀取，將其轉(zhuǎn)換成稀疏數(shù)組
//0.獲取字符輸入流
BufferedReader br = new BufferedReader(new FileReader("稀疏數(shù)組/map.data"));
List<String> list = new ArrayList<>();
String s = "";
//1.按行讀取
while ((s = br.readLine()) != null) {
list.add(s);
}
br.close();
int[][] newSparseArrayRead = new int[list.size()][3];
String s1 = list.get(0);
//2.通過\t將字符進(jìn)行分割
String[] split = s1.split("\t");
//3.先將稀疏數(shù)組第一行放入數(shù)組中
newSparseArrayRead[0][0] = Integer.parseInt(split[0]);
newSparseArrayRead[0][1] = Integer.parseInt(split[1]);
newSparseArrayRead[0][2] = list.size() - 1;
//4.設(shè)置count值一睁，進(jìn)行后面的判斷钻弄。二維數(shù)組的行數(shù)。
int count2 = 0;
for (int i = 1; i < list.size(); i++) {
String str = list.get(i);
String[] strings = str.split("\t");
count2++;
for (int j = 0; j < strings.length; j++) {
newSparseArrayRead[count2][j] = Integer.parseInt(strings[j]);
}
}
System.out.println("讀取文件后建立的稀疏數(shù)組：");
for (int[] ints : newSparseArrayRead) {
for (int anInt : ints) {
System.out.printf("%d\t", anInt);
}
System.out.println();
}
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~");
//將稀疏數(shù)組轉(zhuǎn)換成二維數(shù)組
//0.創(chuàng)建二維數(shù)組
int[][] chessArr2 = new int[newSparseArrayRead[0][0]][newSparseArrayRead[0][1]];
//1.遍歷稀疏數(shù)組者吁，進(jìn)行二維數(shù)組的還原
for (int i = 1; i < newSparseArrayRead.length; i++) {
chessArr2[newSparseArrayRead[i][0]][newSparseArrayRead[i][1]] = newSparseArrayRead[i][2];
}
//2.遍歷二維數(shù)組進(jìn)行輸出
for (int[] ints : chessArr2) {
for (int anInt : ints) {
System.out.print(anInt + "\t");
}
System.out.println();
}
}
}
2. 隊(duì)列
2.1. 隊(duì)列的一個(gè)使用場(chǎng)景
銀行排隊(duì)：先排隊(duì)的人先辦理業(yè)務(wù)窘俺，后來的人依次排在隊(duì)伍后面等待辦理。
2.2. 隊(duì)列介紹
- 隊(duì)列是一個(gè)有序列表复凳，可以用數(shù)組或是鏈表來實(shí)現(xiàn)瘤泪。
- 遵循先入先出的原則。即：先存入隊(duì)列的數(shù)據(jù)育八，要先取出对途。后存入的要后取出
-
示意圖：(使用數(shù)組模擬隊(duì)列示意圖)
2.3. 數(shù)組模擬隊(duì)列思路
- 隊(duì)列本身是有序列表，若使用數(shù)組的結(jié)構(gòu)來存儲(chǔ)隊(duì)列的數(shù)據(jù)髓棋，則隊(duì)列數(shù)組的聲明如下圖, 其中 maxSize 是該隊(duì)列的最大容量实檀。
-
因?yàn)殛?duì)列的輸出、輸入是分別從前后端來處理按声，因此需要兩個(gè)變量 front 及 rear 分別記錄隊(duì)列前后端的下標(biāo)膳犹，front 會(huì)隨著數(shù)據(jù)輸出而改變，而 rear 則是隨著數(shù)據(jù)輸入而改變签则，如圖所示:
- 當(dāng)我們將數(shù)據(jù)存入隊(duì)列時(shí)稱為”addQueue”须床，addQueue 的處理需要有兩個(gè)步驟：思路分析
1. 將尾指針往后移：rear+1 , 當(dāng) front == rear 【空】
2. 若尾指針 rear 小于隊(duì)列的最大下標(biāo) maxSize-1，則將數(shù)據(jù)存入 rear 所指的數(shù)組元素中渐裂，否則無法存入數(shù)據(jù)豺旬。rear == maxSize - 1[隊(duì)列滿] - 代碼實(shí)現(xiàn)
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(3);
char key = ' '; //接收用戶輸入
Scanner scanner = new Scanner(System.in);
boolean loop = true;
while (loop) {
System.out.println("s(show): 顯示隊(duì)列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加數(shù)據(jù)到隊(duì)列");
System.out.println("g(get): 從隊(duì)列取出數(shù)據(jù)");
System.out.println("h(head): 查看隊(duì)列頭的數(shù)據(jù)");
key = scanner.next().charAt(0);
switch (key) {
case 's':
arrayQueue.showQueue();
break;
case 'e':
loop = false;
scanner.close();
break;
case 'a':
System.out.println("請(qǐng)輸入要添加的數(shù)：");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case 'g':
try {
int res = arrayQueue.getQueue();
System.out.printf("取出的數(shù)據(jù)：%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int header = arrayQueue.showHeader();
System.out.printf("隊(duì)列頭數(shù)據(jù)：%d\n", header);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
break;
}
}
System.out.println("程序退出~~");
}
}
//使用數(shù)組模擬隊(duì)列
class ArrayQueue {
private int front;//隊(duì)列頭
private int rear;//隊(duì)列尾
private int maxSize;//用來表示數(shù)組的最大容量
private int[] arr;//該數(shù)組用來存放數(shù)據(jù)钠惩，模擬隊(duì)列
// 創(chuàng)建隊(duì)列的構(gòu)造器
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
front = -1;// 指向隊(duì)列頭部，分析出 front 是指向隊(duì)列頭的前一個(gè)位置.
rear = -1;// 指向隊(duì)列尾族阅，指向隊(duì)列尾的數(shù)據(jù)(即就是隊(duì)列最后一個(gè)數(shù)據(jù))
arr = new int[maxSize];
}
//判斷隊(duì)列是否滿
public boolean isFull() {
return rear == maxSize - 1;
}
//判斷隊(duì)列是否為空
public boolean isEmpty() {
return front == rear;
}
//添加數(shù)據(jù)到隊(duì)列
public void addQueue(int value) {
//判斷隊(duì)列是否滿
if (isFull()) {
System.out.println("隊(duì)列已滿篓跛，添加失敗");
return;
}
//隊(duì)列未滿
rear++;//rear后移
arr[rear] = value;
System.out.println("添加成功");
}
//獲取隊(duì)列的數(shù)據(jù)，出隊(duì)列
public int getQueue() {
//判斷隊(duì)列是否空
if (isEmpty()) {
throw new RuntimeException("隊(duì)列為空耘分，取出失敗");
}
front++;
return arr[front];
}
//顯示隊(duì)列的所有數(shù)據(jù)
public void showQueue() {
//判斷隊(duì)列是否空
if (isEmpty()) {
System.out.println("隊(duì)列為空");
return;
}
for (int i = front + 1; i <= rear; i++) {
System.out.printf("arr[%d] = %d\n", i, arr[i]);
}
}
//顯示隊(duì)列的頭數(shù)據(jù)举塔，注意不是取出數(shù)據(jù)
public int showHeader() {
//判斷隊(duì)列是否空
if (isEmpty()) {
throw new RuntimeException("隊(duì)列為空，取出失敗");
}
return arr[front + 1];
}
}
- 問題分析并優(yōu)化
1. 目前數(shù)組使用一次就不能用求泰，沒有達(dá)到復(fù)用得效果
2. 將這個(gè)數(shù)組使用算法，改進(jìn)成一個(gè)環(huán)形隊(duì)列 取模：%
2.4. 數(shù)組模擬環(huán)形隊(duì)列
對(duì)前面的數(shù)組模擬隊(duì)列的優(yōu)化计盒，充分利用數(shù)組渴频。因此將數(shù)組看做是一個(gè)環(huán)形的。(通過取模的方式來實(shí)現(xiàn)即可)
-
分析說明：
1. 尾索引的下一個(gè)為頭索引時(shí)表示隊(duì)列滿北启，即將隊(duì)列容量空出一個(gè)作為約定,這個(gè)在做判斷隊(duì)列滿的時(shí)候需要注意 (rear + 1) % maxSize == front 滿]
2. rear == front [空]
3. 分析示意圖:
- 代碼實(shí)現(xiàn)
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
//測(cè)試一把
System.out.println("測(cè)試數(shù)組模擬環(huán)形隊(duì)列的案例~~~");
// 創(chuàng)建一個(gè)環(huán)形隊(duì)列
CircleArray queue = new CircleArray(4); //說明設(shè)置 4, 其隊(duì)列的有效數(shù)據(jù)最大是 3
char key = ' '; // 接收用戶輸入
Scanner scanner = new Scanner(System.in);//
boolean loop = true;
// 輸出一個(gè)菜單
while (loop) {
System.out.println("s(show): 顯示隊(duì)列");
System.out.println("e(exit): 退出程序");
System.out.println("a(add): 添加數(shù)據(jù)到隊(duì)列");
System.out.println("g(get): 從隊(duì)列取出數(shù)據(jù)");
System.out.println("h(head): 查看隊(duì)列頭的數(shù)據(jù)");
key = scanner.next().charAt(0);// 接收一個(gè)字符
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("輸出一個(gè)數(shù)");
int value = scanner.nextInt();
queue.addQueue(value);
break;
case 'g': // 取出數(shù)據(jù)
try {
int res = queue.getQueue();
System.out.printf("取出的數(shù)據(jù)是%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h': // 查看隊(duì)列頭的數(shù)據(jù)
try {
int res = queue.headQueue();
System.out.printf("隊(duì)列頭的數(shù)據(jù)是%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; // 表示數(shù)組的最大容量
//front 變量的含義做一個(gè)調(diào)整： front 就指向隊(duì)列的第一個(gè)元素, 也就是說 arr[front] 就是隊(duì)列的第一個(gè)元素
//front 的初始值 = 0
private int front;
//rear 變量的含義做一個(gè)調(diào)整：rear 指向隊(duì)列的最后一個(gè)元素的后一個(gè)位置. 因?yàn)橄Ｍ粘鲆粋€(gè)空間做為約定. //rear 的初始值 = 0
private int rear; // 隊(duì)列尾
private int[] arr; // 該數(shù)據(jù)用于存放數(shù)據(jù), 模擬隊(duì)列
public CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
}
// 判斷隊(duì)列是否滿
public boolean isFull() {
return (rear + 1) % maxSize == front;
}
// 判斷隊(duì)列是否為空
public boolean isEmpty() {
return rear == front;
}
// 添加數(shù)據(jù)到隊(duì)列
public void addQueue(int n) {
// 判斷隊(duì)列是否滿
if (isFull()) {
System.out.println("隊(duì)列滿卜朗，不能加入數(shù)據(jù)~");
return;
}
//直接將數(shù)據(jù)加入
arr[rear] = n;
//將 rear 后移, 這里必須考慮取模
rear = (rear + 1) % maxSize;
}
// 獲取隊(duì)列的數(shù)據(jù), 出隊(duì)列
public int getQueue() {
// 判斷隊(duì)列是否空
if (isEmpty()) {
// 通過拋出異常
throw new RuntimeException("隊(duì)列空，不能取數(shù)據(jù)");
}
// 這里需要分析出 front 是指向隊(duì)列的第一個(gè)元素
// 1. 先把 front 對(duì)應(yīng)的值保留到一個(gè)臨時(shí)變量
// 2. 將 front 后移, 考慮取模
// 3. 將臨時(shí)保存的變量返回
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
// 顯示隊(duì)列的所有數(shù)據(jù)
public void showQueue() {
// 遍歷
if (isEmpty()) {
System.out.println("隊(duì)列空的咕村，沒有數(shù)據(jù)~~");
return;
}
// 思路：從 front 開始遍歷场钉，遍歷多少個(gè)元素
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
// 求出當(dāng)前隊(duì)列有效數(shù)據(jù)的個(gè)數(shù)
public int size() {
// rear = 2
// front = 1
// maxSize = 3
return (rear + maxSize - front) % maxSize;
}
// 顯示隊(duì)列的頭數(shù)據(jù)， 注意不是取出數(shù)據(jù)
public int headQueue() {
// 判斷
if (isEmpty()) {
throw new RuntimeException("隊(duì)列空的懈涛，沒有數(shù)據(jù)~~");
}
return arr[front];
}
}
