Chapter 6 - 陣列 Arrays 目標： 介紹陣列的資料結構 了解如何使用陣列進行儲存、排序和搜尋數值序列及表格 了解如何宣告陣列、設定陣列初值和參照陣列的個別元素 能夠將陣列傳給函式 了解基本排序的技術 能夠宣告且操作多維陣列

Chapter 6 - 陣列 Arrays 本章綱要 6.1 簡介 6.2 陣列 6.3 陣列的宣告 6.4 陣列的使用範例 6.1 簡介 6.2 陣列 6.3 陣列的宣告 6.4 陣列的使用範例 6.5 將陣列傳遞給函式 6.6 陣列的排序 6.7 範例研究：使用陣列計算平均數、中數和眾數 6.8 搜尋陣列：線性搜尋和二元搜尋 6.9 多維陣列

6.1 簡介 陣列 Arrays 相同型別的相關資料組成的結構 靜態資料：程式執行過程中，其大小不會改變 動態資料結構(chapter12)

6.2 陣列 Arrays 陣列開頭的元素是 第 0 個元素 陣列 Array 由連續的記憶體位置組成 有相同的型態與名稱 要參照(存取)陣列的某個元素時，需要寫明 陣列的名稱 (第幾個)位置 格式: arrayname[ position number ] 陣列的第一個元素是在位置 0 n 個元素的陣列 c: c[ 0 ], c[ 1 ]…c[ n - 1 ] 陣列每個元素的使用與正常的變數類似 c[ 0 ] = 3; printf( "%d", c[ 0 ]+ c[ 1 ]+ c[ 2 ] ); 可以對陣列的元素作正常的運算，若 x = 3, c[ x – 2 ] += 5; 陣列開頭的元素是 第 0 個元素

6.2 陣列 Arrays 陣列的名稱(注意：此陣列的所有元素都有相同的名稱, c) 陣列 c 元素的位置 c[6] -45 6 72   6.2 陣列 Arrays c[6] -45 6 72 1543 -89 62 -3 1 6453 78 陣列的名稱(注意：此陣列的所有元素都有相同的名稱, c) c[0] c[1] c[2] c[3] c[11] c[10] c[9] c[8] c[7] c[5] c[4] 陣列 c 元素的位置

優先順序 Operators Associativity ()[] left to right ++ -- static_cast<type>() right to left(prefix) ++ -- + - ! left to right(postfix) * / % left to right + - left to right << >> left to right < <= > >= left to right == != left to right && left to right || left to right ?: left to right = += -= *= /= %= right to left , left to right

6.3 定義陣列 宣告陣列時，需說明 宣告多個相同型態的陣列 陣列名稱 陣列的型態(每個元素的型態、所佔的 bytes 數) 6.3 定義陣列 宣告陣列時，需說明 陣列名稱 陣列的型態(每個元素的型態、所佔的 bytes 數) 陣列的元素個數(陣列元的開始與結束位置) 例如： int c[ 12 ]; float hi[ 3284 ]; 宣告多個相同型態的陣列 與宣告多個相同型態變數的方式相似 int b[ 100 ], x[ 27 ];

6.4 陣列的使用範例 設定初值的敘述 int n[ 5 ] = { 1, 2, 3, 4, 5 }; 6.4 陣列的使用範例 設定初值的敘述 int n[ 5 ] = { 1, 2, 3, 4, 5 }; int n[ 5 ]; // 不會自動作 initialize 若給的初值不夠、最右邊的部份自動設 0 int n[ 5 ] = { 0 }; 將所有元素都設為 0 若給了太多的初值、則造成語法錯誤 若沒有給元素個數、就以初值的個數當作元素個數 int n[] = { 1, 2, 3, 4, 5 }; 陣列 n 就有 5 個元素

Element Value 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0

注意此陣列如何宣告、初值化與使用、輸出時的格式化 Element Value 0 32 1 27 2 64 3 18 4 95 5 14 6 90 7 70 8 60 9 37

Element Value 0 2 1 4 2 6 3 8 4 10 5 12 6 14 7 16 8 18 9 20

