Lab 5: A note on pointers
搶救指標大作戰

這個實習裡請大家暫時放下 C++ 中各種新的語法, 物件, 類別, iostream 中新的用法, 成員函式, 函式覆載, 公開的/私有的... 今天我們要來和指標奮戰一下, 大家都接觸指標至少一年了, 也都知道指標的能耐, 至少知道程式裡指標對你的影響, 常常會讓你花很多很多的時間在抓一些會到處跑的 bug, 常常讓你覺得如果在程式裡能夠不用指標, 千萬不要去用, 以往都會收到很多同學用陣列實作堆疊, 實作串列, 實作樹狀結構的程式, 覺得有一點因噎廢食的感覺。

這裡我們再一次說明指標的用法, 對於已經很清楚的同學來說, 可以稍微輕鬆一點, 有的時候看到另外一種說明方法也可以讓自己更深入了解一些, 對於不太清楚指標的用法, 看到指標還有點畏懼的同學來說, 請把握機會, 儘量在實作中提出問題, 指標並不是無法學習的東西, 你的概念有錯誤, 實作時又沒有注意指標的陷阱, 才會留下許多許多隱藏的問題。

運算子 & 以及 * 的確使得語法產生相當的變化, 但是我相信各位可以藉由這個實習使得你對於 C/C++ 指標的認識更上一層, 使得指標不再是你的惡夢, 當然也不要變成你放棄資工的藉口。

請注意, 這個實習的內容並沒有包括記憶體配置, 只包含了指標型態的變化, 關於記憶體配置所衍生的記憶體問題, 在課堂裡會另外談到

1. 在 C/C++ 中指標就是記憶體位址, 在其他語言中並不見得如此, 在 C/C++ 中以這種方式來實現指標是為了效率和操作低階裝置的考量

2. 請定義如下的指標變數, 並用 C printf() 中的 %p 格式印出它們的數值 (十六進位)

       整數指標變數
          int *ptrInt; // 雖然 int 和 * 中間有空格, 但是請把 int* 當成是一種型態名稱
       倍精準浮點指標變數
          double *ptrDouble; // double * 是一種型態名稱
       結構指標變數
           struct Record  // Record * 是一種型態名稱
           {
               int iData;
               double dData;
           } *ptrRecord;

   ptrInt, ptrDouble, ptrRecord 都是可以存放資料的變數, 你要先在裡面放一點資料才會想要用 printf() 來列印這些變數的 內容, 可是放什麼好呢? (自己決定一下囉!)

   另外你還可以嘗試用 iostream 印這三個變數裡面存放的記憶體位址!

3. 在上一部份中你有沒有發現: 雖然 ptrInt, ptrDouble, 和 ptrRecord 是三個型態不同的變數, 可是 printf() 卻只用單一的格式轉換字元 %p 來處理就好了? (在 C 裡還有其它的資料型態是這樣的嗎?)

   最主要的原因是它們雖然型態不同, 但是在記憶體內所佔的大小相同, 格式也相同。

   接下來請用 printf() 或是 cout 印出 sizeof(ptrInt), sizeof(int *), sizeof(int), sizeof(ptrDouble), sizeof(double *), sizeof(double), sizeof(ptrRecord), sizeof(Record *), sizeof(Record) 的數值, 看到的數值和你預期的相同嗎?

   請注意各種指標型態變數所佔的記憶體大小都一樣, 那麼為什麼要分為各種不同型態的指標呢? 不是都是存放記憶體的位置資料嗎?
   最主要的原因是間接存取資料時編譯器需要知道透過這個記憶體位址要取得的資料有幾個位元組, 例如 *ptrDouble 是 8 個位元組，取得的資料參與運算時, 例如 *ptrDouble + 1, 1 需要轉換為 double, 加號 + 代表倍精準浮點數的加法
   

4. C/C++ 記憶體模型: C/C++ 沒有自己的抽象記憶體模型, 如下圖, 它們直接用機器的記憶體模型來運作: 請注意程式本身放在記憶體裡, 所處理的資料也都放在記憶體裡

指標變數是個變數, 也就是說可以把一個記憶體位址的資料存放在這個變數裡面, 當然也可以把先前存放的記憶體位址資料再拿出來使用, 例如:

    int x, y;
    int *ptr1, *ptr2;
    ptr1 = &x; // 存放資料到 ptr1 變數內
    printf("%p", ptr1); // 以十六進位格式列印出 ptr1 內所存放的資料
    ptr2 = ptr1+1; // 把存放在 ptr1 變數內的記憶體位址資料取出, 
                   //執行整數指標變數的加法, 加 1 以後實際記憶體位址增加 4

    ptr1 = &x;  // 在 ptr1 變數中記錄變數 x 的記憶體位置
    *ptr1 = 10; // *ptr1 代表變數 x, 將資料存放到變數 x 中
                // (透過 ptr1 指標變數間接存取變數 x)
    printf("%d", *ptr1); // *ptr1 代表變數 x, 由 變數 x 中取得資料
    y = *ptr1;

