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

Chapter 4 - 陣列 Arrays 本章綱要 4.1 簡介 4.2 陣列 4.3 陣列的宣告 4.4 陣列的使用範例 4.1 簡介 4.2 陣列 4.3 陣列的宣告 4.4 陣列的使用範例 4.5 將陣列傳遞給函式 4.6 陣列的排序 4.7 範例研究：使用陣列計算平均數、中數和眾數 4.8 搜尋陣列：線性搜尋和二元搜尋 4.9 多維陣列 4.10 「可選讀的範例研究」物件的探索：辨識類別的運算

第5章會講到 pointer，這裡講的 array 與 pointer 有些相似的地方。 4.1 簡介 陣列 Arrays 相同型別的相關資料組成的結構 靜態資料：程式執行過程中，其大小不會改變 陣列型態 C-like, 以指標為基礎的陣列 C++, 將陣列當作物件來處理 第5章會講到 pointer，這裡講的 array 與 pointer 有些相似的地方。 第6章講到 structure and class，這是相關資料的集合，但這些資料間可以有不同的資料型態。

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

4.2 陣列 Arrays 陣列的名稱(注意：此陣列的所有元素都有相同的名稱, c) 陣列 c 元素的位置 c[6] -45 6 72   4.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

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

4.4 陣列的使用範例 設定初值的敘述 int n[ 5 ] = { 1, 2, 3, 4, 5 }; 4.4 陣列的使用範例 設定初值的敘述 int n[ 5 ] = { 1, 2, 3, 4, 5 }; 若給的初值不夠、最右邊的部份自動設 0 若給了太多的初值、則造成語法錯誤 int n[ 5 ] = { 0 }; 將所有元素都設為 0 int n[ 5 ]; // 不會自動作 initialize 若沒有給元素個數、就以初值的個數當作元素個數 int n[] = { 1, 2, 3, 4, 5 }; 陣列 n 就有 5 個元素 執行上的小技巧 4.1 利用初值設定方式給陣列初值是在編譯階段作的，因此其執行速度會比用 assignment 的方式給初值還要快，因為 assignment 是在 run-time 時作的。

17 for ( int i = 0; i < 10; i++ ) 18 n[ i ] = 0; 1 // Fig. 4.3: fig04_03.cpp 14 int n[ 10 ]; 17 for ( int i = 0; i < 10; i++ ) 18 n[ i ] = 0; 20 cout << "Element" << setw( 13 ) << "Value" << endl; 23 for ( int j = 0; j < 10; j++ ) 24 cout << setw( 7 ) << j << setw( 13 ) << n[ j ] << endl; Element Value 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 n[6] n[0] n[1] n[2] n[3] n[9] n[8] n[7] n[5] n[4]

1. Initialize array using a declaration 1 // Fig. 4.4: fig04_04.cpp 2 // 陣列宣告時、作初值化 3 #include <iostream> 4 5 using std::cout; 6 using std::endl; 7 8 #include <iomanip> 9 10 using std::setw; 11 12 int main() 13 { 14 int n[ 10 ] = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37 }; 15 16 cout << "Element" << setw( 13 ) << "Value" << endl; 17 18 for ( int i = 0; i < 10; i++ ) 19 cout << setw( 7 ) << i << setw( 13 ) << n[ i ] << endl; 20 21 return 0; 22 } 1. Initialize array using a declaration 2. Define loop 3. Print out each array element Program Output 注意此陣列如何宣告、初值化與使用、輸出時的格式化 32 27 64 18 95 14 90 70 60 37 n[6] n[0] n[1] n[2] n[3] n[9] n[8] n[7] n[5] n[4] Element Value 0 32 1 27 2 64 3 18 4 95 5 14 6 90 7 70 8 60 9 37

#include <iostream> using std::cout; using std::cin; //Fig. 4.5: fig04_05.cpp #include <iostream> using std::cout; using std::cin; using std::endl; #include <iomanip> using std::setw; int main() { const int arraySize = 10; int j, s[arraySize]; for(j = 0;j < arraySize;j++) s[j] = 2 + 2 * j; cout << “Element” << setw(13) << “Value” << endl; cout << setw(7) << j << setw(13) << s[j] << endl; return 0; } s[6] 2 4 6 8 10 12 14 16 18 20 s[0] s[1] s[2] s[3] s[9] s[8] s[7] s[5] s[4] 可以用 const int 變數來宣告陣列元素個數 Element Value 0 2 1 4 2 6 3 8 4 10 5 12 6 14 7 16 8 18 9 20

