C Functions

Size: px

Start display at page:

Download "C Functions"

帛茹
7 years ago
Views:

4 大部分用來解決真實世界問題的電腦程式, 都要比我們在前幾章中所介紹的程式大很多經驗告訴我們, 發展和維護大型程式的最好方法, 便是以一些較小的單元或模組 (module) 來建構整個程式, 這些小單元要比整個大程式好管理多了這種技巧稱為各個擊破 (divide and conquer) 本章將介紹關於 C 在設計實作操作和維護大型程式方面的功能

5 C 裡面的模組稱為函式 (function) C 程式的撰寫, 通常是將程式設計師所寫的新函式, 與位於 C 標準函式庫 (C standard library) 中事先寫好的函式結合起來構成一個程式 C 標準函式庫提供了包羅萬象的函式, 包括了常用的數學運算字串處理字元處理輸入 / 輸出, 以及許多其他有用的功能

9 我們所用過的 printf scanf 和 pow 函式都是標準函式庫的函式你可以為某個將在程式中許多位置用到的工作, 撰寫成一個函式這種函式有時稱為程式設計師自訂函式 (programmerdefined functions) 定義此函式的敘述式只需撰寫一次, 而且這些敘述式對其他函式來說是隱藏起來的函式經由函式呼叫 (function call) 的方式引用 (invoked) 函式呼叫指明了欲引用之函式的名稱, 並提供所需的資訊 ( 當作引數,argument) 給受呼叫函式, 以執行其工作

10 與此十分類似的是管理的階層形式老闆 ( 呼叫函式或呼叫者,calling function 或 caller) 要求某位員工 ( 受呼叫的函式,called function) 去執行某項工作, 並在工作完成後回報 ( 圖 5.1) 舉個例來說, 某個函式想在螢幕上顯示資訊, 它便呼叫員工函式 printf 去執行這項工作, 然後 printf 將資訊顯示出來, 並在顯示完畢之後回報 -- 或返回 (return) -- 呼叫函式老闆函式並不知道員工函式如何執行這項工作

11 員工可能會再呼叫其他的員工函式, 而老闆並不曉得我們將很快可以看到, 諸如此類的隱藏製作細節將如何來促進良好的軟體工程圖 5.1 展示了 main 函式以階層式的方式與數個員工函式進行通訊請注意 worker1 的動作相當於 worker4 和 worker5 的老闆函式函式間的關係並非一定如此圖所示的階層式架構

13 數學函式庫函式讓你能夠執行某些常用的數學運算函式在程式裡引用的方法, 通常是先寫函式名稱, 接著寫一個左括號, 然後跟著寫此函式的引數 (argument) ( 或是由逗號分隔的一個引數列 ), 最後再寫一個右括號例如, 若程式設計師想計算並印出的平方根, 可以寫成 printf( "%.2f", sqrt( ) ); 當此敘述式執行時, 數學函式庫函式 sqrt 將被呼叫來計算括號內之值 (900.0) 的平方根

14 900.0 這個數便是 sqrt 函式的引數上述的敘述式將會印出 sqrt 函式的引數型別為 double, 它的傳回值的型別也是 double 數學函式庫中所有函式傳回的浮點數, 其資料型別都是 double 請注意到 double 型別的值和 float 型別的值類似, 都可以使用 %f 轉換指定詞來輸出

16 函式的引數可以是常數變數或運算式如果 c 1 = 13.0,d = 3.0, f = 4.0, 的話, 下面的敘述式 printf( "%.2f", sqrt( c1 + d * f ) ); 將計算並且印出 * 4.0 = 25.0 的平方根, 答案是 5.0 圖 5.2 整理一些 C 的數學函式庫函式在此圖中, 變數 x 和 y 的型別都是 double.

19 函式讓你能夠模組化一個程式所有宣告在函式定義裡的變數都是區域變數 (local variable)-- 只有定義它們的函式才知道這些變數的存在大多數的函式都有一列參數 (parameter) 參數提供了函式間交換資訊的管道函式的參數也是區域變數

