[阵列, 指标?] 使徒七最令人头痛的地方就在於能随意分离合体, 一下阵列一下指标 很容易让各位驾驶员迷惑。在使徒七里你务必要使用阵列来储存所有的数 字, 然後把这个阵列「传」给 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)