可以將存陣列元素個數的變數用 const 來宣告，免得該變數的值被改變，因為陣列元素個數不會改變。 1 // Fig. 4.7: fig04_07.cpp 2 // A const object must be initialized 3 4 int main() 5 { 6 const int x; // Error: x must be initialized 7 8 x = 7; // Error: cannot modify a const variable 9 10 return 0; 11 } 1. Initialize const variable 2. Attempt to modify variable   Program Output 注意 const變數必須作初值化、因為其值在宣告後不能再改變 Fig04_07.cpp: Error E2304 Fig04_07.cpp 6: Constant variable 'x' must be initialized in function main() Error E2024 Fig04_07.cpp 8: Cannot modify a const object in function main() *** 2 errors in Compile *** 可以將存陣列元素個數的變數用 const 來宣告，免得該變數的值被改變，因為陣列元素個數不會改變。 const 的變數在宣告時必須作 initialize，之後其值不能再被改變。 可以 constant expression 的地方都可以用 constant variable

在可執行的敘述中，將值指定給常數變數、這是語法錯誤。 只能用常數來宣告陣列的元素個數(包括自動與靜態陣列) 4.4 陣列的使用範例 常見的程式設計錯誤 4.4-4.5 在可執行的敘述中，將值指定給常數變數、這是語法錯誤。 只能用常數來宣告陣列的元素個數(包括自動與靜態陣列) 用 constant variable 可以增加可讀性，也可以比較容易作調整元素個數(scalable)。 軟體工程的觀點 4.1 使用常數變數來定義陣列元素個數，可讓程式更容易調整。

fig04_08.cpp (1 of 1) fig04_08.cpp output (1 of 1) 1 // Fig. 4.8: fig04_08.cpp 2 // Compute the sum of the elements of the array. 3 #include <iostream> 5 using std::cout; 6 using std::endl; 8 int main() 9 { 10 const int arraySize = 10; 12 int a[ arraySize ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 14 int total = 0; 16 17 for ( int i = 0; i < arraySize; i++ ) 18 total += a[ i ]; 20 cout << "Total of array element values is " << total << endl; 22 return 0; 24 } fig04_08.cpp (1 of 1) fig04_08.cpp output (1 of 1) a[6] 1 2 3 4 5 6 7 8 9 10 a[0] a[1] a[2] a[3] a[9] a[8] a[7] a[5] a[4] Total of array element values is 55

4.4 陣列的使用範例 常見的程式設計錯誤 4.6 存取超出陣列範圍的元素是邏輯錯誤、不是語法錯誤 測試與除錯的小技巧 4.1-4.3 4.4 陣列的使用範例 常見的程式設計錯誤 4.6 存取超出陣列範圍的元素是邏輯錯誤、不是語法錯誤 測試與除錯的小技巧 4.1-4.3 將陣列放在迴圈中執行時，陣列的駐標絕不可小於 0、也必須小於元素個數，以確保其執行之正確性。 程式應該確認輸入資料的正確性、以免錯誤的資訊影響程式的計算。 第六章介紹類別時，我們會發展一個「智慧型陣列」，能自動檢查所存取的元素是否超出範圍，如此可減少錯誤。 可攜性的小技巧 4.1 存取超出陣列範圍的元素所引起的嚴重性，要視系統而定，通常會更改到其他變數的內容。

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

17 cout << "Element" << setw( 13 ) << "Value" 1 // Fig. 4.9: fig04_09.cpp 14 const int arraySize = 10; 15 int n[ arraySize ] = { 19, 3, 15, 7, 11, 9, 13, 5, 17, 1 }; 17 cout << "Element" << setw( 13 ) << "Value" 18 << setw( 17 ) << "Histogram" << endl; 21 for ( int i = 0; i < arraySize; i++ ) { 22 cout << setw( 7 ) << i << setw( 13 ) 23 << n[ i ] << setw( 9 ); 25 for ( int j = 0; j < n[ i ]; j++ ) 26 cout << '*'; 28 cout << endl; 30 } 19 3 15 7 11 9 13 5 17 1 n[6] n[0] n[1] n[2] n[3] n[9] n[8] n[7] n[5] n[4] fig04_09.cpp (1 of 2) Element Value Histogram 0 19 ******************* 1 3 *** 2 15 *************** 3 7 ******* 4 11 *********** 5 9 ********* 6 13 ************* 7 5 ***** 8 17 ***************** 9 1 *

