C Arrays

Size: px

Start display at page:

Download "C Arrays"

坪姚
5 years ago
Views:

4 本章將介紹資料結構中的重要主題陣列 (Arrays) 是由相同型別的相關資料項所組成的資料結構在第十章當中, 我們會討論 C 的 struct( 結構 )- 它可能是由不同型別的相關資料項所組成的資料結構陣列和結構都屬於靜態的資料結構, 它們在程式執行期間的大小並不會改變十二章介紹的是動態資料結構, 例如串列佇列堆疊和樹, 它們都可以在程式執行期間改變大小

5 陣列是一群具有相同名稱以及相同型別的記憶體位置若要引用陣列的某個位置或元素, 我們必須指定陣列名稱, 以及此元素在陣列中的位置編號 (position number) 圖 6.1 表示一個稱為 c 的整數陣列這個陣列含有 12 個元素 (elements) 我們可以使用陣列名稱, 並且在後面接著一個放有位置編號的中括號 ([]), 來引用任何一個元素

6 每個陣列中的第一個元素均是第零個元素 (zeroth element) 所以陣列 c 的第一個元素是 c[0], 第二個元素稱是 c[1], 第七個元素稱為 c[6], 用一般化的表示式來說, 陣列 c 當中的第 i 個元素是 c[i - 1]. 陣列名稱如同其它變數一樣, 只能夠使用字母數字和底線, 但是陣列名稱的第一個字母不能夠以數字開頭中括號中的位置編號正式名稱為下標 (subscript) 或索引 (index) 下標必須是整數或是整數運算式

7 如果在程式中使用運算式當作下標, 就會以此運算式運算之後的值當作下標值例如, 假設 a=5, b=6 底下的敘述式 c[ a + b ] += 2; 將會為陣列中的元素 c[11] 加上 2 請注意, 具有下標的陣列名稱是一個左值 (lvalue) - 它可以用於指定運算子的左邊

8 讓我們更進一步地檢視圖 6.1 的陣列此陣列的名稱 (name) 是 c 它的 12 個元素分別是 c[0], c[1], c[2],...,c[11] c[0] 的值 (value) 是 -45,c[1] 的值是 6,c[2] 的值是 0,c[7] 的值是 62,c[11] 的值是 78 若我們想印出陣列 c 前三個元素所含之值的總和, 可以撰寫以下的敘述式 : printf( "%d", c[ 0 ] + c[ 1 ] + c[ 2 ] ); 若想將陣列 c 的第七個元素除以 2, 並將結果設給變數 x, 可以寫成

11 用來圈住陣列下標的中括號事實上被認為是 C 的運算子它們的運算優先順序和函式呼叫運算子 ( 也就是放在函式後面, 用來呼叫函式的括號 ) 相同圖 6.2 列出截至目前為止, 我們所介紹過的運算子的運算優先順序和結合性

13 陣列會佔用記憶體空間你會指定每個陣列所需要的元素型別和元素個數, 電腦會依此來預留適當大小的記憶體空間若要告訴電腦為具有 12 個元素的整數陣列 c 預留空間, 你可以使用以下的定義 : int c[ 12 ];

14 以下的定義 int b[ 100 ], x[ 27 ]; 為整數陣列 b 預留 100 個元素的位置, 以及為整數陣列 x 預留 27 個元素的位置陣列還可以儲存別種資料型別字元字串及他們與陣列之間的相似之處, 將於第八章討論而指標與陣列之間的關係, 則會在第七章中討論

15 圖 6.3 的程式使用了一個 for 敘述式, 將 10 個元素的整數陣列 n 的所有元素的初始值設定為零, 並且以表列的方式印出這個陣列的內容第一個 printf 敘述式 ( 第 16 行 ) 印出兩個欄位的標題, 著由 for 敘述式印出這兩個欄位的內容

18 陣列中的元素也可以在陣列宣告時就指定初始值, 其方式就是在宣告之後加上一個等號和大括號包住的一串初始值 (initializers) 串列圖 6.4 的程式便是在宣告時為陣列設了 10 個初始值 ( 第 9 列 ), 並以表列的方式印出這個陣列的內容

21 如果給定的初始值的個數小於陣列的元素個數, 則剩下的元素將自動指定初始值為零例如, 圖 6.3 中陣列 n 的元素在下列的宣告後也會全部指定初始值為零 : int n[ 10 ] = { 0 }; 這個定義明確為第一個元素指定初始值零, 並且也自動為其餘的 9 個元素指定初始值零, 因為初始值的個數少於陣列的元素個數