將陣列中每個元素的值加起來 Total of array element values is 383

6.4 陣列的使用範例 下一個例子作的問題描述如下： 四十位同學對學生餐廳食物打分數，分數從1分到10分(1分代表最差10分代表最好)，將40位同學打的分數放在一整數陣列中，統計此次問卷的結果。 這是很典型的陣列應用，將某個陣列的值當作另一個陣列的駐標 subscript。 frequency[0] 沒有用到，這是為了程式清楚而犧牲一點點 memory 的效率，其實這樣作的執行速度也會稍微快一點點。

一陣列的值是另一陣列的 subsrcipt。 Rating Frequency 1 2 2 2 3 2 4 2 5 5 6 11 7 5 8 7 9 1 10 3

6.4 陣列的使用範例 如果前面 responses 中有某個元素的值為 13，則 ++frequency[responses[j]] 這行會執行到 ++frequency[13]的 statement，但是在宣告時 frequency 只有 11 個元素，所以會有一些問題。 C 不檢查所存取的位置是否超過該陣列所宣告的範圍。 因此若您執行 ++frequency[13] 仍然是合法的，但是會將 frequency 名稱開頭往後第13個元素的內容增加1. 因為 C 沒有作陣列的邊界檢查，所以我們在取存陣列元素時有沒有超過範圍必須自己負責。

6.4 陣列的使用範例 常見的程式設計錯誤 6.6 存取超出陣列範圍的元素是邏輯錯誤、不是語法錯誤 增進效能的小技巧 6.2 程式應該確認輸入資料的正確性、以免錯誤的資訊影響程式的計算。

6.4 陣列的使用範例 下面的例子是將陣列中的每個數字當作資料、畫出其直條圖。 再之後的例子，是類似第三章中使用亂數擲骰子6000次，計算 1、2、3、4、5、6 出現的次數, Fig 3.8。此時用陣列來作就快多了。可與第三章中的 Fig 3.8 比較一下。

Element Value Histogram 0 19 ******************* 1 3 *** 2 15 *************** 3 7 ******* 4 11 *********** 5 9 ********* 6 13 ************* 7 5 ***** 8 17 ***************** 9 1 *

字元的陣列 Arrays of characters 所有字串都有一個字串結束字元(空字元 null character) ('\0') 6.4 陣列的使用範例 字串 strings 字元的陣列 Arrays of characters 所有字串都有一個字串結束字元(空字元 null character) ('\0') 例如： char string1[] = “first"; char string1[] = { ‘f', ‘i', ‘r', ‘s', ‘t', '\0’ }; “first”:字串常數 字串的駐標與一般陣列寫法相同 string1[ 0 ] is ‘f' string1[ 3 ] is ‘s' 從鍵盤輸入字串時 char string2[ 10 ]; scanf( "%s", string2 ); 讀入使用者輸入的字串(到空格為止、自動加上空字元) 若輸入太多字元，會超出所宣告的陣列範圍 字串 initialize 的方法 兩種作法結果相同 可個別存取字串的某個元素 輸入字串的方法 輸入到 white space 止

Face Frequency 1 1029 2 951 3 987 4 1033 5 1010 6 990

輸入的字串被「空白」分開，“there” 留在緩衝區裡面 注意如何像陣列一樣存取字串的個別元素 字串輸出時，會輸出到 \0 才停止

Enter a string: Hello there string1 is: Hello string2 is: string literal string1 with spaces between characters is: H e l l o

6.4 陣列的使用範例 下一個例子是討論 static array，與前面所說宣告成 static 的變數一樣，static array 在離開 function 之後仍然存在，第二次再進入該 function 時，其值與第一次離開始相同；且沒有作 initialize 時，會自動將每個元素的值設為 0。

