楔子：
- 資料結構包括線性結構和非線性結構，
1、線性結構：
1) 線性結構作為最常用的資料結構，其特點是資料元素之間存在一對一的線性關系
2) 線性結構有兩種不同的存盤結構，即順序存盤結構(陣列)和鏈式存盤結構(鏈表)，順序存盤的線性表稱為順序表，順序表中的存盤元素是連續的
3) 鏈式存盤的線性表稱為鏈表，鏈表中的存盤元素不一定是連續的，元素節點中存放資料元素以及相鄰元素的地址資訊
4) 線性結構常見的有：陣列、佇列、鏈表和堆疊，后面我們會詳細講解
2、非線性結構：
非線性結構包括：二維陣列，多維陣列，廣義表，樹結構，圖結構
稀疏陣列：
1、需求：
撰寫的五子棋程式中，有存盤退出和續上盤的功能，因為該二維陣列（棋盤）的很多值是默認值0（代表沒有棋子）, 因此記錄了很多沒有意義的資料 ---> 稀疏陣列，
2、基本介紹：
當一個陣列中大部分元素為０，或者為同一個值的陣列時，可以使用稀疏陣列來保存該陣列，
3、稀疏陣列的處理方法是：
1）記錄陣列一共有幾行幾列，有多少個不同的值
2）把具有不同值的元素的行列及值記錄在一個小規模的陣列中，從而縮小程式的規模
4、應用實體：
1) 使用稀疏陣列，來保留二維陣列(棋盤、地圖等等)
2) 把稀疏陣列存盤，并且可以從新恢復原來的二維陣列陣列，
3) 代碼實作：
package org.burning.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;
chessArr1[4][5] = 2;
// 輸出原始的二維陣列
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 代表當前行
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]);
}
System.out.println();
/*
將稀疏陣列 --> 恢復成原始二維陣列
1. 先讀取稀疏陣列的第一行，根據第一行的資料，創建原始的二維陣列
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();
}
}
}
控制臺：
原始的二維陣列:
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
稀疏陣列為：
11 11 3
1 2 1
2 3 2
4 5 2
恢復后的二維陣列:
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
Process finished with exit code 0
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500653.html
標籤：其他
下一篇：第三講 Linux測驗