22 陣列並不會自動地將初始值設定為零你必須至少將第一個元素的初始值設定為零, 剩下的元素才會自動設定為零這種把陣列初始化為零的方法, 如果應用在 static 陣列時, 會在編譯時期完成 ; 如果應用在自動陣列中, 則會在執行期間完成

24 以下的陣列定義 int n[ 5 ] = { 32, 27, 64, 18, 95, 14 }; 將會造成一個語法錯誤, 因為初始值的數目會比陣列的元素個數還多

26 如果在一個有初始值串列的定義上省略陣列的大小, 則此陣列的元素個數將等於初始值串列上的元素個數例如, int n[] = { 1, 2, 3, 4, 5 }; 將會產生一個具有 5 個元素的陣列

27 圖 6.5 的程式將 10 元素的陣列 s 的元素指定初始值為 2, 4, 6,...,20, 並且以表列的方式印出這個陣列的內容陣列元素的數值會以迴圈計數器乘以 2 再加上 2 而得到

30 本程式使用了 #define 前置處理器命令第 4 行 #define SIZE 10 定義了一個符號常數 (symbolic constant) SIZE, 其值為 10 符號常數是一個識別字, 它會在程式編譯之前, 由 C 的前置處理器將它代換成代換文字 (replacement text)

31 當程式進行前置處理時, 所有出現符號常數的位置都會代換成代換文字 10 利用符號常數來指定陣列的大小, 將可以使程式更具擴充性 (scalable) 我們可以將圖 6.5 #define 命令列中 SIZE 的定義從 10 改為 1000, 以便讓第一個 for 迴圈 ( 第 13 列 ) 為 1000 個元素的陣列填入數值如果沒有使用符號常數 SIZE, 我們必須修改程式的三個位置, 才能夠將程式變成處理 1000 個元素的陣列

33 如果程式當中第 4 行的 #define 前置處理器命令之後加上分號的話, 則程式中所有出現符號常數 SIZE 的位置都會被前置處理器代換成文字 10; 這在編譯時期將會造成語法錯誤, 或在執行時期造成邏輯錯誤

38 圖 6.6 的程式將 12 元素的整數陣列 a 的所有內含值進行加總 for 迴圈本體內的敘述式 ( 第 16 列 ) 為我們做了這件事

40 我們的下一個例子利用陣列來分析整理某項調查中所收集的資料請看以下的問題描述要求 40 位學生對學生自助餐廳的食物打分數, 分數為 1 分到 10 分 (1 代表很差,10 代表非常好 ) 請將這 40 份回應放到一個整數陣列中, 並且整理此項調查的結果這是一種典型的陣列應用 ( 見圖 6.7) 我們希望整理出每一種回應 (1 到 10) 的數量

41 陣列 responses ( 第 17 列 ) 是個含有 40 個元素的陣列, 它會用來存放學生們的回應我們另外使用一個 11 個元素的陣列 frequency ( 第 14 列 ) 來計算每種回應的次數但是我們捨棄第一個元素 ( 亦即 frequency[0]) 不用, 因為用 frequency[1] 來代表反應 1 的次數較合乎邏輯這會允許我們直接使用每個回應當作 frequency 陣列的下標

47 for 迴圈 ( 第 24 列 ) 從 responses 陣列中一次取出一個回應, 然後將 frequency 陣列中的 10 個計數器 (frequency[1] 到 frequency[10]) 中的某一個遞增 1 迴圈中的關鍵敘述式是 ( 第 25 列 ) ++frequency[ responses[ answer ] ]; 此敘述式會根據 response[answer] 的值來遞增適當的 frequency 計數器

48 當 answer 為 0,responses[answer] 為 1 時, ++frequency[responses[answer]]; 將解釋成 ++frequency[ 1 ]; 它會將陣列元素 1 遞增當 answer 為 1,responses[answer] 為 2 時, ++frequency[responses[answer]]; 將解釋成 ++frequency[ 2 ]; 它會將陣列元素 2 遞增

49 當 answer 為 2,responses[answer] 為 6 時, ++frequency[responses[answer]]; 將解釋成 ++frequency[ 6 ]; 會將陣列元素 6 遞增, 依此類推請注意, 不論在這項調查中有多少個回應, 都只需要一個 11 元素的陣列 ( 元素 0 不用 ) 來整理調查的結果但如果資料中含有不合法的數值, 例如 13, 則程式會嚐試為 frequency[13] 加 1 而這已超出陣列的範圍

50 C 並不會進行陣列範圍檢查, 來防止程式存取到一個不存在的元素因此, 執行中的程式可能會超出陣列的界線而不自知所以你必須能夠確保所有的陣列的存取都在陣列的範圍內

