函數指標

1. 存放資料的記憶體位址 vs. 存放程式的記憶體位址

2. 藉由函數指標擴充函數的彈性

3. qsort 庫存函數應用

什麼是指標變數? 為什麼需要指標變數?

一個程式裡所用到的資料或是計算過程中的資料都會記錄在主記憶體裡面, 在 C 程式中每一個變數都有一個起始的記憶體位址, 每一個常數字串, 每一個陣列, 每一個動態配置的變數或是陣列都有起始的記憶體位址, 例如:

  char *addr1 = "Constant String";
  int *addr2 = &x;  /* int x; */
  double *addr3 = y;  /* double y[100]; */
  char *addr4 = (char *) malloc(sizeof(char)*200);

這四個 addr? 變數裡面存放的資料都是對應的變數的起始記憶體位址, 你可以用 %p 的 printf 轉換命令來用十六進位列印這些位址, 例如 :

  printf("%p", addr1);

你可以運用 "間接存取運算子 - *", 透過這些存放記憶體位址的變數來使用到原來的變數, 例如:

  *addr2 = 100;              /* x = 100 */
  printf("x = %d\n", *addr2): /* printf("x = %d\n", x): */

這些存放記憶體位址的變數也稱為指標變數, 程式裡面使用這些變數的最主要目的是 "增加程式碼的彈性", 例如在下面的程式片段中

  int tmp, x, y;
  ...
  tmp = x;
  x = y;
  y = tmp;

變數 x 和變數 y 裡面存放的資料在執行過這幾列程式之後會交換過來, 但是三列程式和變數 x, 變數 y 緊緊地綁在一起, 你不能拿這三列程式去交換存放在變數 x1 和 y1 裡面的資料, 除非你複製上面幾列程式碼並且修改為

  int tmp, x1, y1;
  ...
  tmp = x1;
  x1 = y1;
  y1 = tmp;

這種狀況在引入指標變數以及間接存取運算子以後大幅改善, 在下面程式中, swap 函數裡面的三列程式可以用來交換任意兩個變數裡面的資料, 只要呼叫 swap 時傳入需要交換內容的變數的位址, 同樣的 swap 函數就可以達成指定的功能, 例如 傳入 &x 和 &y 則 swap 就會交換變數 x 和變數 y 的資料, 傳入 &x1 和 &y1 則 swap 就會交換變數 x1 和變數 y1 的資料,:

  int tmp, x, y, x1, y1;
  ...
  swap(&x, &y);
  ...
  swap(&x1, &y1);
  ...
  void swap(int *ptr1, int *ptr2)
  {
      tmp = *ptr1;
      *ptr1 = *ptr2;
      *ptr2 = tmp;
  }

什麼是函數指標? 為什麼需要使用函數指標?

在 von Neuman 架構的電腦上, 一段可以執行的程式必須放在記憶體裡面, CPU 才能夠執行它, 因此每一個可以執行的函數都有它的記憶體起始位址, 就好像一個變數有記憶體位址一樣 , 例如:

#include <stdio.h>
#include <stdlib.h>
	
double square(double x)
{
    return x * x;
}

int main(void)
{
    printf("address of square = %p(%p)\n", square, &square);
    printf("address of main = %p(%p)\n", main, &main);
    system("pause");
    return 0;
}

main() 函數中有兩次出現 square, 但是不論是 square 或是 &square 都不是呼叫函數 square, 它們只是代表函數 square 的記憶體位址的常數, 如果要執行 square 函數, 在 square 名稱之後必須有一對小括號以及其中的參數, 例如:

square(x);

  double (*fp)(double);
  ...
  fp = square;  /* 存放記憶體位址到變數 fp 裡 */
  ...
  (*fp)(x); /* 透過記憶體位址變數 fp, 間接呼叫函數 square */

上面這個型態 double (*)(double) 雖然不是 C 語言裡最 "難看" 的, 是我們到目前為止看到最 "難看" 的變數型態, 第一個 double 是函數的回傳值, 第二個 double 是函數的參數型態, 這個 double 外面的小括號則很清楚地指出它是一個函數, 前面的 * 代表的是記憶體位址, 其外的小括號則區辨 double * 和 double (*) 兩種不同寫法代表的不同意義。

為什麼宣告一個函數指標變數需要跟編譯器說明它需要幾個參數, 參數的型態, 還有回傳值的型態? 最主要就在於需要透過這個指標變數間接呼叫函數, 當然就需要上述資料, 編譯器才能檢查傳入的參數個數和型態, 並且進行適當的型態轉換, 回傳值也才能在適當型態轉換之後繼續運算。

函式指標變數 fp 的宣告和一般變數的宣告差異很大, 不過我們還是可以運用 C 語言的 typedef 敘述重新改寫上面的定義, 使得它看起來像是一般變數的定義:

  typedef double (*FuncPtr_t)(double);
  FuncPtr_t fp;   /* more like a normal variable definition */
  ...
  fp = square;
  ...
  (*fp)(x);

函式指標的應用 - 二分法勘根程式

修改二分法勘根程式使得使用者可以挑選下列兩個方程式

x² - 2 - cos(2 * x) = 0 in [0, 2] or

0.05 x³ + 0.6 x² - 5 = 0 in [-4, -2]