老實說, 如果你希望 "會用" 指標變數就好了, 那你看到這裡就夠了, 把你以前看過和指標相關的範例都拿出來好好解釋一下, 應該就可以有一些心得了, 不過因為你是資訊系的, 你還是應該嘗試了解接下來比較 "進階" 的解釋...

基本概念也是下面定理的應用

軟體工程的基本定理 (Fundamental Theorem of Software Engineering, FTSE) by Andrew Koenig

Any problem can be solved by introducing an extra level of indirection.

    int x=123;
    int y=456;
    int z=789;
    int r=135;
    int s=246;

    int *ptr;
    ptr = &x;
    
    *ptr = *ptr * *ptr - 1;

請注意要用"單一不重複的一段"程式碼來完成, 不要把幾列程式拷貝好幾次, 然後更改變數名稱來完成, 否則如果有 10000 個變數那該怎麼辦?

    void squareMinusOne(int *x)
    {
        *x = *x * *x - 1;
    }

函式就是用 "相同程式碼" 來處理 "不同資料變數" 的機制, 如果函式裡希望更改所處理的資料的話, 就不能不依靠指標變數了

我們平常說指標是一種間接的存取 (indirection), 最主要的目的其實就是允許你的程式用 "單一一段" 的程式碼處理 "不同的資料變數"

你在生活中常常用同樣的方法去應付很多不一樣的人與事, 以不變應萬變才會省力, 在程式中也是這樣而已, 這樣子程式就有 "彈性" 了, 否則如果有一萬種資料變數就要寫一萬段雷同的程式來處理了, 不會吧! 你能夠想像沒有指標變數的日子嗎? 也是可以過的, 只是有一點雷而已

    int x[1000];
    ...
    for (i=0; i<1000; i++)
    {
        x[i] = i;
        printf("%d\n", x[i]);
        x[i] = x[i] * x[i] * x[i] * x[i] * x[i] - 1;
    }

    for (i=0; i<1000; i++)
    {
        *(x+i) = i;
        printf("%d\n", *(x+i));
        *(x+i) = *(x+i) * *(x+i) * *(x+i) * *(x+i) * *(x+i) - 1;
    }

    int x[1000]; // 請注意 x 在程式中代表陣列 第一個元素的位址
                 // 它的型態是一個整數的常數指標 int * const 
    ...
    x[50] = 10;  // *(x+50) = 10;
    z = x[i];    // z = *(x+i);
    printf("%d\n", x[x[3]]); // *(x+*(x+3))

    50[x] = 10; // *(50+x) = 10;

    int x[2], *xptr=x;
    printf("xptr=%p\n", xptr);
    printf("xptr+1=%p\n", xptr+1);
    printf("&x[0]=%p\n", &x[0]);
    printf("&x[1]=%p\n", &x[1]);

    double y[2], *yptr=y;
    printf("yptr=%p\n", yptr);
    printf("yptr+1=%p\n", yptr+1);
    printf("&y[0]=%p\n", &y[0]);
    printf("&y[1]=%p\n", &y[1]);

請注意 *xptr 是一個整數, CPU 執行到這裡的時候需要去記憶體中取出 4 個位元組, *yptr 是一個倍精準浮點數, CPU 執行到這裡的時候需要去記憶體中取出 8 個位元組, 因此對於 xptr 和 yptr 的加 1 會有不同的結果

你可以試試下面的加法:

    double x[10];
    double *x0ptr = &x[0];
    double *x5ptr = &x[5];
    printf("%x\n", x0ptr+x5ptr);

一般來說兩個指標變數的內容加起來一定不是一個合理的記憶體位址, 所以 compiler 不會接受

再試試

    printf("%p %p\n", x5ptr, x0ptr);
    printf("%d\n", x5ptr-x0ptr);

    int x[10][3];
    printf("%p\n", x);
    printf("%p\n", x+1);

x 和 x+1 之間差了 12, 是三個整數所需要的記憶體大小, x 這個指標常數的型態和它這個(一維)陣列的第一個元素的指標是一樣的, 也就是 int (*)[3] 的型態

    int *ptr1;
    ptr1 = x;

沒有辦法將 int (*)[3] 的型態的資料轉換為 int * 型態的資料

先看一個簡單的例子:

    double *ptr1;
    int *ptr2;
    ptr1 = ptr2;

    ptr1 = (double *) ptr2;