54 我們的下一個例子 ( 參閱圖 6.8) 會從陣列讀取數值, 然後將這些資訊以長條圖 (histogram) 印出來 - 先印出每個數字, 然後再根據其大小印出相同數目的星號程式中的巢狀 for 迴圈會負責印出這些長條圖 ( 第 20 列 ) 此外, 我們使用 printf( \n ) 來結束每個長條圖的列印 ( 第 24 列 )

57 投擲一個六面的骰子 6000 次, 來驗證亂數產生器是否真的可以產生亂數現在我們就將該程式改寫成陣列版本, 結果如圖 6.9 所示

60 現在讓我們來討論使用字元陣列來存放字串在此之前, 唯一介紹過的字串處理能力就是以 printf 輸出一個字串而對 C 而言, 字串 ( 如 "hello") 的是一個存放各個字元的陣列字元陣列可以使用字串常數來指定初始值例如, char string1[] = "first"; 會將陣列 string1 的元素初始值設定為字串常數 "first" 中的各個字元

61 上述宣告中陣列 string1 的大小, 將由編譯器根據字串的長度來加以決定字串 first 包含五個字元加上一個稱為空字元 (null character) 的字串終止字元因此, 陣列 string1 實際上含有 6 個元素空字元的字元常數表示法為 '\0' C 的所有字串都會以此字元做為結束用來表示字串的字元陣列, 其宣告的大小應該要能夠放入字串的字元以及結束的空字元字元陣列也可以用初始值串列中的個別字元常數, 來指定初始值

62 以下的宣告和前面的宣告是相同的 char string1[] = { 'f', 'i', 'r', 's', 't', '\0' }; 因為字串實際上是字元所組成的陣列, 所以我們可以使用陣列下標記號來直接存取字串當中各別的字元例如,string1[0] 是字元 'f', 而 string1[3] 則是字元 's' 我們可以用 scanf 及轉換指定詞 %s, 直接從鍵盤輸入一個字串到字元陣列中

63 例如, char string2[ 20 ]; 產生了一個能夠存放 19 個字元加上一個結束空字元的字元陣列敘述式 scanf( "%s", string2 ); 則會從鍵盤讀入一個字串到 string2 當中字元陣列的名稱並沒有像其它變數一樣, 要加上 & 才能夠傳給 scanf & 通常會用來提供 scanf 有關變數在記憶體中的位置, 讓 scanf 能夠將讀入的數值放到該位置

64 我們將在第 6.5 節討論傳遞陣列給函式的問題屆時我們將可以看到, 陣列名稱代表陣列的起始位址, 因此便不需要使用 & scanf 函式將會一直讀入字元, 直到遇上了空白 tab 新行或 end-of-file 指示器為止字串不應該大於 19 個字元, 我們必須留一個位置給結束的空字元假如使用者鍵入了 20 個以上的字元, 你的程式可能會當掉! 因此, 請使用轉換指定詞 %19s, 如此 scanf 就不會將超過陣列末端的字元寫入記憶體

65 使字元陣列能夠放得下由鍵盤所讀入之字串是你的責任 scanf 函式會一直由鍵盤上讀入字元, 直到遇到第一個空白字元為止 - 它不會檢查陣列的大小所以 scanf 可能會將資料寫到陣列的範圍以外

67 一個代表字串的字元陣列, 可以用 printf 和轉換指定詞 %s 來加以輸出上述的陣列 string2 可以用以下的敘述式印出 printf( "%s\n", string2 ); 如同 scanf,printf 也不會檢查字元陣列到底有多大它會一直列印此陣列的字元, 直到遇到結束的空字元為止

68 圖 6.10 的程式示範以字串常數來為字元陣列指定初始值, 讀入一個字串到字元陣列中, 以字串的方式印出一個字元陣列, 以及存取字串中的各別字元等

71 圖 6.10 使用一個 for 敘述式 ( 第 22 列 ) 來走訪 string1 陣列, 並且用轉換指定詞 %c 將每個字元以空白區隔印出 for 敘述式中的條件 string1[i]!= '\0', 在尚未遇到代表字串結束的空字元之前, 將會一直為真

72 static 區域變數在程式執行期間會一直存在, 但只有在此函式的本體內才能夠使用它我們可以將 static 用於一個區域陣列的定義上, 這樣陣列就不會在每次函式呼叫時產生以及指定初始值, 也不會在每次離開這個函式時加以清除這樣子可以減少程式的執行時間, 特別是經常呼叫含有大型陣列函式的程式