21 有數個動機誘使我們將程式函式化第一個動機是各個擊破的方法使得程式發展更容易管理另一個動機是軟體可以重複使用性 (software reusability)-- 利用現有的函式做為磚塊來建構新程式軟體的可重複使用性是物件導向程式設計的主要因素, 當你學習了 C 語言所衍生出來的語言 ( 像是 C++ Java 以及 C#) 之後, 你將會瞭解更多每當我們撰寫含括標準函式庫函式 ( 如 printf scanf 和 pow) 的程式時, 就使用了抽象化技巧第三個動機是可以避免程式中重覆地撰寫相同的程式碼像函式這種包裝好的程式碼, 可以在程式中的各個位置呼叫來執行

24 經由妥善的函式命名和定義, 程式可以由執行某些特定工作的標準化函式來加以建構, 而不需使用各人撰寫的程式碼此項技術稱為抽象化 (abstraction) 每當我們撰寫含括標準函式庫函式 ( 如 printf scanf 和 pow) 的程式時, 就使用了抽象化技巧第三個動機是可以避免程式中重覆地撰寫相同的程式碼像函式這種包裝好的程式碼, 可以在程式中的各個位置呼叫來執行

27 我們介紹過的每個程式都含有一個稱為 main 的函式, 它負責呼叫標準函式庫函式來完成程式的工作再讓我們來看看程式設計師該如何撰寫他們自己的函式請看圖 5.3 的程式, 此程式使用了一個稱為 square 的函式來計算 1 到 10 之整數的平方

31 在此程式中,square 函式是在 main 的 printf 敘述式 ( 第 14 行 ) 中被引用 (invoked) 或被呼叫 (called) printf( "%d ", square( x ) ); /* function call */ 函式 square 用它的參數 (parameter) y 接收了一份 x 的複製品 ( 第 22 行 ) 然後 square 執行 y * y 的計算 ( 第 24 行 ) 計算的結果傳回給引用 square 的 printf 敘述式, 接著 printf 便將此結果顯示出來這個過程將因 for 重複敘述式的使用而重複 10 次

32 square 的定義告訴我們它希望接收一個整數參數 y 位於函式名稱之前的保留字 int ( 第 22 行 ), 則表示 square 將傳回一個整數值 square 中的 return 敘述式用來將計算結果傳回給呼叫函式第 5 行 int square( int y ); /* function prototype */ 函式原型 (function prototype) 括號內的 int 告訴編譯器,square 希望從呼叫函式接收一個整數值

33 而函式名稱之前的 int 則告訴編譯器,square 會傳回一個整數值給呼叫函式編譯器根據函式的原型來檢查對 square ( 第 14 行 ) 的呼叫, 看它是否使用正確的回傳型別, 引數的數目是否正確, 引數的型別是否正確, 以及引數的排列順序是否正確函式定義的格式如下 return-value-type function-name( parameter-list ) { definitions statements }

34 function-nam 是任何合法的識別字 return-value-type 是指傳回給呼叫者之結果的資料型別 return-value-type 為 void 的話, 表示此函式沒有傳回值有時候把 return-value-type function- name 以及 parameter-list 稱為函式標頭 (function header)

37 parameter-list 中的各參數是以逗號分隔, 它含有在函式呼叫時所接收的參數宣告如果某個函式不接收任何的數值, 那麼它的 parameter-list 為 void 每個參數的型別都必須明確列出

42 大括號內的 definitions 和 statements 構成了函式的本體 (function body) 函式的本體通常也稱為區塊 (block) 任何區塊中都可以宣告變數, 區塊可以是巢狀的函式不能夠定義在另一個函式之內

49 有三種方式將控制權傳回引用函式的位置如果函式並沒有回傳值, 則當到達函式終止的右大括號時, 控制權便自動地傳回我們也可以執行底下的敘述式來傳回控制權 return; 如果函式有回傳值的話, 底下的敘述式 return expression; 會將 expression 的值傳回給呼叫者

50 圖 5.4 是我們的第二個例子此程式使用一個程式設計師自訂函式 maximum, 來判斷並傳回三個整數中最大的一個這三個整數傳給了 maximum( 第 19 行 ), 以決定最大整數 maximum 將最大值以 return 敘述式傳回給 main ( 第 37 行 )

55 ANSI C 最重要的功能之一便是函式原型 (function prototype) 標準 C 委員會向 C++ 的開發者借用這項功能函式原型會告訴編譯器有關函式傳回值的資料型別, 函式希望接收到的參數個數, 參數的型別, 以及這些參數的排列順序編譯器將利用函式原型來驗證函式呼叫

56 早期版本的 C 並沒有執行這類的檢查, 編譯器無法偵測到這些錯誤, 因此函式呼叫有可能不正確這種函式呼叫可能會導致致命的執行時錯誤, 或者導致非致命但卻難以偵錯的邏輯錯誤

58 圖 5.4 中 ( 第 5 行 ), 函式 maximum 的函式原型為 /* function prototype */ int maximum( int x, int y, int z ); 它指明了 maximum 有三個型別為 int 的引數, 且傳回型別為 int 的呼叫結果請注意, 函式原型和 maximum 函式定義的第一行是一樣的

61 不合函式原型規定的函式呼叫將造成編譯錯誤若是函式原型與函式定義不一致的話, 也會造成錯誤舉例來說, 如果圖 5.4 中的函式原型變成了 void maximum( int x, int y, int z ); 將會使編譯器產生一個錯誤, 因為這個函式原型中的 void 回傳型別, 與函式標頭中的 int 回傳型別不一致

62 函式原型的另一項功能是強制的引數型別轉換 (coercion of arguments), 亦即強迫引數變成恰當的型別例如, 雖然數學函式 sqrt 其函式原型 ( 位於 math.h 檔 ) 規定了一個 double 引數, 但我們可以用一個整數引數來呼叫它, 而且此函式也能正確地運作敘述式 printf( "%.3f\n", sqrt( 4 ) ); 可以正確地執行 sqrt(4), 並印出值 2.000

63 編譯器會在引數值傳給 sqrt 之前, 將整數值 4 轉換成 double 值 4.0 總而言之, 當引數的值沒有準確地對應到函式原型中的參數型別時, 這些引數值將會在函式呼叫之前, 先轉換成正確的型別這種轉換如果沒有遵守 C 的提升規則 (promotion rules) 的話, 可能導致不正確的結果產生提升規則規定了在不遺漏資料的前提下, 某一型別如何才能轉換成另一型別

64 在 sqrt 的例子中,int 可以自動轉換成 double 而不會遺漏資料不過, 若是 double 轉換成 int 的話,double 值的小數部分將會捨去將大的整數型別轉換成較小的整數型別 ( 如 long 變 short), 也可能造成數值改變提升規則會自動應用到含有兩種 ( 或更多 ) 資料型別之數值的運算式, 也稱為混合型別運算式 (mixed-type expressions)

65 混合型別運算式中, 每一個值的型別會自動提升為此運算式中的最高型別 ( 事實上是為每個值製造一個暫時的值, 用在運算式的計算上 -- 原來的值並沒有跟著改變 ) 圖 5.5 由最高型別至最低型別列出了所有的資料型別, 並列出每一個型別的 printf 和 scanf 轉換指定

67 將數值轉換成較低的型別, 通常會得到不正確的值因此, 我們只能用 cast 運算子, 或明確地將值指定給較低型別的變數, 才能夠轉換成較低的型別函式的引數值要想能夠轉換成函式原型中的參數型別, 其條件是這些數值必須能夠直接指定給那些型別的變數圖 5.3 的 square 函式使用了一個整數參數, 若我們以一個浮點數引數來呼叫它的話, 此引數將轉換成 int( 較低的型別 ), 而 square 則可能經常傳回不正確的值

69 如果某個函式沒有函式原型, 那麼編譯器將會以第一次遇到此函式的形式 ( 不論是函式定義或函式呼叫 ), 來建立它自己的函式原型這可能會產生警告或錯誤 ( 取決於你用的編譯器 )

72 要了解 C 是如何處理函式呼叫, 我們必須先了解一種稱為堆疊 (stack) 的資料結構你可以把堆疊想成一疊盤子當一個盤子堆上去的時候, 通常是放在頂端, 又稱為把盤子推入 (push) 堆疊同樣地, 當一個盤子拿下來的時候, 通常是從頂端拿, 又稱為把盤子從堆疊取出 (pop) 堆疊是一種後進先出 (last-in, first-out,lifo) 的資料結構, 也就是說, 最後推入 ( 加入 ) 堆疊的項目會最先從堆疊取出 ( 移除 )

73 當程式呼叫函數時, 被呼叫的函數必須知道要怎麼回到呼叫者的位置, 因此呼叫函數的返回位址會被推入程式執行堆疊 (program execution stack) 中, 又稱作函式呼叫堆疊 (functioncall stack) 假如發生了一系列的函式呼叫, 返回位址會依後進先出的順序被推入堆疊中, 因此每個函式都能返回它的呼叫者程式執行堆疊中也包含了程式執行時, 函式所使用的區域變數的記憶體

74 這些儲存在程式執行堆疊中的資料, 也稱為函式呼叫的活動紀錄 (activation record) 或堆疊框架 (stack frame) 當函式呼叫發生時, 此函式呼叫的活動紀錄會被推入程式執行堆疊中當函式返回它的呼叫者時, 此函式呼叫的活動紀錄會從堆疊中被取出, 而程式就無法使用這些區域變數了

75 當然, 電腦的記憶體容量有限, 因此可以用來儲存程式執行堆疊中活動紀錄的記憶體容量也是有限的假如函式呼叫的數量超過程式執行堆疊可以儲存的活動紀錄時, 會產生稱為堆疊溢位 (stack overflow) 的錯誤

76 每個標準函式庫都有一個相對應的標頭 (header), 它含有此函式庫中所有函式的函式原型, 以及這些函式所需之各種資料型別和常數的定義圖 5.6 依字母的順序列出了可以含括進程式裡的標準函式庫標頭檔在此圖中, 巨集這個名詞出現了許多次, 我們將在第 13 章再詳細地介紹你也可以撰寫自己的標頭檔程式設計師定義的標頭檔, 也應以.h 做為副檔名

77 我們可以用前置處理器命令 #include 含括進程式設計師定義的標頭檔舉例來說, 假如我們的 square 函式位在標頭檔 square.h 中, 我們可以將標頭檔含括在我們的程式中在程式的上方使用下列的命令 : #include "square.h"

80 傳值呼叫 (call by value) 和傳參考呼叫 (call by reference) 是大多數的程式語言用來引用函式的兩種方式當以傳值呼叫來傳遞引數時, 此引數值的一份複製將會傳給受呼叫的函式對此複製所做的修改並不會影響到呼叫者原來變數的值當以傳參考來傳遞引數時, 呼叫者允許受呼叫函式修改原來的變數值當受呼叫函式不需修改呼叫者的原始變數時, 應該使用傳值呼叫

81 如此一來, 便可防止偶發性的副作用 (side effect) ( 變數被更改 ), 而此項副作用會大幅妨礙正確和可信賴軟體系統的研發傳參考呼叫最好只用在可靠度高, 且必須修改原始變數的受呼叫函式身上對 C 來說, 所有的呼叫都是傳值呼叫在第六章可以看到陣列將會自動地以傳參考呼叫來傳遞

82 現在讓我們來介紹一個有趣的程式應用, 模擬和賭博程式在電腦的應用程式裡, 我們可以用 C 標準函式庫中, 標頭檔 stdlib.h 中的 rand 函式來模擬機會的運行請看下列的問題描述 : i = rand(); 其中 rand 函式會產生一個介於 0 和 RAND_MAX ( 定義在 <stdlib.h> 標頭檔中的符號常數 ) 之間的整數

83 ANSI 標準規定 RAND_MAX 的值至少需為 32767, 此也是兩個位元組 ( 即 16 bit) 所能表示的最大整數值本節的程式測試環境是 RAND_MAX 值為的 C 系統如果 rand 真的可以隨機產生整數的話, 那麼每一次呼叫 rand 時,0 到 RAND_MAX 之間的每一個整數應有相同的機會 (chance) 或機率 (probability) 選到 rand 所產生的值, 其範圍通常不合乎某個特定應用的需求

84 例如, 一個模擬擲銅板動作的程式, 只需要用 0 來代表正面以及用 1 來代表反面而一個模擬擲骰子動作的程式, 則需要 1 到 6 來代表骰子的 6 個面為了示範 rand, 讓我們發展一個程式來模擬投擲 6 面的骰子 20 次, 並印出每一次擲所得的值 rand 的函式原型在 <stdlib.h> 檔裡我們以模數運算子 (%) 與 rand 一起使用, 如下 rand() % 6 來產生 0 到 5 的整數

85 這稱為比例化 (scaling) 6 稱為比例因子 (scaling factor) 接著再將產生的結果加 1, 將數值的範圍移位 (shift) 因此圖 5.7 裡的結果便落在 1 到 6 之間其結果因編譯器而異

88 為了證明這些數出現的機率差不多, 我們用圖 5.8 的程式來模擬 6000 次的骰子投擲從 1 到 6 的每個整數出現的次數都應在 1000 次左右就如同程式的輸出所示, 我們可以用比例化和移位的方式, 將 rand 函式模擬成 6 面骰子的投擲結果程式中的 switch 敘述式並沒有提供 default 狀況

89 還有, 我們使用了 %s 轉換指定詞來印出字串 "Face" 和 "Frequency" 做為每一列的標頭 ( 第 53 列 ) 在學到第六章的陣列後, 我們將展示如何將整個 switch 結構換成單行的敘述式

94 再次執行圖 5.7 的程式時會出現同樣的順序那麼這些值如何能稱為亂數呢? 諷刺的是, 這種重複性卻是 rand 函式的一項重要的特性

95 當我們偵錯一個程式時, 此重複性正是修正程式不可以或缺的事實上,rand 函式所產生的是虛擬亂數 (pseudorandom numbers) 重複呼叫 rand 所產的數列, 看起來也是隨機的只不過每次執行時, 都會出現相同的數列一旦程式已經偵錯完成了, 我們便可以透過一些其他的步驟, 來使每次的執行產生不同的數列

96 此過程稱為隨機化 (randomizing), 可以用標準函式庫函式 srand 來進行 srand 函式需要一個 unsigned 整數引數, 它為 rand 函式提供了種子 (seed), 讓 rand 能夠在每次執行時產生不同順序的亂數我們在圖 5.9 中示範 srand 的用法

97 而型別為 unsigned 的變數也存放在至少兩個位元組的記憶體裡但兩個位元組的 unsigned 卻只能代表 0 到之間的正整數而四個位元組的 unsigned 也只能代表 0 到之間的正整數 srand 函式需要一個 unsigned 值的引數我們在 scanf 裡用轉換指定詞 %u 來讀進 unsigned 變數的數值 srand 的函式原型位於 <stdlib.h> 裡

100 讓我們來執行這個程式數次, 並觀察其結果我們可以看到, 當我們輸入不同的 seed 時, 此程式每次執行所產生的亂數順序便不相同如果我們想要不需每次輸入一個 seed, 便能達到隨機化的效果, 可以用如下的敘述式 srand( time( NULL ) ); 此舉可以使電腦自動地讀取它內部的時鐘, 來做為 seed 的值 time 函式會傳回從 1970 年 1 月 1 日午夜到目前所經過的秒數

101 此值將轉換成一個 unsigned 整數, 並做為亂數產生器的 seed 在上述敘述式中,time 函式會以 NULL 做為引數 (time 可以以字串來表示它傳回的值 ; 若以 NULL 為引數的話, 則不具此項功能 ) time 的函式原型位於 <time.h> 裡

102 直接由 rand 所產生的值一定落在 : 0 rand() RAND_MAX 前面我們介紹過如何以下列敘述式來模擬六面骰子的投擲結果 : face = 1 + rand() % 6; 此敘述式會將一個整數值 ( 隨機的 ) 指定給變數 face, 而且一定在 1 < face < 6 這個範圍內我們注意到範圍的大小 ( 在範圍內連續整數的個數 ) 為 6, 而範圍的起始數為 1

103 從上面的敘述式我們可以看出, 範圍的大小取決於對 rand 進行比例化之數值 ( 即 6), 而範圍的起點則是加到 rand() % 6 的數值因此, 我們可以歸納出如下的結果 : n = a + rand() % b; 其中 a 代表位移值 (shifting value), 即連續整數範圍的第一個數 b 代表比例因子 ( 即連續整數範圍的大小 )

104

105 一種最普遍的賭博遊戲是稱為 "crap" 的擲骰子遊戲, 這個遊戲的規則很簡單, 如下 : 玩家投擲兩顆骰子每一顆骰子有六個面這些面分別刻有 1, 2, 3, 4, 5, 和 6 個點當骰子靜止下來後, 將兩個骰子朝天的那一面的點數相加起來如果第一次投擲便擲出 7 點或 11 點, 那麼判定玩家贏若第一次擲出 2 點 3 點或 12 點 ( 這些點數稱為 crap), 那麼則是玩家輸 ( 莊家贏 ) 如果第一次擲出 4 點 5 點 6 點 8 點 9 點或 10 點, 則這個點數成為玩家的目標點數你必須繼續投擲這兩顆骰子, 直到擲出你的目標點數才算贏但若玩家在達成目標點數之前擲出了 7 點, 則判定玩家輸圖 5.10 的程式模擬了這個遊戲, 圖 5.11 則列出了數個執行結果

106

107

108

109

110

111 請注意遊戲規則, 玩家在第一次及後續輪擲時, 均需投擲兩顆骰子我們定義了 rolldice 函式來投擲骰子, 並計算印出他們的點數和函式 rolldice 只定義一次, 不過卻在程式中的兩個位置呼叫 ( 第 23 和 51 列 ) rolldice 不需要引數, 因此我們在它的參數列寫上 void ( 第 76 列 ) rolldice 函式會傳回兩顆骰子的點數和, 所以在它的函式標頭以 int 標示其回傳型別

112 玩家在第一輪便可能贏或輸, 或者在接下來的數回合中都有可能贏或輸變數 gamestatus 被定義為新型別 enum Status, 用來記錄目前的狀態第 8 行建立了一個稱為列舉 (enumeration) 的使用者定義型別列舉由關鍵字 enum 定義, 它是一個表示為識別字的整數常數的集合列舉常數 (Enumeration constants) 有時候稱為符號常數 enum 裡面的值從 0 開始, 並且以 1 遞增

113 在第 8 行, 常數 CONTINUE 的值是 0,WON 的值是 1, 以及 LOST 的值是 2 但是也可以將整數型別的值指定給 enum 中的識別字 ( 參見第 10 章 ) 列舉中的識別字必須唯一, 但是不能有重複的元素

114

115

116 如果玩家在第一回合或接下來的回合中贏了,gameStatus 將設定為 WON 如果玩家在第一回合或接下來的回合中輸了,gameStatus 將設定為 LOST 其他的狀況下則會將 gamestatus 設定為 CONTINUE, 表示遊戲還須繼續進行在第一次投擲之後, 如果遊戲已經結束了,while 結構將因 gamestatus 不等於 CONTINUE 而跳過 ( 第 50 行 ) 程式接著執行第 68 行的 if...else 敘述式如果 gamestatus 為 1 的話, 則它會印出 "Player wins", 否則便印出 "Player loses"

117 在第一次投擲之後, 若遊戲未結束, 那麼便將 sum 存到 mypoint 這個變數由於此時 gamestatus 等於 CONTINUE, 所以程式接下來執行 while 敘述式 ( 第 50 列 ) while 的每次重複都會呼叫 rolldice 來產生新的 sum 如果 sum 和 mypoint 相同的話, 將 gamestatus 設為 1, 表示玩家贏了, 接著 while 的條件檢查失敗, 程式跳出 while 迴圈繼續 if...else 結構的執行 If...else 結構印出 "Player wins" 後 ( 第 65 列 ), 便結束了整個程式

118 如果 sum 等於 7 的話 ( 第 58 列 ),gamestatus 將設為 2 表示玩家輸了, 接著跳出 while 迴圈, 然後 if...else 敘述式 ( 第 65 行 ) 印出 "Player loses" 之後, 程式便會結束執行請注意到本程式的控制結構我們使用了兩個函式 (main 和 rolldice), 以及 switch, while, 巢狀 if...else 和巢狀 if 等敘述式我們將在習題裡介紹到一些有關 craps 遊戲的有趣特性

119 在第二章到第四章當中, 我們已使用了識別字來做為變數的名稱變數的特性包括了名稱型別大小和值在本章中我們也使用了識別字做為使用者定義的函式名稱事實上, 程式中的每一個識別字都還有一些其他特性, 包括儲存類別 (storage class), 儲存佔用期間 (storage duration) 範圍 (scope) 和連結 (linkage) C 提供了四種儲存類別, 分別以下列四個儲存類別指定詞 (storage class specifiers) 來表示 : auto, register, extern, 和 static 識別字的儲存類別 (storage class) 有助於判斷他們的儲存佔用期間範圍和連結等特性識別字的儲存佔用期間 (storage duration) 是指此識別字存在記憶體中的時期

120 有些識別字只存在一下子, 有些則重複地建立和清除, 而有些則在程式的執行過程中一直都存在識別字的範圍是指此識別字在程式中能夠被參考的範圍有些識別字在整個程式中都可以引用, 而有些只能程式的某部分所引用識別字的連結 (linkage) 是指在有數個原始程式檔的情況下 ( 第 14 章將會介紹 ), 此識別字是否只有目前的原始檔知道它, 還是只要正確的宣告的話, 任何原始檔都可以知道它的存在本節將討論儲存類別, 以及儲存佔用期間

121 5.13 節將討論範圍至於識別字的連結, 和使用數個原始檔的程式設計, 則留等第 14 章再繼續討論上述的四個儲存類別指定詞, 可以分為兩種儲存佔用期間 : 自動儲存佔用期間 (automatic storage duration) 和靜態儲存佔用期間 (static storage duration) auto 和 register 這兩個關鍵字用來宣告自動儲存佔用期間的變數具有自動儲存佔用期間的變數, 是在程式控制進入宣告他們的區塊時, 才會產生出來而當程式控制離開這個區塊時, 他們便清除了

122 只有變數才能具有自動儲存佔用期間函式的區域變數 ( 宣告在函式的參數列或函式本體中的變數 ) 通常都具有自動儲存佔用期間識別字 auto 用來明確地宣告變數為自動儲存佔用期間

123 例如, 下列的宣告表示 float 變數 x 和 y 為自動區域變數, 他們只存在於宣告他們的函式本體中 : auto double x, y; 區域變數內定為具有自動儲存佔用期間, 因此 auto 識別字很少使用在接下來的內容中, 我們會將具有自動儲存佔有期間的變數, 簡稱為自動變數 (automatic variables)

124

125

126 在機器語言的程式中, 資料通常都會載入暫存器中, 以進行計算及其他的處理

127

128 編譯器可以忽略 register 的宣告例如, 當暫存器的數目不敷編譯器使用時下面的宣告建議編譯器將整數變數 counter 放到電腦的暫存器中, 並指定它的初始值為 1: register int counter = 1; 關鍵字 register 只能對自動變數使用

129

130 識別字 extern 和 static 是用來將變數或函式的識別字宣告為具有靜態儲存佔用期間具有靜態儲存佔用期間的識別字, 從程式開始執行時便已經存在對變數來說, 當程式開始執行時, 便為它配置好儲存並設好初始值了 ( 只做一次 ) 對函式來說, 在程式開始執行時, 此函式的名稱就存在了

131 不過, 即使這種變數和函式的名稱在程式一開始執行時便存在, 並不代表這些識別字在程式的各個角落都可以使用識別字的範圍 ( 名稱可以使用的區域 ) 和儲存暫用期間是另一個主題我們將在 5.13 節中討論有兩種識別字屬於靜態儲存佔用期間 : 外部的識別字 ( 如全域變數和函式的名稱 ), 以及以儲存類別指定詞 static 宣告的區域變數全域變數和函式名稱預設為 extern 的儲存類別

132 全域變數的製造方法是將變數的宣告放在任何函式定義之外, 他們將會在整個程式執行期間, 一直保有他們的值全域變數和函式, 可以被同檔案中位於他們的宣告或定義之後的任何函式參考這便是為什麼要使用函式原型的原因之一當我們為某個呼叫 printf 的程式含入 stdio.h 之後, printf 的函式原型便放到檔案的前頭, 這使得 printf 這個名稱能夠讓檔案的其他位置都知道

133

134 以保留字 static 宣告的區域變數也只能夠在定義它的函式中使用, 但它並不像自動變數,static 區域變數在程式離開這個函式之後, 還會保有他們的值當這個函式下一次再進行呼叫時,static 區域變數的值會和此函式上次離開函式時的值相同下面的敘述式會將區域變數 count 宣告為 static, 並為它指定初始值 1 static int count = 1;

135 如果你沒有明確指定初始值的話, 則所有靜態儲存佔用期間的數字變數, 都會將初始值設定為 0 extern 和 static 這兩個關鍵字如果用於外部識別字的話, 會具有特殊的意義我們將在第 14 章討論明確使用 extern 和 static 在外部識別字以及多個原始檔的程式上

136 識別字的範圍 (scope) 是指可以參考到此識別字的程式部分例如, 當我們在某區塊中宣告一個區域變數時, 此變數只能在這個區塊或其內的巢狀區塊引用識別字的四種範圍分別是函式範圍 (function scope) 檔案範圍 (file scope) 區塊範圍 (block scope) 以及函式原型範圍 (function-prototype scope) 標籤 ( 識別字再加一個冒號, 如 start:) 是唯一具有函式範圍 (function scope) 的識別字標籤可以在他們出現的函式中的任何位置使用, 不過出了這個函式的本體, 便不能參用這些標籤

137 標籤會用在 switch 敘述式 ( 如 case 標籤 ) 和 goto 敘述式裡 ( 見第 14 章 ) 標籤屬於函式內部的實作細節, 函式將其隱藏起來不讓別的函式知道這種隱藏 -- 較正式的稱法為資訊隱藏 (information hiding)..是以最小權限原則 (principle of least privilege) 建構的方法, 是良好的軟體工程最基本的原則之一宣告在任何函式之外的識別字都具有檔案範圍 (file scope) 從這種識別字宣的位置開始, 一直到整個檔案結束, 所有的函式中都會知道它的存在

138 全域變數函式定義, 和放在函式之外的函式原型都具有檔案範圍宣告在區塊之內的識別字都具有區塊範圍 (block scope) 區塊範圍終止的位置在此區塊的結束右大括號 (}) 宣告在函式一開頭的區域變數, 和此函式的參數都具有區塊範圍任何區塊都可以含有變數的宣告