First call to each function: Values on entering staticArrayInit: array1[ 0 ] = 0 array1[ 1 ] = 0 array1[ 2 ] = 0 Values on exiting staticArrayInit: array1[ 0 ] = 5 array1[ 1 ] = 5 array1[ 2 ] = 5 Values on entering automaticArrayInit: array2[ 0 ] = 1 array2[ 1 ] = 2 array2[ 2 ] = 3 Values on exiting automaticArrayInit: array2[ 0 ] = 6 array2[ 1 ] = 7 array2[ 2 ] = 8   Second call to each function: array1[ 0 ] = 10 array1[ 1 ] = 10 array1[ 2 ] = 10

6.5 將陣列傳遞給函式 只寫陣列名稱，不需加上中括號 陣列傳遞方式是 call-by-reference 6.5 將陣列傳遞給函式 只寫陣列名稱，不需加上中括號 要傳遞的陣列 myArray 宣告為 int myArray[ 24 ]; 傳給函式 myFunction, 呼叫函式的方式就像下面 myFunction( myArray, 24 ); 通常陣列大小也會同時傳到函式中 陣列傳遞方式是 call-by-reference 陣列名稱就代表陣列開頭(第零個)元素的位置 因此函式會知道陣列存放的位置 因此函式可以修改陣列原來的記憶體位置內容 將陣列個別元素傳到函式的方式是 call-by-value 將陣列與下標(i.e., myArray[ 3 ]) 同時傳到函式中

6.5 將陣列傳遞給函式 函式原型中可以不寫參數名稱 函式原型 6.5 將陣列傳遞給函式 函式原型 void modifyArray( int b[], int arraySize ); 函式原型中可以不寫參數名稱 int b[] 可寫成 int [] int arraysize 可寫成 int 其實 array 也可以用 call-by-value 的方式傳到函式中，就是將 array 放在 structure 中，但很少用。 array 的元素也可以用 call-by-reference 的方式傳到函式，用下一章的 pointer 方式可以作到。

array = 0012FF78 &array[0] = 0012FF78 &array = 0012FF78

Functions can modify entire arrays Functions can modify entire arrays. Individual array elements are not modified by default.

○下面的例子再次示範將陣列宣告成 const 的用法，一個宣告成 const 的參數不可被改變。 Effects of passing entire array by reference:   The values of the original array are: 0 1 2 3 4 The values of the modified array are: 0 2 4 6 8 Effects of passing array element by value: The value of a[3] is 6 Value in modifyElement is 12 The value of a[ 3 ] is 6 ○下面的例子再次示範將陣列宣告成 const 的用法，一個宣告成 const 的參數不可被改變。 ○因為 array 都是 call-by-reference，被呼叫的函式都可以改變陣列的內容，若希望陣列內容保證不會在被呼叫的函式中改變的話，可以將陣列參數宣告成 const。

改變 const 變數會有 syntax error. Compiling... FIG06_14.C fig06_14.c(24) : error C2166: l-value specifies const object fig06_14.c(25) : error C2166: l-value specifies const object fig06_14.c(26) : error C2166: l-value specifies const object

6.5 將陣列傳遞給函式 用 call-by-reference 的方式傳陣列參數比較有效率，若用 call-by-value 的方式需要花時間、空間複製大量資料。 軟體工程的觀點 6.3 型別修飾字 const 可用在函式定義中的陣列參數，避免函式修改到傳入之陣列的內容，這又是最小開放權限的一個例子，函式若非絕對必要修改陣列內容的話，就不要給它修改的權力。

6.6 陣列的排序 排序資料 Bubble sort (氣泡排序法) 非常重要的應用 6.6 陣列的排序 排序資料 非常重要的應用 任何虛擬組織都需要對某些資料作排序，例如：支票、電話號碼、人名等等。 大量資料必須被排序 排序的方法非常多，這裡先介紹一個最簡單的。 Bubble sort (氣泡排序法) 需要在陣列中執行好幾回 每回都將最大的數字放到最後面 都是拿連續的兩個數字相比較 若前面小於等於後面，則不改變 若前面大於後面，兩資料內容對調（交換） 重複前面的步驟一定要作好排序(最多 n – 1次, n 是資料數)

