Pointer Application

指向二維陣列的指標 int z[4][2] 是一個二維陣列，也代表一個「包含 兩個整數元素的陣列」的位址 我們可以宣告一個指向「包含兩個整數元素的陣 列」的指標，用來儲存這個陣列的位址 int (*pz)[2]; pz 是一個指到整數陣列的指標，它所指到的陣列包 含了兩個整數元素 若不加括號 int *pz[2] 代表的是有 2 個 int* 的陣列 pz = z; 把 pz 這個指標當作二維陣列來使用 例如： pz[2][1] 就相當於是 z[2][1]

傳二維陣列給 function 指標 int (*ap)[COLS] 和 int arr2[ROWS][COLS] 這個 二維陣列具有同樣的型別， 都是一個包含 COLS 個元 素的陣列的起始位址 [COLS] 一定要寫，因為 這樣 compiler 才知道指 標指到的是一個「包含了 COLS 個元素的整數陣列」 假如兩個指標 pa 和 pb 指 到的陣列的大小不一樣， 則這兩個指標的型別就不 一樣，因為 pa+1 和 pb+1 的效果是不同的 範例 8-1

指標陣列 用指標陣列 ( 每個陣列的元素都是指標 ) 來把一維陣列轉 變成二維陣列來使用 由於 *(aPtr[0]) 的意義相當於 aPtr[0][0] ，又或者 *(aPtr[5]+2) 的意義相當於 aPtr[5][2] ，所以我們可以把 aPtr 當作二維陣列使用 輸出： 範例 8-2

動態取得記憶體：使用 malloc() 和 free() stdlib.h 提供了兩個常用來管理記憶體的 functions malloc() 取得記憶體 free() 釋放記憶體 malloc() 參數是想要取得的記憶體大小 (bytes) 回傳值的是指向 void 型別的指標，所以必須依照想 要的型別，對指標做強制轉換 int* ptr = (int*)malloc(array_size* sizeof(int)); free() 參數是指向想要釋放記憶體位置的指標 free(ptr);

附註：程式如果不斷取得記憶體，但沒有正確地用 free() 釋放不再用到的空間，一但原本用來記錄位址的指標變數 的值被改變，例如指到了別的地方，則原本那塊記憶體就 沒有人能找得到，也就沒人能再使用它，這會造成所謂的 memory leak 的問題。 How many doubles do you want? 10 1: : : : : : 輸出： exit(EXIT_FAILURE) 結束 程式並傳回錯誤訊息給作 業系統 exit() 這個 function 和 EXIT_FALURE 常數也都是 stdlib.h 提供的 範例 8-3

不定長度陣列 有效率分配記憶體，把所有字串都存起來 字串需使用 strlen(buffer)+1 個 bytes 儲存 ('\0' 所需 ) 輸入 / 輸出 A b Peter Jim yaaaaaaaaaaaaaaaaaaaaaaaa 範例 8-4

Function pointer 左邊這個例子使用了一個 function 指 標依序儲存了 func1 與 func2 的位址。 function pointer 只能指向具有特定 特徵的函數。因而所有被同一 pointer 指向的函數必須具有相同的 參數和回傳型態 輸出 : fun_ptr 指向 fun1 : 10 fun_ptr 指向 fun2 : 4 範例 8-5

void* void 型態的指標沒有任何的型態資訊，所 以只用來持有位址資訊 void * 可以指向任何類型的數據 您不可以使用 * 運算子對 void 型態指標提取 值 (dereference) 必須轉型至對應的型態，才能進行操作 以下以 stdlib.h 中的 qsort 函式為例

qsort 當我們要排序 (sort) 陣列內的元素時，可以自己實作 各種排序演算法，也可以直接使用 qsort 。 qsort 的函式宣告 void qsort ( void * base, size_t num, size_t size, int ( * compar ) ( const void *, const void * ) ); 第一個參數為所欲排序的陣列 第二個參數為該陣列的個數 第三個參數為利用 sizeof 計算陣列元素所佔的記憶體空間 第四個參數為函數指標，須自行定義排序陣列的排序比較 方式

int ( * compar ) ( const void *, const void * ) qsort 希望使用者傳入一個 function ，藉此決定如 何比較 參數分別為兩個陣列元素的位置 ( 元素 1, 元素 2) 當兩個元素相等時，回傳 0 當元素 1 應在元素 2 之前時，回傳負值 當元素 1 應在元素 2 之後時，回傳正值 在 pointer 前面加 const 代表不會改變所指向的變 數值。

藉由 function pointer 與 void* 讓 qsort 可以 排序各種型態的元素。 輸出 範例 8-6

