指针和定长数组

晨曦之光 发布于 2012/04/10 14:58
阅读 255
收藏 0

数组就是指针这个说法并不正确,只能说数组的名字是一个指针,指向数组的第一个元素,而数组的内容是该指针指向的内存后面连续的一段内存,这些内存可以用指针来寻址。重要的特点是“连续的一段内存”,因此数组元素就不能像链表节点那样仅仅通过一个指针来互相联系,它必须保证元素是一个挨着一个的,既然数组元素存在于连续内存,有了第一个元素的指针和元素的大小,后面的元素也就可以自然而然的得到了,可见数组是一种链表的特化,它不依靠显式的指针来首尾相接,而是靠“地址连续”这个特点隐式的首尾相接。
     和链表相比,数组省去了next/prev字段,从而也就节省了sizeof(type*)*n这个么大小的内存空间,然而节省空间是有代价的,那就是数组必须有一个“外围”的数据结构以保证其地址空间连续,或者数组在编译的时候确定其大小n,直接为其预留sizeof(type)*n这么大的空间,否则无法保证同一个数组相邻元素间地址连续的要求。如果编译期间数组的长度是动态的,那么由于编译器并不知道数组的大小,只有在运行时才能确定,这样的话为其分配多大的连续空间好呢?要知道地址空间是有限的,分配小了可能不足以满足运行时数组大小的最大需求,分配大了可能会浪费很多可能根本不需要的内存,因此数组必须在编译的时候确定其大小,即使它有一个外围数据结构,比如:
struct type1 {
    ...
    type2 t2[x];
    ...
}
虽然type1保证了t2的地址空间一定连续,这里的x也一定要是确定的长度,否则type1的大小就没有办法确定,不管type1在栈上分配-机器隐式分配内存,还是在堆上分配-程序员显式分配内存,都需要确定type1的大小。
     为了地址的连续性导致了数组必须在编译期确定大小无疑是一个限制,这样的话,对于不确定大小和元素个数的数据结构,就必须使用链表来显式将元素互相连接了,如此一来即使知道在运行时分配的空间是连续的,也一定要使用一个额外的next/prev指针相连接,这样很不合理,因此gcc提供了在结构体后面增加一个0长度数组的办法支持变长的数据结构,使得程序可以在运行的时候分配出诸如数组一样的连续空间的数据结构,节省了内存:
struct test {
    char *ptr;
    int value;
    char reverse[0];
}
如果在运行时,你确定reverse的长度为n,那么就可以如下这样为test结构体分配内存:
struct test *t = (struct t*)malloc(sizeof(struct test)+n*sizeof(char));


原文链接: http://blog.csdn.net/dog250/article/details/6180605
加载中
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部