18 int frequency[ arraySize ] = { 0 }; 20 srand( time( 0 ) ); 22 1 // Fig. 4.10: fig04_10.cpp 17 const int arraySize = 7; 18 int frequency[ arraySize ] = { 0 }; 20 srand( time( 0 ) ); 22 23 for ( int roll = 1; roll <= 6000; roll++ ) 24 ++frequency[ 1 + rand() % 6 ]; 26 27 cout << "Face" << setw( 13 ) << "Frequency" << endl; 28 30 for ( int face = 1; face < arraySize; face++ ) 31 cout << setw( 4 ) << face 32 << setw( 13 ) << frequency[ face ] << endl; fig04_10.cpp (1 of 2) Face Frequency 1 1003 2 1004 3 999 4 980 5 1013 6 1001

4.4 陣列的使用範例 字元的陣列 Arrays of characters 4.4 陣列的使用範例 字串 initialize 的方法 兩種作法結果相同 字串 strings 字元的陣列 Arrays of characters 所有字串都有一個字串結束字元(空字元 null character) ('\0') 例如： char string1[] = "hello"; char string1[] = { 'h', 'e', 'l', 'l', 'o', '\0’ }; 字串的駐標與一般陣列寫法相同 string1[ 0 ] is 'h' string1[ 2 ] is 'l' 從鍵盤輸入字串時 char string2[ 10 ]; cin >> string2; 讀入使用者輸入的字串(到空格為止、自動加上空字元) 若輸入太多字元，會超出所宣告的陣列範圍 ’h’ ’e’ ’l’ ’\0’ string1 ’o’ 可個別存取字串的某個元素 輸入字串的方法 輸入到 white space 止

字串輸出時，會輸出到 \0 才停止 輸入的字串被「空白」分開，“there” 留在緩衝區裡面 1. Initialize strings 1 // Fig. 4_12: fig04_12.cpp 2 // Treating character arrays as strings 3 #include <iostream> 4 5 using std::cout; 6 using std::cin; 7 using std::endl; 8 9 int main() 10 { 11 char string1[ 20 ], string2[] = "string literal"; 12 13 cout << "Enter a string: "; 14 cin >> string1; 15 cout << "string1 is: " << string1 16 << "\nstring2 is: " << string2 17 << "\nstring1 with spaces between characters is:\n"; 18 19 for ( int i = 0; string1[ i ] != '\0'; i++ ) 20 cout << string1[ i ] << ' '; 21 cout << endl; 22 cin >> string1; // reads "there" 23 cout << "\nstring1 is: " << string1 << endl; 24 25 cout << endl; 26 return 0; 27 } 輸入的字串被「空白」分開，“there” 留在緩衝區裡面 1. Initialize strings 2. Print strings 2.1 Define loop 2.2 Print characters individually 2.3 Input string 3. Print string Program Output 注意如何像陣列一樣存取字串的個別元素 字串輸出時，會輸出到 \0 才停止 Enter a string: Hello there string1 is: Hello string2 is: string literal string1 with spaces between characters is: H e l l o string1 is: there

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

static array, 自動 initialize 為 0 //Fig. 4.13: fig04_13.cpp static array 的例子 #include <iostream> using std::cout; using std::endl; void staticArrayInit(void); void automaticArrayInit(void); int main() { cout << "First call to each function:” << endl; staticArrayInit(); automaticArrayInit(); cout << “\n\nSecond call to each function:” << endl;; cout << endl; return 0; } void staticArrayInit(void) { static int array1[3]; int i; cout << "\nValues on entering staticArrayInit:\n"; for(i = 0;i < 3;i++) cout << “array1[“ << i <<] = “ << array1[i] << “ “; cout << "\nValues on exiting staticArrayInit:\n"; cout << “array1[“ << i << “] = “ << array1[i]+=5 << “ “; static array, 自動 initialize 為 0

void automaticArrayInit(void) { int array2[3] = {1, 2, 3}; int i; cout << “\n\nValues on entering automaticArrayInit:\n”; for(i = 0;i < 3;i++) cout << “array2[“ << i << “] = “ << array2[i] << “ “; cout << “\nValues on exiting automaticArrayInit:\n”; cout << “array2[“ << i << “] = “ << array2[i]+=5 << “ “; } 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: array1[0] = 1 array1[1] = 2 array1[2] = 3 Values on exiting automaticArrayInit: array1[0] = 6 array1[1] = 7 array1[2] = 8 Second call to each function: array1[0] = 10 array1[1] = 10 array1[2] = 10

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

4.5 將陣列傳遞給函式 函式原型中可以不寫參數名稱 函式原型 4.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 這個 class，會將 array 的 size 一起放在 class 中，這樣將 array 傳到函式時，就不需要另外傳陣列的大小了。

1. Define function to take in arrays 1 // Fig. 4.14: fig04_14.cpp 2 // Passing arrays and individual array elements to functions 3 #include <iostream> 4 5 using std::cout; 6 using std::endl; 7 8 #include <iomanip> 9 10 using std::setw; 11 12 void modifyArray( int [], int ); // appears strange 13 void modifyElement( int ); 14 15 int main() 16 { 17 const int arraySize = 5; 18 int i, a[ arraySize ] = { 0, 1, 2, 3, 4 }; 19 20 cout << "Effects of passing entire array call-by-reference:" 21 << "\n\nThe values of the original array are:\n"; 22 23 for ( i = 0; i < arraySize; i++ ) 24 cout << setw( 3 ) << a[ i ]; 25 26 cout << endl; 27 28 // array a passed call-by-reference 29 modifyArray( a, arraySize ); 30 31 cout << "The values of the modified array are:\n"; 1. Define function to take in arrays 1.1 Initialize arrays 2. Modify the array (call by reference) Functions can modify entire arrays. Individual array elements are not modified by default. No parameter names in function prototype. 1 2 3 4 a[0] a[1] a[2] a[3] a[4] The values of the original array are: 0 1 2 3 4 The values of the modified array are: 0 2 4 6 8

2.1 Modify an element (call by value) 32 33 for ( i = 0; i < arraySize; i++ ) 34 cout << setw( 3 ) << a[ i ]; 35 36 cout << "\n\n\n" 37 << "Effects of passing array element call-by-value:" 38 << "\n\nThe value of a[3] is " << a[ 3 ] << '\n'; 39 40 modifyElement( a[ 3 ] ); 41 42 cout << "The value of a[3] is " << a[ 3 ] << endl; 43 44 return 0; 45 } 46 47 // In function modifyArray, "b" points to the original 48 // array "a" in memory. 49 void modifyArray( int b[], int sizeOfArray ) 50 { 51 for ( int j = 0; j < sizeOfArray; j++ ) 52 b[ j ] *= 2; 53 } 54 55 // In function modifyElement, "e" is a local copy of 56 // array element a[ 3 ] passed from main. 57 void modifyElement( int e ) 58 { 59 cout << "Value in modifyElement is " 60 << ( e *= 2 ) << endl; 61 } 2.1 Modify an element (call by value) 3. Print changes. 3.1 Function Definitions 2 4 6 8 a[0] a[1] a[2] a[3] a[4] 1 2 3 4 a[0] a[1] a[2] a[3] a[4] Effects of passing array element call-by-value:   The value of a[3] is 6 Value in modifyElement is 12 b Parameter names required in function definition 6 e 12