6.6 陣列的排序 Example: Example: 4, 6 68, 89 45, 89 37, 89 45, 68 37, 68 6.6 陣列的排序 Example: original: 3 4 2 6 7 pass 1: 3 2 4 6 7 pass 2: 2 3 4 6 7 Small elements "bubble" to the top Example: Original: 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 4, 6 68, 89 45, 89 37, 89 pass1: 2, 4, 6, 8, 10, 12, 68, 45, 37, 89 45, 68 37, 68 pass2: 2, 4, 6, 8, 10, 12, 45, 37, 68, 89 37, 45 pass3: 2, 4, 6, 8, 10, 12, 37, 45, 68, 89

Data items in original order 2 6 4 8 10 12 89 68 45 37 Data items in ascending order 2 4 6 8 10 12 37 45 68 89

兩個變數內容要對調時，需要有一個額外的變數才行。 氣泡排序法的想法很簡單，較容易了解、寫程式的速度也比較快，但執行速度比較慢。 氣泡排序法的速度可以再改進(ex6.11)， 第二層迴圈不需要每次都執行 arraySize-1 次，因為 pass1 之後已經保證最大的元素會放到最後一個元素… 當已經排好後，這個版本的程式還是會繼續作。有時候，第一層的迴圈可以不需要作到 arraySize – 1 次，只要有一次 pass 中沒有任兩相鄰的數字對調即可。

6.7 範例研究：使用陣列計算平均數、中數和眾數 6.7 範例研究：使用陣列計算平均數、中數和眾數 Mean(平均) 平均值＝總合/個數 Median(中間數) 將數字作排序後、最中間的元素值 1, 2, 3, 4, 5 (3 is median) Mode(眾數) 出現最多次的數字 1, 1, 1, 2, 3, 3, 4, 5 (1 is mode)

******** Mean The mean is the average value of the data items. The mean is equal to the total of all the data items divided by the number of data items ( 99 ). The mean value for this run is: 681 / 99 = 6.8788   Median The unsorted array of responses is 6 7 8 9 8 7 8 9 8 9 7 8 9 5 9 8 7 8 7 8 6 7 8 9 3 9 8 7 8 7 7 8 9 8 9 8 9 7 8 9 6 7 8 7 8 7 9 8 9 2 7 8 9 8 9 8 9 7 5 3 5 6 7 2 5 3 9 4 6 4 7 8 9 6 8 7 8 9 7 8 7 4 4 2 5 3 8 7 5 6 4 5 6 1 6 5 7 8 7 The sorted array is 1 2 2 2 3 3 3 3 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9

The median is element 49 of the sorted 99 element array. For this run the median is 7 ******** Mode Response Frequency Histogram   1 1 2 2 5 0 5 0 5 1 1 * 2 3 *** 3 4 **** 4 5 ***** 5 8 ******** 6 9 ********* 7 23 *********************** 8 27 *************************** 9 19 ******************* The mode is the most frequent value. For this run the mode is 8 which occurred 27 times.

針對某個關鍵值(key value)來搜尋陣列 Linear search(線性搜尋、速度比較慢) 6.8 搜尋陣列：線性搜尋與二元搜尋 針對某個關鍵值(key value)來搜尋陣列 Linear search(線性搜尋、速度比較慢) 從頭開始，一個一個比較，看哪個元素的值與我們要找的 key 值相同。 通常用在沒有排序，且元素個數較少的陣列。已經排序好的數列可以用線性搜尋嗎？ 下面程式只找出第一個出現的位置。 Of course

Enter integer search key: 36 Found value in element 18 37 Value not found

6.8 搜尋陣列：線性搜尋與二元搜尋 Binary search(二元搜尋) 只能對排序好的陣列作搜尋 6.8 搜尋陣列：線性搜尋與二元搜尋 Binary search(二元搜尋) 只能對排序好的陣列作搜尋 每次都比較最中間(middle)的元素值 若相等表示已經找到了。 若所要找的值比中間值小(key < middle), 只需找前半部。 若所要找的值比中間值大(key > middle), 繼續找後半部。 速度非常快，2n 個元素只需要 n 次比較。 例如：30 個元素的陣列最多只要五次比較即可找到。 25 > 30

