[秘技] 使徒七同步秘技 (1)

看板b94902xxx作者ericsk (認真的艾瑞克)時間18年前 (2005/11/03 01:04)推噓21(21推 0噓 2→)

留言23則, 22人參與討論串1/2 (看更多)

[陣列, 指標?] 使徒七最令人頭痛的地方就在於能隨意分離合體, 一下陣列一下指標很容易讓各位駕駛員迷惑。在使徒七裡你務必要使用陣列來儲存所有的數字, 然後把這個陣列「傳」給 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

推

purincess

11/03 02:09, , 1^F

11/03 02:09, 1^F

推

doudi

11/03 02:11, , 2^F

11/03 02:11, 2^F

推

ericsk

11/03 02:15, , 3^F

11/03 02:15, 3^F