○下面的例子再次示範將陣列宣告成 const 的用法，一個宣告成 const 的參數不可被改變。 Effects of passing entire array call-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 call-by-value: The value of a[3] is 6 Value in modifyElement is 12 Program Output ○下面的例子再次示範將陣列宣告成 const 的用法，一個宣告成 const 的參數不可被改變。 ○因為 array 都是 call-by-reference，被呼叫的函式都可以改變陣列的內容，若希望陣列內容保證不會在被呼叫的函式中改變的話，可以將陣列參數宣告成 const。

//Fig. 4.15: fig04_15.cpp const 的例子 #include <iostream> using std::cout; using std::endl; void tryToModifyArray(const int []); int main() { int a[] = {10, 20, 30}; tryToModifyArray(a); cout << a[0] << ‘ ‘ << a[1] << ‘ ‘ << a[2] << ‘\n’; return 0; } void tryToModifyArray(const int b[]) { b[0] /= 2; b[1] /= 2; b[2] /= 2; 改變 const 變數會有 syntax error. d:\cpphtp4_examples\ch04\Fig04_15.cpp(26) : error C2166: l-value specifies const object d:\cpphtp4_examples\ch04\Fig04_15.cpp(27) : error C2166: l-value specifies const object d:\cpphtp4_examples\ch04\Fig04_15.cpp(28) : error C2166: l-value specifies const object