139 在巢狀區塊的情形下, 如果外層區塊的某個識別字與內層區塊某個識別字名稱相同的話, 外層區塊的識別字在內層區塊裡將隱藏起來, 直到內層區塊結束為止這表示當執行到內層區塊時, 內層區塊看到的是它自己的識別字的值, 而不是外層區塊那個與它同名稱的識別字的值雖然宣告為 static 的區域變數從程式一開始執行便存在, 但他們仍然是屬於區塊範圍

140 因此儲存佔用期間並不會影響到識別字的範圍唯一具有函式原型範圍 (function-prototype scope) 的是用在函式原型參數列中的識別字我們在前面曾經提過, 函式原型的參數列中並不需要名稱 -- 只需要型別如果參數列中使用了名稱的話, 編譯器將會忽略這些名稱這些識別字可以在程式的其他位置重複使用, 而不會有模稜兩可以的情況發生

141

142

143 圖 5.12 的程式分別以全域變數, 自動區域變數, 以及 static 區域變數, 來示範範圍界定的問題程式中宣告了一個全域變數 x, 並將其初始值設為 1 ( 第 9 行 ) 這個全域變數在任何區塊 ( 或函式 ) 內將會隱藏起來, 如果他們也都宣告了一個稱為 x 的變數的話 main 程式中宣告了一個區域變數 x, 並將其初始值設為 5 ( 第 14 行 ) 這個變數會印出來, 以顯示全域的 x 在 main 裡隱藏起來了接下來, 一個新區塊定義在 main 裡面, 它也宣告了一個區域變數 x, 初始值為 7 ( 第 19 行 )

