02月 20th, 2010C语言中高维数组与一维数组的相互折叠
毫无疑问，C语言里，最麻烦的地方，就是指针和数组的互相转换问题了。因为，它俩实质上就是一个东西。
今天要说的是，如何将简单的一维数组和多位数组互相转换。
我们知道，在C语言的申明中，我们可以申明一个2维数组，形如：
int a[2][5]
从申明的含义上，a是一个有2个元素的数组，它的元素，我们记为t。而t怎是一个有5个int元素的数组。
从参数的解释上，事实上 int a[][] 和 int **a是一样的。
而从内存空间的分配上，int a[2][5]和 int b[10]一样，是占用10个连续的int空间。其顺序是：a[0][0],a[0][1]…a[0][4],a[1][0]…a[1][3],a[1][4]
有了上面这些内容，我们就可以像折叠一样，把一串很长的一维数组，给一层一层的折叠成高维数组。下面是我随手写的一段样例代码：
#include <stdio.h> int main (void) { int a[20]; int (*b)[5]; // 申明很猥琐，见最后红字 int i,j; for (i=0; i<20; i++) { a[i]=20-i; } b=a; for (i=0; i<4; i++) for (j=0; j<5; j++) printf ("%d ",b[i][j]); return 0; }
这样做有什么意义呢？
本质上说，确实没有什么太大的意思。而且很多时候，我们可以很轻易的将一个高维数组里的(i,j,k)位置映射到顺序存放的一维数组里。
譬如说对于int a[p][q][r]中的位置(i,j,k)事实上，对应于int a[p*q*r]中的：
i*q*r + j*r + k
（而且事实上，在计算机内部，也就是这么做的。）
反过来，我们也可以通过模、除运算，将一个线性空间中的位置换算成高维空间的位置。式子比较奇怪，就不写了。
如果非要说什么这样通过折叠的方式，重叠指针的好处的话……那就是如果一组数，我们既需要顺序的方位，又希望可以通过指定行列的方式来获取的话……可能会比较方便。（当然，我觉得把上面那个 i*q*r + j*r + k 写成一个宏，也是未尝不可的。但是，总觉得，乘法什么的，交给编译器去做，会不会比我写的要快些？）
最后，再给一个很牵强的应用代码。
描述是这样的，我有4组数据，每组包含5个int数。
然后，我希望以行为基本单位排序，排序的依据是，某一列的数值大小。
下面是样例代码：
#include <stdio.h> #include <stdlib.h> int col=0; int cmp (const void *x, const void *y) { return *((int*)x+col) - *((int*)y+col); } int main () { int a[20]= { 11,41,41,21,31, 22,32,22,42,12, 33,23,13,13,43, 44,14,34,34,24}; int (*b)[5]; int i,j; b=a; printf ("sort by col 1:\n"); // 注意一下，col1 不是第一列，是第二列。从0开始！ qsort (b,4,sizeof(b[0]),cmp); for (i=0; i<4; i++) { for (j=0; j<5; j++) printf ("%3d ",b[i][j]); printf ("\n"); } printf ("*************\n"); printf ("sort by col 2:\n"); col=2; qsort (b,4,sizeof(b[0]),cmp); for (i=0; i<4; i++) { for (j=0; j<5; j++) printf ("%3d ",b[i][j]); printf ("\n"); } return 0; }
最后多说几句，这里比较麻烦的是qsort的使用。
在qsort的cmp函数中，传入的两个参数分别是要排序数组的每个元素的地址。
换句话说，如果要排序a[]，那么每次传入的参数就是 &a[i]
高维数组事实上就是折叠过得一维数组。也就是说，在事实上，对于2维数组b[][]，我们有 (void*)&b[0] == (void*)&b[0][0]。而这两者的区别，也只是类型的不同而已。这也就是我在取值符前面，强制转换为void*的原因。
由此，我们在写cmp函数的时候，切莫将x强制转换为int**，而只需要转换为int*就好。
红字醒目
int (*b) [5] 和 int *b [5] 是不一样的。
int (*b) [5] 表示：b是一个指针，它指向一个含有5个整数的数组
int *b [5] （没有括号！）表示：b是一个有5个元素的数组，它的每个元素是一个指向整数的指针。更易懂的写法是 int* b[5]
int (*b) [5] 中，如果b是x的话，那么b+1就是x+5*int
而在没有括号的版本中，b+1其实是&b[1]