4.5 將陣列傳遞給函式 用 call-by-reference 的方式傳陣列參數比較有效率，若用 call-by-value 的方式需要花時間、空間複製大量資料。 常見的程式設計錯誤 4.10 忘記陣列是用 call-by-reference 方式來傳遞，而修改陣列內容可能引起邏輯錯誤。 良好的程式設計習慣 4.3 某些程式設計者會將參數名稱寫在函式原型裡面，如此可讓程式更加清楚，編譯器會忽略這些名稱。 軟體工程的觀點 4.3 型別修飾字 const 可用在函式定義中的陣列參數，避免函式修改到傳入之陣列的內容，這又是最小開放權限的一個例子，函式若非絕對必要修改陣列內容的話，就不要給它修改的權力。

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

4.6 陣列的排序 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

//Fig. 4.16: fig04_16.cpp bubble sort 遞增排列 #include <iostream> using std::cout; using std::endl; #include <iomanip> using std::setw; int main() { const int arraySize = 10; int a[arraySize] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37} int i, hold; cout << “Data items in original order\n”; for(i = 0;i < arraySize;i++) cout << setw(4) << a[i]; for(int pass = 0;pass < arraySize - 1;pass++) for(i = 0;i < arraySize - 1;i++) if(a[i] > a[i+1]) { hold = a[i]; a[i] = a[i+1]; a[i+1] = hold; } cout << “\nData items in ascending order\n”; cout << endl; return 0;

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

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

2. Call functions mean, median, and mode   1 // Fig. 4.17: fig04_17.cpp 2 // This program introduces the topic of survey data analysis. 3 // It computes the mean, median, and mode of the data. 4 #include <iostream> 5 6 using std::cout; 7 using std::endl; 8 using std::ios; 9 10 #include <iomanip> 11 12 using std::setw; 13 using std::setiosflags; 14 using std::setprecision; 15 16 void mean( const int [], int ); 17 void median( int [], int ); 18 void mode( int [], int [], int ); 19 void bubbleSort( int[], int ); 20 void printArray( const int[], int ); 21 22 int main() 23 { 24 const int responseSize = 99; 25 int frequency[ 10 ] = { 0 }, 26 response[ responseSize ] = 27 { 6, 7, 8, 9, 8, 7, 8, 9, 8, 9, 28 7, 8, 9, 5, 9, 8, 7, 8, 7, 8, 29 6, 7, 8, 9, 3, 9, 8, 7, 8, 7, 30 7, 8, 9, 8, 9, 8, 9, 7, 8, 9, 31 6, 7, 8, 7, 8, 7, 9, 8, 9, 2, 32 7, 8, 9, 8, 9, 8, 9, 7, 5, 3, 33 5, 6, 7, 2, 5, 3, 9, 4, 6, 4, 1. Function prototypes 1.1 Initialize array 2. Call functions mean, median, and mode

