---
title: 'Array靜態陣列'
disqus: kyleAlien
---

Array靜態陣列
===

## OverView of Content

如有引用參考請詳註出處，感謝 :smile_cat:

[TOC]

## Static Data Sturct
* 靜態陣列有稱為`密集串列`，它是一種`有序串列`的資料使用**連續記憶體空間**
* 配置是在編譯期間，所以必須事先宣告，容易有浪費記憶體空間的現象
> 優點 : 找查記憶體十分快速
> 缺點 : 對於拓展空間、插入資料很浪廢資源，需要移動大量資料
* 列為主 : C、C++、Java...等等 (以下**主要介紹**)
* 行為主 : Fortran 語言(暫不介紹)

陣列 Array
---
* 陣列宣告方式是以數學式的宣告方式，而呼叫時是以陣列的方式呼叫

// 數學式 1～5
int[5] a = {874, 22, -3, 99, 0};    
// 陣列式 0~4
a[0] = 874;                         
a[1] = 22;
a[2] = -3;
a[3] = 99;
a[4] = 0;

// 陣列超出範圍
a[5] = ???;
// a[5] 超出範圍，無法確定其值 !    (C 可以超出, Java 不允許超出)

> 陣列是電腦儲存資料的方式是一維
> > 電腦儲存的 index 是從 0 開始
> > 數學儲存的 index 是從 1 開始

> 而**數學的二維表達方式是使用矩陣**，而電腦儲存二維的方式是透過一維的拓展
> 也就是說**實際電腦記憶體中無法以矩陣分是儲存，就以線性方是在電腦儲存，可視為一維矩陣的延伸處理**
> > 電腦儲存的 index 是從 (0,0) 開始
> > 數學儲存的 index 是從 (1,1) 開始

### 一維陣列

#### C/C++

typedef struct {
    int   a;        // 4
    short b;        // 2
    char  c;        // 1
} Data_T;

int main() {
    Data_T dataArray[10] = {0};

    "1: "
    int array1[] = {0};
    int array2[5];
    int array3[5] = {0};

    "2: "
    printf("array1 size: %i\n", sizeof(array1));    // 4
    printf("Data_T size: %i\n", sizeof(Data_T));    // 8
    "3: "
    printf("dataArray size: %i\n", sizeof(dataArray) / sizeof(Data_T)); //10
}

* 1: C/C++ 宣告方式，可以以 struct 型式宣告陣列，並且有三種模式
> 宣告一個，不固定長度的陣列-->初始化
> 宣告一個，固定長度的陣列-->不初始化
> 選告一個，固定長度的陣列-->初始化
* 2: 計算的大小
> 第一個： **未定義矩陣長度的陣列，長度預設是一個，也就是 4 byte**
>
> 第二個： 原本計算出的大小應該是 7 byte，但答案是 8 byte
> **struct 會依照目前內部最大的空間作為倍數，做==數據對齊==**
* 3: 計算 struct Arrays 的方法(詳細請看C是如何計算和使用 sizeof)

#### Java

class TestClass {
    private String str;
    TestClass(String str) {
        this.str = str;
    }
    String getData() {
        return str;
    }
}

public class main {
    public static void main(String []args) {
        "1: "
        int[] array1;
        int []array2;
        int array3[];
        
        TestClass[] testClassArray = {  new TestClass("kyle"), 
                                        new TestClass("Alien"), 
                                        new TestClass("Pan")
                                        };

        for(int i = 0; i < testClassArray.length; i++) {
            "2: "System.out.println(testClassArray[i].getData());
        }
        "3: "System.out.println(testClassArray[3].getData());
    }
}

* 1: Java 有三種宣告方式，可以以 class 類型宣告陣列
> 但 **Java 宣告陣列不需要提供陣列的大小，陣列的大小在初始化時自動決定**
* 2: index 是 0 ~ 2，可正常輸出
* 3: 當超出範圍時會拋出錯誤，ArrayIndexOutOfBoundsException