strcmp 在進入字串的排序之前，先補充一個比較字串的 函式 strcmp int strcmp ( const char* str1, const char* str2 ); 此函式會從第一個字元逐一比對，若相等則繼續 直到有字元不相等或遇到 ’\0’ 回傳值 0: 兩字串相等 不等於 0: 第一個不相等字元的 ascii code 相減的值

排序字串 以下介紹如何排序字串來統整 pointer 的概念 在交換字串值時，我們不需要使用 strcpy ，直接 交換 char* 更有效率 ! 前面，當我們排序 int 的陣列時， qsort 的 compare 函式傳入的是 int* 所以現在排序 char* 的陣列時， qsort 的 compare 函式傳入的是 char* 的指標，也就是 char**

要改變 char* 的 “ 值 ” ，也 就是 address ，要使用 char** 利用 strcmp ，可以讓字 串依照字典順序排序 (a~z) 輸入 zaqq Abc ccc aaaaaa wwwww 輸出 Abc aaaaaa ccc wwwww zaqq 範例 8-7

Recursion

Recursion( 遞迴 ) Recursion 簡單的說就是 function 在執行的 時候呼叫自己。 程式中使用到迴圈 (for,while) 的地方通常都 可以改成用 recursion 方式來做。 遞迴與迴圈一樣最重要的是終止條件。 Why use recursion? 程式行數較少，方便撰寫。 迴圈好還是遞迴好 ?

三種遞迴方式 直接遞迴 (direct recursion) 最基本的遞迴，在 function 的中間呼叫自己。 間接遞迴 (indirect recursion) 原 function 先呼叫另一個 function ，再從那 個 function 呼叫原 function 。 尾端遞迴 (tail recursion) 在程式的最後呼叫自己，沒什麼意義，不 如用循序的方式寫。

失敗的遞迴 如果遞迴程式如同右邊一 樣，不給予任何終止條件， 此程式將會產生執行錯誤。

遞迴範例 1 取 N 階乘，左邊為遞迴寫法，右邊為迴圈寫 法 範例 8-8 範例 8-9

遞迴範例 1(Cont.) 輸入輸出 : 出現錯誤 !?? 在 linux 可能就會顯示 下面訊息 也就是 “segmentation fault”

Why segmentation fault? 所謂 segmentation 是指 二進位檔案內的區域， 所有某種特定型別資訊 被保存在裡面。 當程式在執行時，會給 予一塊記憶體位置給程 式做暫存用。 當你的 data 存取到不屬 於他的區段時就會產生 錯誤。 在上面範例中是因為輸 入值過大造成過多的遞 迴次數，使得本身的記 憶體區段不夠用，而存 取到別的區段造成錯誤。 DATA 0x x00016FF 0x x00019FF 0x x00020FF ?

遞迴範例 2 以 fibonacci 數列做範例，左邊為遞迴寫法， 右邊為迴圈寫法 範例 8-10 範例 8-11

遞迴範例 3 這個範例是將字串所 有的排列組合印出。 list[]=“abc”,i=0,n=2 輸出如下 : 範例 8-12

經典範例 - 河內塔 有 3 根棍子， n 個圓盤，每個圓盤大小都不 一樣，一開始圓盤全部放在最左邊，從上 到下為小到大，最終需將全部圓盤移動到 最右邊，計算總共移動次數。 移動條件：一次移動一個，大圓盤不能在 小圓盤上。 AB C

經典範例 - 河內塔 (Cont.) 在這裡以三個圓盤做動畫範例 AB C 共移動七次

經典範例 - 河內塔 (Cont.) 如何用遞迴 ? Step1: 把較小兩個從 A 移動到 B 。 Step2: 把最大的從 A 移動到 C 。 Step3: 把較小兩個從 B 移動到 C 。

經典範例 - 河內塔 (Cont.) 範例程式將移動 次數紀錄下來。 Step1: 把較小 n-1 個從 A 移動到 B 。 Step2: 把最大的從 A 移動到 C 。 Step3: 把較小 n-1 個從 B 移動到 C 。 step1 step2 step3 範例 8-13

Modular Programming

main.c hanoi.c hanoi.h 範例 8-14 當程式越寫越大的 時候，我們會希望 程式能夠模組化， 最基本的就是把一 些 function 抽出來 放在另外一個檔案 裡面。 並使用一個 header file 讓其他檔案要 使用該 function 的 時候可以 include 它。 左邊為一個基本的 範例。