3. Define function mean 3.1 Define function median 34 7, 8, 9, 6, 8, 7, 8, 9, 7, 8, 35 7, 4, 4, 2, 5, 3, 8, 7, 5, 6, 36 4, 5, 6, 1, 6, 5, 7, 8, 7 }; 37 38 mean( response, responseSize ); 39 median( response, responseSize ); 40 mode( frequency, response, responseSize ); 41 42 return 0; 43 } 44 45 void mean( const int answer[], int arraySize ) 46 { 47 int total = 0; 48 49 cout << "********\n Mean\n********\n"; 50 51 for ( int j = 0; j < arraySize; j++ ) 52 total += answer[ j ]; 53 54 cout << "The mean is the average value of the data\n" 55 << "items. The mean is equal to the total of\n" 56 << "all the data items divided by the number\n" 57 << "of data items (" << arraySize 58 << "). The mean value for\nthis run is: " 59 << total << " / " << arraySize << " = " 60 << setiosflags( ios::fixed | ios::showpoint ) 61 << setprecision( 4 ) 62 << static_cast< double >( total ) / arraySize << "\n\n"; 63 } 64 65 void median( int answer[], int size ) 66 { 67 cout << "\n********\n Median\n********\n" 3. Define function mean 3.1 Define function median

3.1 Define function median 3.1.1 Sort Array 3.1.2 Print middle element 68 << "The unsorted array of responses is"; 69 70 printArray( answer, size ); 71 bubbleSort( answer, size ); 72 cout << "\n\nThe sorted array is"; 73 printArray( answer, size ); 74 cout << "\n\nThe median is element " << size / 2 75 << " of\nthe sorted " << size 76 << " element array.\nFor this run the median is " 77 << answer[ size / 2 ] << "\n\n"; 78 } 79 80 void mode( int freq[], int answer[], int size ) 81 { 82 int rating, largest = 0, modeValue = 0; 83 84 cout << "\n********\n Mode\n********\n"; 85 86 for ( rating = 1; rating <= 9; rating++ ) 87 freq[ rating ] = 0; 88 89 for ( int j = 0; j < size; j++ ) 90 ++freq[ answer[ j ] ]; 91 92 cout << "Response"<< setw( 11 ) << "Frequency" 93 << setw( 19 ) << "Histogram\n\n" << setw( 55 ) 94 << "1 1 2 2\n" << setw( 56 ) 95 << "5 0 5 0 5\n\n"; 3.1 Define function median 3.1.1 Sort Array 3.1.2 Print middle element 3.2 Define function mode 3.2.1 Increase frequency[] depending on response[] Notice how the subscript in frequency[] is the value of an element in response[] (answer[]).

Print stars depending on value of frequency[] 96 97 for ( rating = 1; rating <= 9; rating++ ) { 98 cout << setw( 8 ) << rating << setw( 11 ) 99 << freq[ rating ] << " "; 100 101 if ( freq[ rating ] > largest ) { 102 largest = freq[ rating ]; 103 modeValue = rating; 104 } 105 106 for ( int h = 1; h <= freq[ rating ]; h++ ) 107 cout << '*'; 108 109 cout << '\n'; 110 } 111 112 cout << "The mode is the most frequent value.\n" 113 << "For this run the mode is " << modeValue 114 << " which occurred " << largest << " times." << endl; 115 } 116 117 void bubbleSort( int a[], int size ) 118 { 119 int hold; 120 3.3 Define bubbleSort Print stars depending on value of frequency[]

3.3 Define bubbleSort 3.3 Define printArray 121 for ( int pass = 1; pass < size; pass++ ) 122 123 for ( int j = 0; j < size - 1; j++ ) 124 125 if ( a[ j ] > a[ j + 1 ] ) { 126 hold = a[ j ]; 127 a[ j ] = a[ j + 1 ]; 128 a[ j + 1 ] = hold; 129 } 130 } 131 132 void printArray( const int a[], int size ) 133 { 134 for ( int j = 0; j < size; j++ ) { 135 136 if ( j % 20 == 0 ) 137 cout << endl; 138 139 cout << setw( 2 ) << a[ j ]; 140 } 141 } 3.3 Define bubbleSort 3.3 Define printArray Bubble sort: if elements out of order, swap them.

4. Program Output ******** 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 4. Program Output

Program Output ******** Mode Response Frequency Histogram 1 1 2 2   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. Program Output

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

//Fig. 4.19: fig04_19.cpp Linear search #include <iostream> using std::cout; using std::endl; using std::cin; int linearSearch(const int [], int, int); int main() { const int arraySize = 100; int a[arraySize], searchKey, element; for(int x = 0; x < arraySize; x++) a[x] = 2 * x; cout << “Enter integer search key:” << endl; cin >> searchKey; element = linearSearch(a, searchKey, arraySize); if(element != -1) cout << “Found value in element “ << element << endl; else cout << “Value not found” << endl; return 0; } int linearSearch(const int array[],int key,int sizeOfArray) { for(int n = 0;n < sizeOfArray;n++) if(array[n] == key) return n; return -1;

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

Binary search 就是每次都從所要找之 list 的中間比較，由比較結果判斷該數字只可能出現在數列 的哪一個部份。 4.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

//Fig. 4.20: fig04_20.cpp Binary search #include <iostream> using std::cout; using std::endl; using std::cin; #include <iomanip> using std::setw; int binarySearch(const int [], int, int, int, int); void printHeader(int); void printRow(const int[], int, int, int, int); int main() { const int arraySize = 15; int a[arraySize],key, result; for(int i = 0; i < arraySize; i++) a[i] = 2 * i; cout << “Enter a number between 0 and 28: ”; cin >> key; printHeader(arraySize); result = binarySearch(a, key, 0, arraySize – 1, arraySize); if(result != -1) cout << ‘\n’ << key << “ found in array element “ << result << endl; else cout << ‘\n’ << key << “ not found” << endl; return 0; }