144 程式再把此變數印出來, 以顯示它掩蓋了外層區塊裡的 x 當這個區塊結束時, 值為 7 的變數 x 便會自動清除這時再印出外層區塊的 x 值, 以顯示此變數已不再受隱藏了程式定義了三個函式, 他們都沒有任何引數也沒有傳回任何東西函式 uselocal 定義一個自動變數 x, 並且將它初始為 25 ( 第 40 列 ) 當呼叫 uselocal 之後, 先印出此變數的值, 然後將它遞增, 最後在離開此函式前再印一次它的值

145 每次函式 uselocal 呼叫時, 自動變數 x 都會重新設成 25 函式 usestaticlocal 宣告了一個 static 變數 x 其初始值為 50 ( 第 53 列 ) 宣告成 static 的區域變數會一直保存他們的值, 即使已經離開了他們的範圍亦是如此當 usestaticlocal 呼叫時, 會先印出 x 的值, 然後將它遞增, 最後在離開此函式之前再印一次 x 的值而在下一次呼叫函式 usestaticlocal 時,static 區域變數 x 的值將會是 51 useglobal 函數沒有宣告任何變數

146 因此當它參考到變數 x 時, 便會使用全域變數 x ( 第 9 行 ) 當 useglobal 呼叫時, 先印出此全域變數的值, 然後將它乘以 10, 最後在離開此函式之前再印一次它的值下次函式 useglobal 再呼叫時, 全域變數的值應該就是上次改過之後的值, 即 10 程式的最後再印一次 main 中的區域變數 x ( 第 33 行 ), 以確定所有的函式呼叫都沒有更改 x 的值, 因為這些函式呼叫所參考到的是其他範圍裡的變數 x

