Try   HackMD

Array靜態陣列

OverView of Content

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

–實作–

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

(一維)記憶體位子運算

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

tags: 資料結構
Last changed by 
 
kyle shanks
正在不斷深入研究 Android / Linux 中 最近自己架設了網站 https://devtechascendancy.com/
0
2065

Read more

Linux 組成、層次概念

Linux 其實是 Unix 的變種，它的本質還是 Unix

Jun 5, 2025
Kyle Resume EN

[TOC]

Mar 2, 2025
Kyle 履歷 Resume

Kyle 履歷 Resume Overview of Content 個人經歷 您好，我是潘奐廷；My english name is Kyle. ( Nickname is alien.) 我畢業於 勤益科技大學，專業類別是 電子系 (高中電機系) 工作經歷 個人開發專案開始時間結束時間公司職位2024年9月till now-自身承接所有業務，包括前端、後端、手機應用、資料設計… 等等在個人撰寫專案的期間有受到「JetBrains 技術佈道師，範聖佑」的邀請到 2024 Kotlin 中文開發者大會 作分享，分享的主題為「Kotlin Multiplatform：打造跨平台SDK 的最佳選擇」

Feb 20, 2025
Android View 事件分發 / 滑動衝突

點擊事件使用到的設計是 責任鏈 模式

Dec 19, 2024
Read more from kyle shanks
Published on HackMD