本章內容 2-1 陣列及陣列位址的計算一維陣列位址計算多維陣列位址計算 2-2 一維陣列的基本運算讀取寫入複製輸出插入資料刪除 2-3 二維陣列及矩陣的儲存與運算矩陣輸出矩陣轉置矩陣相加矩陣相乘 2-4 字串 ( 字元陣列 ) 計算字串長度字串複製字串比較子字串擷取 2

Size: px

Start display at page:

Download "本章內容 2-1 陣列及陣列位址的計算一維陣列位址計算多維陣列位址計算 2-2 一維陣列的基本運算讀取寫入複製輸出插入資料刪除 2-3 二維陣列及矩陣的儲存與運算矩陣輸出矩陣轉置矩陣相加矩陣相乘 2-4 字串 ( 字元陣列 ) 計算字串長度字串複製字串比較子字串擷取 2"

壶诗尚
5 years ago
Views:

1 第二章 Array 版權屬作者所有, 非經作者同意不得用於教學以外用途 1

2 本章內容 2-1 陣列及陣列位址的計算一維陣列位址計算多維陣列位址計算 2-2 一維陣列的基本運算讀取寫入複製輸出插入資料刪除 2-3 二維陣列及矩陣的儲存與運算矩陣輸出矩陣轉置矩陣相加矩陣相乘 2-4 字串 ( 字元陣列 ) 計算字串長度字串複製字串比較子字串擷取 2

3 2-1 陣列及陣列位址的計算陣列 (Array) 是由多個相同型別元素所組成的串列, 這些元素共用一個名稱來表示, 並且加上編號 ( 或稱註標,index) 以區別個別的元素我們可以把陣列想像成一排有編號的格子, 這些格子都存放相同類型的物品, 例如鞋子我們可以隨意打開某一個編號的格子, 以查看裡面的內容 ; 我們也可以把鞋子擺在某一個喜歡的鞋格內, 這就是所謂的隨機存取 (random access) list[0] list[1] list[2] list[3] list[4]

4 2-1 陣列及陣列位址的計算宣告 int list[]; 如果每個元素大小為 len 個 bytes list[0] list[1] list[2] list[3] list[4] list[0] 的 ( 起始 ) 位址是 X list[1] 的位址是 X + 1 len list[2] 的位址是 X + 2 len : list[k] 的位址是 X + k len 陣列的元素在記憶體中是連續的位置 list[0] 是陣列 list 的頭一個元素 list[1] 是編號 1 號元素, 它緊接著 0 號元素同樣的, list[i+1] 的位置是緊接著 list[i] 的 4

5 例 2.1 有一整數陣列 int A[60]; 則此陣列共佔多少位元組 ( 設 sizeof(int)=4)? 若 A[0] 在記憶體中的位址為 03C4 16, 則元素 A[20] 的位址為何? A[0] A 陣列共佔 60 4 = 240 (bytes) A[20] 的位址 = A[0] 的位址 + 位移量 = 03C (20 0 ) 4 = 03C A[1] A[2] A[20] A[9] 位移量 =

6 int list[6][] 此二維陣列的所有元素在邏輯上可以排成一個有 6 列 (row, 橫者為列 ) 行 (column, 直者為行 ) 的平面格子第 0 行第 1 行第 2 行第 3 行第 4 行第 0 列 [0][0] [0][1] [0][2] [0][3] [0][4] 第 1 列 [1][0] [1][1] [1][2] [1][3] [1][4] 第 2 列 [2][0] [2][1] [2][2] [2][3] [2][4] 第 3 列 [3][0] [3][1] [3][2] [3][3] [3][4] 第 4 列 [4][0] [4][1] [4][2] [4][3] [4][4] 第列 [][0] [][1] [][2] [][3] [][4] 6

7 二維陣列在邏輯上表示為平面實體排列順序是線性的第 1 列第 2 行 :List[1][2] 值是 19 第 3 列第 1 行 :List[3][1] 值是 2 以列為主 (row major) (0,0) (0,1) (0,2) (0,3) (0,4) (1,0) (1,1) (,3) (,4) 以行為主 (column major) (0,0) (1,0) (2,0) (3,0) (4,0) (,0) (0,1) (1,1) (4,4) (,4) 7