147

148

149

150

151 到目前為止, 我們所討論過的程式, 其結構通常是某個函式以階層式的方式呼叫其他的函式不過對某些類型的問題來說, 如果函式可以呼叫它自己, 將會十分有用遞迴函式 (recursive function) 就是一種可以直接或間接呼叫自己的函式遞迴是進階電腦科學課程中所討論的一項複雜的課題在本節和下一節中, 將會介紹簡單的遞迴範例

152 本書的第五到八章以及第十二章, 將廣泛地介紹遞迴在 5.16 節的圖 5.17 中, 將整理本書所有關於遞迴的 31 個範例和習題首先讓我們瞭解遞迴的觀念, 然後再來看看幾個含有遞迴函式的程式遞迴函式的解決問題方法都具有一些共同特點他們會呼叫一個遞迴函式來解決問題, 這個函式只曉得如何解決最簡單的情況, 或稱為基本情況 (base case)

153 如果此函式是在基本情況下呼叫, 那麼它便會傳回某個數值如果是以較複雜的問題來呼叫, 則此函式會將問題分成兩個概念性的小塊 : 一塊是此函式知道該怎麼做, 另一塊是此函式不知道該怎麼做的部分, 為了使遞迴順利進行, 後面一塊必須類似原來的問題, 不過比原先的問題簡單也比較小