Binary search 的副程式 輸出表頭，只執行一次 int binarySearch(const int b[], int searchKey, int low, int high, int size) { int middle; while(low <= high) { middle = (low + high)/2; printRow(b, low, middle, high, size); if(searchKey == b[middle]) return middle; else if(searchKey < b[middle]) high = middle - 1; else low = middle + 1; } return –1; void printHeader(int size) { int j; cout << “\nSubscripts:\n”; for(j = 0;j < size;j++) cout << setw(3) << j << ‘ ‘; cout << ‘\n’; for(j = 0;j < 4 * size;j++) cout << ‘-’; cout << endl; Binary search 的副程式 輸出表頭，只執行一次

void printRow(const int b[], int low, int mid, int high, int size) { for(int j = 0;j < size;j++) if(j < low || j > high) cout << “ “; else if(j == mid) cout << setw(3) << b[j] << ‘*’; else cout << setw(3) << b[i] << ‘ ‘; cout << endl; } 輸出一列、search 一次輸出一次 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 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 8 10* 12 8* 8 found in array element 4

4.8 搜尋陣列：線性搜尋與二元搜尋 執行上的小技巧 4.6 二元搜尋的執行效率比線性搜尋快很多，但是二元搜尋的數列必須經過排序，排序的速度比搜尋的速度慢很多。如果要作很多次搜尋的話，那先作一次排序就是值得的。

4.9 多維陣列 Multiple subscripts多維陣列 – 類似表格(有列與行) 初值化 int a[3][4]; 4.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

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

注意三個 initialization的結果 //Fig. 4.22: fig04_22.cpp 多維陣列的 initialization #include <iostream.h> void printArray(int [][3]); int main() { int array1[2][3] = {{1,2,3,}, {4,5,6}}, array2[2][3] = {1, 2, 3, 4, 5}, array3[2][3] = {{1, 2}, {4}}; cout << “Values in array1 by row are:” << endl; printArray(array1); cout << “Values in array2 by row are:” << endl; printArray(array2); cout << “Values in array3 by row are:” << endl; printArray(array3); return 0; } void printArray(int a[][3]) { for(int i = 0;i < 2;i++) { for(int j = 0;j < 3;j++) cout << a[i][j] << ‘ ‘; cout << endl; 注意三個 initialization的結果 注意 a[][3] 這個參數的宣告方式必須寫出每列有幾個元素電腦才能找到每個元素的位置在哪裡 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

1.1 Define functions to take double scripted arrays 1 // Fig. 4.23: fig04_23.cpp 2 // Double-subscripted array example 3 #include <iostream> 4 5 using std::cout; 6 using std::endl; 7 using std::ios; 8 9 #include <iomanip> 10 11 using std::setw; 12 using std::setiosflags; 13 using std::setprecision; 14 15 const int students = 3; // number of students 16 const int exams = 4; // number of exams 17 18 int minimum( int [][ exams ], int, int ); 19 int maximum( int [][ exams ], int, int ); 20 double average( int [], int ); 21 void printArray( int [][ exams ], int, int ); 22 23 int main() 24 { 25 int studentGrades[ students ][ exams ] = 26 { { 77, 68, 86, 73 }, 27 { 96, 87, 89, 78 }, 28 { 70, 90, 86, 81 } }; 29 30 cout << "The array is:\n"; 31 printArray( studentGrades, students, exams ); 32 cout << "\n\nLowest grade: " 33 << minimum( studentGrades, students, exams ) 1. Initialize variables 1.1 Define functions to take double scripted arrays 1.2 Initialize studentgrades[][] 2. Call functions minimum, maximum, and average Each row is a particular student, each column is the grades on the exam.

2. Call functions minimum, maximum, and average 3. Define functions 34 << "\nHighest grade: " 35 << maximum( studentGrades, students, exams ) << '\n'; 36 37 for ( int person = 0; person < students; person++ ) 38 cout << "The average grade for student " << person << " is " 39 << setiosflags( ios::fixed | ios::showpoint ) 40 << setprecision( 2 ) 41 << average( studentGrades[ person ], exams ) << endl; 42 43 return 0; 44 } 45 46 // Find the minimum grade 47 int minimum( int grades[][ exams ], int pupils, int tests ) 48 { 49 int lowGrade = 100; 50 51 for ( int i = 0; i < pupils; i++ ) 52 53 for ( int j = 0; j < tests; j++ ) 54 55 if ( grades[ i ][ j ] < lowGrade ) 56 lowGrade = grades[ i ][ j ]; 57 58 return lowGrade; 59 } 60 61 // Find the maximum grade 62 int maximum( int grades[][ exams ], int pupils, int tests ) 63 { 64 int highGrade = 0; 65 66 for ( int i = 0; i < pupils; i++ ) 2. Call functions minimum, maximum, and average 3. Define functions 傳一個二維陣列的元素進去

這裡當作一個一維陣列來處理 3. Define functions 67 68 for ( int j = 0; j < tests; j++ ) 69 70 if ( grades[ i ][ j ] > highGrade ) 71 highGrade = grades[ i ][ j ]; 72 73 return highGrade; 74 } 75 76 // Determine the average grade for a particular student 77 double average( int setOfGrades[], int tests ) 78 { 79 int total = 0; 80 81 for ( int i = 0; i < tests; i++ ) 82 total += setOfGrades[ i ]; 83 84 return static_cast< double >( total ) / tests; 85 } 86 87 // Print the array 88 void printArray( int grades[][ exams ], int pupils, int tests ) 89 { 90 cout << " [0] [1] [2] [3]"; 91 92 for ( int i = 0; i < pupils; i++ ) { 93 cout << "\nstudentGrades[" << i << "] "; 94 95 for ( int j = 0; j < tests; j++ ) 96 cout << setiosflags( ios::left ) << setw( 5 ) 97 << grades[ i ][ j ]; 98 } 99 } 3. Define functions 這裡當作一個一維陣列來處理

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