8 在以列為主 (row major) 的對應中, list[6][] 可以想像成有 6 個長度為的一維陣列, 因為 6 的平面是由 6 條長度的長條組成第 0 行第 1 行第 2 行第 3 行第 4 行第 0 列 [0][0] [0][1] [0][2] [0][3] [0][4] 第 1 列 [1][0] [1][1] [1][2] [1][3] [1][4] 第 2 列 [2][0] [2][1] [2][2] [2][3] [2][4] 第 3 列 [3][0] [3][1] [3][2] [3][3] [3][4] 第 4 列 [4][0] [4][1] [4][2] [4][3] [4][4] 第列 [][0] [][1] [][2] [][3] [][4] 6 條 8

9 如果 list[6][] 每個元素大小為 len 個 bytes, 而且 list[0][0] 的位址為 X, 則 : list[0][3] 的位址是 X + (3 0) len =X + 3 len list[4][3] 的位址是 X + ((4-0) +(3-0)) len = X + (4 +3) len 因為 list[4][3] 之前有 4 整列 ( 每列有個元素 ), 加 3 個元素將其整理為通式, 若有陣列 list[r][c]: 假設 list[0][0] 的位址是 X 則 list[m][n] 的位址 = X + ((m -0) c + (n - 0)) len = X + (m c + n) len r c + m n m c + n 0 m-1 m r-1 n : 長條區域 0 n-1 n c-1 (m,n) m c : 整塊矩形區域 r c 9

10 例 2.3 假設有一宣告為 float A[8][10] 的浮點數陣列, 則 : 此陣列共佔多少位元組 ( 設 sizeof(float) = 4)? 若 A[0][0] 在記憶體中的位址為 03C4 16, 則元素 A[0][9] 的位址為何? 元素 A[6][] 的位址為何? 1. 陣列 A 共佔 = 320 (bytes) 2. A[0][9] 的位址 = A[0][0] 的位址 + 位移量 = 03C ( ) 4 = 03C = 03E8 16 在 A[0][9] 之前有 9 個元素 ( A[0][0] ~ A[0][8] ) 3. A[6][] 的位址 = A[0][0] 的位址 + 位移量 = 03C ( ) 4 = 03C = 04C8 16 在 A[6][] 之前有 6 整列加個元素 = = 6 個元素 10

11 共有 C1 層每層共有 C2 C3 個三維陣列 A[C1][C2][C3], 我們可以想像三維陣列是由小方塊疊成的立方體 : C2 C3 A 1 [6][4][8] 可以想像成有 6 個 A 2 [4][8] 的 2 維陣列 (6 4 8 的立體是由 6 層 4 8 的平面組成 ) 每層 4 8 個 C1 共有 6 層 A[a][b][c] 的位址計算 : 在它之上有整整 a 層, 同一層中在它之前有整整 b 列, 而同列中在它之前有 c 個元素因此 A[a][b][c] 拉成線性相當於距離 A[0][0][0] 有 ( a C2 C3 + b C3 + c ) 個元素 C1 C2 C3 + + a b c ((a C2) + b) C3) + c = a C2 C3+b C3 +c 11

12 例 2.4 三維陣列位址的計算若已知三維陣列 int A[8][10][] 在記憶體中的起始位址為 03C4 16, 且假設每個整數 ( int ) 的大小為 2, 則元素 A[3][8][4] 的位址為何? 解析 A[3][8][4] 的位址 = A[0][0][0] 的位址 + 位移量 = 03C ( ) 2 = 03C =

13 2-2 一維陣列的基本運算以下是陣列的六種基本運算 (operation) : 1. 檢索 ( 讀出 ) 編號為 i 的元素內含值 ; e.g., i =4 value = list[4] ; ( 複雜度 O(1)) 2. 將新值寫入編號為 i 的元素位置 list[4] = NewValue ; ( 複雜度 O(1)) 3. 將一陣列的所有元素複製到另一陣列 ( 陣列的複製 ) 4. 將一陣列的所有元素輸出到螢幕. 在編號 i 的位置插入一新元素, 原來 i 和之後的元素各往後挪一個位置如果陣列編號從 0 到 n-1, 則 n-1 號元素可能將喪失 6. 刪除編號 i 的元素, 原來 i +1 和之後的元素各往前挪一個位置第 n-1 號元素變成無意義 ( 或填入固定值 ) 13

