[陣列, 指標?] 使徒七最令人頭痛的地方就在於能隨意分離合體, 一下陣列一下指標 很容易讓各位駕駛員迷惑。在使徒七裡你務必要使用陣列來儲存所有的數 字, 然後把這個陣列「傳」給 qsort 函式來處理。 所以我們要先來熟悉 陣列的長相。 相信各位都了解，當我們宣告一個陣列時（比方說 int a[10];）， 其實就是要系統在這個 block 中給我們一段連續的記憶體空間來使用， 這個陣列有 10 個元素依序由低記憶體位址排到高記憶體位址，每個元素 的大小是 sizeof(int) ，在大多數 32-bit 的處理器環境下這個值是 4， 表示 4 個位元組（byte），如果是 64-bit 的處理器則為 8，以 32-bit 為例的話，陣列應該是這樣的：（假設從記憶體位址 0x20 開始） 0x20 0x24 0x28 0x2C 0x38 0x3C 0x40 ──┬──┬──┬──┬ ┬──┬──┬── │a[0]│a[1]│a[2]│………│a[8]│a[9]│ ──┴──┴──┴──┴ ┴──┴──┴── 而在 C 語言裡，陣列的名稱用來表示陣列第一個元素的位址，所以在這 個例子中， a 的值是 0x20 ，資料型態是 int *。為什麼是 int * 呢？ 因為它表示的是第一個元素 a[0] 的位址， a[0] 的資料型態是 int ， 那麼指到 a[0] 位址的變數，自然資料型態是 int * 囉。 如果換到 N-dimentional 的陣列呢？我們以 2-dimentional 陣列 來看，int b[3][2];　在記憶體中的長相應該是：（一樣假設從0x20開始） ← b[0] →← b[1] →← b[2] → 0x20 0x24 0x28 0x2c 0x30 0x34 0x38 ┬────┬────┬────┬────┬────┬────┬─ ... │ b[0][0]│ b[0][1]│ b[1][0]│ b[1][1]│ b[2][0]│ b[2][1]│... ┴────┴────┴────┴────┴────┴────┴─ 這樣的話，我們可以先看成有三個陣列 b[0], b[1], b[2]，用上面的例 子同理可以推出 b[0], b[1], b[2] 的資料型態是 int *，所以再推廣下 去，就能夠得到 b 的資料型態就是 int ** 。 所以到目前為止，你應該可以看得出來 x[y] 這種表示法不過就是 把 x 的位址加上 y 個單位後，該記憶體位址的值。 上面這句話用 C 的寫法就會像是: x[y] == *(x+y); 你一定覺得很奇怪，如果以第一個例子來看的話， a[2] 就等同於 *(a+2); 可是圖例不是說了 a[2] 的位址在 0x28 了嗎？ a+2 怎麼會對呢？ 你的質疑是對的，小學一年級的學生都知道 20 + 2 是 22 而不是 28， 難道你好人助教是在畫唬爛嗎？.... 請你再注意黃色的那句話，加 y 並不是純數字上的增加 y ，而是加上 y 個單位。還記得 a 陣列每個元素的資料型態是 int 嗎？所以一個 元素的單位是 4個byte （用 32-bit 環境），所以 a + 2 在位址的計算 上就會是 a + 2*sizeof(int)，這個單位的換算 compiler 會幫你作完， 所以你只要快快樂樂地寫 *(a+2) 就完全等於 a[2] 了。而在第二個例子， b[0], b[1], b[3] 都是一個 int[2] 的陣列，所以對 b 來說，一個 offset 單位就會是 2*sizeof(int)，所以 b + 1 的值就會是 28 了。 這時一定有人會舉一反三，既然陣列的構造如此，只要有一個 base address， 再一個 offset 就可以取值了，那我不就可以寫成這樣： int a[10]; int *p, *q; p = &a[3]; q = &a[6]; 這樣 p[0] == a[3], p[1] == a[4], ...., p[6] == a[9] q[-3] == a[3], q[-2] == a[4], q[-1] == a[5], q[0] == a[6] ... （按：使徒七強烈暗示） 沒錯！這樣寫沒有問題，但要注意的是， p[7] 是不合法的，因為你之前已經 說了你只要連續 10 個 int 的空間，p[7] 會存取到 a[10]，在某些系統下 你存取不合法的位址是會讓程式當掉的，但如果系統配置記憶體時剛好在 a 的後面配置其它合法的變數時，p[7] 雖然是合法的記憶體位址，但你可能就 會拿到奇怪的值而讓你的程式出現許多神妙的 bug，所以在用指標或陣列 時必須要格外地小心。 撐到這裡，我十分佩服你沒有直接按 end 略過，但我必須提醒的一點就是： 對一個指標變數而言，在它前面使用 * 運算子表示一個取值的動作 (de-reference)，而它取值必須要看這個指標的資料型態來決定。 假如一個指標是 int * ，那你對它取值的時候，就會從你給它的位址開始 抓 sizeof(int) 個 byte 來算出對應的數。這也說明了你不能直接對 void * 的指標變數取值。 void * 雖然可以接任何的指標（因為不管是 哪種資料型態，指標變數的大小都是 sizeof(int)，以 32-bit 的系統 來說就是 4 byte），但是當你取值的時候，compiler 沒辦法知道你接 的是哪個資料型態的變數，它只知道目前這個變數是 void *，所以無法 直接取值。以下是個簡單的例子： #define INT 1 #define DOUBLE 2 1 void show(void *p, int option) 2 { 3 switch(option) { 4 case INT: 5 printf("%d\n", *(int*)p); 6 break; 7 case DOUBLE: 8 printf("%f\n", *(double*)p); 9 break; 10 } 11 } ..... int a=10; double b = 20.5; show(&a, INT); show(&b, DOUBLE); 在這個例子中，我們由 option 來決定指標 p 應該要轉型成什麼資料型態， 然後才能取值，在第 5 列我們可以看到，我先將 p 轉型成 int * ，然後 才對它取值，而在第 8 列則是先轉型成 double * 之後才取值。 在使徒七中會用到 comp function，照 qsort 的介面來看，你的 comp function 要有兩個參數 const void *a 及 const void *b。會這樣來 制定介面，是要給使用 qsort 的人方便，因為設計 qsort 的人不知道 你要排序的陣列長什麼樣， comp function 是用來兩兩元素比對使用 的，所以 comp function 的部份保留了彈性用 void * 來接參數， 但你在實作 comp function 的時候就要注意，在 comp function 裡的 運算都必須要經過一個型態轉換(cast)的動作，你必須要把a, b 兩個參數 先轉型到正確的資料型態才能作運算。 關於 qsort 及 comp function　更詳細的秘技先留在後面的 part。 閱讀完這篇文章，你必須先將等級提升到了解陣列及指標的關係後才能 開啟火星之門朝火星邁進。 （待續） --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.217.117 ※ 編輯: ericsk 來自: 140.112.31.143 (11/03 22:54)