154 由於新的問題看起來很像原來的問題, 因此, 此函式呼叫它自己來解決這個較小的問題 - 這稱為遞迴呼叫 (recursive call), 也稱為遞迴步驟 (recursion step) 遞迴步驟裡也包含了 return 這個保留字, 因為它的結果會和知道問題該如何解決的部分, 結合形成最後的結果, 並且傳回給最原始的呼叫者, 可能是 main 當對遞迴函式的原始呼叫還沒得到結果時, 遞迴步驟便會持續執行下去

155 遞迴步驟可以導致更多相同的遞迴步驟函式持續地將每個問題分成兩個概念性的小塊為了使遞迴能結束, 每次所衍生出之較簡單的問題, 應該逐漸地接近基本情況當到達基本情況時, 當時的函式將結果傳回給上一份的函式, 接著如骨牌效應似的回傳動作, 最終將可以讓原始的函式將結果傳回給 main

156 非負整數的階乘 n, 寫成 n! ( 讀作 n 階乘 ) 如以下乘積 : n (n 1) (n 2) 1 的乘積, 而 1! 等於 1,0! 也定義成 1 例如,5! 便是 5*4*3*2*1 的乘積, 其值為 120 對於大於等於零的整數 number, 其階乘可以用 for 敘述句重複地 (iteratively) 計算 ( 這不是遞迴 ) 如下 : factorial = 1; for ( counter = number; counter >= 1; counter-- ) factorial *= counter;