14 3. 陣列的複製 ; ( 複雜度 O(n)) list1[i] = list2[i] i 從 0 到 7 ( 從 0 到 n-1 ) list1[] list2[] [0] [1] [2] [3] [4] [] [6] [7](n-1) 1. void ArrayCopy( int list1[], int list2[], int n) 2. { int i; 3. for (i = 0 ; i < n ; i++) 4. list1[i ] = list2[i] ;. } 14

15 4. 陣列的輸出 ; ( 複雜度 O(n)) 輸出 list[i] i 從 0 到 7 ( 從 0 到 n-1 ) list [] [0] [1] [2] [3] [4] [] [6] [7](n-1) 1. void PrintArray( int list [], int n) 2. { int i; 3. for (i = 0 ; i < n ; i++) 4. cout << list[i] << endl ; //C: printf( %d\n, list[i]);. } 1

16 . 陣列元素的插入 ; ( 複雜度 O(n)) 插入前的陣列插入後的陣列 List[0] 插入點 i 2 2 List[1] 插入 67 至 list[3] List[2] List[3] ( i ) 結束往下搬移 list[i] List[4] (i+1) List[] List[6] 開始往下搬移 list[n-2] List[7] (n-1) 從倒數第二個資料開始 (list[n-2]), 到插入點為止 (list[i]) 每個元素往下移一個位置 16

17 6. 陣列元素的刪除 ; ( 複雜度 O(n)) 刪除前的陣列刪除後的陣列 List[0] 刪除點 i 2 2 List[1] 刪除 list[3] 開始往上搬移 list[i+1] 結束往上搬移 list[n-1] List[2] List[3] ( i ) List[4] List[] List[6] 從刪除點的下一個資料開始 (list[i+1]), 到最後一個資料為止 (list[n-1]) 每個元素往上移一個位置 List[7] (n-1) 17

18 2-3 二維陣列及矩陣的儲存與運算二維陣列可以用來儲存數學的矩陣及行列式, 因此可以用來解決諸如解聯立方程組等線性代數問題數學習慣表示法資料結構示意圖 3 列 4 行 a a a a a a a a a a a a a 00 a 01 a 10 a 11 a 02 a 12 a 20 a 21 a 22 a 03 a 13 a 23 18

19 for (i = 0 ; i < m ; i++) // 照顧矩陣每一列 { for (j = 0 ; j < n ; j++) // 照顧矩陣第 i 列的每一個元素 cout << A[i][j] << ; //C: printf( %d, A[i][j]); cout << endl ; //C: printf( \n ); // 印完一列要換行 } i 由上而下照顧每一列 j 由左而右照顧每一行 a 00 a 01 a 10 a 11 a 02 a 12 a 03 a 13 a 20 a 21 a 22 a 23 19

20 特徵 :B[j][i] = A[i][j] ( 行列顛倒 ) A= a 00 a 01..a 0(n-1) a 10 a 11..a 1(n-1)... a (m-1)0.. a (m-1)(n-1) m n B= A t = a 00 a 10..a (m-1)0 a 01 a 11..a (m-1)1... a 0(n-1).. a (n-1)(m-1) n m A= B= A t = for( i=0 ; i < rows ; i++) for( j=0 ; j < cols ; j++) B[j][i] = A[i][j] ; 20

21 矩陣相加 : 對應的元素相加特徵 :C[i][j] = A[i][j] + B[i][j] a 00 a 01..a 0(n-1) a 10 a 11..a 1(n-1)... a (m-1)0.. a (m-1)(n-1) m n + b 00 b 01..b 0(n-1) b 10 b 11..b 1(n-1)... b (m-1)0.. b (m-1)(n-1) m n = a 00 +b 00 a 10 +b 10 a 01 + b 01 a 11 + b1 01..a 0(n-1) + b 0(n-1)..a 1(n-1) + b 1(n-1).. a (m-1)0 +b a (m-1)0 (m-1)1 + b (m-1)1 a (m-1)(n-1) +b (m-1)(n-1) m n = for( i=0 ; i < rows ; i++ ) for( j=0 ; j < cols; j++ ) C[i][j] = A[i][j] + B[i][j] ; 21

22 A m n B n t = C m t c 00 是 A 矩陣的第 0 列向量乘上 B 矩陣的第 0 行向量 ( 即 : 內積 ) c 00 = [a 00 a 01 a 0(n-1) ] b 00 b 10 b (n-1)0 = a 00 b 00 + a 01 b a 0(n-1) b (n-1)0 (n 個乘法 ) n-1 = Σ a 0k b k0 k=0 c ij 是 A 矩陣的第 i 列向量乘上 B 矩陣的第 j 行向量特徵 : n-1 c ij = Σ a ik b kj k=0 22

23 = 矩陣相乘 :C(m t) 中每個元素是兩個向量內積 for( i = 0 ; i < m ; i++ ) for( j = 0 ; j < t ; j++ ) { C[i][j] = 0 ; for( k = 0 ; k < n ; k++ ) C[i][j] = C[i][j] + A[i][k] * B[k][j] ; } 23

24 2-4 字串在 C/C++ 語言中, 字串就是有結束符號的字元陣列 char name[10] = { Merry } ; char str [12] ; [0] [1] [2] [3] [4] [] [6] [7] [8] [9] name M e r r y \0 [10] [11] str \0 結束符號字串的結束符號是 \0 ( 空字元 NULL), 就是 8 個 bit 都是 0 的 byte 24

25 字串的長度計算 strlen() [0] [1] [2] [3] [4] [] [6] [7] [8] [9] name M e r r y \0 計數器 len 從這裡開始呼叫 strlen(name) 將會得到計數器 len 停在這裡 int strlen( char S[] ) { int len ; for ( len = 0 ; S[len]!= \0 ; len++) ; return ( len ) ; } 技巧是在迴圈中不斷將計數器 (len) 的值加 1, 直到碰到空字元時就結束 2

26 字串的複製 strcpy() [0] [1] [2] [3] [4] [] [6] [7] [8] [9] name M e r r y \0 計數器 i 從這裡開始計數器 i 停在這裡呼叫 strcpy(s, name) 會將字串 name 的內容複製到字串 S int strcpy( char S1[], char S2[]) { int i ; for ( i = 0; S2[i]!= \0 ; i++) S1[i] = S2[i] ; S1[i] = \0 ; } 技巧是不斷做逐字元拷貝, 直到碰到空字元就停止 26

27 字串的比較 strcmp [0] [1] [2] [3] [4] [] [6] [7] [8] [9] S1 M e r r y \0 S2 M e r r y m \0 計數器 i 從這裡開始呼叫 strcmp(s1,s2) 會將 S1 和 S2 從頭一個字元開始比起, 直到分出大小或兩者比完後完全相等為止 int strcmp( char S1[], char S2[]) { int i; for ( i = 0; S1[i] ==S2[i]; i++) if (S1[i]== \0 && S2[i] == \0 ) return (0); if ( S1[i] < S2[i]) return ( 1) ; else return (1) ; } 27

28 子字串的截取 substr [0] [1] [2] [3] [4] [] [6] [7] [8] [9] S D a t a M i n e \0 呼叫 substr(s1,s,,4) 會從 S 字串的第個字元開始截取 4 個字, 並且放入 S1 字串中 S1 M i n e \0 void substr( char S1[], char S[], int i, int n ) { int len, end, j,k ; len = strlen( S ) ; end = i + n ; if ( (end>len) ( n==0)) end = len ; for ( j = i, k=0 ; j < end ; j++, k++) S1[k]= S [j]; S1[k] = \0 ; } 28

jQuery實戰手冊

jQuery實戰手冊 3-4 多維陣列的觀念當陣列的維度是二維以上時, 就稱為多維陣列而其中最常見是三維陣列, 其圖形為三度空間的立體圖形, 並且我們可以將三維陣列視為多個二維陣列的組合 Dim 陣列名稱 (L,M,N) As 資料型態 L 代表二維陣列個數 M 代表列數 N 代表行數 Dim Score (2,3,4) As Integer ' 二維陣列的個數 : 0~2 共有 3 個二維陣列 ' 列註標表示範圍