3-4 多維陣列的觀念 當陣列的維度是二維以上時, 就稱為多維陣列 而其中最常見是三維陣列, 其圖形為三度空間的立體圖形, 並且我們可以將三維陣列視為多個二維陣列的組合 Dim 陣列名稱 (L,M,N) As 資料型態 L 代表二維陣列個數 M 代表列數 N 代表行數 Dim Score (2,3,4) As Integer ' 二維陣列的個數 : 0~2 共有 3 個二維陣列 ' 列註標表示範圍 : 0~3 共有 4 列 ' 行註標表示範圍 : 0~4 共有 5 行設計一個某高中,3 次月考, 全班 4 位同學的 5 個科目成績 利用三維陣列來存取每位學生的成績 Dim Score(2, 3, 4) As Integer 3-14 月考次數學生人數科目數此例子中 Score 陣列共有三個註標, 故 Score 陣列是一個三維陣列 宣告 Score 是由 3 個 (0~2) 二維陣列, 每個二維陣列包含 4 列 (0~3),5 行 (0~4) 組合而成的整數三維陣列 並且共計有 3 4 5=60 元素 如圖 3-4 所示 :
陣列 (Array) Score(2,0,0) Score(1,0,0) Score(0,0,0) (0,0,0) (0,0,1) (0,0,2) (0,0,3) (0,0,4) (0,1,0) (0,1,1) (0,1,2) (0,1,3) (0,1,4) (0,2,0) (0,2,1) (0,2,2) (0,2,3) (0,2,4) (0,3,0) (0,3,1) (0,3,2) (0,3,3) (0,3,4) 圖 3-4 三維陣列的邏輯配置 假設老師利用二維表格, 來記錄學生的三次月考成績, 如下 所示 : 第一次月考成績單 姓名 國文 英文 數學 資料庫 程式設計 張三 65 85 78 75 69 李四 66 55 52 92 47 王五 75 99 63 73 86 雄雄 77 88 99 91 99 第二次月考成績單 姓名 國文 英文 數學 資料庫 程式設計 張三 77 88 66 77 66 李四 65 66 88 55 77 王五 70 88 56 88 88 雄雄 80 90 95 99 99 3-15
第三次月考成績單 姓名 國文 英文 數學 資料庫 程式設計 張三 55 67 56 98 67 李四 66 69 76 66 78 王五 77 89 88 77 77 雄雄 88 89 99 97 88 題目 : 三維陣列的應用程式檔案名稱 ch3_4.sln 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 Public Class Form1 Dim i, j, k As Integer Dim Temp As String = "" Dim Stu_Sum(2, 4) As Integer ' 學生總成績 Dim Stu_Average(2, 4) As Integer ' 學生平均成績 Dim Subject_Sum(2, 4) As Integer ' 科目總成績 Dim Subjcet_Average(2, 4) As Integer ' 科目平均成績 Dim Stu_Name() As String = {" 張三 ", " 李四 ", " 王五 ", " 雄雄 "} Dim Score(,,) As Integer = {{{65, 85, 78, 75, 69}, {66, 55, 52, 92, 47}, {75, 99, 63, 73, 86}, {77, 88, 99, 91, 99}}, {{77, 88, 66, 77, 66}, {65, 66, 88, 55, 77}, {70, 88, 56, 88, 88}, {80, 90, 95, 99, 99}}, {{55, 67, 56, 98, 67}, {66, 69, 76, 66, 78}, {77, 89, 88, 77, 77}, {88, 89, 99, 97, 88}}} Private Sub Button1_Click() Handles Button1.Click ' ======= 讀取資料並計算各科總分 ====== For k = 0 To 2 '3 次月考 For i = 0 To 3 ' 控制列數 For j = 0 To 4 ' 控制行數 ' 計算出每一位 同學 的總成績 Stu_Sum(k, i) = Stu_Sum(k, i) + Score(k, i, j) ' 計算出每一 科目 的總成績 Subject_Sum(k, j) = Subject_Sum(k, j) + Score(k, i, j) Next j Next i Next k '========= 印出開頭 ======== For k = 0 To 2 '3 次月考 Temp = Temp & "========= 第 " & (k + 1) & " 次月考成績如下 :========" & vbnewline Temp = Temp & " 姓名 國文英文數學計概程設 " & vbnewline Temp = Temp & "===================================" & vbnewline ' ======== 印出成績單 ======= For i = 0 To 3 ' 控制列數 3-16
陣列 (Array) 題目 : 三維陣列的應用程式檔案名稱 ch3_4.sln 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 Temp = Temp & Stu_Name(i) For j = 0 To 4 ' 控制行數 Temp = Temp & " " & Score(k, i, j) Next j Temp = Temp & vbnewline Next i Temp = Temp & vbnewline Temp = Temp & vbnewline Temp = Temp & vbnewline Label1.Text = Temp Next k End Sub Private Sub Button2_Click() Handles Button2.Click ' ======== 印出學科平均成績 ======= Label2.Text = " 學科平均 " Label4.Text = " 學科平均 " Label6.Text = " 學科平均 " For k = 0 To 2 '3 次月考 For j = 0 To 4 ' 控制行數 (' 計算出每一科目的平均分數 ) Subjcet_Average(k, j) = Subject_Sum(k, j) / 4 Next j Next k For j = 0 To 4 ' 控制行數 Label2.Text = Label2.Text & " " & Subjcet_Average(0, j) Label4.Text = Label4.Text & " " & Subjcet_Average(1, j) Label6.Text = Label6.Text & " " & Subjcet_Average(2, j) Next j End Sub Private Sub Button3_Click() Handles Button3.Click ' ======== 印出學生平均成績 ======= Label3.Text = " 學生成績 " & vbnewline & vbnewline Label5.Text = " 學生成績 " & vbnewline & vbnewline Label7.Text = " 學生成績 " & vbnewline & vbnewline For k = 0 To 2 For i = 0 To 3 ' 計算出每一位同學的平均成績 Stu_Average(k, i) = Stu_Sum(k, i) / 5 Next i Next k For i = 0 To 3 Label3.Text = Label3.Text & Stu_Average(0, i) & vbnewline Label5.Text = Label5.Text & Stu_Average(1, i) & vbnewline Label7.Text = Label7.Text & Stu_Average(2, i) & vbnewline Next i End Sub End Class 3-17
3-5 陣列在記憶體中的表示法 陣列是由一連串的記憶體組合而成, 其陣列元素之儲存位址計算, 如下所示 : 一 一維陣列 (1) 若陣列 A 有 N 個元素, 其陣列的起始位址為 Lo, 並且索引值從 0 開始,d 為元素大小, 則 A[i] 的起始位置為多少? 以 VB2008 宣告方式 :Dim A(N) As Integer 0 1 2 i N-1 d d Lo Lo+2d Lo+i*d 令 : Lo 為起始位址 d 為元素大小 3-18 則 A[i] 之位置計算 =Lo+i*d
陣列 (Array) 假設每一個整數佔用 2 個 byte, 若 A 陣列的起始位址是 100 開始, 則 A[5] 的起始位址為多少? 令 : Lo=100 d=2 則 A[5]=100+5*2=100+10=110 (2) 若陣列 A 的索引從 L 到 U, 其陣列的起始位址為 Lo,d 為元素大小, 則 A[i] 的起始位置為多少? 宣告方式 :A[LU] L L+1 L+ 2 i U d d Lo Lo+2d Lo+(i-L)*d 令 : Lo 為起始位址 d 為元素大小則 A[i] 之位置計算 =Lo+(i-L)*d 假設每一個整數佔用 2 個 byte, 若 A[10] 起始位址是 200 開始, 則 A[20] 的位址為多少? 令 : Lo=200 d=2 則 A[20]=200+(20-10)*2=200+10*2=220 3-19
二 二維陣列宣告方式 :A[0M-1, 0N-1] 其中 :M 代表列數 (Row), 橫向 N 代表行數 (Column), 縱向 所以, 共有 M*N 格 0 1 2 3 4 N-2 N-1 0 1 2 M-2 M-1 說明 : 圖的儲存位置 :A[1,4] 圖的儲存位置 :A[2,1] 圖的儲存位置 :A[M-1,N-2] 3-5.1 Row-major( 以列為主 ) 在二維陣列中, 如何將二維陣列轉成一維陣列, 一般而言, 有兩種方式 : 以列 (Row) 為主 或 以行 (Column) 為主 但 VB2008 語言的記憶體配置方式都是以列為主 一 以列為主 (Row-major) 方式 : 以列為主的二維陣列要轉為一維陣列時, 是將二維陣列 由上往下 一列一列讀入一維陣列, 亦即將二維陣列儲存的邏輯位置轉換成實際電腦中主記憶體的存儲方式 如下圖所示 : 3-20
陣列 (Array) 0 1 2 N-1 主記憶體 0 A[0,0] 1 A[0,1] 2 3 A[0,N-1] A[1,0] A[1,1] M-1 A[M-1,N-1] ( 邏輯位置 ) ( 實體位置 ) 二 以列為主的儲存公式 : 令 Lo 為起始位址 d 為元素大小則 A[i,j] 的位置 =Lo+[i*N+j]*d 0 1 2 3 0 1 2 N-1 j 行 A[i,j] i 列 M-11 的位置為 :A[3,2]=Lo+[3*N+2]*d=Lo+(3N+2)*d 因此, 當 Lo=1, N=10,d=1 時, 則 A[3,2]=1+(3*10+2)*1=33 1. 宣告方式 A[L 1 U 1, L 2 U 2 ] 其 : 列數為 U 1 -L 1 +1 行數為 U 2 -L 2 +1 3-21
2. 以列為主的儲存公式 : A[i,j] 的位置 =Lo+[(i-L 1 )*( U 2 -L 2 +1)+(j-L 2 )]*d 檔案在附書光碟中 以列為主 (Row-major) 以行為主 (Column-major) 請將下列的二維陣列轉換成一維陣列 ( 以列為主 ) 0 1 2 3 4 0 1 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3-22
陣列 (Array) 題目 : 二維矩陣轉一維矩陣 ( 以列為主 ) 程式檔案名稱 ch3_5_1.sln 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 Public Class Form1 Dim N As Integer = 3 ' 列數 Dim M As Integer = 5 ' 行數 Dim Array_Data1(,) As Integer = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}} Dim Array_Data2(N * M) As Integer Dim Temp1 As String = "" Dim Temp2 As String = "" Dim row, column, i As Integer Private Sub Form1_Load() Handles MyBase.Load Temp1 = Temp1 & " 二維資料之原始資料 :" & vbnewline For row = 0 To N - 1 For column = 0 To M - 1 If (Array_Data1(row, column) >= 10) Then Temp1 = Temp1 & Array_Data1(row, column) & " " Else Temp1 = Temp1 & Array_Data1(row, column) & " " End If Next column Temp1 = Temp1 & vbnewline Next row Label1.Text = Temp1 End Sub End Class Private Sub Button1_Click() Handles Button1.Click Temp2 = Temp2 & " 以列為主 :" & vbnewline For row = 0 To N - 1 For column = 0 To M - 1 i = column + row * M Array_Data2(i) = Array_Data1(row, column) & " " Next column Next row For i = 0 To N * M - 1 Temp2 = Temp2 & Array_Data2(i) & " " Next i Label2.Text = Temp2 End Sub 3-23
3-5.2 Column-major( 以行為主 ) 一 以行為主 (Column-major) 方式 : 以行為主的二維陣列要轉為一維陣列時, 是將二維陣列 由左往右 一行一行讀入一維陣列, 亦即將二維陣列儲存的邏輯位置轉換成實 際電腦中主記憶體的存儲方式 如下圖所示 : 0 1 2 N-1 主記憶體 0 A[0,0] 1 A[1,0] 2 3 A[M-1,0] A[0,1] A[1,1] M-1 A[M-1,N-1] 二 以行為主的儲存公式 : 令 Lo 為起始位址 d 為元素大小 則 A[i,j] 的位置 =Lo+[j*M+i]*d ( 邏輯位置 ) ( 實體位置 ) 0 1 2 N-1 0 1 i 列 2 3 A[i,j] 3-24 M-1 j 行
陣列 (Array) 的位置為 :A[3,2]=Lo+[2*M+3]*d 因此, 當 Lo=1, M=10,d=1 時, 則 A[3,2]=1+(2*10+3)*1=24 宣告方式 A[L 1 U 1, L 2 U 2 ] 其 : 列數為 U 1 -L 1 +1 行數為 U 2 -L 2 +1 以行為主的儲存公式 : A[i,j] 的位置 =Lo+[(j-L 2 )*( U 1 -L 1 +1)+(i-L 1 )]*d 請將下列的二維陣列轉換成一維陣列 ( 以行為主 ) 0 1 2 0 1 2 3 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3-25
題目 : 多維矩陣轉一維矩陣 ( 以行為主 ) 程式檔案名稱 ch3_5_2.sln 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 Public Class Form1 Dim N As Integer = 3 ' 列數 Dim M As Integer = 5 ' 行數 Dim Array_Data1(,) As Integer = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}} Dim Array_Data2(N * M) As Integer Dim Temp1 As String = "" Dim Temp2 As String = "" Dim row, column, i As Integer Private Sub Form1_Load() Handles MyBase.Load Temp1 = Temp1 & " 二維資料之原始資料 :" & vbnewline For row = 0 To N - 1 For column = 0 To M - 1 If (Array_Data1(row, column) >= 10) Then Temp1 = Temp1 & Array_Data1(row, column) & " " Else Temp1 = Temp1 & Array_Data1(row, column) & " " End If Next column Temp1 = Temp1 & vbnewline Next row Label1.Text = Temp1 End Sub Private Sub Button1_Click() Handles Button1.Click Temp2 = Temp2 & " 以行為主 :" & vbnewline For row = 0 To N - 1 For column = 0 To M - 1 i = row + column * N Array_Data2(i) = Array_Data1(row, column) & " " Next column Next row For i = 0 To N * M - 1 Temp2 = Temp2 & Array_Data2(i) & " " Next i Label2.Text = Temp2 End Sub End Class 3-26
陣列 (Array) 3-5.3 二維陣列的四個題型 給予所有資料 已知以下三個條件 : Row major 或 Column major 給予 Lo 給予 d 求 A[i,j] 之位置? 給予一個二維陣列 A[-4..3, -3..2], Lo=100, d=1, 採用 Row-major 方式, 請計算 A[2,2] 的位置 在 A[-4..3, -3..2] 陣列中, 共有 (3-(-4)+1)=8 列,(2-(-3)+1)=6 行公式 :A[i,j] 的位置 =Lo+[(i-L 1 )*( U 2 -L 2 +1)+(j-L 2 )]*d A[2,2] 的位置 =100+[(2-(-4))*6+(2-(-3))]*1 =100+[36+5]*1=141 給予二個已知位址 <1> 自行判斷出給予的二維陣列是 Row-major 或 Column-major 求 A[i,j] 之位置? 給予一個二維陣列的資料如下 : A[3,2] 的位址 =1110 A[2,3] 的位址 =1115 d1=1 求 A[1,4] 及 A[5,4] 之位址? 判斷 A[ 3, 2] =1110 v ^ ^ A[ 2, 3] =1115 3-27
因為 A[2, 3] 的行與位址大小成正比, 所以是以行為主 (Column-major) 方法一 : A[ 3, 2] =Lo+[2*M+3]*d =Lo+(2M+3)*1 =Lo+2M+3=1110------------------(1) A[ 2, 3] =Lo+[3*M+2]*d =Lo+(3*M+2)*1 =Lo+3*M+2=1115-----------------(2) (2)-(1) M-1=5 M=6 代入 (1) Lo+2*6+3=1110 Lo=1095 方法二 : A[ 2, 3]= A[ 3, 2]+[(3-2)*M+(2-3)]*d =1110+M-1=1115 M=6 求 A[1,4]=1095+[4*6+1]=1120 A[5,4] =1095+[4*6+5]*1=1124 給予二個已知位址 <2> 自行判斷出給予的二維陣列是 Row-major 或 Column-major, 並且兩者皆須求算完之後, 可能一合一不合或兩者皆合求 A[i,j] 之位置? 給予一個二維陣列的資料如下 : A[3,3] 的位址 =121 A[6,4] 的位址 =159 d=1 求 A[4,5] 之位址? 判斷 A[ 3, 3] =121 ^ ^ ^ A[ 6, 4] =159 因此, 有兩種情況, 必須要各別分析 : 假設以列為主 (Row-major) A[6,4]= A[3,3]+[(6-3)*N+(4-3)]*1 =121+3N+1=159 N=37/3( 有小數 ) Row-major 不合 3-28
陣列 (Array) 因此, 必須要再求算以行為主 (Column-major) A[6,4]= A[3,3]+[(4-3)*M+(6-3)]*1 =121+M+3=159 M=35 求 A[4,5] 之位址 = A[3,3]+[(5-3)*35+(4-3)]*1 =121+70+1=192 給予三個已知位址 自行判斷出給予的二維陣列是 Row-major 或 Column-major, 如果是 Row-major, 則必須要再求算 N, d 如果是 Column-major, 則必須要再求算 M, d 求 A[i, j] 之位置? 給予一個二維陣列的資料如下 : A[1,1] 的位址 =2 A[2,3] 的位址 =18 A[3,2] 的位址 =28 求 A[4,5] 之位址? 判斷 A[ 2, 3] =18 ^ v ^ A[ 3, 2] =28 因為 A[2, 3] 的列與位址大小成正比, 所以是以列為主 (Row-major) 因此, 必須要再求算 N,d A[ 2, 3] =A[1,1]+[(2-1)*N+(3-1)]*d =2+Nd+2d=18------------------(1) A[3, 2] =A[1,1]+[(3-1)*N+(2-1)]*d =2+2Nd+d=28------------------(2) (1)*2-(2) 式 8=2+3d d=2 代回 (1) N=6 求 A[4,5] 之位址 = A[1,1]+[(4-1)*6+(5-1)]*2 =2+36+8=46 3-29
0B 一 基本題 題庫來源 : 研究所及高普考 1. 請詳細定義 陣列 的意義及優點? 並說明使用 一般變數 與 陣列變數 的差異? 2. 有一整數陣列 int A[50]; ( 假設 sizeof(int)=2) (1) 此陣列共佔多少位元組? (2) 若 A[0] 在記憶體中的位址為 03C416, 則元素 A[21] 的位址為何? (3) 若 A[31] 在記憶體中的位址為 10E916, 元素 A[40] 的位址為何? 3. 有一 4 3 陣列 [Aij], 其中 1 i 4, 1 j 3, 若採取以列為主 (row-major) 的連續記憶體儲存方式, 則元素 A32 應儲存記憶體中的位址為何?( 假設 A11 的記憶體位址在 A 的位址 ) 4. 請將下列的稀疏矩陣儲存到二維陣列中 0 0 0 0 5 0-1 0 0 0 1 0 3 0 0 0 0 0 0 0 0 2 4 0 0 0 0 0 0 0 5. 在程式語言中如果我們使用二維陣列來處理資料, 但是, 如何將資料內容儲存到主記憶體中的一維陣列? 請詳細說明兩種方法 6. 假設有一個 (2 3) 矩陣 A, 請將它轉置為 (3 2) 的 B 矩陣 其矩陣 A 的內容如下 : 11 A = 14 12 15 13 16 2 3 3-58 7. 假設 A,B 都是 (2 3) 矩陣, 請將 A 矩陣加上 B 矩陣以得到一個 (2 3) 的 C 矩陣 其矩陣 A,B 的內容如下 : 11 A = 14 12 15 13 16 2 3 21 B = 24 22 25 23 26 2 3
陣列 (Array) 二 進階題 1. 假設 A 為 (2 3) 矩陣, 而 B 為 (3 3) 矩陣, 請將 A 矩陣乘上 B 矩陣以 得到一個 (2 3) 的 C 矩陣 其矩陣 A,B 的內容如下 : 1 A = 4 2 5 3 6 2 3 1 B = 0 0 1 1 0 1 1 1 3 3 2. 設假有一個下三角矩陣 (Lower-Triangular Matrix),B 是一個 m n 的陣列, 其中 B(i,j)=0, i<j (1) 求 B 陣列中非 0 元素的最大個數 (2) 如何將 B 陣列以最經濟的方式儲存在記憶體中 3. 若為一下半部三角矩陣, 即 A[i,j]=a ij, 假如 i j; 反之 A[i,j]=0, 其中 a ij 0,1 i N,1 j N, 且 N>1 假設矩陣中的每一個非零元素皆以一個位置來儲存, 而 A[i,j]=0 元素不儲存, 同時假設矩陣是以列為主的方式儲存在一連續記憶體 若 A[1,1] 儲存在 1000 處, 且 A[2,2] 儲存在 1002 處, 則 A[i,j] 應存在那裡? 4. 在一個二維的方形矩陣中, 當主對角線以上的元素均為零時, 稱為 lower-triangular matrix 若欲將 A 中非零元素對映到一個一維陣列中, 請問 : (1) B 陣列的大小為何? (2) 試求出一個位址計算公式將 A(i,j) 對映到 B(k) 中, 分別以列為主和以行為主兩種方式 (3) 矩陣 A 中之零項元素 A(i,j) 中的 i 與 j 有何關係? (4) 試寫一個 Algorithm 將二維矩陣 A 中的元素 ( 非零項 ) 儲存到一維矩陣 B 中 (5) 試寫一個 Algorithm 從 B 陣列中取出 A(i,j) 5. 一個陣列 (Array) 以列為主的順序存放在記憶體中, 每個陣列佔用四個單位的記憶體 若起始位置是 100, 下列宣告中所列元素存放位置為何? Var A:array[-1001, 1...100], 求 A[1,12] 的位址? Var A:array[510, -10...20], 求 A[5,-5] 的位址? 3-59