74 宣告成 static 的陣列會自動在編譯時期進行初始化假如你沒有明確地為 static 陣列設定初值, 編譯器就會將陣列元素的初始值設定為零圖 6.11 的程式示範含有宣告 static 區域陣列 ( 第 22 列 ) 的 staticarrayinit 函式 ( 第 25 列 ), 以及含有自動區域陣列 ArrayInit ( 第 44 列 ) 的 automaticarrayinit 函式 ( 第 47 列 ) 其中呼叫兩次 staticarrayinit 函式 ( 第 12 和 16 列 ) 此函式中的 static 區域陣列的初始值被編譯器設為零 ( 第 25 列 ) 此陣列會先印出這個陣列的內容, 接著為每個元素加上 5, 然後再印出一次陣列的內容

75 當這個函式第二次呼叫時,static 陣列仍保有上一次呼叫後的數值它也呼叫兩次 automaticarrayinit 函式 ( 第 13 和 17 列 ) 函式中的自動區域陣列的元素的初始值會設定為 1, 2, 3 ( 第 47 行 ) 此陣列會先印出這個陣列的內容, 接著為每個元素加上 5, 然後再印出一次陣列的內容第二次呼叫函式時, 因為此陣列具有自動儲存佔用期間, 所以陣列元素的初始值會指定為 1, 2, 3

81 若我們想傳遞陣列引數給某個函式的話, 只需要指定陣列名稱即可, 不必加任何的中括號例如, 若陣列 hourlytemperatures 的宣告定義為 int hourlytemperatures[ 24 ]; the function call modifyarray( hourlytemperatures, 24 ) 會傳遞陣列 hourlytemperatures 和其大小給函式 modifyarray

82 和內含字串的 char 陣列不同, 其它形式的陣列並沒有特殊的結束字元因為這個原因, 當傳遞一個陣列給函式時, 程式通常也會將陣列的大小一起傳給函式, 使函式能夠正確處理元素的數量 C 會自動以傳參考的方式, 來將陣列傳給函式被呼叫的函式能夠更改位於呼叫者內的原始陣列陣列的名稱實際上是此陣列第一個元素的位址因為我們傳遞了陣列的起始位址, 所以被呼叫函式即可得知儲存這個陣列的位置

83 所以當被呼叫函式在其函式本體內更改陣列的元素時, 它便會更改到陣列的真正元素所在的原始記憶體位置圖 6.12 的程式利用 %p 轉換指定詞 ( 一個用來列印位址的特殊轉換指定詞 ) 印出 array,&array[0] 和 &array, 來驗證陣列名稱確實是此陣列第一個元素所在的位址 %p 轉換指定詞通常會將位址以十六進制數的形式印出來

84 十六進制數 ( 基底為 16) 是由數元 0 到 9, 以及字母 A 到 F ( 相當於十進制的 10-15) 所組成附錄 C 將針對二進制 ( 基底為 2) 八進制 ( 基底為 8) 十進制 ( 基底為 10; 標準整數 ) 和十六進制的整數, 進行介紹和比較這個程式的輸出結果顯示,array 和 &array[0] 的值都是 0012FF78

87 雖然整個陣列會以傳參考呼叫的方式來進行傳遞, 不過各別的陣列元素卻與簡單的變數一樣, 會以傳值呼叫來進行傳遞這種單一而簡單的資料項 ( 例如各別的整數浮點數以及字元 ) 稱為純量 (scalar) 若我們想傳陣列中的某元素給一個函式, 可以用這個元素的下標名稱當做此函式呼叫的引數我們將在第 7 章介紹如何以純量 ( 亦即各別的變數和陣列元素 ) 來模擬傳參考呼叫

89 函式若想經由函式呼叫來接收一個陣列, 則此函式的參數列中必須指明它將希望接收一個陣列例如, 函式 modifyarray ( 本節中較前面的函式呼叫 ) 的標頭可以寫成 void modifyarray( int b[], int size ) 這表示 modifyarray 函式希望以參數 b 接收一個整數陣列, 以及以參數 size 接收此陣列的元素個數在陣列的中括號裡不需要指定陣列的大小

90 如果指定了大小, 則編譯器會檢查它是否大於零, 然後省略它指定一個負的大小會造成編譯錯誤由於陣列會自動模擬成傳參考呼叫來進行傳遞, 因此當被呼叫函式使用陣列名稱 b 時, 實際上會引用呼叫函式的原始陣列 ( 在上述呼叫中是引用陣列 hourlytemperatures) 圖 6.13 的程式示範傳遞整個陣列和傳遞一個陣列元素之間的差異此程式首先會印出整數陣列 a 的 5 個元素 ( 第行 )

