Chapter 6 - 陣列 Arrays 目標： 介紹陣列的資料結構 了解如何使用陣列進行儲存、排序和搜尋數值序列及表格

Presentation on theme: "Chapter 6 - 陣列 Arrays 目標： 介紹陣列的資料結構 了解如何使用陣列進行儲存、排序和搜尋數值序列及表格"— Presentation transcript:

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

2 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 多維陣列

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

4 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 個元素

5 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 元素的位置

6 優先順序 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

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

8 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 個元素

9 Element Value

10 注意此陣列如何宣告、初值化與使用、輸出時的格式化
Element Value

11 Element Value

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

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

14

15 一陣列的值是另一陣列的 subsrcipt。
Rating Frequency

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

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

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

19

20 Element Value Histogram
******************* *** *************** ******* *********** ********* ************* ***** ***************** *

21 字元的陣列 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 止

22

23 Face Frequency

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

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

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

27

28

29

30 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

31 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 ]) 同時傳到函式中

32 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 方式可以作到。

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

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

35

36

37 ○下面的例子再次示範將陣列宣告成 const 的用法，一個宣告成 const 的參數不可被改變。
Effects of passing entire array by reference: The values of the original array are: The values of the modified array are: 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。

38

39 改變 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

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

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

42 6.6 陣列的排序 Example: Example: 4, 6 68, 89 45, 89 37, 89 45, 68 37, 68
6.6 陣列的排序 Example: original: pass 1: pass 2: 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

43

44

45 Data items in original order
Data items in ascending order

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

47 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)

48

49

50

51

52

53

54

55

56 ******** 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 = Median The unsorted array of responses is The sorted array is

57 The median is element 49 of
the sorted 99 element array. For this run the median is 7 ******** Mode Response Frequency Histogram * *** **** ***** ******** ********* *********************** *************************** ******************* The mode is the most frequent value. For this run the mode is 8 which occurred 27 times.

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

59

60

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

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

63 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

64

65

66

67

68

69 Enter a number between 0 and 28: 25
Subscripts: * * 24 26* 28 24* 25 not found Enter a number between 0 and 28: 8 * 8 10* 12 8* 8 found in array element 4

70 Enter a number between 0 and 28: 6
Subscripts: * * 6 found in array element 3

71 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

72 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] 也是語法錯誤。

73 注意三個 initialization的結果

74 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 的方式儲存陣列

75

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

77

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

79

80 The array is: [0] [1] [2] [3] studentGrades[0] studentGrades[1] studentGrades[2] 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

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