之前學完了Java SE的知識，掌握了面向物件的編程思想，但對集合、多執行緒、反射、流的使用等內容理解的還不是很深入，打算再學習資料結構與演算法的同時，在空閑的時間里去圖書館看《Java
核心技術 卷 I》這本書，很多大佬對這本書很推崇，之前在圖書館也看過其他Java的書籍，經過對比，這本書確實寫的很有內涵；之后也會把看書程序中的識訓寫出來分享給大家，同時，連續的更新博客也是對自己學習的督促，終極目標：超越大我兩級的學長，拿到大廠sp，年薪40w+！！！
一、資料結構和演算法簡介
二、稀疏陣列
稀疏陣列的應用實體
1) 稀疏陣列，來保留類似前面的二維陣列(棋盤、地圖等等)
2) 把稀疏陣列存盤，并且可以從新恢復原來的二維陣列資料
二維陣列與稀疏陣列的轉換
二維陣列 轉 稀疏陣列的思路
1.遍歷原始的二維陣列，得到有效資料的個數 sum
2.根據sum就可以創建稀疏陣列 sparseArr int[sum + 1][3]
3.將二維陣列的有效資料存入到稀疏陣列
稀疏陣列 轉 原始的二維陣列的思路
1.先讀取稀疏陣列的第一行，根據第一行的資料，創建原始的二維陣列，比如上面的 chessArr2 = int[11][11]
2.在讀取稀疏陣列后幾行的資料，并賦給原始的二維陣列即可，
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;
// 新加的棋子；只需在這加就可以
chessArr1[4][5] = 6;
// 輸出原始的二維陣列
System.out.println("原始的二維陣列~~");
for (int[] row : chessArr1) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
// 將二維陣列 轉 稀疏陣列的思路
// 1.先遍歷二維陣列 得到非0資料的個數
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr1[i][j] != 0) {
sum++;
}
}
}
// 2.創建對應的稀疏陣列
int sparseArr[][] = new int[sum + 1][3];
// 給稀疏陣列賦值
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
// 遍歷二維陣列，將非0的值存放到sparseArr中
int count = 0;// count 用于記錄是第幾個非0資料
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];
}
}
}
// 輸出稀疏陣列的形式
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]);
}
// 將稀疏陣列-->>恢復成原始的二維陣列
// 1.先讀取稀疏陣列的第一行，根據第一行的資料，創建原始的二維陣列
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
// 2.在讀取稀疏陣列后幾行的資料(從第二行開始)，并賦給原始的二維陣列即可
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();
}
}
}三、佇列
陣列模擬佇列 
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;
//輸出一個選單
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;
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];
}
}上述代碼問題分析：
1）目前陣列使用一次就不能用，沒有達到復用的效果
2）將這個陣列使用演算法，改進成一個環形的佇列(使用到了取模：%相關的演算法)
代碼優化：陣列模擬環形佇列
思路如下：
1.front變數的含義做一個調整：front就指向佇列的第一個元素，也就是說arr[front]就是佇列的第一個元素front的初始值 = 0
2.rear變數的含義做一個調整：rear指向佇列的最后一個元素的后一個位置，因為希望空出一個空間做為約定，rear的初始值 = 0
3.當佇列滿時，條件是[rear + 1] % maxSize == front【滿】
4.對佇列為空的條件，rear == front空
5.當我們這樣分析，佇列中有效的資料的個數：(rear + maxSize - front) % maxSize
6.我們就可以在原來的佇列上修改得到，一個環形佇列
public class CircleArrayQueueDemo {
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(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;
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];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/298938.html
標籤：java