91 接著 a 和它的大小會傳遞給函式 modifyarray ( 第 27 列 ), 將 a 的每個元素都乘上 2 ( 第列 ) 然後回到 main 再印出 a 的內容 ( 第行 ) 如同輸出所示,a 的元素確實由 modifyarray 改變了接下來, 程式會印出 a[3] 的數值 ( 第 38 列 ), 並且將 a[3] 傳給函式 modifyelement ( 第 40 列 ) 此函式會為它的引數乘上 2 ( 第 64 列 ), 並印出運算後的新值然而當回到 main 後再印出一次 a[3] 的數值 ( 第 43 列 ), 我們發現它並沒有改變因為各別的陣列元素會以傳值呼叫來進行傳遞

96 在很多種狀況下, 你的程式不可以用來更改陣列中的元素但由於陣列會以模擬的傳參考呼叫來傳遞, 因此你很難控制呼叫函式不去更改陣列的值 C 提供一種特殊的型別修飾詞 const 來避免呼叫函式更改陣列的值當一個陣列參數前面加上 const 修飾詞之後, 陣列的元素在函式的本體當中會成為常數, 所以在函式本體內任何試圖更改陣列之值的動作, 都會造成編譯時期的錯誤這讓你能夠修正程式, 以確保陣列元素不會受到更動

97 圖 6.14 解釋 const 修飾詞的用法函式 trytomodifyarray( 第 20 列 ) 和參數 const int 一起定義, 這項定義指出陣列 b 為常數, 並且不能夠更改輸出的結果是編譯器所產生的錯誤訊息 - 使用不同的系統會產生不同的錯誤結果此函式中試圖修改陣列元素的三個敘述式, 都會造成編譯錯誤 l-value specifies a const object.

100

101 排序 (Sorting) 資料 ( 也就是照特定的順序放置資料, 例如遞增或遞減順序 ) 是電腦最重要的應用之一在本章中, 我們將討論最簡單的排序技術而我們將在第十二章和附錄 F 中, 再介紹一些較複雜但效率較好的排序技術

102

103 圖 6.15 的程式以遞增順序, 為擁有 10 個元素的陣列 a ( 第 10 列 ) 中的所有元素值進行排序我們所使用的技術稱為氣泡排序 (bubble sort 或 sinking sort), 因為較小的數值將會如氣泡浮出水面一樣, 慢慢地上升至陣列的頂點, 而較大的數值則會沉到陣列的尾端這個技巧會對陣列處理數個回合在每一回合當中, 將會比較相鄰的一對元素如果此對元素為遞增順序 ( 或相等 ) 的話, 則將他們維持現狀如果這對元素為遞減順序的話, 便將他們的值對調過來

104

105

106

107 此程式首先比較 a[0] 和 a[1], 然後比較 a[1] 和 a[2], 然後比較 a[2] 和 a[3], 然後一直持續下去, 直到比較完 a[8] 和 a[9] 才結束這一回合注意到雖然有 10 個元素, 但只有執行 9 次比較由於採用的是相鄰比較法, 因此在一個回合中, 一個大的數可能會往後移動數個位置, 但小的數卻可能只往前移一個位置在第一回合裡, 最大的數保證會移到陣列的最底部, 即 a[9]

108 在第二回合裡, 次大的數保證會沈到 a[8] 而在第九回合裡, 第九大的數即可保證沈到 a[1] 而此時剩下的最小的值恰好在 a[0] 裡因此, 雖然這個陣列含有 10 個元素, 但只需 9 個回合便能將之排序完成排序的動作是由巢狀的 for 迴圈來執行的 ( 第行 )

109 如果需要對調的話, 將由下列三個指定動作來進行 hold = a[ i ]; a[ i ] = a[ i + 1 ]; a[ i + 1 ] = hold; 其中額外的變數 hold, 會用來暫時存放對調的兩個數當中的一個對調動作不能只用以下的兩個指定動作來進行 a[ i ] = a[ i + 1 ]; a[ i + 1 ] = a[ i ];

110 例如, 若 a[i] 為 7,a[i + 1] 為 5 的話, 在第一個指定動作之後, 這兩個值都將變為 5, 而 7 則漏失了因此需要一個額外的變數 hold 氣泡排序的優點是它很容易撰寫但氣泡排序執行得相當慢, 因為每次的交換只能朝元素的最終位置前進一步尤其是在排序很大的陣列時在習題中, 我們將發展出一種較有效率的氣泡排序法一些遠比氣泡排序法有效率的排序方法已經發展出來了

111 電腦常會用來進行調查資料分析 (survey data analysis), 也就是用來編輯分析測驗和民意調查的結果圖 6.16 使用陣列 response 來初始化 99 個調查的回應每個回應都是範圍介於 1 到 9 之間的數字這個程式會計算 99 個數值的平均數中位數和眾數平均數是這 99 個數值的算術平均數函式 mean ( 第 40 列 ) 會將這 99 個元素加起來再除 99 來求出平均值中位數是位在中間的值