增加一個函數 g() 來實作第二個函數

修改 bisect() 的參數如下來傳入一個函數指標 fp

double bisect(double x_left, /* input  - endpoints of interval in */ 
              double x_right, /*          which to look for a root */ 
              double (*fp)(double), /*     function pointer          */
              double epsilon) /* input  - error tolerance          */

bisect 函數裡面原本用 f(x_ mid), f(x_left), 和 f(x_right) 改成運用間接的函數呼叫 (*fp)(x_mid), (*fp)(x_left), 和 (*fp)(x_right)

呼叫 bisect 的地方就可以改為 bisect(-4, -2, g, tolerance); 把函數位址 g 傳遞給 bisect 函數

如何使用 <stdlib.h> 的 qsort() 函數?

這個例子裡面我們要運用 stdlib.h 裡提供的 qsort() "快速排序法" 工具程式來排序一些資料, 不過我們需要再一次簡單地介紹陣列的定義與使用方法: 陣列是一群在記憶體裡面位置接續在一起的變數, 它們有相同的型態和單一的名稱, 有點像是數學定義裡面的向量 a = (a₁, a₂, ..., a_n) 或是矩陣 b = (b₁₁, b₁₂, ..., b_nn), 可以用集合的名稱代表整體, 也可以去使用個別的元素

使用方法:

陣列的定義:

    double data[10]; 
    /* 一次定義十個 double 型態的變數, 
       分別是: data[0], data[1], ..., data[9] */ 

陣列的使用:

    data[5] = 10.0; 
    /* 把 10.0 儲存在陣列的第六個元素裡 */

    x = 123 * data[5] / 456; 
    /* 由陣列的第六個元素裡取得資料以進行其它運算 */

    for (i=0; i<10; i++)
        data[i] = ((double)rand())/(RAND_MAX+1); 
    /* 在陣列的每一個元素裡存放一個 [0, 1) 區間中的數字 */

    for (sum=0,i=0; i<10; i++)
        sum += data[i]*data[i];   
    /* 計算陣列裡每一個數字的平方和 */

查詢 qsort 會看到如下的說明:

#include <stdlib.h>

void qsort(void *base, size_t num, size_t width, 
           int (__cdecl *compare)(const void *elem1, const void *elem2));

參考下圖, 這個 qsort 函數使用 "快速排序" 演算法來排列陣列裡的資料

首先它的參數包括下列
base 是陣列第一個元素的記憶體位址,
num 是陣列裡想要排序的元素的個數,
width 是每一個元素的大小 (單位是位元組),
compare 是比較兩個元素大小的函數指標.

因為 qsort 是某一個系統開發者寫的函數, 它當然不知道你的陣列裡面任何兩個元素該如何比較順序, 所以你必須把比較大小的機制寫成一個函數, 將函數指標傳遞給 qsort 函數, 如此每次 qsort 函數想要知道兩個元素的大小順序時, 它只要把兩個元素的記憶體位址傳給 compare 函數, 就可以得到比較的結果. 如果是 負數的話, 代表第一個元素在第二個元素之前, 如果是 0 的話, 代表兩個元素的順序相同, 如果是正數的話, 代表第一個元素在第二個元素之後; 另外, 因為撰寫 qsort 函數的人完全不知道使用者想要它排序的資料的型態, 所以函數 compare 的兩個輸入資料的型態都是 void *, 是沒有特定格式的記憶體位址的型態, 不能用間接存取運算子直接運算, 必須要先做強制的型態轉換, 才能去比較大小, 例如在下面的 compare 函數中, 我們知道每一個被排序的元素包含兩個整數, 同時元素的順序是根據第二個整數來決定的, 所以我們把參數 arg1 的型態強制轉為 (int *) 如此接下來的記憶體位址計算以及資料存取 *((int *)arg1+1) 都會用四個位元組的整數來處理, 也就是說 (*int *)arg1 + 1 是把變數 arg1 裡面存放的記憶體位址加上 "存放一個整數的變數的大小" (也就是加上 4 個位元組),然後 key1 = *(位址); 則是 間接存取運算子, 將存放在指定位址上用來比對的資料取出儲存在變數 key1 中

#include <stdlib.h> /* qsort, system */
#include <stdio.h>  /* printf */

int compare(const void *arg1, const void *arg2);

int main(void)
{
   int i;
   int data[] = {221, 123, 320, 456, 945, 210, 1234, 355, 769, 323};
   int ndata = sizeof(data) / (sizeof(int)*2);

   /* Sort remaining args using Quicksort algorithm: */
   qsort((void *)data, (size_t)ndata, 2*sizeof(int), compare);

   /* Output sorted list: */
   for (i = 0; i < ndata; ++i)
      printf("%d (key=%d)\n", data[2*i], data[2*i+1]);
   printf("\n");

   system("pause");
   return 0;
}

int compare(const void *arg1, const void *arg2)
{
    int key1 = *((int*)arg1+1);
    int key2 = *((int*)arg2+1);
    if (key1 < key2)
        return -1;
    else if (key1 == key2)
        return 0;
    else
        return 1; 
}

or simply

int compare(const void *arg1, const void *arg2)
{
    return ((int*)arg1)[1] - ((int*)arg2)[1]; 
}

Sample execution program