Binary search 就是每次都從所要找之 list 的中間比較，由比較結果判斷該數字只可能出現在數列 的哪一個部份。 6.8 搜尋陣列：線性搜尋與二元搜尋 令 ai, 1 <= i <= n, 是所要找的非遞減的數列，在這個數列中是否有 x 這個數字，有的話就傳回其下標，不存在的話，就 return -1。(這是 search) Binary search 就是每次都從所要找之 list 的中間比較，由比較結果判斷該數字只可能出現在數列 的哪一個部份。 -15, -6, 0, 7, 9, 23, 54, 82, 101, 112, 125, 131, 142, 151 找 151 找 -14 找 110

Enter a number between 0 and 28: 25   Subscripts: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ------------------------------------------------------------ 0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28 16 18 20 22* 24 26 28 24 26* 28 24* 25 not found Enter a number between 0 and 28: 8 0 2 4 6* 8 10 12 8 10* 12 8* 8 found in array element 4

Enter a number between 0 and 28: 6   Subscripts: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ------------------------------------------------------------ 0 2 4 6 8 10 12 14* 16 18 20 22 24 26 28 0 2 4 6* 8 10 12 6 found in array element 3

6.9 多維陣列 Multiple subscripts多維陣列 – 類似表格(有列與行) 初值化 int a[3][4]; 6.9 多維陣列 Multiple subscripts多維陣列 – 類似表格(有列與行) 就像矩陣：存取時要指明第幾列、與第幾行 初值化 int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } }; 一列一列地給初值 int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } }; int a[3][4]; 第零列 第一列 第二列 第零行 第一行 第二行 第三行 a[ 0 ][ 0 ] a[ 1 ][ 0 ] a[ 2 ][ 0 ] a[ 0 ][ 1 ] a[ 1 ][ 1 ] a[ 2 ][ 1 ] a[ 0 ][ 2 ] a[ 1 ][ 2 ] a[ 2 ][ 2 ] a[ 0 ][ 3 ] a[ 1 ][ 3 ] a[ 2 ][ 3 ] 行下標   陣列名稱 列下標 1 2 3 4 1 0 3 4

6.9 多維陣列 存取方式 前面的寫法將輸出 0 不能將下標寫在一起再用逗點隔開，下面的寫法是錯的。 6.9 多維陣列 存取方式 int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } }; printf( "%d", b[ 0 ][ 1 ]); 前面的寫法將輸出 0 不能將下標寫在一起再用逗點隔開，下面的寫法是錯的。 cout << b( 0, 1 ); 如此寫 C++ 編譯器會以為要作函式呼叫。 用 b[0, 1] 也是語法錯誤。

注意三個 initialization的結果

array2 的結果可看出 C 是 用row major 的方式儲存陣列 Values in array1 by row are: 1 2 3 4 5 6 Values in array2 by row are: 4 5 0 Values in array3 by row are: 1 2 0 4 0 0 array2 的結果可看出 C 是 用row major 的方式儲存陣列

傳一個二維陣列的元素進去

這裡當作一個一維陣列來處理

The array is: [0] [1] [2] [3] studentGrades[0] 77 68 86 73 studentGrades[1] 96 87 89 78 studentGrades[2] 70 90 86 81   Lowest grade: 68 Highest grade: 96 The average grade for student 0 is 76.00 The average grade for student 1 is 87.50 The average grade for student 2 is 81.75

多維陣列存在記憶體中仍必須是一維的存法，row major 的排列表示第一列的資料存在最前面、再存第二列、第三列…；若是 column major 則表示先存第一行、再第二行、第三行…。高於二維的陣列也用相同原則。C++ 是用 row major 的方式。能夠傳一列資料進函式，無法只傳某一行資料進函式。 二維陣列的元素是一維陣列、三維陣列的元素是二維陣列、…，n 維陣列的元素是 n-1 維陣列。C++ 的 compiler 至少提供 12 維的陣列。