157 階乘函式的遞迴定義, 可以經由觀察下列關係而得 : n! = n (n 1)! 例如, 由底下的式子可以證明 5! 即等於 5*4! 5! = ! = 5 ( ) 5! = 5 (4!) 5! 的計算可以如圖 5.13 所示執行

158 圖 5.13(a) 顯示遞迴呼叫不斷地進行, 直到 1! 計算成 1 為止, 這時遞迴將會結束圖 5.13(b) 顯示了每個遞迴呼叫會回傳數值給呼叫它的函式, 直到計算出最終的數值並且傳回之後才停止圖 5.14 的程式利用遞迴來計算並印出 0 到 10 之整數的階乘值 ( 稍後將解釋為何選用 long 資料型別 ) 遞迴函式 factorial 檢查結束條件是否為真, 亦即 number 是否小於等於 1

159 如果 number 小於等於 1 則 factorial 傳回 1, 不需再進一步的遞迴, 程式也因而結束如果 number 大於 1 的話, 便執行底下的敘述式 return number * factorial( number - 1 ); 此敘述式將問題表示成 number 與對 factorial 遞迴呼叫 ( 用來求出 number-1 的階乘 ) 的乘積 factorial (number-1) 比原來的 factorial(number) 稍微簡單一點

160 函式 factorial 宣告成接收一個 long 型別的參數 ( 第 22 列 ), 並傳回一個 long 型別的結果, 這是 long int 的縮寫 ANSI 標準規定, 型別為 long int 的變數至少要以 4 個位元組來儲存, 因此它所能表示的最大值為我們可以在圖 5.14 中看到, 階乘值很快地就會變得非常大選用資料型別 long 使得此程式能夠在整數位元數較小的電腦 ( 如 2 個位元組 ) 上計算大於 7! 的階乘值

161

162

163

164 我們用轉換指定詞 %ld 來印出 long 的值但是由於 factorial 函式所產生的數值很快地變得非常大, 就算用 long int 也沒辦法印出, 太大的階乘值會超出 long int 變數的最大值在習題裡我們會發現, 需要用 double 來算出較大數值的階乘值

165 這指出 C 語言 ( 以及許多其他的程式語言 ) 的一項弱點, 這種程式語言無法簡易地擴展來處理不同應用的獨特需求而 C++ 則是一種可擴充的程式語言, 它讓我們能建立任何大小的整數

166

167

168 費伯那契級數 0, 1, 1, 2, 3, 5, 8, 13, 21, 是以 0,1 開始, 之後的每一個 Fibonacci 數, 都是它的前兩個 Fibonacci 數之和這種數列會在自然界中出現, 特別是描述了螺旋狀連續兩個 Fibonacci 數的比值為一常數

169 這個常數也在自然界中不斷地出現, 稱為黃金比例 (golden ratio) 或黃金平均值 (golden mean) 人們試著找出黃金比例以求美觀而建築師們也將窗戶, 房間和建築物的長寬比例設計成黃金比例此外, 明信片的長寬比也依此黃金比例來設計

170 費伯那契級數可以遞迴地定義, 如下 : fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(n) = fibonacci(n 1) + fibonacci(n 2) 圖 5.15 的程式利用函式 Fibonacci, 遞迴地計算出第 n 個 Fibonacci 數 Fibonacci 數會迅速變成很大, 因此我們必須以 long 來做為 fibonacci 函式的參數和傳回值的型別在圖 5.15 當中, 每個輸出行分別表示一次程式執行的結果

171

172

173

174

