ii 序言 序 C 語言的最大特色就是 指標 (Pointer), 這是個讓人又愛又怕受傷害的主題 有一句話是, 學過 C, 而不會指標, 那只能說您看過 C 熟悉指標的人, 會將它比喻是天上那一顆最美的星星, 而讓不懂的人, 頭上會冒星星, 同樣是星星, 但卻有不同的情境 指標好難喔, 像無字天書, 不知道該如何學, 從哪一地方開始下手, 有沒有秘訣, 常常有人會對我講這些話, 並問我有沒有好方法可以 頓悟 它 有許多人學到指標時, 便裹足不前 基本原因是沒有專書討論指標及與其相關的主題 基於此, 便開始規劃, 撰寫一本以指標為核心的書籍, 使得對指標不太懂的人, 可以輕易了解指標的運作原理與其應用, 同時也可以讓已了解的人精益求精, 更進一步探考個中的奧秘 現在, 已夢想成真, 從書名 精通 C/C++ 指標 : 深入系統底層技術, 就知道它是您學習與深入指標的最佳讀本 本書內容精彩無比, 除了對 C/C++ 語言的指標有深入的探討外, 同時也將與指標有異曲同工之妙的 reference 詳加討論, 所以本書不僅有 C 而已, 還包括 C++ 程式語言, 有關 reference 的主題 其實不僅 C++ 使用 reference 的概念,Java C# 以及 Python 也是以 reference 達到和 C 語言的指標之功能 所以本書也加入 Java C# 以及 Python 這三種程式語言相關議題的討論 我們從 C 語言的指標與其息息相關的記憶體基本概念, 開始展開這一次的快樂探險旅程, 其中會經過 : 指標與變數 指標與陣列 指標與函數 指標與字串 指標與結構 鏈結串列 二元搜尋樹 指標與檔案處理等刺激關卡, 希望能有效導引讀者進入指標的深層世界 同時也會以鏈結串列 二元搜尋樹, 檔案的處理等重要的主題, 加以應用於本書所談的其它程式語言, 從而驗證指標與 reference 的相似功能
序言 iii 本書的共有六篇, 前五篇分別是當今很紅的程式語言, 分別是 C C++ Java Visual C# 及 Python 第六篇是各種程式語言比較篇, 將 C C++ Java Visual C# 及 Python 等五種程式語言, 在程式語言基本架構上的主題做比較, 希望此篇可以讓您一窺程式語言之美 撰寫本書的心情不知為什麼, 雖然很辛苦, 但覺得好愉快, 因為我的期望快實現了, 因為您可以從本書輕輕鬆鬆的了解指標的精髓, 進而加以應用, 並告訴我, 指標是天上閃亮的星星 擁護我的讀者不在少數, 有的在國內, 有的在大陸, 因此, 常常會聽到 : 老師, 我是看您的書長大的 真的有一種使命感, 要撰寫一些進階有參考價值的書, 本書完成了, 真誠的希望您可以從書中獲取一些知識, 做為您的一技之長 再一次的謝謝您的一路的相陪 支持與鼓勵, 讓我有動力再出發, 感恩 mjtsai168@gmail.com
04 指標與函數 4-1 函數初探 4-2 兩數對調 4-3 再論傳址呼叫 4-4 指向函數的指標 4-5 傳回指標的函數 4-6 除錯題 4-7 問題演練 4-8 程式實作
80 Part 1 C 程式語言篇 4-1 函數初探 函數 (function) 是執行某一任務的片段程式 它的好處是使程式模組化 重複使用 降低維護成本等功能 函數可分為兩種, 一為庫存函數 (library function), 它是編譯器所提供的, 二為使用者自定函數 (user-defined function), 它是由使用者撰寫的 本章所討論的是後者 函數的呼叫可分為傳值呼叫 (call by value) 與傳址呼叫 (call by address) 傳值呼叫表示實際參數傳給形式參數的是值 (value), 而傳址呼叫則是傳位址 (adddress) 我們先從一簡單的範例談起, 請參閱範例程式 functioncall-5 範例程式 :functioncall-5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 /* functioncall-5.c*/ double calaverage(double, double); double x, y, aver; printf(" 請輸入 x 與 y 的浮點數 : "); scanf("%lf %lf", &x, &y); aver = calaverage(x, y); printf("x 與 y 的平均數為 : %.2f\n", aver); double calaverage(double a, double b) double average; average=(a+b)/2; return average;
Chapter 4 指標與函數 81 輸出結果 請輸入 x 與 y 的浮點數 : 12.34 45.67 x 與 y 的平均數為 : 29.01 程式將實際參數 x 與 y 傳送給 calaverage 函數的形式參數 a 與 b, 計算此兩數的平均數, 並指定給 average 變數後, 回傳給主程式的 aver, 最後將它輸出 注意! 由於 calaverage 函數的資料型態是 double, 所以函數的回傳值 average 的資料型態也必須是 double 由於 aver 變數用於接收 average 變數值, 所以 aver 的資料型態也必須是 double 由於實際參數傳給形式參數是變數值, 所以稱此為傳值呼叫 4-2 兩數對調 指標到底有什好處呢? 我們從兩數對調的運作方式談起, 請參閱範例程 式 swaptype 範例程式 :swaptype 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 /* swaptype.c */ void swap_by_address(int *, int *); void swap_by_value(int, int); int x=100, y=200; /* Call by value */ printf("call by value\n"); printf("before swapping...\n"); printf("x=%d, y=%d\n", x, y); swap_by_value(x, y); printf("after swapping...\n"); printf("x=%d, y=%d\n\n", x, y); /* Call by address */ x = 100; y = 200;
82 Part 1 C 程式語言篇 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 printf("call by address\n"); printf("before swapping...\n"); printf("x=%d, y=%d\n", x, y); swap_by_address(&x, &y); printf("after swapping...\n"); printf("x=%d, y=%d\n\n", x, y); void swap_by_value(int a, int b) int temp; temp = a; a = b; b = temp; void swap_by_address(int *a, int *b) int temp; temp = *a; *a = *b; *b = temp; 輸出結果 Call by value Before swapping... x=100, y=200 After swapping... x=100, y=200 Call by address Before swapping... x=100, y=200 After swapping... x=200, y=100
Chapter 4 指標與函數 83 從輸出結果得知, 利用傳值呼叫無法達到兩數對調的效果, 但利用傳址 呼叫就可以 swap_by_value() 為傳值呼叫函數, 如圖 4-1 所示 : x 10 y 20 a 10 temp b 20 temp = a; a = b; b = temp; 圖 4-1 傳值呼叫 而 swap_by_address() 為傳址呼叫函數, 如圖 4-2 所示 : &x &y x 10 20 a temp b temp = *a; *a = *b; *b = temp; 圖 4-2 傳址呼叫 4-3 再論傳址呼叫 接下來, 討論一些常以傳址方式運作的範例 4-3-1 找尋陣列中的最大值 首先討論如何呼叫一函數, 尋找出陣列的最大值, 如範例程式 findmax 所示
84 Part 1 C 程式語言篇 範例程式 :findmax 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 /* findmax.c*/ int findmax(int [], int); int i; int arr[] = 20, 10, 100, 40, 60, 80, 90; int elements = sizeof(arr)/sizeof(arr[0]); int maxnumber = findmax(arr, elements); printf("max( "); for(i=0; i<elements; i++) printf("%d ", arr[i]); printf(") is %d\n", maxnumber); int findmax(int x[], int n) int j; int max = x[0]; for(j=1; j<n; j++) if(x[j] > max) max = x[j]; return max; 輸出結果 Max( 20 10 100 40 60 80 90) is 100 在 findmax 函數中 ( 第 20~28 行 ),x 陣列其實就是 arr 陣列, 因為此函數的呼叫是傳址呼叫, 將 arr 陣列第一個元素的位址, 指定給 x 陣列 findmax() 函數也可以撰寫成以下的片段程式 :
Chapter 4 指標與函數 85 int findmax(int *, int n); /* 函數語法宣告 */ int findmax(int *x, int n) /* 函數定義 */ int j; int max = *x; for(j=1; j<n; j++) if(*(x+j) > max) max = *(x+j); return max; 上述兩種寫法都可以 因為 [] 和 * 都是指標 我個人比較喜歡使用 * 的方式, 因為它好像天上一顆閃亮的星星 4-3-2 加總一維陣列的元素 接下來, 討論如何呼叫一函數, 以計算一維陣列元素的總和, 如範例程 式 sumofarray1-1 所示 範例程式 :sumofarray1-1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 /* sumofarray1-1.c */ int sum(int [], int); int i; int arr[] = 10, 20, 30, 40, 50, 60, 70, 80, 90, 100; int elements = sizeof(arr)/sizeof(arr[0]); int total = sum(arr, elements); printf("sum( "); for(i=0; i<elements; i++) printf("%d ", arr[i]); printf(") is %d\n", total);
86 Part 1 C 程式語言篇 20 21 22 23 24 25 26 int sum(int x[], int n) int j, t = 0; for(j=0; j<n; j++) t += x[j]; return t; 輸出結果 Sum( 10 20 30 40 50 60 70 80 90 100 ) is 550 也可以使用另一種方式撰寫之, 如範例 sumofarray1-2 所示 範例程式 :sumofarray1-2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 * sumofarray1-2.c */ int sum(int *, int); int i; int arr[] = 10, 20, 30, 40, 50, 60, 70, 80, 90, 100; int elements = sizeof(arr)/sizeof(arr[0]); int total = sum(arr, elements); printf("sum("); for(i=0; i<elements; i++) printf("%d ", arr[i]); printf(") is %d\n", total); int sum(int *x, int n) int j, t = 0; for(j=0; j<n; j++) t += *(x+j); return t;
Chapter 4 指標與函數 87 輸出結果 Sum( 10 20 30 40 50 60 70 80 90 100 ) is 550 從輸出結果驗證, 使用 t += x[j]; 與 t += *(x+j); 是一樣的 4-3-3 加總二維陣列的元素 以上是傳送一維陣列, 那二維陣列應如何傳送呢? 我們來探討如何呼叫一函數, 以計算二維陣列的總和, 請參閱範例程式 sumofarray2-1 範例程式 :sumofarray2-1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 /* sumofarray2-1.c */ int sum(int [][2], int, int); int i, j, row, column, total=0; int arr2[][2] = 10, 20, 30, 40, 50, 60, 70, 80, 90, 100; int elements = sizeof(arr2)/sizeof(arr2[0][0]); row = elements / 2; column = 2; total = sum(arr2, row, column); printf("there are %d elements in the array\n", elements); printf("sum(\n"); for(i=0; i<row; i++) for (j=0; j<column; j++) printf("%3d ", arr2[i][j]); printf("\n");
88 Part 1 C 程式語言篇 21 22 23 24 25 26 27 28 29 30 31 32 33 34 printf(") is %d\n", total); int sum(int p2[][2], int n, int m) int i, j, t = 0; for(i=0; i<n; i++) for(j=0; j<m; j++) t += p2[i][j]; return t; 輸出結果 There are 10 elements in the array Sum( 10 20 30 40 50 60 70 80 90 100 ) is 550 另一種方式的寫法, 如範例程式 sumofarray2-2 所示 範例程式 :sumofarray2-2 1 2 3 4 5 6 7 8 9 10 11 12 /* sumofarray2-2.c */ int sum(int (*p2)[2], int); int i, j, row, column, total = 0; int arr2[][2] = 10, 20, 30, 40, 50, 60, 70, 80, 90, 100; int elements = sizeof(arr2)/sizeof(arr2[0][0]); row = elements / 2; column = 2;
Chapter 4 指標與函數 89 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 total = sum(arr2, row); printf("there are %d elements in the array\n", elements); printf("sum(\n"); for(i=0; i<row; i++) for (j=0; j<column; j++) printf("%d ", arr2[i][j]); printf("\n"); printf(") is %d\n", total); getch(); int sum(int (*p2)[2], int n) int i, j, t = 0; for(i=0; i<n; i++) for(j=0; j<2; j++) t += *(*(p2+i)+j); return t; 輸出結果如同範例 sumofarray2-1 我們知道 *p 和 p[] 的表示方法是相通的 所以只要將 p2[][2] 改為 (*p2)[2] 就可以了 同理, 也驗證以下的式子是相等的 p2[i][j] == *(*(p2+i)+j);
90 Part 1 C 程式語言篇 4-4 指向函數的指標 指向函數的指標 (pointer to function) 相信有些人從未用過, 或根本沒聽過, 指標怎麼會和函數有關連呢? 指向指標的函數可使得程式在應用上顯得更為靈活, 當您要使用哪一函數, 只要將指標指向此函數即可, 其實就是將函數名稱設定給一指標, 因為函數名稱是一位址 ( 當然是在記憶體的位址 ), 在未進入此主題時, 讀者須分辨 int *pf(int); - 與 int (*pf)(int); - 是不一樣的, 其中 表示 pf 是一函數, 此函數有一參數為 int 型態, 且會回傳一指向 int 的指標, 下一節將詳加討論 而 為 pf 是一指向某一函數的指標, 此函數最後回傳 int 值 在處理指向函數指標時, 有一些需要特別注意的地方 : int add(int, int); int (*pf)(int, int); pf = add; 因為 add 函數有 2 個參數, 故 pf 指標也要有 2 個參數才能匹配 以下是不正確的使用方法 : double add1(double, double); int add2(int); int (*pf)(int, int); pf = add1; /* 錯, 因為兩者函數之參數的資料型態不同 */ pf = add2; /* 錯, 因為兩者函數之參數的個數不同 */ 有了以上的認知後, 咱們來研究範例程式 pointertofunction 做了什麼事 範例程式 :pointertofunction 1 2 3 4 /* pointertofunction.c */ int add(int, int); int substract(int, int);
Chapter 4 指標與函數 91 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 int multiply(int, int); int divide(int, int); int (*operation)(int, int); int x, y, output; printf(" 請輸入 x 與 y: "); scanf("%d %d", &x, &y); operation = add; output = (*operation)(x, y); printf("%d + %d = %d\n", x, y, output); operation = substract; output = (*operation)(x, y); printf("%d - %d = %d\n", x, y, output); operation = multiply; output = (*operation)(x, y); printf("%d * %d = %d\n", x, y, output); operation = divide; output = (*operation)(x, y); printf("%d / %d = %d\n", x, y, output); int add(int a, int b) return a+b; int sub(int a, int b) return a-b; int multiply(int a, int b)
92 Part 1 C 程式語言篇 46 47 48 49 50 51 52 return a*b; int divide(int a, int b) return a/b; 輸出結果 請輸入 x 與 y: 100 2 100 + 2 = 102 100 2 = 98 100 * 2 = 200 100 / 2 = 50 程式中有四個函數分別處理加 (add) 減(sub) 乘(multiply) 除(divide), 同時也宣告一指向函數的指標 operation, 當要處理加法時, 則將 add 指定給 operation 同理, 要處理乘法, 也只要將 multiply 指定給 operation 便可, 以此類推 程式要求使用者輸入二個數值 x y, 並將其結果存放於 output 4-5 傳回指標的函數 前面曾提及 int *pf(int); 它是一回傳指標的函數 (function returns a pointer), 其表示 pf 是一函數, 此函數有一個參數, 而且會回傳一指向 int 的指標 請參閱範例程式 functionretpointer 範例程式 :functionretpointer 1 2 3 4 /* funtionretpointer.c */ int *pf(int [], int); #define MAX 5
Chapter 4 指標與函數 93 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 int k[max]; int total=0, n; int i[max] = 10, 20, 30, 40, 50; int *ptr; ptr = pf(i, MAX); printf("ptr = %#x\n\n", ptr); printf("sum of (\n"); for(n=0; n<max; n++) printf("k[%d] = %d \n", n, *(ptr+n)); total += *(ptr+n); printf(") is %d\n", total); int *pf(int x[], int n) int m; int j[] = 100, 200, 300, 400, 500; for(m=0; m<n; m++) k[m] = j[m]+x[m]; printf("k[%d] = %d\n", m, k[m]); printf("k = %#x\n", k); return k; 輸出結果 k[0] = 110 k[1] = 220 k[2] = 330 k[3] = 440 k[4] = 550 k = 0x1030
94 Part 1 C 程式語言篇 ptr = 0x1030 Sum of ( k[0] = 110 k[1] = 220 k[2] = 330 k[3] = 440 k[4] = 550 ) is 1650 程式中有一函數的原型宣告, 如下所示 : int *pf(int [], int); 此表示 pf 是一函數, 有兩個參數, 而且會回傳一指向 int 的指標 程式中的 k 是陣列名稱, 表示陣列第一個元素的位址 當 pf 函數結束時, 將回傳 k 給 main 函數的 ptr 指標變數, 使得 ptr 是一指向 k 陣列第一個元素的位址, 亦即 ptr 等同於 &k[0] ( 從輸出結果得知為 0x1030)
Chapter 4 指標與函數 95 4-6 除錯題 小蔡老師出了以下程式, 要請大家一起來 Debug 1. /* sumofarraybugs-1.c */ int sum(int *, int); int i; int arr[] = 10, 20, 30, 40, 50, 60, 70, 80, 90, 100; int elements = sizeof(arr)/sizeof(arr[0]); int total = sum(arr, elements); printf("sum("); for(i=0; i<elements; i++) printf("%d ", arr[i]); printf(") is %d\n", total); int sum(int *x, int n) int j, t=0; for(j=0; j<n; j++) t += *(x); return t; 2. /* sumofarraybugs-2.c */ int sum(int *, int); int i; int arr[] = 10, 20, 30, 40, 50, 60, 70, 80, 90, 100; int elements = sizeof(arr)/sizeof(arr[0]); int total = sum(arr, elements); printf("sum(");
96 Part 1 C 程式語言篇 for(i=0; i<elements; i++) printf("%d ", arr[i]); printf(") is %d\n", total); int sum(int *x, int n) int j, t=0; for(j=0; j<n; j++) t += *(x+j); return t; 3. /* sumofarray2-1-bugs.c */ int sum(int [][2], int, int); int i, j, row, column, total=0; int arr2[][2] = 10, 20, 30, 40, 50, 60, 70, 80, 90, 100; int elements = sizeof(arr2)/sizeof(arr2[0][0]); row = elements / 2; column = 2; total = sum(arr2, row, column); printf("there are %d elements in the array\n", elements); printf("sum(\n"); for(i=0; i<row; i++) for (j=0; j<column; j++) printf("%3d ", arr2[i][j]); printf("\n"); printf(") is %d\n", total); int sum(int p2[][], int n, int m) int i, j, t=0;
Chapter 4 指標與函數 97 for(i=0; i<n; i++) for(j=0; j<m; j++) t += p2[i][j]; return t; 4. /* sumofarray2-2-bugs.c */ int sum(int *p[2], int); int i, j, row, column, total=0; int arr2[][2] = 10, 20, 30, 40, 50, 60, 70, 80, 90, 100; int elements = sizeof(arr2)/sizeof(arr2[0][0]); row = elements / 2; column = 2; total = sum(arr2, row); printf("there are %d elements in the array\n", elements); printf("sum(\n"); for(i=0; i<row; i++) for (j=0; j<column; j++) printf("%3d ", arr2[i][j]); printf("\n"); printf(") is %d\n", total); int sum(int *p2[2], int n) int i, j, t=0; for(i=0; i<n; i++) for(j=0; j<2; j++) t += *(*(p2+i)+j); return t;
98 Part 1 C 程式語言篇 5. /* functionretpointer-bugs.c */ int *pf(int [], int); #define MAX 5 int total = 0, k; int i[max] = 10, 20, 30, 40, 50; int *ptr; ptr = pf(i, MAX); printf("ptr=%p\n\n", ptr); printf("sum of (\n"); for(k=0; k<max; k++) printf("k[%d]=%d \n", k, *(ptr+k)); total += *(ptr+k); printf(") is %d\n", total); int *pf(int x[], int n) int m; int k[max]; int j[] = 100, 200, 300, 400, 500; for(m=0; m<n; m++) k[m] = j[m] + x[m]; printf("k[%d]=%d\n", m, k[m]); printf("k=%p\n", k); return k;
Chapter 4 指標與函數 99 4-7 問題演練 1. 試申述下列敘述的意義 : (a) int (*p)(int); (b) int *p(int); 4-8 程式實作 1. 請先定義一含有十個資料的一維陣列, 再利用傳址方式將此陣列,(1) 傳給 input 函數, 以便輸入資料,(2) 傳給 total 函數, 計算此陣列元素的和, 之後將總和回傳 2. 請先定義一含有八個資料的二維陣列 (2 列 4 行 ), 再利用傳址方式將此陣列,(1) 傳給 input 函數, 以便輸入資料,(2) 傳給 total2 函數, 計算此陣列元素的和, 之後將總和回傳 3. 撰寫兩種排序的方法, 如氣泡排序與插入排序, 之後以 4-4 節所論及指向函數的指標之方法, 撰寫一主程式分別呼叫這兩個函數 4. 試以第三章的命令列引數, 在命令列提示字元的模式下, 將一陣列的資料以氣泡排序加以排序之 sort r 或 sort -a r 表示以降幕 ( 由大至小 ) 的方式排序之,a 則表示以升幕 ( 由小至大 ) 的方式排序之