再回到剛才有問題的敘述

    ptr1 = x; // compilation error

    int *ptrInt;
    int (*ptrAry)[3];

    int 型態在記憶體內佔了 4 個 byte, 可以存放一個整數,
    int[3] 型態在記憶體內佔了 12 個 byte, 可以存放三個整數

    int x;
    x = 10; // correct
    int y[3], z[3];
    y = z; // error

    y[2] = 10;
    *(y+2) = 10;

    (*ptrAry)[2] = 10; // 代表設定陣列中的第三個元素為 10
    *((*ptrAry)+2) = 10;

*ptrAry[1] 就是 *(*(ptrAry+1)) 也是 ptrAry[1][0]

(*ptrAry)[0] 就是 **ptrAry, 代表上圖中標示 1 的那個整數變數

    int x[10];

    int x[10];
    int (*ptr)[10]; // ptr 可以放 "10 個整數的陣列" 
                    //     的記憶體位址
    ptr = x;

    ptr = &x;

下面這個程式是把上面的概念應用到二維陣列上

    int x[10][3];
    int *ptr1 = &x[0][0];
    int (*ptr2)[3] = &x[0]; // x[0] 代表 3 個整數的陣列
    int *ptr3 = x[0]; // x[0] 也代表陣列裡第一個元素的位址
    int (*ptr4)[10][3] = &x; // x 代表 10 個 3 個整數的陣列
    int (*ptr5)[3] = x; // x 也代表陣列中第一個元素的位址
                        //   這代表 3 個整數的陣列
    
    有了上面 ptr1 到 ptr5 這些指標, 該怎樣使用呢?
    *ptr1 是一個整數
    *ptr2 是一個三個元素的陣列, 可以用下列存取個別元素
       (*ptr2)[0]   (*ptr2)[1]    (*ptr2)[2]   或是
      **ptr2       *((*ptr2)+1)   *((*ptr2)+2)
    *ptr3 是一個整數
    *ptr4 是一個大的陣列, 有 10 * 3 個整數, 用法比較多
       (*ptr4)[0] (*ptr4)[1] ... (*ptr4)[9] 
                             分別代表 3 個整數的陣列
       (*ptr4)[5][2] 代表一個整數
           或是上述等效的純指標用法 *(*(*ptr4+5)+2)
    *ptr5 是一個三個元素的陣列, 可以用下列存取個別元素
       (*ptr5)[0]   (*ptr5)[1]    (*ptr5)[2]

    int **ptr1;
    int (*ptr2)[3];

    1. (*ptr2)[1]
    2. (*ptr1)[1]
    3. (*(ptr2+1))[1]
    4. (*(ptr1+1))[1]
    

你能夠寫一段程式, 視資料的內容來決定怎麼處理它嗎? 直覺看來這個問題並不困難, 可以用下面的 switch 敘述來完成,

    int x;
    ...    // 設定 x 的內容
    switch (x)
    {
    case 1:
        fun1(y, z); break;
    case 2:
        fun2(y, z); break;
    ...
    case 5:
        fun5(y, z); break;
    }

    typedef void (*PF)(int, int);
    
    PF funAry[5] = {fun1, fun2, fun3, fun4, fun5};
    // 或是 void (*funAry[5])(int, int)={fun1, fun2, ...};
    
    (*funAry[x])(y, z); // 取代上面整個 switch 敘述

比較實際的函式指標範例其實就是 Lab 1-2 步驟七 的 qsort() 和 Lab 2-2 步驟三, 四 sort() 和 find()

假設我們希望將下面程式中 data 這個結構變數在記憶體中的內容一個 byte 一個 byte 用十六進位列印出來, 例如:

00: 77
01: be
02: 9f
03: 1a
04: 2f
05: dd
06: 5e
07: 40
08: 7b
09: 00
10: 00
11: 00
12: 7c
13: 00
14: 00
15: 00
16: 7d
17: 00
18: 00
19: 00
20: 7e
21: 00
22: 00
23: 00
24: 61
25: 62
26: 63
27: 64
28: 65
29: 20
30: 40
31: 00

請寫一個函式來做這件事:

    void printContent(void *ptr, int length)
    {
        int i;
        unsigned char *dataArray = (unsigned char *) ptr;
        for (i=0; i<length; i++)
            printf("%d: %2x\n", i, dataArray[i]);
    }
    
    struct DataRecord
    {
        double x;
        int y[4];
        char z[5];
    };
    
    void main()
    {
        DataRecord data;
        int i;

        data.x = 123.456;
        for (i=0; i<4; i++)
            data.y[i] = 123+i;
        for (i=0; i<5; i++)
             data.z[i] = 'a'+i;
        ...
        printContent(&data, sizeof(data));
    }