main.c hanoi.c hanoi.h 範例 8-14 此範例是由範例 修改的，執行結 果同範例 8-13 。 此範例單純將本來 範例 8-13 的一個檔 案分成三個。 hanoi 這個 function 的宣告在 hanoi.h 裡面，所以 main.c 需要在最前面的地 方 include hanoi.h 才可以使用它。

main.c hanoi.c hanoi.h 範例 8-14 由於在多檔案的 project 中，可能會 有多個檔案同時 include 到同一個 header 檔。 在 hanoi.h 最前面的 兩行 ( 註 1) 是告訴 compiler 不要重覆 include 到同一個檔 案。 請記得在最後面加 上 #endif 。

main.c hanoi.c hanoi.h 範例 8-14 我們提供的範例 code 是用 code::blocks 的 project 做範例，所 以將此 project 打開 就可以直接做編譯 及執行。 Windows 其餘的程式編輯軟 體也都是使用類似 的方式。 而使用指令列或 linux 相關 OS ，需 要使用下面的指令 做編譯。 其餘細節會另外做 補充。 gcc main.c hanoi.c hanoi.h

註 1 －引用防護 在開發 C 語言專案時，我們通常在每一個 標頭檔 (header file) 的開始與結尾，使用 #ifndef #define #endif 的方式防止重複引用 (include) 。 在某些 C 語言編譯器中，提供了 #pragma once 這樣的編譯指引，可以避免冗長的引 用防護撰寫語法。 參考資料：

條件編譯 當你所編譯的程式需要在不同的平 台或不同的 OS 上編譯，這時候就需 要使用旗標 (flags) 來達到條件編譯。 左邊為簡單的範例。 當編譯的時候加上 -Dx86_64 的時候， 輸出會是 x86_64 。 同理，編譯的 flags 就是 -D 後面接 define 的名稱。 Code::blocks 的設定方式會在 appendix 說明。 範例 8-15 例： gcc 8-15.c –DARM

Appendix

pragma 一個編譯程式定向 (pragma) 是由程式師嵌 入於原始程式碼 (source code) 的資料，以 告知編譯器應當如何編譯，其他原始程式 碼則告知編譯器應當編譯什麼。 不同的編譯器 (compiler) 會有不同的 pragma 實作。 以下簡介如何在 Code Block 裡面設定編譯 旗標。 參考資料：

設定 compile 的旗標 (flags) step1( 以範例 8-15 為例 )

設定 compile 的旗標 (flags) step2

設定 compile 的旗標 (flags) step3

設定 compile 的旗標 (flags) step4

設定 compile 的旗標 (flags) step5 編譯 & 執行

Standard library 補充 (stdio.h) int remove(const char ∗ filename) – 移除檔案 int rename(const char ∗ oldname,const char ∗ newname) – 修改檔案名稱 FILE ∗ tmpfile(void) – 建立一個暫存檔，其模式是 wb+ char ∗ tmpnam(char s[L_tmpnam]) – 建立一個暫存名稱

Standard library 補充 (ctype.h) isalnum(c)─ 判斷 isalpha(c) || isdigit (c) iscntrl (c)─ 判斷是否為 control characters isdigit (c)─ 判斷是否為數字字元 isprint (c)─ 判斷是否為可印出字元 ( 包含空格 ) ispunct(c)─ 判斷是否為標點符號 isspace(c)─ 判斷是否為空格、 tab 或換行 返回值非 0 為 True ，返回值為 0 則為 False 。

Standard library 補充 (stdlib.h) void ∗ bsearch ( const void ∗ key, const void ∗ base, size _t n, size _t size, int ( ∗ cmp ) ( const void ∗ keyval, const void ∗ datum ) ); – 二元搜尋， base 為欲搜尋之字元集合之指標， key 為被搜尋之字串或數列之指標。

Standard library 補充 (assert.h) void assert(int expression) – 用於對程式是否繼續執行做判斷，避免程式的 參數或指標等被惡意修改造成程式出錯。

Standard library 補充 (assert.h) clock_t clock()─ 回傳 cpu 時間。 time_t time(time_t ∗ tp)─ 回傳從 1970/1/1 到 現在的秒數時間。 double difftime(time_t t1,time_t t2)─ 計算時 間差。 char ∗ asctime(const struct tm ∗ tp)─ 用字串格 式顯示時間。

gcc 定義好的 macro __FILE__ ：印出檔案路徑及名稱 __LINE__ ：印出當前 source code 位置的行 數。 __func__ ：印出當前在哪個 function 裡面。 __DATE__ ：印出編譯時的日期。 __TIME__ ：印出編譯時的時間。 __VERSION__ ：印出編譯的 gcc 版本 請注意大小寫。