175 從 main 對 Fibonacci 的呼叫不是遞迴呼叫 ( 第 18 列 ), 其他對 Fibonacci 的呼叫全都是遞迴呼叫 ( 第 33 列 ) 每次 Fibonacci 被呼叫時, 它會馬上檢測基本情況 --n 是否等於 0 或等於 1 如果是的話, 將傳回 n 有趣地是, 如果 n 大於 1, 遞迴步驟會產生兩個遞迴呼叫, 每個都代表一個比原來問題還簡單的問題圖 5.16 示範 Fibonacci 函式如何計算 Gibonacci(3)

176

177 此圖產生一些有趣的問題,C 編譯器是以何種順序來對運算子的運算元求值呢? 另一個不同的問題就是運算子應用到運算元的順序為何, 也就是由運算子優先次序來獲取運算規則圖 5.16 說明, 在求 fibonacci( 3 ) 的值時, 會先進行兩次遞迴呼叫, 這分別是 fibonacci( 2 ) 和 fibonacci( 1 ) 但這兩個呼叫執行的順序為何呢? 大多數的程式設計師都假設運算元是由左向右運算

178 但令人訝異的是,ANSI 標準並沒有指明大多數運算子 ( 包括 +) 的運算元之運算順序因此, 你不應該對這種順序進行任何假設程式可能先執行 fibonacci( 2 ) 再執行 fibonacci( 1 ), 也可能先執行 fibonacci( 1 ) 再執行 fibonacci( 2 ) 在本程式以及其他許多的程式裡, 這兩種執行順序會得到相同的結果

179 不過在某些程式中, 對某個運算元運算可能會產生副作用, 而影響運算式最終的結果在 C 的大多數運算子中,ANSI 標準只規定四種運算子的運算元運算順序, 他們是 &&,, 逗號運算子 (,) 和 (?:) 前三個屬於二元運算子, 他們的運算子均由左往右運算

180 [ 請注意 : 在函式呼叫中用來分隔引數的逗號不是逗號運算子 ] 最後一個是 C 的唯一的三元運算子它的最左邊運算元一定最先運算 ; 如果運算得到非零的值, 便進行中間運算元的運算, 並忽略最右邊的運算元 ; 而如果最左邊運算元運算的結果為零, 那麼便進行最右邊運算元的運算, 並且忽略掉中間的運算元

181

182

183 關於遞迴程式 ( 例如我們用來產生 Fibonacci 數的程式 ) 有一點值得注意, 也就是它的複雜度等級的問題在 fibonacci 函式中, 每一級的遞迴都會讓呼叫的總數變為 2 倍, 亦即計算第 n 個 Fibonacci 數時, 需要執行 2n 次的遞迴呼叫這會很快失去控制想想看, 當我們要計算第 20 個 Fibonacci 數, 便需要約 220 個函式呼叫, 也就是一百萬個函式呼叫要計算第 30 個 Fibonacci 數, 便需要約 230 個函式呼叫, 也就是十億個函式呼叫

184 電腦科學家將這種現象稱為指數等級複雜度 (exponential complexity) 遇上這類的問題, 即使是世界上最強大的電腦也束手無策了! 有關複雜度的問題, 特別是指數複雜度, 在稱為演算法的進階電腦科學課程中會加以介紹

185

186 本節中討論的範例是用直覺的方法來計算 Fibonacci 數列, 但是應該有更好的方式習題 5.48 要你深入研究遞迴, 找出其他實作遞迴 Fibonacci 演算法的方法

187 在上一節中, 我們討論兩個可以輕易以遞迴或迭代方式來製作的函式本節將比較這兩種方法, 並且討論在何種條件下, 程式設計師應該選用哪一種方法迭代和遞迴都是以控制結構為基礎 : 迭代使用重複結構 ; 遞迴使用選擇結構迭代和遞迴都含有重覆性 : 迭代明確地使用重複結構 ; 遞迴則使用重複的函式呼叫

188 迭代和遞迴都含有一個終止檢測 : 重複在迴圈繼續條件失敗時結束 ; 遞迴在到達基本情況時結束迭代使用計數器控制重複結構, 遞迴則逐步接近終止 : 迭代會持續改變計數器的值, 直到計數器的值讓迴圈持續的條件不符合為止 ; 遞迴則持續將原始的問題簡化, 直到問題變成基本狀況為止

189 迭代和遞迴都可能會產生無窮迴圈 : 在迴圈持續的條件永遠不是偽的時候, 迭代會產生無窮迴圈 ; 在遞迴步驟無法將問題收斂到基本狀況時, 遞迴會產生無窮迴圈遞迴有許多缺點由於它會重複引用函式, 造成多餘的負擔因此在執行時間和記憶體空間兩方面, 都會帶來昂貴的額外負擔

190 每個遞迴呼叫都會產生此函式的另一份拷貝 ( 實際上只有此函式內的變數 ), 這將消耗可觀的記憶體空間迭代則通常只會在同一個函式內進行, 因此沒有重複的呼叫函式所造成的額外記憶體負擔為什麼要使用遞迴呢?

191

192

193 圖 5.17 整理本書中 31 個有關遞迴的例子

194

195

196 讓我們以本書中常提到的一些觀點來結束本章良好的軟體工程是很重要的, 而高效率也是很重要的不幸地是, 這兩種目標通常無法兼顧良好的軟體工程是我們能夠更容易管理複雜軟體系統的關鍵高效率則是實現未來軟體系統的關鍵, 在硬體上, 對計算的需求甚至更高哪裡有適合這裡的函式呢?

197

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1 0 0 = 1 0 = 0 1 = 0 1 1 = 1 1 = 0 0 = 1 : = {0, 1} : 3 (,, ) = + (,, ) = + + (, ) = + (,,, ) = ( + )( + ) + ( + )( + ) + = + = = + + = + = ( + ) + = + ( + ) () = () ( + ) = + + = ( + )( + ) + = = + 0