【資料結構】陣列
陣列的觀念
【定義】陣列是指一群具有相同名稱及資料型態的變數之集合。
【特性】
- 佔用連續記憶體空間。
- 用來表示有序串列之一種方式。
- 各元素的資料型態皆相同。
- 支援隨機存取(Random Access)與循序存取(Sequential Access)。
- 插入或刪除元素時較為麻煩。因為須挪移其他元素。
【優點】
(1)利用註標（Index）可以快速的輸入資料。
輸入：for(i=0;i<5;i++) //利用「迴圈結構」
A[i]=i*2+1; //快速「輸入資料」到「陣列」中
(2) 利用註標（Index）一次可以輸出大批的資料。
輸出：for(i=0;i<5;i++) //利用「迴圈結構」
WriteLine(A[i]); //從「陣列」一次「輸出大批」的資料
【定義】宣告陣列時，其括弧內的「註標」個數，只有一個時稱為「一維陣列」。在一維陣列中，常使用的運算指令有五種。
- 讀取(Read)
- 寫入(Write)
- 插入(Insert)
- 刪除(Delete)
- 複製(Copy)
讀取(Read)
【定義】利用註標（Index）來「讀取」資料。
【例如】將A陣列的第二個元素放到X目的變數中。
【寫法】X= A[1]; //陣列的註標是從0開始
【圖解】
寫入(Write)
【定義】利用註標（Index）來「寫入」資料。
【例如】將數值50寫入到陣列的第二個索引位置中。
【寫法】A[1]=50; //陣列的註標是從0開始
【圖解】
插入(Insert)
【定義】在指定的註標 i 的位置插入一項新元素，原來註標 i 和之後的元素都必須要再往後挪移一個位置。
【例如】將在註標1的位置插入一項新元素(15)。
【演算法】
Procedure ArrayInsert(int A[],int Max,int i ,int value)
Begin
If(i>0 && i<=Max) //判斷欲插入位置i是否存在，如果有，則
{
for(count=Max-1;count>i;count--) //i位置及後面的元素逐一往後挪
A[count]=A[count-1];
A[i]=value; //最後再將新元素插入到第i位置
}
Else //如果欲插入位置i不存在，則
Return 0; //傳回0
End
End Procedure
【圖解】
【說明】
首先將30往後挪移一個位置，再將A[1]的元素20，往後挪移放到A[2]位置中，最後再插入15到A[1]中。
刪除(Delete)
【定義】指刪除指定的註標 i 位置的元素，原來註標 i的元素被刪除，為了避免浪費記憶體空間，因此，之後的元素都必須要再往前挪一個位置。
【例如】將在註標1的位置刪除一項舊元素(20)。
【演算法】
Procedure ArrayDelete(int A[],int Max,int i)
Begin
If(i>0 && i<=Max) //判斷欲刪除元素位置i是否存在，如果有，則
{
for(count=i;count<Max-1;count++) //i位置後面的元素逐一往前挪
A[count]=A[count+1];
A[Max-1]=0; //最後再將0放到最後一個位置
}
Else //如果欲插入位置i不存在，則
Return 0; //傳回0
End
End Procedure
【圖解】
【說明】 首先將A[1]的元素20刪除，再將A[2]的元素30往前挪移一個位置，最後再寫入0到A[2]中。
複製(Copy)
【定義】指將「來源陣列」的元素內含值全部逐一copy到「目的陣列」。
【例如】將A陣列的元素內含值全部逐一copy到B陣列中。
【演算法】
Procedure ArrayCopy(int A[],int B[], int Max)
Begin
If(Max>0) //判斷陣列是否有元素內含值，如果有，則
{
for(count=0;count<Max-1;count++) //A陣列全部逐一copy到B陣列
B[count]=A[count];
}
Else //如果陣列沒有元素，則
Return 0; //傳回0
End
End Procedure
【圖解】
【說明】
A陣列的元素內含值全部逐一copy到B陣列中，例如A[0]元素會被copy到B[0]中，A[1]元素放到B[1]中，以此類推。
陣列的宣告
(1) 變數宣告
int A, B, C; //宣告三個變數(A,B,C)為整數型態
以上三個變數與變數之間都是個別獨立的記憶體空間。
(2) 陣列宣告
int A[3]; //宣告一維陣列A，共有A[0]、A[1]、A[2]三個元素
以上三個記憶體空間，可以讓我們連續儲存多項資料，並且資料與資料之間都是按照順序排列的記憶體空間。
陣列的儲存方式
【定義】陣列名稱之後加上“註標”即可存取陣列元素。
【舉例】宣告一個A[3]的陣列，並分別儲存10,20,30
Procedure ArrayCopy(int A[],int B[], int Max)
Begin
If(Max>0) //判斷陣列是否有元素內含值，如果有，則
{
for(count=0;count<Max-1;count++) //A陣列全部逐一copy到B陣列
B[count]=A[count];
}
Else //如果陣列沒有元素，則
Return 0; //傳回0
End
End Procedure
【實例】請依序輸入六位同學的成績到陣列中，並計算及輸出「總和」
第一種寫法：使用陣列，但未使用for迴圈演算法
int A[6] = {100, 98, 88, 67, 75, 90};
int sum = A[0] + A[1] + A[2] + A[3] + A[4] + A[5];
Console.WriteLine("總和為：" + Sum);
第二種寫法：使用陣列，並且使用for迴圈演算法 (最佳)
int A[6] = {100, 98, 88, 67, 75, 90};
int sum = 0;
for (int i = 0; i < 6; i++) {
sum = sum + A[i];
}
Console.WriteLine("總和為：" + Sum);
二維陣列的觀念
在前面所介紹一維陣列，可以視為直線方式來存取資料，這對於一般的問題都可以順利的處理，但是對於比較複雜的問題時，那就必須要使用二維陣列來處理。否則會增加程式的複雜度。
例如：計算4位同學的5科成績之總分與平均的問題。
【定義】宣告陣列時，其括弧內的「註標」個數，有兩個時稱為「二維陣列」。
【語法】資料型態 陣列名稱[M][N];
【說明】M代表列數，N代表行數
【存取方法】利用二維陣列中的兩個註標來表示。
多維陣列的觀念
【定義】宣告陣列時，其括弧內的「註標」個數，是二個以上時，就稱為「多維陣列」。其中最常見是三維陣列，其圖形為三度空間的立體圖形，並且我們可以將三維陣列視為多個二維陣列的組合。
【語法】資料型態 陣列名稱[L][M][N];
【說明】L代表二維陣列個數，M代表列數，N代表行數
【舉例】設計有某一個大學，3次月考，全班4位同學的5科目成績時。利用三維陣列來存取每人學生的成績。
【說明】
此例子中Score陣列共有三個註標，故Score陣列是一個三維 陣列。
//其中，第一個註標為：二維陣列的個數： 0~2 共有3個二維陣列
第二個註標為：列註標表示範圍： 0~3 共有4列
第三個註標為：行註標表示範圍： 0~4 共有5行
【圖解】
【說明】宣告Score是由3個(0~2)二維陣列，每個二維陣列包含4列 (0~3)，5行(0~4)組合而成的整數三維陣列。並且共計有3×4×5＝60元素。
陣列在記憶體中的表示法
陣列是由一連串的記憶體組合而成，其陣列元素之儲存位址計算，
大致上，可分為一維陣列與二維陣列來說明：
Ⅰ. 一維陣列
[題目1]若陣列A有N個元素，其陣列的起始位址為Lo，並且索引值從0開始，d 為元素大小，則A[i]的起始位置為多少？
令：Lo為起始位址，d為元素大小，則A[i]之位置計算=Lo+i*d。
【舉例】假設每一個整數佔用2個byte，若A陣列的起始位址是100開始，則A[5]的起始位址為多少？
令：起始位址Lo=100
元素大小d=2
則A[5]之位置計算=Lo+i*d =100+5*2=100+10=110
[題目2]若陣列A的索引從L到U，其陣列的起始位址為Lo， d為元素大小，則A[i]的起始位置為多少？
宣告方式：A[L…U]
令：Lo為起始位址，d為元素大小，則A[i]之位置計算=Lo+(i-L)*d
【舉例】假設每一個整數佔用2個byte，若A[10]起始位址是200開始，則A[20]的位址為多少？
令：Lo起始位址=200 ，d元素大小=2
則A[20]之位置計算=Lo+(i-L)*d =200+(20-10)*2=200+10*2=220
二維陣列
宣告方式：A[0…M-1, 0…N-1]， 其中：M代表列數(Row)，橫向，N代表行數(Column)，縱向。所以，共有M*N格。
說明：¡圖的儲存位置：A[1,4]，△圖的儲存位置：A[2,1]，o圖的儲存位置：A[M-1,N-2]
Row-major(以列為主)
【定義】以列為主的二維陣列要轉為一維陣列時，是將二維陣列「由上往下」一列一列讀入一維陣列。亦即將二維陣列儲存的邏輯位置轉換成實際電腦中主記憶體的存儲方式。
【圖解】
【以列為主的儲存公式】
令Lo為起始位址，d為元素大小，則二維陣列A[i,j]位置會儲存到一維陣列的那一個位置呢？
公式=Lo+[i*N+j]*d
Column-major(以行為主)
【定義】以行為主的二維陣列要轉為一維陣列時，必須將二維陣列「由左往右」一行一行讀入一維陣列。亦即將二維陣列儲存的邏輯位置轉換成實際電腦中主記憶體的存儲方式。
【圖解】
【以行為主的儲存公式】
令Lo為起始位址
d為元素大小
則二維陣列A[i,j]位置會儲存到一維陣列的那一個位置呢？
公式=Lo+[j*M+i]*d
多項式(polynomials)
多項式(polynomial)的表示式為
其中Ai為非零項的係數，且多項式的每一項均使用三個欄位來表示(分別為 coef, exp, link) 。其節點的資料結構如下所示：
其中：Coef：表示該變數的係數
Exp：表示該變數的指數
Link：表示指向下一個節點的指標
【表示方法】
【方法一】依照指數高低依序儲存係數
【作法】假設最高指數為n，則準備一個一維陣列A[1..n+2]，
其內容如下：
【練習】假設f(x)=7X4+5X2+3X
因為最高指數為4，則準備一個一維陣列A[1..6]，
【解答】
步驟一：準備一個一維陣列A[1..6]
步驟二：存入最高指數及分別存入Xn, Xn-1,…,X0之係數
【優點】
(1)只要儲存係數，比較節省儲存指數空間。
(2)適用於零項次較少的多項式。
【缺點】
不適用於零項次極多的多項式，儲存時非常浪費空間。
Ex: f(X)=5X100+1
則必須要準備一個一維陣列A[1..102]，在實際使用上只用了3格，因此，會浪費99格。
【方法二】只儲存非零項次的係數與指數
【作法】假設多項式有K個非零項次，則準備一個一維陣列A[1..2K+1]，其內容如下：
【練習】假設f(X)=5X100+1
因為有2個非零項次，則準備一個一維陣列A[1..5]
【解答】
步驟一：準備一個一維陣列A
步驟二：存入K 、係數及指數
【優點】適用於零項次極多的多項式。
【缺點】當非零項次極多時，不適用。
矩陣(Matrices)
【定義】
類似二維陣列，它是利用一個m × n矩陣來表示這個矩陣擁有
m列（Rows）和n行（Columns）。
一般而言，資料結構上常用到的矩陣有四種：
- 矩陣轉置(Matrix Transposition)
- 矩陣相加(Matrix Addition)
- 矩陣相乘(Matrix Multiplication)
- 稀疏矩陣(Sparse Matrix)
矩陣轉置(Matrix Transposition)
【定義】
假設有一個(m × n)矩陣A，則我們可以將A矩陣轉置為(n × m)的B矩陣，並且B矩陣的第j列第i行的元素等於A矩陣的第i列第j行的元素，
以數學式來表示為：Bji=Aij
【假設】A矩陣與B矩陣的m與n都是從1開始計算，因此，A,B矩陣的表示如下：
說明：A矩陣的第i列第j行的元素等於B矩陣的第j列第i行的元素
【演算法】
Procedure Matrix_Transpose(int m, int n, int A[m][n], int B[n][m])
Begin
for(i = 1; i <= m; i++) //外迴圈，先掃瞄第1列到第m列
for(j = 1; j <= n; j++) //內迴圈，再掃瞄第1行到第n行
//將A陣列的第i列第j行的元素放到B陣列的第j列第i行的元素中
B[j][i] = A[i][j];
End
End Procedure
矩陣相加(Matrix Addition)
【定義】
假設A,B都是(m × n)矩陣，則我們可以將A矩陣加上B矩陣以得到一個C矩陣，並且此C矩陣亦為(m × n)矩陣。因此：
在C矩陣上的第i列第j行的元素必定等於A矩陣的第i列第j行的元素加上B矩陣的第i列第j行的元素。
以數學式來表示為：Cij= Aij+Bij
【假設】A、B、C矩陣的m與n都是從1開始計算，因此，A,B兩個矩陣相加等於C矩陣，其表示如下：
【演算法】
Procedure Matrix_Add(int m, int n, int A[m][n], int B[m][n], int C[m][n]) Begin for(i = 1; i <= m; i++) //外迴圈，先掃瞄第1列到第m列 for(j = 1; j <= n; j++) //內迴圈，再掃瞄第1行到第n行 /*將A陣列的第i列第j行的元素加上B陣列的第i列第j行的元素之後， 放到C陣列的第i列第j行的元素中 */ C[i][j] = A[i][j] + B[i][j]; End End Procedure
矩陣相乘(Matrix Multiplication)
【定義】
假設A為(m × n)矩陣，而B為(n × p)矩陣，則我們可以將A矩陣乘上B矩陣以得到一個(m × p)的C矩陣，因此，在C矩陣上的第i列第j行的元素必定等於A矩陣的第i列乘上B矩陣的第j行(兩個向量的內積)，以數學式來表示為：
【假設】A、B、C矩陣的m與n都是從1開始計算，因此，A,B兩個矩陣相乘等於C矩陣，其表示如下：
【演算法】
Procedure Matrix_Mul(int m, int n, int p, int A[m][n], int B[n][p], int C[m][p])
Begin
for(i = 0; i < m; i++) //外迴圈，先掃瞄第1列到第m列
for(j = 0; j < n; j++) //內迴圈，再掃瞄第1行到第n行
{
C[i][j]=0;
/*將A矩陣的第i列第j行的元素加上B矩陣的第i列第j行的
元素的結果放到C矩陣上的第i列第j行的元素中*/
for(k=0;k<p;k++)
C[i][j] = C[i][j] + A[i][k] * B[k][j];
}
End
End Procedure
C#程式
#include <iostream>
void MultiplyWithOutAMP() {
int aMatrix[3][2] = {{1, 4}, {2, 5}, {3, 6}};
int bMatrix[2][3] = {{7, 8, 9}, {10, 11, 12}};
int product[3][3] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
// Multiply the row of A by the column of B to get the row, column of product.
for (int inner = 0; inner < 2; inner++) {
product[row][col] += aMatrix[row][inner] * bMatrix[inner][col];
}
std::cout << product[row][col] << " ";
}
std::cout << "\n";
}
}
void main() {
MultiplyWithOutAMP();
getchar();
}
稀疏矩陣(Sparse Matrix)
【定義】 是指矩陣中大部份元素都沒有使用，元素稀稀落落，所以稱為稀疏矩陣。
【概念】在M × N 的矩陣中，多數的資料值為０。
【處理方法】
【方法一】直接利用M × N的二維陣列來一一對應儲存。
【缺點】
1. 浪費空間：因為多數為０。
2. 浪費時間：因為要處理一些不必要的計算。
【方法二】利用3-tuple結構來儲存非零元素
【作法】假設有一個M*N的稀疏矩陣中共有K個非零元素，則必須要準備一個二維陣列A[0..K,0..2]