112 中位數是中間的值函式 mefian ( 第 61 列 ) 呼叫 bubblesort ( 定義在第 133 列 ) 來對回應的陣列進行遞增排序, 然後從已排序的元素當中選出中間的元素 answer[size / 2] 要注意當有偶數個元素的時候, 中位數是由兩個中間數的平均算出不過 median 函式目前並不提供此項功能此外, 程式會呼叫 printarray( 第 156 列 ) 函式來印出 response 陣列眾數是這 99 個反應中出現頻率最高的數值

113 函式 mode ( 第 82 行 ) 會對每種類型的回應執行計數的動作, 並且以此來決定眾數, 它會選出最大的計數值目前這一版本的 mode 函式並沒有處理相等的狀況 ( 見習題 7.14) 函式 mode 也產生長條圖, 它可以以圖形化來輔助眾數的決定圖 6.17 顯示此程式的執行結果

114

115

116

117

118

119

120

121

122

123

124 有時候可能需要知道陣列中是否有一個符合某個關鍵值 (key value) 的數值找出陣列中某個元素的過程稱為搜尋 (searching) 本節將為您介紹兩種搜尋的技術 - 最簡單的線性搜尋 (linear search) 和較有效率 ( 也較複雜 ) 的二元搜尋 (binary search)

125 線性搜尋 ( 見圖 6.18) 用搜尋關鍵值 (search key) 來比較陣列中的每個元素由於陣列中並沒有任何特別的順序, 所以有可能在第一次比較就找到, 也有可能要到最後一個元素才能找到平均上, 程式需要一半的陣列元素來與搜尋鍵比較

126

127

128

129

130 對於小型的陣列或未排序過的陣列而言, 線性搜尋可以表現的很好但是將線性搜尋用在大型陣列上, 就很沒有效率了如果陣列已經排序過了, 則我們可以用速度很快的二元搜尋法二元搜尋演算法在每次比較之後, 就可以將已排序陣列中一半的元素刪去不考慮此演算法先找出陣列的中間元素, 將之與搜尋關鍵值作比較

131 如果相等的話, 表示已找到要找的元素, 就將此元素的陣列下標傳回如果不相等, 此時問題便簡化成只需搜尋陣列的某一半如果搜尋的關鍵值小於陣列的中間元素, 就搜尋陣列的前半部 ; 否則就會搜尋陣列的後半部假如在指定的子陣列 ( 原始陣列的一部分 ) 當中找不到搜尋的關鍵值, 演算法就會搜尋原始陣列的四分之一

132 搜尋的動作會一直持續到搜尋關鍵值等於子陣列的中間元素為止, 或是子陣列只包含一個與搜尋關鍵值不相等的元素為止 ( 也就是沒有找到搜尋關鍵值 ) 在最壞的情形之下, 使用二元搜尋來搜尋 1023 個元素的陣列只需 10 次比較重複將 1024 除以 2 將會得到 516, 256, 128,64, 32, 16, 8, 4, 2, 1 等數值即 1024(210) 只要除以 2 十次, 便可得到 1 除以 2 的動作相當於二元搜尋的比較動作

133 一個具有 (220) 個元素的陣列, 最多需要進行 20 次的比較, 就能找到搜尋關鍵值而一個具有十億個元素的陣列, 最多也只需要 30 次比較便能找到搜尋關鍵值這比起線性搜尋, 有了大幅的效能改進, 線性搜尋需要的比較次數平均為陣列元素個數的一半對一個具有十億個元素的陣列來說, 平均要比較 5 億次, 與最多比較 30 次相比, 其差別是很大的

134 任何一個陣列的最大比較次數, 可以由大於此陣列元素個數的第一個 2 的次方數來加以決定圖 6.19 的程式為 binarysearch 函式的迭代版本 ( 第行 ) 此函式 ( 定義在第 32 列 ) 接收四個引數 - 要搜尋的一個整數陣列 b, 一個整數 searchkey, 陣列的 low 下標, 和陣列的 high 下標 ( 這些定義了陣列要搜尋的部分 ) 如果搜尋關鍵值不等於子陣列的中間元素, 則 low 下標或 high 下標將會受到更改, 所以它能夠繼續搜尋較小範圍的子陣列

135 如果搜尋關鍵值小於中間的元素, 下標 high 將設定為 middle-1, 接下來程式會繼續搜尋 low 到 middle-1 的元素如果搜尋關鍵值大於中間的元素, 則下標 low 將會設定為 middle+1, 接下來程式會繼續搜尋 middle+1 至 high 之間的元素這個程式使用 15 個元素的陣列第一個大於 15 的 2 的次方數是 16(24), 因此最多只需要 4 次便能找到搜尋鍵

