指针&数组

發表於 2015-08-30

指针和数组是C语言中常用的类型（数据结构）
《C Programming Language》一书中提到，指针访问比数组访问效率高一些，这是真的吗？
本着一个求知（ba gua）的心，我决定一探究竟=。=

指针和数组

数组和指针的关系、区别是什么？

简单地说，数组名是一个指针常量

  1. 数组名映射到程序常量区的一段数据，其中保存了数组的首地址
  2. 数组名的值不能改变，不能作为左值
  3. 通过下标访问数组元素是通过数组首元素地址（数组名）加上偏移量实现的
    因此，指针必须有类型限制（才能够正确的计算步长）
    另外，对于数组a，a[6]和6[a]是等价的
    没错！6[a]是成立的，但是为了程序的可读性，尽量不要刻意这么用

C语言的多维数组

“数组的数组”和“多维数组”

  • 数组的数组：
    即为“有一个数组，它的元素也是数组”，诸如a[2][2]的形式
  • 多维数组：
    即为“有一个数组，它的元素都是整型（浮点数等）数据，但是它有多个维度”，诸如a[2,2]的形式

显然，C语言所说的“多维数组”，本质上是“数组的数组”

多维数组的内存布局

简单来说，C语言以“行主序”的规则布局内存，也就是说“最右边的下标先变化”
以二维数组为例，a[2][4]的内存布局如下：
a[0][0], a[0][1], a[0][2], a[0][3], a[1][0], a[1][1], a[1][2], a[1][3]

锯齿状数组的使用

锯齿状数组：某一维或某几维长短不一的数组
以二维数组为例，char a[5][50]
我可以在a[0]保存一个很长的字符串，在a[1]保存一个很短的字符串，但是这样做就浪费了许多的空间
这时候，我们就可以创建一个锯齿状数组来节约空间 

char my_string1[] = "aaaaaaaaaaaaaaaaa";
char my_string2[] = "a";
char *my_strings[5] = { my_string1, my_string2 };

char a[3];和char b[4];不是同种类型

虽然元素都是字符，而且都能通过char *指针访问，但它们的确是属于不同的类型
用二维数组来展示更加明显，假定char c[1][2];、char d[3][4];
那么前者只能由指针char (*p)[2];来访问
后者只能由指针char (*q)[4];来访问
两者显然是不同的

char *p = "abc";和char a[] = "abc"

前者的”abc”保存在常量区中，不可改变
后者的”abc”保存在栈中，是可变的
如果试图改变前者的元素，如p[1] = 'd';，编译能够通过，但运行时会导致程序异常（试图修改常量区内容）
char *p = "abc";这种写法存在着弊病，C++尝试否定这种写法，但这种写法过于普遍，最后为了兼容C而只好接受
更好的写法是认为的加上常量限定符，即const char *p = "abc";，来显式说明p指向的是一个常量
这样，当尝试去修改p所指向的值时，编译器就会报错

函数传值

无论函数的形参是char a[]还是char *a
a都是一个可变的指针变量，而不会作为一个常量

另外，假定有如下定义： 

void main(){
    int a[6];
    example(a);
}
void example( int a[] ){
    /*empty*/
}

sizeof( a )得到的是数组的空间大小（而非长度）
sizeof( b )得到的是一个指针的空间大小（而不能取得数组的大小）
所以，无法通过sizeof运算符在函数内部获取到“传入”的数组的大小
另外，为了直观，应尽量使用形参char *a

那么，如何得知传入的数组的大小？

  1. 增加一个额外的参数，提示数组的长度
  2. 为数组的最后一个元素赋予特殊的值，来提示数组的结束

效率比较

《C专家编程》指出，
“使用现代的产品质量优化的编译器，一维数组和指针引用所产生的代码并不具有显著差别”

通过下标访问元素

这里以char a[] = "abcd";和char *p = a;为例
比较a[3]和p[3]的区别
（假设a数组的首地址为123,p的地址为789）

  • a[3]
    1. 计算目标地址，即123 + 3 * 1得到a的第四个元素地址为126
    2. 在地址126处提取一个字节的字符
  • p[3]
    1. 在地址789处提取四个字节的地址，即a数组的首地址123
    2. 计算目标地址，即123 + 3 * 1得到a的第四个元素地址为126
    3. 在地址126处提取一个字节的字符

可以看到，指针访问比数组访问多了一个步骤，从这一点看，通过下标的方式，数组访问的效率反而稍高一些

处理多个元素

这里以char a[] = "abcd";和char *p = a;为例
通过两种方式来遍历数组中的所有元素
（假设a数组的首地址为123,p的地址为789）

  • 数组访问

    for(i=0; i<3; i++){
    t = a[i];
}
  1. 访问第一个元素
    计算目标地址，即123 + 0 * 1得到a的第一个元素地址为123
    在地址123处提取第一个字符’a’
  2. 访问第二个元素
    计算目标地址，即123 + 1 * 1得到a的第二个元素地址为124
    在地址124处提取第二个字符’b’
  3. ……

  • 指针访问 

    for(i=0; i<3; i++){
    t = *p++;
}
  1. 访问第一个元素
    在地址789处提取四个字节的地址123
    在地址123处提取第一个字符’a’
    p自增即p + 1为124
  2. 访问第二个元素
    在地址789处提取四个字节的地址124
    在地址124处提取第一个字符’b’
    p自增即p + 1为125
  3. ……

可以看到，数组访问每次都要计算目标地址，而指针访问只需要直接提取数据
尽管指针需要偏移，但只作加减运算，而数组访问需要进行乘法运算，显然效率低一些
（实际上，现代计算机处理器的乘法运算得到很好的优化，其计算速度已经接近加减运算了，真正的瓶颈在于除法运算）

现代编译器

现代编译器常常会直接把数组转换成对应的指针形式，
在这种编译器下，无论是数组访问还是指针访问都会形成相同的机器指令

参考资料

#

#C
python笔记
《C专家编程》小记