**--實作--**
> 

#### (一維)記憶體位子運算
> int[10] a = {0}, a[0] addr is 0x0010, a[5] addr 為多少 ?
>
> Ans : 由於 **a[5] 是電腦陣列表達式，數學表達式是 a(5+1) 的地方，也就是 a5**
> // **以下計算使用數學式計算**
>
> 0x0010 + (6 - 1)(行) * 4(byte) = 0x0010 + 20
> 0x0010 + 0x0014
> 0x0024

### 二維陣列
#### C/C++

typedef struct {
    int   a;        // 4
    short b;        // 2
    char  c;        // 1
} Data_T;

int main() {
    Data_T dataArray[10][5] = {0};

    "1: "
    int array1[][5] = {0};
    int array2[5][5];
    int array3[5][5] = {0};

    "2: "
    printf("array1 size: %i\n", sizeof(array1)); // 20
    printf("array2 size: %i\n", sizeof(array2)); // 100
    
    printf("Data_T size: %i\n", sizeof(Data_T)); // 8
    printf("dataArray size: %i\n", sizeof(dataArray // 400
    printf("dataArray size: %i\n", sizeof(dataArray) / sizeof(Data_T)); // 50
}

* 1: C/C++ 宣告方式，同上有三種方式
> **一維陣列可不必定義大小，但二維的陣列一定要定義大小（不然不知道何時換行）**
* 2: 計算的大小
> 未定義預設一維就是 1， 4(byte) * 1 * 5 = 20
> 定義預設一維就是 5， 4(byte) * 5 * 5 = 100
> struct array -> 8 (struct 大小, 單位 byte) * 10 * 5 = 400
#### Java

class TestClass {
    private String str;
    TestClass(String str) {
        this.str = str;
    }
    String getData() {
        return str;
    }
}

public class main {
    public static void main(String []args) {
        "1: "
        int[][] array1;
        int [][]array2;
        int array3[][];
        
        TestClass[][] testClassArray = {	
                            {new TestClass("kyle"), new TestClass("12")}, 
                            {new TestClass("Alien"), new TestClass("23")}, 
                            {new TestClass("Pan"), new TestClass("16")}
                                    };
        "2: "
        System.out.println("one length: " + testClassArray.length);
        System.out.println("second length: " + testClassArray[0].length);
    
        
        for(int i = 0; i < testClassArray.length; i++) {
            for(int j = 0; j < testClassArray[i].length; j++) {
                System.out.print(testClassArray[i][j].getData() + " ");
            }
            System.out.println();
        }
    }
}

* 1: Java 有三種宣告方式，可以以 class 類型宣告陣列
> 但 **Java 宣告陣列不需要提供陣列的大小，一維、二維陣列的大小在初始化時自動決定**
* 2: 透過自動偵測可判斷一維、二維的長度
> **testClassArray.length 是指向外層(二圍)的長度**
> testClassArray[0].length 是指內層(一維)的長度

**--實作--**
> 

#### (二維)記憶體位子運算
> int[10][5] a = {0}, a[0][0] addr is 0x0010, a[3][2] addr 為多少 ?
>
> Ans : 由於 **a[3][5] 是電腦陣列表達式，數學表達式是 a(3+1)(2+1) 的地方，也就是 a42(矩陣)**
> // **以下計算使用數學式計算**
>
> 0x0010 + ((4 - 1)(列) * 5(行) + (2 - 1)(行)) * 4(byte)= 0x0010 + (15 + 1) * 4
> 0x0010 + 0x0040
> 0x0050

### 三維陣列
#### C/C++

typedef struct {
    int   a;        // 4
    short b;        // 2
    char  c;        // 1
} Data_T;

int main() {
    Data_T dataArray[10][5][2] = {0};

    "1: "
    int array1[][5][2] = {0};
    int array2[5][5][2];
    int array3[5][5][2] = {0};

    "2: "
    printf("array1 size: %i\n", sizeof(array1)); // 20 * 2
    printf("array2 size: %i\n", sizeof(array2)); // 100 * 2
    
    printf("Data_T size: %i\n", sizeof(Data_T)); // 8
    printf("dataArray size: %i\n", sizeof(dataArray // 400 * 2
    printf("dataArray size: %i\n", sizeof(dataArray) / sizeof(Data_T)); // 50 * 2
}

* 1: C/C++ 宣告方式，同上有三種方式
> **一維陣列可不必定義大小，但二維、三維的陣列一定要定義大小**
* 2: 計算的大小
> 未定義預設一維就是 1， 4(byte) * 1 * 5 * 2= 40
> 定義預設一維就是 5， 4(byte) * 1 * 5 * 2= 200
> struct = 8 * 10 * 5 * 2 = 800
#### Java

class TestClass {
    private String str;
    TestClass(String str) {
        this.str = str;
    }
    String getData() {
        return str;
    }
}

public class main {
    public static void main(String []args) {
        "1: "
        int[][][] array1;
        int [][][]array2;
        int array3[][][];
        
        TestClass[][][] testClassArray = 
            { 
                { 
                    {new TestClass("kyle"), new TestClass("12")}, 
                    {new TestClass("Alien"), new TestClass("23")}, 
                    {new TestClass("Pan"), new TestClass("16")}
                },
                { 
                    {new TestClass("kyle"), new TestClass("150cm")}, 
                    {new TestClass("Alien"), new TestClass("170cm")}, 
                    {new TestClass("Pan"), new TestClass("165cm")}
                },		
            };

        System.out.println("one length: " + testClassArray.length);
        System.out.println("second length: " + testClassArray[0].length);
        System.out.println("third length: " + testClassArray[0][0].length);
		
        for(int i = 0; i < testClassArray.length; i++) {
            for(int j = 0; j < testClassArray[i].length; j++) {
                for(int k = 0; k < testClassArray[i][j].length; k++) {
                    System.out.print(testClassArray[i][j][k].getData() + " ");
                }
                System.out.println("---");
            }
            System.out.println();
        }
    }
}

* 1: Java 有三種宣告方式，可以以 class 類型宣告陣列
> 但 **Java 宣告陣列不需要提供陣列的大小，一維、二維、三維陣列的大小在初始化時自動決定**
* 2: 透過自動偵測可判斷一維、二維、三維的長度
> **testClassArray.length 是指向最外面一層(三圍)的長度**
> testClassArray[0].length 是指第二層(二維)的長度
> testClassArray[0][0].length 是指最內層(一維)的長度

**--實作--**
> 

#### (三維)記憶體位子運算
> int[10][5][10] a = {0}, a[0][0][0] addr is 0x0010, a[3][2][7] addr 為多少 ?
>
> Ans : 由於 **a[3][5][8] 是電腦陣列表達式，數學表達式是 a(3+1)(2+1)(8+1) 的地方，也就是 a429(矩陣)**
> // **以下計算使用數學式計算**
>
> 0x0010 + ((4 - 1)(列) * 5(行) * 10(高)+ (2 - 1)(行) * 10(高) + (9 - 1)(高)) * 4(byte)= 0x0010 + (150 + 10 + 8) * 4
> 0x0010 + 0x02A0
> 0x02B0
>

矩陣
---
* 矩陣是數學表達式，所以下方的**公式皆是以數學式表達，公式目的是為了轉換成電腦中的陣列**

### 矩陣相加
> 相加矩陣的**行列必須相等**

public class StartCoding {
	
	public static boolean checkSize(int [][]a, int [][]b) {
		boolean check = false;
		int aLen = a.length;
		int bLen = b.length;
		
		if(aLen == bLen) {
			if(a[0].length == b[0].length) {
				check = true;
			}
		}
		return check;
	}
	
	public static int[][] addMatrix(int [][]a, int [][]b) {
		if(!checkSize(a, b)) {
			return null;
		}
		int row = a.length;
		int column = a[0].length;
		int[][] c = new int[row][column];
		for(int i = 0; i < row; i++) {
			for(int j= 0; j < column; j++) {
				c[i][j] = a[i][j] + b[i][j];
			}
		}
		return c;
	}

	public static void main(String[] args) {
		int [][]A = {	// 3*3
				{1,2,3},
				{4,5,6},
				{7,8,9}
		};
		
		int [][]B = { 	// 3*3
				{1,1,1},
				{2,2,2},
				{3,3,3}
		};
		
		int[][] Result = addMatrix(A, B);
		if(Result != null) {
			System.out.println("Result: ");
			for(int i = 0; i < Result.length; i++) {
				for(int j = 0; j < Result[i].length; j++) {
					System.out.print(Result[i][j] + " ");
				}
				System.out.println();
			}
		}
	}
}

**--實作--**
> 

### 矩陣相乘
* 矩陣相乘算式
> 以 (3\*2) * (2\*4) = (3\*4) 的矩陣
> \[{1,1}, {2,2}, {3,3}] \* \[{4,4,4,4}, {1,2,3,4}]
>
> \[
> {(1\*4 + 1\*1), (1\*4 + 1\*2), (1\*4 + 1\*3), (1\*4 + 1\*4)},
> {(2\*4 + 2\*1), (2\*4 + 2\*2), (2\*4 + 2\*3), (2\*4 + 2\*4)},
> {(3\*4 + 3\*1), (3\*4 + 3\*2), (3\*4 + 3\*3), (3\*4 + 3\*4)},
> ]
>
> 結果: 3\*4 的矩陣
> \[5, 6, 7, 8
> 10, 12, 14, 16
> 15, 18, 21, 24]

public class StartCoding {
	
	public static boolean checkSize(int [][]a, int [][]b) {
		boolean check = false;
		int aLen = a[0].length;
		int bLen = b.length;
		
		if(aLen == bLen) {
			check = true;		// check inner
		}
		return check;
	}
	
	public static int[][] multiplyMatrix(int [][]a, int [][]b) {
		if(!checkSize(a, b)) {
			return null;
		}
		int row = a.length;			// 3
		int column = b[0].length;	// 4
		int work = b.length;		// 2
		int[][] c = new int[row][column];
		
		for(int i = 0; i < row; i++) {		// 0 ~ 2
			for(int j = 0; j < column; j++) {// 0 ~ 3
				int temp = 0;
				for(int k = 0; k < work; k++) {	// k is Specify work index 0 ~ 1
					temp = temp + (a[i][k] * b[k][j]);
				}
				c[i][j] = temp;
			}
		}
		return c;
	}

	public static void main(String[] args) {
		int [][]A = {	// 3*2
				{1,1},
				{2,2},
				{3,3},
		};
		
		int [][]B = { 	// 2*4
				{4,4,4,4},
				{1,2,3,4},
		};
		
		int[][] Result = multiplyMatrix(A, B);
		if(Result != null) {
			System.out.println("Result: ");
			for(int i = 0; i < Result.length; i++) {
				for(int j = 0; j < Result[i].length; j++) {
					System.out.print(Result[i][j] + " ");
				}
				System.out.println();
			}
		} else {
			System.out.println("Matrix format Err");
		}
	}
}

**--實作--**
> 

### 轉置矩陣
* 斜對角轉置矩陣，旋轉一個正方形矩陣，**對換斜對角的值**

public class StartCoding {
	
	public static boolean checkSize(int [][]a) {
		boolean check = false;
		int aLen = a.length;
		int bLen = a[0].length;
		
		if(aLen == bLen) {
			check = true;		// check row == column
		}
		return check;
	}
	
	public static int[][] turnMatrix(int [][]a) {
		if(!checkSize(a)) {
			return null;
		}
		
		int row = a.length;
		int column = a[0].length;
		int [][]c = new int[row][column];		// create target/result array
		for(int i = 0; i < row; i++) {
			for(int j = 0; j < column; j++) {
				c[i][j] = a[j][i];
			}
		}
		
		return c;
	}

	public static void main(String[] args) {
		int [][]A = {	// 3*3
				{1,2,3},
				{4,5,6},
				{7,8,9},
		};
		
		int[][] Result = turnMatrix(A);
		if(Result != null) {
			System.out.println("Result: ");
			for(int i = 0; i < Result.length; i++) {
				for(int j = 0; j < Result[i].length; j++) {
					System.out.print(Result[i][j] + " ");
				}
				System.out.println();
			}
		} else {
			System.out.println("Matrix format Err");
		}
	}
}

**--實作--**
> 

### 稀疏矩陣
* 一個矩陣中大部分都為 0 時，可把稀疏矩陣轉換成壓縮矩陣(兩個可以互相轉換)
* 壓縮是為了有效的利用空間，所以用了**三項式的資料結構**(i,j,Item-value)
> A(0,1) 該矩陣的列數
> A(0,2) 該矩陣的行數
> A(0,3) 該矩陣的非零項目的總數

| index | 1 | 2 | 3 |
| -------- | -------- | -------- | -------- |
| 0 | 6(總列數) | 6(總行數) | 8(總非零數) |
| 1 | 列 | 行 | 數值 |
| 2 | 列 | 行 | 數值 |
| 3 | 列 | 行 | 數值 |

public class StartCoding {
	private static final int Trinomial = 3;
	
	public static int[][] decompress(int [][]a) {
		int row = a[0][0];
		int colume = a[0][1];
		int unZeroCount = a[0][2];
		int temp = 1;
		int [][]c = new int[row][colume];
		
		for(int i = 0; i < row; i++) {
			for(int j = 0; j < colume; j++) {
				int saveRow = (a[temp][0] - 1);
				int saveColume = (a[temp][1] - 1);
				if(i == saveRow && j == saveColume) {
					c[i][j] = a[temp][2];
					temp = temp + 1 > unZeroCount ? temp : temp + 1;
				}
			}
		}
		return c;
		
	}
	
	public static int[][] compression(int [][]a) {
		int unZeroCount = 0;
		int row = a.length;
		int colume = a[0].length;
		
		for(int i = 0; i < row; i++) {
			for(int j = 0; j < colume; j++) {
				if(a[i][j] != 0) {	// find not 0 value
					unZeroCount++;
				}
			}
		}
		
		int [][] c = new int[unZeroCount + 1][Trinomial];	// +1 for one line is info
		
		c[0][0] = row;
		c[0][1] = colume;
		c[0][2] = unZeroCount;
		int temp = 1;
		for(int i = 0; i < row; i++) {
			for(int j = 0; j < colume; j++) {
				if(a[i][j] != 0) {
					c[temp][0] = i + 1;
					c[temp][1] = j + 1;
					c[temp++][2] = a[i][j];
				}
			}
		}
		
		return c;
	}
	
	private static void print(int[][] a) {
		for(int i = 0; i < a.length; i++) {
			for(int j = 0; j < a[i].length; j++) {
				System.out.print(a[i][j] + "  ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		int [][]A = {	// 6*6
				{ 25,  0,  0, 32,  0,-25},
				{  0, 33, 77,  0,  0,  0},
				{  0,  0,  0, 55,  0,  0},
				{  0,  0,  0,  0,  0,  0},
				{101,  0,  0,  0,  0,  0},
				{  0,  0, 38,  0,  0,  0},
		};

		System.out.println("----------------- compression");
		int [][] Result = compression(A);
		print(Result);
		System.out.println("----------------- decompression");
		int [][] conveter = decompress(Result);
		print(conveter);
	}
}

**--實作--**
> 

### 三角矩陣
> 三角矩陣又分為，右上、左上、右下、左下三角矩陣，除了三角區域以外都是0元素
> 我們**可以把三角矩陣的==二維模式透過一維的陣列存取==**，目的為了壓縮矩陣大小，節省空間
> 透過**呼叫原矩陣座標在一維陣列中取出儲存值**
> **Item 總數公式 `n*(n+1)/2`** (正三角)

#### 右上三角
* 找出向量座標 A2-3(i = 2, j = 3) 在一維陣列 B[index] 中的 index
* index = n*(i-1) - (i * (i-1))/2 + j
> n*(i-1) : 算出 A2-3 以上的面積
> (i * (i-1))/2 : 扣除矩陣中 0 的項目(0 不放入一維陣列中儲存)
> j : 加上位移的座標

public class StartCoding {

	public static void main(String[] args) {
		int [][]A = {	// 4*4
				{ 25,  1, 15, 32},
				{  0, 33, 77, -1},
				{  0,  0, -9, 55},
				{  0,  0,  0,  9}
		};
		
		CompressSize cs = new CompressSize(A);
		
		for(int i = 0; i < A.length; i++) {
			for(int j = 0; j < A[i].length; j++) {
				int x = cs.getDataByMatrixIndex(i + 1, j + 1);	// +1 is array type to matrix type
				System.out.println(x);
			}
		}
		System.out.println("---------");
		
		System.out.println("A23 : " + cs.getDataByMatrixIndex(2, 3));
	}
	
}

class CompressSize {
	private int[] array;
	private int size = 0;
	
	public CompressSize(int [][]a) {
		makeArray(a);
		
		int index = 0;
		for(int i = 0; i < a.length; i++) {
			for(int j = 0; j < a[i].length; j++) {
				if(a[i][j] != 0) {
					array[index++] = a[i][j];
				}
			}
		}
	}
	
	private void makeArray(int [][]a) {
		size = a.length;
		int s = (size * (size + 1)) /2;
		array = new int[s];
	}
	
	public int getDataByMatrixIndex(int x, int y) {
		int cache = size * (x-1);
		int notZero = (x * (x-1)) / 2;
		cache = cache - notZero + y;
		return array[cache - 1];	// cache is matrix type, -1 for change to array type-=0
	}
}

**--實作
> 

#### 左下三角

* **主要改變在 getDataByMatrixIndex 的算式**
* 找出向量座標 A32(i = 3, j = 2) 在一維陣列 B[index] 中的 index
* index = (i * (i-1))/2 + j
> (i * (i-1))/2 : **非 0 的項目**(0 不放入一維陣列中儲存)
> j : 加上位移的座標

public class StartCoding {

	public static void main(String[] args) {
		int [][]A = {	// 4*4
				{ 25,  0,  0,  0},
				{  1, 33,  0,  0},
				{  2, 10, -8,  0},
				{  3, 20, 50,  9}
		};
		
		CompressSize cs = new CompressSize(A);
		
		for(int i = 0; i < A.length; i++) {
			for(int j = 0; j < A[i].length; j++) {
				int x = cs.getDataByMatrixIndex(i + 1, j + 1);	// +1 is array type to matrix type
				System.out.println(x);
			}
		}
		System.out.println("---------");
		
		System.out.println("A32 : " + cs.getDataByMatrixIndex(3, 2));
	}
	
}

class CompressSize {
	... 同上
	public int getDataByMatrixIndex(int x, int y) {
		int notZero = (x * (x-1)) / 2;
		int cache = notZero + y;
		return array[cache - 1];	// cache is matrix type, -1 for change to array type
	}
}

**--實作
> 

#### 左上三角
* **主要改變在 getDataByMatrixIndex 的算式**

// 主要在改變 getDataByMatrixIndex 的算式

#### 右下三角
* **主要改變在 getDataByMatrixIndex 的算式**

// 主要在改變 getDataByMatrixIndex 的算式

## Appendix & FAQ

:::info
:::

###### tags: `資料結構`