136 這個程式使用 printheader 函式 ( 第列 ) 來輸出陣列下標, 並且使用 printrow 函式 ( 第列 ) 在二元搜尋的過程當中輸出每個子陣列每個子陣列的中間元素都會標上星號 (*), 來表示此元素將與搜尋鍵進行比較

137

138

139

140

141

142

143

144 C 語言的陣列可以有多重下標多重下標陣列 ( 又稱多維陣列 ) 經常會用來表示表格 (tables), 其數值是依照列 (rows) 和行 (columns) 排列的資料所組成為了指出特定的表格元素, 我們必須指定兩個下標 : 一般而言, 第一個下標會指定元素的列數, 第二個下標則會指定元素的行數使用兩個下標來指定某個特定元素的陣列, 稱為二維陣列

145 多重下標陣列能夠有兩個以上的索引圖 6.20 示範一個二維陣列 a 這個陣列包含三列以及四行, 因此它稱為 3x4 的陣列更一般地來說, 一個有 m 列和 n 行的陣列就稱為 mxn 陣列 (m-by-n array)

146

147 在圖 6.20 中, 陣列 a 的每個元素都可以用 a[i][j] 的方式來加以指定, 其中 a 是陣列名稱, 而 i 和 j 則會用來指出 a 的每個元素的下標第一列所有元素名稱的第一個下標都是 0; 而第四行所有元素名稱的第二個下標都是 3

148

149 多維陣列可以和一維陣列一樣, 在宣告時指定其初始值例如, 二維陣列 b[2][2] 可以用以下的方式來宣告並且指定初始值 : int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } }; 這些數值會以列為單位, 並且用大括號括起來第一個括號的值會初始化第 0 列, 第二個括號的值會初始化第 1 列所以 1 和 2 分別會初始化 b[0][0] 和 b[0][1] 3 和 4 分別初始化 b[1][0] 和 b[1][1]

150 如果某一列的初始值個數不夠的話, 則此列剩下的元素會將初始值設定為零因此, int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } }; 會將 b[0][0] 初始化成 1 b[0][1] 初始化成 0 b[1][0] 初始化成 3 b[1][1] 初始化成 4

151 圖 6.21 表示定義和初始化二維陣列這個程式定義了三個陣列, 每個陣列都有兩列和三行 ( 也就是每個陣列有六個元素 ) array1 的定義 ( 第 11 列 ) 提供了 6 個初始值 ( 分別放在兩個子串列中 ) 第一個子串列會將陣列的第一列 ( 也就是第 0 列 ) 初始值設定為 1, 2, 3; 第二個子串列則會將陣列的第二列 ( 也就是第 1 列 ) 初始值設定為 4, 5, 6

152

153

154

155 如果從 array1 的初始值串列當中移除每個子串列的大括號, 則編譯器會先用這些數值來為第一列指定初始值, 接著再為第二列指定初始值 array2 ( 第 12 列 ) 的定義提供 5 個初始值這 5 個初始值會先指定給第一列, 然後再指定給第二列所有沒有明確初始值的元素都會自動設定為零, 因此 array2[1][2] 的初始值將為零 Array3 ( 第 13 列 ) 的宣告提供了 3 個初始值 ( 分別放在兩個子串列中 )

156 給第一列的子串列將第一列的前兩個元素設定為 1 和 2, 第 3 個元素則自動設定為零給第二列的子串列則只將第一個元素設定為 4, 而剩下的兩個元素也自動設定為零這個程式呼叫了 printarray 函式 ( 第列 ) 來印出每一個陣列的元素此陣列的定義將陣列參數指定為 const int a[][3] 當我們在接收一維陣列做為函式的引數時, 函式參數串列的陣列括號是空的

157 而多維陣列的第一個下標也不需指定, 但其他的下標則都是必須的編譯器將利用這些下標, 來判斷多維陣列的元素位於記憶體中的什麼位置不論是幾維的陣列, 所有的陣列元素都是連續的存放在記憶體中的對二維陣列來說, 元素存放在記憶體中的順序是第一列之後跟隨著第二列在參數宣告時提供下標值, 可以讓編譯器告訴這個函式如何找到陣列中的某個元素

158 在二維陣列中, 每一列基本上都是一個一維陣列若想找到某一列的某個元素, 編譯器必須知道每一列到底有多少個元素, 這樣子它才可以算出總共要跳過多少個元素, 才能夠找到所要的元素因此, 當我們的例子在存取 a[1][2] 時, 編譯器便知道要跳過第一列的 3 個元素, 找到第二列 ( 即列 1) 然後編譯器才會存取此列的第三個元素 ( 即元素 2)