4.10 [可選讀的範例研究] 物件的探索：辨識類別的運算 前兩章的最後一節我們討論到電梯的例子，第二章討論所需要的 class、第三章討論每個 class 所需要的 attributes。這一章討論每個 class 所需要的 operations (或 behaviors)。下一章討論 class 彼此之間的 interaction. 類別的操作(operation)就是此類別提供給客戶端(clients)的服務，或者說提供給別人呼叫的功能。 收音機的 operation: 開、關、轉大小聲、轉台等；汽車的 operations: 加速、剎車、轉彎、換擋等等。 物件一般不會自動執行它的操作，而是別的物件送 message 進來、表示需要這個物件作某個操作時才會作。類似呼叫副程式。 我們的例子中的 class 需要有哪些 operations 呢？與這些 class 的動作有關，先看描述這個問題所用到的動詞或動詞片語，可約略了解。

4.10 [可選讀的範例研究] 物件的探索：辨識類別的運算 Elevator moves, arrives at a floor, resets the elevator button, sounds the elevator bell, signals its arrival to a floor, opens its door, closes its door Clock Ticks every second Scheduler Randomly schedules times, creates a person, tells a person to step onto a floor, verifies that a floor is unoccupied, delays creating a person by one second Person Steps onto floor, presses floor button, presses elevator button, enters elevator, exits elevator Floor Resets floor button, turns off light, turns on light FloorButton Summons elevator ElevatorButton Signals elevator to move Door (opening of door)signals person to exit elevator, (opening of door) signals person to enter elevator Bell Light Building

4.10 [可選讀的範例研究] 物件的探索：辨識類別的運算 前面每個 class 可能需要通知別的 class 作一些動作，因此通常是在別的 class 底下會有相對應的 operations。例如：Elevator 要 reset elevator button，因此在 elevatorButton 底下會有一個 resetButton(), 當 elevator 通知要 reset 時就由這個函式來回應。同樣的 person 會按 button，因此在 elevatorButton 與 floorButton 中必須有 pressButton() 來回應。 不需要由別的 class 傳 message 呼叫的動作就不需要成為 operations，例如電梯的移動。

Clock time:int = 0 getTime():int Tick():void Elevator currentFloor:int = 1 direction:enum = up capacity:int = 1 arrivalTime:int moving:bool = false processTime(time:int):void personEnters():void personExits():void summonElevator():void prepareToLeave():void Door open:bool = false openDoor():void closeDoor():void Floor capacity:int = 1 occupied:bool = false elevatorArrived():void isOccupied():bool Bell <none yet> ringBell():void Light on:bool = false turnOff(): void turnOn(): void Scheduler floor1ArrivalTime:int floor2ArrivalTime:int processTime(time:int):void FloorButton pressed:bool = false pressButton():void resetButton():void Building <none yet> runSimulation(): void Person ID:int stepOntoFloor():void exitElevator():void enterElevator():void ElevatorButton pressed:bool = false resetButton():void pressButton():void

4.10 [可選讀的範例研究] 物件的探索：辨識類別的運算 Sequence diagrams：模擬表示圖 :Building :Clock :Scheduler :Elevator tick() {currentTime < totalTime} getTime() time processTime(currentTime:int) processTime(currentTime:int)

building:Building scheduler:Scheduler floor1:Floor floor2:Floor processTime(Time) isOccupied():bool bool [occupied = false] [occupied = true] 《create》 :Person delayArrival(floor1) personArrives() scheduleArrival(floor1) isOccupied():bool bool [occupied = false] [occupied = true] 《create》 :Person personArrives() delayArrival(floor2) scheduleArrival(floor2)