159 許多常見的陣列處理都會使用 for 重複敘述式例如, 下面的敘述式會將圖 6.20 中的陣列 a 的第三列所有元素, 均設定為零 for ( column = 0; column <= 3; column++ ) { a[ 2 ][ column ] = 0; } 由於我們指定對第三列操作, 因此第一個下標應該都是 2 (0 是第一列,1 是第二列 )

160 這個迴圈只改變第二個下標 ( 即行 ) 上述的 for 敘述式和下列的指定敘述式是相同的 a[ 2 ][ 0 ] = 0; a[ 2 ][ 1 ] = 0; a[ 2 ][ 2 ] = 0; a[ 2 ][ 3 ] = 0;

161 底下的巢狀 for 敘述式則計算了陣列 a 所有元素的總和 total = 0; for ( row = 0; row <= 2; row++ ) { for ( column = 0; column <= 3; column++ ) { total += a[ row ][ column ]; } } 這個 for 敘述式一次一列地來計算此陣列元素的總和

162 外層的 for 敘述式先將 row ( 即列下標 ) 設定為零, 所以內層的 for 敘述式便計算第一列的總和接著外層 for 敘述式將 row 遞增成 1, 將第二列的元素加到總和裡最後, 外層 for 敘述式會將 row 遞增成 2, 因此第三列的元素也會加到總和當巢狀的 for 敘述式結束時, 程式就會列印出結果

163 圖 6.22 的程式使用 for 敘述式對一個 3x4 的陣列 studentgrades 執行幾種其他常見的陣列處理陣列的每一列代表一個學生, 而每一行則代表學生四次考試成績中的其中一次陣列的處理是由四個函式來加以執行函式 minimum ( 第行 ) 會找出所有學生在本學期中的最差成績

164 函式 maximum ( 第行 ) 會找出所有學生在本學期中的最高成績函式 average ( 第行 ) 會算出某位學生本學期的平均成績函式 printarray ( 第行 ) 會以表列的方式清楚印出這個二維陣列.

165

166

167

168

169

170

171

172 函式 minimum, maximum 和 printarray 接收了三個引數 -studentgrades 陣列 ( 在每個函式裡都稱為 grades), 學生的人數 ( 亦即陣列的列數 ) 以及考試的次數 ( 亦即陣列的行數 ) 這三個函式都使用巢狀的 for 敘述式來走訪 grades 陣列

173 以下的巢狀 for 敘述式是取自 minimum 函式的定義 : /* loop through rows of grades */ for ( i = 0; i < pupils; i++ ) { /* loop through columns of grades */ for ( j = 0; j < tests; j++ ) { if ( grades[ i ][ j ] < lowgrade ) { lowgrade = grades[ i ][ j ]; } /* end if */ } /* end inner for */ } /* end outer for */

174 外層的 for 敘述式開始時會將 I ( 即列下標 ) 設定為 0, 這使得第一列的元素 ( 第一個學生的成績 ) 可在內層 for 敘述式的本體當中, 與變數 lowgrade 進行比較內層的 for 敘述式走訪了某列中的四個成績, 並且比較每個成績與 lowgrade 的大小如果成績小於 lowgrade, 則將 lowgrade 設定為該成績. 接著外層 for 敘述式將 row 的下標遞增成 1, 將第二列的元素加到總和裡

175 接著外層 for 敘述式將 row 的下標遞增成 2, 將第三列的元素加到總和裡當巢狀結構執行完畢後,lowGrade 便是這個二維陣列中的最差成績了函式 maximum 的運作類似於 minimum 函式 average ( 第 87 列 ) 有兩個引數 - 一個存放某位學生所有考試成績的一維陣列 ( 稱為 setofgrades), 以及此陣列中的考試成績數目

176 當呼叫 average 時, 第一個傳遞給它的引數是 studentgrades[student] 這將使得二維陣列某一列的位址傳給 average 引數 studentgrades[1] 是此二維陣列第二列的起始位址二維陣列實際上是由一維陣列所組成的陣列, 而一維陣列的名稱即代表它在記憶體中的位址函式 average 計算所有陣列元素的總和, 然後將總和除以考試成績的個數, 最後將結果以浮點數傳回

Microsoft PowerPoint - Bronson-v3-ch07.ppt [相容模式]

Microsoft PowerPoint - Bronson-v3-ch07.ppt [相容模式] C++ FOR ENGINEERS AND SCIENTISTS THIRD EDITION Chapter 7 Arrays Objectives 2 In this chapter, you will learn about: One-dimensional arrays 一維陣列 Array initialization 陣列起始化 Declaring and processing two-dimensional